Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of row-wise operations performed on the corresponding matrix of coefficients.
To perform row reduction on a matrix, one uses a sequence of elementary row operations to modify the matrix until the lower left-hand corner of the matrix is filled with zeros, as much as possible. There are three types of elementary row operations:
Swapping two rows,
Multiplying a row by a nonzero number,
Adding a multiple of one row to another row.
Using these operations, a matrix can always be transformed into an upper triangular matrix, and in fact one that is in row echelon form. Once all of the leading coefficients (the leftmost nonzero entry in each row) are 1, and every column containing a leading coefficient has zeros elsewhere, the matrix is said to be in reduced row echelon form. This final form is unique; in other words, it is independent of the sequence of row operations used. For example, in the following sequence of row operations (where two elementary operations on different rows are done at the first and third steps), the third and fourth matrices are the ones in row echelon form, and the final matrix is the unique reduced row echelon form.
Using row operations to convert a matrix into reduced row echelon form is sometimes called Gauss–Jordan elimination. In this case, the term Gaussian elimination refers to the process until it has reached its upper triangular, or (unreduced) row echelon form. For computational reasons, when solving systems of linear equations, it is sometimes preferable to stop row operations before the matrix is completely reduced.
function backSubstitution(A) {
let m = A.length;
let x = new Array(m);
for (let i = m - 1; i >= 0; i--) {
x[i] = A[i][m];
for (let j = i + 1; j < m; j++) {
x[i] -= A[i][j] * x[j];
}
x[i] = x[i] / A[i][i];
}
return x;
}
function augment(m, v) {
let a = new Array(m.length);
for (let i = 0; i < m.length; i++) {
a[i] = [...m[i], v[i]];
}
return a;
}
function gauss(A) {
let n = A.length;
for (let k = 0; k < n; k++) {
for (let i = k + 1; i < n; i++) {
let f = A[i][k] / A[k][k]; // factor to scale the current row
for (let j = k + 1; j <= n; j++) {
A[i][j] -= f * A[k][j]; // subtract k-th row multipied by f
}
A[i][k] = 0; // fill lower triangle with zero
}
}
}
/*
let A1 = [
[1, 2, 1],
[3, 2, 4],
[4, 4, 3]
];
let v1 = [5, 17, 26];
let A1A = augment(A1, v1);
console.log("augmented matrix=", A1A);
gauss(A1A);
console.log(A1A);
*/
let A2 = [
[1, 2, 1, -1],
[3, 2, 4, 4],
[4, 4, 3, 4],
[2, 0, 1, 5]
];
let v2 = [5, 16, 22, 15];
let A2A = augment(A2, v2);
console.log("A2=", A2A);
gauss(A2A);
console.log(A2A);
let x = backSubstitution(A2A);
console.log(x);
Another implementation
function print(M, msg) {
console.log("======" + msg + "=========");
for (var k = 0; k < M.length; ++k) {
console.log(M[k]);
}
console.log("==========================");
}
function diagonalize(M) {
var m = M.length;
var n = M[0].length;
for (var k = 0; k < Math.min(m, n); ++k) {
// Find the k-th pivot
var i_max = findPivot(M, k);
if (A[i_max][k] == 0)
throw "matrix is singular";
swap_rows(M, k, i_max);
// Do for all rows below pivot
for (var i = k + 1; i < m; ++i) {
// Do for all remaining elements in current row:
var c = A[i][k] / A[k][k];
for (var j = k + 1; j < n; ++j) {
A[i][j] = A[i][j] - A[k][j] * c;
}
// Fill lower triangular matrix with zeros
A[i][k] = 0;
}
}
}
function findPivot(M, k) {
var i_max = k;
for (var i = k + 1; i < M.length; ++i) {
if (Math.abs(M[i][k]) > Math.abs(M[i_max][k])) {
i_max = i;
}
}
return i_max;
}
function swap_rows(M, i_max, k) {
if (i_max != k) {
var temp = A[i_max];
A[i_max] = A[k];
A[k] = temp;
}
}
function makeM(A, b) {
for (var i = 0; i < A.length; ++i) {
A[i].push(b[i]);
}
}
function substitute(M) {
var m = M.length;
for (var i = m - 1; i >= 0; --i) {
var x = M[i][m] / M[i][i];
for (var j = i - 1; j >= 0; --j) {
M[j][m] -= x * M[j][i];
M[j][i] = 0;
}
M[i][m] = x;
M[i][i] = 1;
}
}
function extractX(M) {
var x = [];
var m = A.length;
var n = A[0].length;
for (var i = 0; i < m; ++i) {
x.push(A[i][n - 1]);
}
return x;
}
function solve(A, b) {
makeM(A, b);
diagonalize(A);
substitute(A);
var x = extractX(A);
return x;
}
// Example usage:
A = [
[9, 3, 4],
[4, 3, 4],
[1, 1, 1]
];
b = [7, 8, 3];
print(A, "Matrix A");
print(b, "Vector b");
var x = solve(A, b);
console.log("Solution (x):", x);
Comments