gauss_jacobi.js

gauss_jacobi.js

/**
 * Algoritmo de jacobi e gauss boladao
 */
 
// metodo para trabalhar melhor com Arrays multidimensional
Array.prototype.makeMatrix = function (d1, d2) {
    var arr = [];
    for(i = 0; i < d2; i++) {
        arr.push(new Array(d1));
    }
    return arr;
};
 
// Metodo para preencher automaticamente os valores de um array
if (!Array.prototype.fill) {
  Array.prototype.fill = function(value) {
 
    if (this == null) {
      throw new TypeError('this is null or not defined');
    }
 
    var O = Object(this);
 
    var len = O.length >>> 0;
 
    var start = arguments[1];
    var relativeStart = start >> 0;
 
    var k = relativeStart < 0 ?
      Math.max(len + relativeStart, 0) :
      Math.min(relativeStart, len);
 
    var end = arguments[2];
    var relativeEnd = end === undefined ?
      len : end >> 0;
 
    var final = relativeEnd < 0 ?
      Math.max(len + relativeEnd, 0) :
      Math.min(relativeEnd, len);
 
    while (k < final) {
      O[k] = value;
      k++;
    }
    
    return O;
  };
}
 
// Metodo para copiar o valor das referencias dos objetos
Object.prototype.clone = function() 
{
    var copy;
 
    if (null == this || "object" != typeof this) return this;
 	
    if (this instanceof Date) {
        copy = new Date();
        copy.setTime(this.getTime());
        return copy;
    }
 	
    if (this instanceof Array) {
        copy = [];
        for (var i = 0, len = this.length; i < len; i++) {
            copy[i] = clone(this[i]);
        }
        return copy;
    }
	
    if (this instanceof Object) {
        copy = {};
        for (var attr in this) {
            if (this.hasOwnProperty(attr)) copy[attr] = clone(this[attr]);
        }
        return copy;
    }
 
    throw new Error("Unable to copy obj! Its type isn't supported.");   
}

 
var Jacobi = function (matrix)
{
    return {
        MAX_ITERATIONS : 100,
        M : matrix,
 
        print : function ()
        {
            var stringMatrix = '';
            var n = this.M.length;
            for (var i = 0; i < n; i++) {
                stringMatrix += "[";
                for (var j = 0; j < n + 1; j++){
                    stringMatrix += this.M[i][j] + " ";
                }
                
                stringMatrix += "]\n";
            }
            console.log(stringMatrix);
        },
 
        transformToDominant : function (r, V, R)
        {
            var n = this.M.length;
            if (r == this.M.length) {
                var T = Array.makeMatrix(n, n+1);
                for (var i = 0; i < R.length; i++) {
                    for (var j = 0; j < n + 1; j++){
                        T[i][j] = M[R[i]][j];
                    }
                }
                M = T;
                return true;
            }
 
            for (var i = 0; i < n; i++) {
                if (V[i]){
                    continue;
                }
 
                var sum = 0;
 
                for (var j = 0; j < n; j++){
                    sum += Math.abs(this.M[i][j]);
                }
 
                if (2 * Math.abs(this.M[i][r]) > sum) {
                    V[i] = true;
                    R[r] = i;
 
                    if (this.transformToDominant(r + 1, V, R)){
                        return true;
                    }
                    V[i] = false;
                }
            }
            return false;
        },
 
 
        makeDominant : function ()
        {
            var visited = new Array(this.M.length);
            var rows = new Array(this.M.length);
 
            visited.fill(false);
 
            return this.transformToDominant(0, visited, rows);
        },
 
        solve : function ()
        {
            var iterations = 0;
            var n = this.M.length;
            var epsilon = 0.000000000000001;
            var X = new Array(n);
            var P = new Array(n);
 
            X.fill(0);
            P.fill(0);
 
            while (true) {
                for (var i = 0; i < n; i++) {
                    var sum = this.M[i][n];
 
                    for (var j = 0; j < n; j++){
                        if (j != i){
                            sum -= this.M[i][j] * P[j];
                        }
                    }
 
                    X[i] = 1/this.M[i][i] * sum;
                }
                
                var stringResult = "";
                stringResult += "X_" + iterations + " = {";
                for (var i = 0; i < n; i++){
                    stringResult += X[i] + ", ";
                }
                stringResult += "}";
                
                console.log(stringResult);
                
                iterations++;
                if (iterations == 1) {
                    continue;
                }
 
                var stop = true;
                for (var i = 0; i < n && stop; i++){
                    if (Math.abs(X[i] - P[i]) > epsilon){
                        stop = false;
                    }
                }
 
                if (stop || iterations == this.MAX_ITERATIONS){
                    break;
                }
                P = X.clone();
            }
        }
    };
};
 
 
var Gaussian = function (matrixInput) {
    return {
 
        matrixInput : matrixInput,
 
        matrixAsString : function (matrix)
        {
            var matrixAsString = '';
            matrix.forEach(function (x){
                var lineAsString = '';
                x.forEach(function (y){
                    lineAsString += y.toFixed(2) + ' ';
                });
                matrixAsString += '| ' + lineAsString + '|\n';
            });
            return matrixAsString;
        },
 
        getSystemResult : function (A)
        {
            var n = A.length;
            var x = new Array(n);
 
            for (var i=n-1; i>-1; i--) {
                x[i] = A[i][n]/A[i][i];
                for (var k=i-1; k>-1; k--) {
                    A[k][n] -= A[k][i] * x[i];
                }
            }
            return x;
        },
 
        getMaxColumn : function (matrix, afterIndex)
        {
            var mLength = matrix.length + afterIndex;
            for (var i = 0; i < mLength; i++) {
                var maxElement = Math.abs(matrix[i][i]);
                var maxRow = i;
                for (var j=i+1; j< j<mLength; j++) {
                    if ( Math.abs(matrix[j][i]) > maxElement ) {
                        maxElement = Math.abs(matrix[j][i]);
                        maxRow = j;
                    }
                }
            }
        },
 
        getMatrixResult : function (A)
        {
            var n = A.length;
 
            for (var i=0; i<n; i++) {
                var maxEl = Math.abs(A[i][i]);
                var maxRow = i;
                for(var k=i+1; k<n; k++) {
                    if (Math.abs(A[k][i]) > maxEl) {
                        maxEl = Math.abs(A[k][i]);
                        maxRow = k;
                    }
                }
 
                for (var k=i; k<n+1; k++) {
                    var tmp = A[maxRow][k];
                    A[maxRow][k] = A[i][k];
                    A[i][k] = tmp;
                }
 
                for (k=i+1; k<n; k++) {
                    var c = -A[k][i]/A[i][i];
                    for(var j=i; j<n+1; j++) {
                        if (i==j) {
                            A[k][j] = 0;
                        } else {
                            A[k][j] += c * A[i][j];
                        }
                    }
                }
            }
 
            return A;
        },
 
        getGaussianResult : function ()
        {
            var matrix = this.getMatrixResult(this.matrixInput);
            return this.getSystemResult(matrix);
        }
    };
};
 
