Linear equations MOC

Gaußian elimination

Gaußian elimination is an algorithm by which a system of linear equations may be manipulated into Row echelon form through elementary row operations.

The algorithm deals with the augmented matrix representation of the system . At each stage, a pivot entry is selected

1. If , if possible, interchange the pivot row with one of the rows below it. If this is not possible, i.e. all entries below the pivot are also , move the pivot one column to the right.
2. If then add a suitable multiple of the pivot row to every row below it, ensuring that every entry below the pivot is .

This process is continued until the pivot position is off the matrix. A modified version, which instead yields reduced row echelon form, is Gauß-Jordan elimination

Implementation

JavaScript

Below is a procedural implementation of the algorithm in JavaScript.

const exampleMatrix = [
  [2, 1, 2, 4],
  [2, 1, 1, 0],
  [4, 3, 2, 4],
];

const scale = (a) => (v) => v.map((x) => a * x);
const add = (v) => (u) => {
  let result = [];
  for (let i = 0; i < v.length && i < u.length; i++) {
    result.push(v[i] + u[i]);
  }
  return result;
};

const GaußianElimination = (input) => {
  let matrix = input.slice(0);

  const m = matrix.length;
  const n = matrix[0].length - 1; // do not include the augmentation column

  let r = 0;
  let c = 0;

  while (r < m && c < n) {
    if (matrix[r][c] === 0) {
      let swapped = false;
      for (let i = r + 1; i < m; i++) {
        if (matrix[i][c] !== 0 && !swapped) {
          const buffer = matrix[r];
          matrix[r] = matrix[i];
          matrix[i] = buffer;
          swapped = true;
        }
      }
      if (!swapped) {
        c++;
      }
    } else {
      for (let i = r + 1; i < m; i++) {
        console.log(i, c, -matrix[i][c] / matrix[r][c]);
        matrix[i] = add(matrix[i])(
          scale(-matrix[i][c] / matrix[r][c])(matrix[r])
        );
      }
      r++;
      c++;
    }
  }
  return matrix;
};

#state/tidy | #SemBr | #lang/en