Gaussian Elimination

Gaussian elimination is a method for solving systems of linear equations. It is a systematic way to transform the system into an equivalent system that is easier to solve.

The general form of a system of linear equations with coefficients and constants is:

The goal of Gaussian elimination is to transform this system into an upper triangular matrix, which can be solved using back substitution. Notice that is the result of the forward elimination step which reduces values of through the elimination process.

Algorithm

The algorithm can be broken down into two main steps: forward elimination and back substitution.

Forward Elimination

The goal of forward elimination is to transform the original system of equations into an upper triangular form, where all elements below the main diagonal are zero.

This is achieved by performing a series of row operations to eliminate the coefficients below the main diagonal of the matrix. The system of equations can be represented in matrix form as:

where is the coefficient matrix, is the vector of unknowns, and is the constant vector. The forward elimination process starts with pivoting: for each column, select the pivot element, which is the largest absolute value in the column from the current row to the last row. This also helps in reducing numerical errors.

Next is row swapping: swap the current row with the row containing the pivot element to bring the pivot to the diagonal position. For example, suppose we have a matrix and we want to swap row with row :

Finally, in the elimination step, for each row below the pivot, subtract a multiple of the pivot row from the current row to make the elements below the pivot zero. For example, to eliminate the element below the pivot , we multiply row by and subtract it from row .

After forward elimination, the matrix is transformed into an upper triangular matrix , where all elements below the main diagonal are zero.

Back Substitution

Once the matrix is in upper triangular form, back substitution is used to find the solution vector . Starting from the last row, solve for each variable by substituting the known values from the previous steps. The back substitution process is as follows:

• Solve for the last variable using the last equation.
• Substitute the known value into the previous equations to solve for the remaining variables.

The result is the solution vector , which satisfies the original system of equations.

The time complexity of Gaussian elimination is , where is the number of equations (or variables). The space complexity is due to the storage of the matrix and vectors involved in the computation.

Here is a simple implementation of Gaussian elimination in JavaScript.

code.js
1function gaussianElimination(A, b) {
2  const n = A.length;
3  const x = new Array(n).fill(0);
4
5  // Forward elimination
6  for (let i = 0; i < n; i++) {
7    // Find pivot row
8    let maxRow = i;
9    for (let k = i + 1; k < n; k++) {
10      if (Math.abs(A[k][i]) > Math.abs(A[maxRow][i])) {
11        maxRow = k;
12      }
13    }
14
15    // Swap rows
16    [A[i], A[maxRow]] = [A[maxRow], A[i]];
17    [b[i], b[maxRow]] = [b[maxRow], b[i]];
18
19    // Make all rows below this one 0 in the current column
20    for (let k = i + 1; k < n; k++) {
21      const factor = A[k][i] / A[i][i];
22      for (let j = i; j < n; j++) {
23        A[k][j] -= factor * A[i][j];
24      }
25      b[k] -= factor * b[i];
26    }
27  }
28
29  // Back substitution
30  for (let i = n - 1; i >= 0; i--) {
31    x[i] = b[i] / A[i][i];
32    for (let k = i - 1; k >= 0; k--) {
33      b[k] -= A[k][i] * x[i];
34    }
35  } 
36
37  return x;
38}
39
40const A = [
41  [1, 2, 3],
42  [4, 5, 6],
43  [7, 8, 9]
44];
45const b = [1, 2, 3];  
46const x = gaussianElimination(A, b);
47console.log(x); // Output: [1, 2, 3]

This function will throw an error if the matrix is singular (i.e., if it does not have a unique solution).