var main = (function ()
{
    var n = 3;
    var M = [
    	   [5, -2,  3, -1],
		   [-3,  9,  1,  2],
		   [2, -1, -7,  3]
    ];
    
    var jacobi = new Jacobi(M);
    console.log("==========================Jacobi============================");
    if (!jacobi.makeDominant()) {
		console.log("Esse metodo nao pode garantir convergencia");
	}
 
    jacobi.print();
 
    jacobi.solve();
    console.log("============================================================");
    
    console.log("===========================Gauss============================");
    var matrixTest = [
        [1, -1, -1, 0],
    	[4, 1, 0, 8],
    	[0, -1, 4, 16]
    ];
    var result = [2.333, -1.333, 3.667];
     
	var gaussian = new Gaussian(matrixTest);
    var resultTest = gaussian.getGaussianResult();
    
    console.log(gaussian.matrixAsString(resultTest));
    
	var resultsCount = 0;
	for (var i=0; i < result.length; i++) {
		if (result[i] == resultTest[i].toFixed(3)) {
			console.log('Passou no '+ i +' resultado. result:'+ resultTest[i]);
			resultsCount++;
		} else {
			console.log('Nâo passou no '+ i +' resultado. result:'+ resultTest[i]);
		}
	}
 
	if(resultsCount == 3) {
		console.log("Passou nos 3 testes!");
	} else {
		console.log("Não passou em algum teste...");
	}
    
    console.log("============================================================");
})();