Gaussian Elimination
The standard direct method for solving systems of linear equations — the backbone of scientific computing.
Try Gaussian Elimination — No Sign-in NeededWhat is the Gaussian Elimination?
Gaussian Elimination is a direct method for solving systems of linear equations. Unlike iterative methods that approach a solution gradually, Gaussian elimination finds the exact solution in a finite, predictable number of steps. It works by applying a sequence of elementary row operations to transform the augmented matrix [A|b] into upper-triangular form — a process called forward elimination — and then recovering the solution variables from back to front using back substitution.
The method is named after Carl Friedrich Gauss, though the underlying ideas appear in Chinese mathematics texts dating back to around 200 BCE. Today, Gaussian elimination (and its variants like LU decomposition) underlies virtually every linear system solver in scientific software, from MATLAB's backslash operator to the numerical core of finite-element analysis packages.
In practice, raw Gaussian elimination is always paired with partial pivoting: before each elimination step, rows are swapped to place the largest available entry on the diagonal. This prevents division by near-zero numbers, which would amplify floating-point rounding errors and produce wildly inaccurate results. With partial pivoting, Gaussian elimination is numerically stable for the vast majority of practical problems.
The Formula
The multiplier mᵢₖ is the ratio of the element to be eliminated to the pivot element. Subtracting mᵢₖ times the pivot row zeros out the column below the pivot.
Step-by-Step Algorithm
- 1
Form the augmented matrix [A|b] combining the coefficient matrix and right-hand side.
- 2
For each column k (the pivot column): find the row with the largest |aᵢₖ| below row k and swap it with row k (partial pivoting).
- 3
For each row i below k: compute multiplier mᵢₖ = aᵢₖ / aₖₖ, then subtract mᵢₖ × row k from row i.
- 4
After elimination, the matrix is upper triangular. Solve for xₙ from the last equation.
- 5
Back-substitute: for i = n−1 down to 1, solve xᵢ = (bᵢ − Σaᵢⱼxⱼ) / aᵢᵢ.
Convergence & Behaviour
Gaussian elimination with partial pivoting is numerically stable for well-conditioned systems. The operation count is (2/3)n³ + O(n²) floating-point operations. The main failure mode is a singular or near-singular matrix — when a pivot is zero or near-zero even after row swaps, the system either has no unique solution or is ill-conditioned. The condition number κ(A) quantifies this: a large condition number means small perturbations in b lead to large changes in x.
Use Gaussian elimination for small to medium dense systems (n up to a few thousand). It is the standard approach when you need the exact solution and the matrix is not sparse.
Avoid it for very large sparse systems (use iterative methods like conjugate gradient or GMRES instead), or when you need to solve the same system with many different right-hand sides (compute the LU decomposition once instead).
Worked Example
Solve the system: 2x + y − z = 8, −3x − y + 2z = −11, −2x + y + 2z = −3.
- 1.Augmented matrix: [[2,1,−1|8],[−3,−1,2|−11],[−2,1,2|−3]]
- 2.Pivot on row 1: eliminate x from rows 2 and 3.
- 3.R2 ← R2 − (−3/2)R1 = [0, 0.5, 0.5 | 1]
- 4.R3 ← R3 − (−1)R1 = [0, 2, 1 | 5]
- 5.Pivot on row 2: eliminate y from row 3.
- 6.R3 ← R3 − 4·R2 = [0, 0, −1 | 1]
- 7.Back-substitute: z = −1, y = (1 − 0.5·(−1))/0.5 = 3, x = (8 − 1·3 − (−1)·(−1))/2 = 2
Result: Solution: x = 2, y = 3, z = −1.
Try It Now — No Account Required
Want the full platform experience?
Sign up free and unlock infinite-zoom canvas, AI Tutor explanations, Canvas LTI grade passback, and your full solve history — pre-loaded with the Gaussian Elimination example above.