Gaussian Elimination

Summary

Gaussian elimination transforms $Ax=b$ into an upper-triangular system $Ux=c$ by elementary row operations, then recovers $x$ by back substitution. Partial pivoting improves numerical stability.

Prerequisites

• Direct Methods - Triangular System
• Elementary row operations

Problem Type

Solve a square linear system $Ax=b$ .

Method Definition

Form the augmented matrix $[A|b]$ . For each column $k=1,\dots ,n-1$ , eliminate entries below the pivot $a_{kk}$ using multipliers $m_{ik}=a_{ik}/a_{kk}$ . After triangularization, apply back substitution.^[1]

With partial pivoting, swap row $k$ with the row of largest $|a_{ik}|$ for $i\ge k$ before eliminating.

Assumptions / Requirements

• $A$ nonsingular (all pivots nonzero after possible row swaps)
• Prefer partial pivoting in floating-point arithmetic

Algorithm

1. For $k=1$ to $n-1$ :
   • Pivot: choose $p\ge k$ maximizing $|a_{pk}|$ ; swap rows $k$ and $p$ (and entries of $b$ ).
   • For $i=k+1$ to $n$ : $m\leftarrow a_{ik}/a_{kk}$ ; row $i\leftarrow$ row $i-m\cdot$ row $k$ .
2. Back-substitute on the resulting upper-triangular system.

Convergence

Direct method: finishes in finitely many arithmetic operations ( $O(n^3)$ ). No iteration.

Error / Accuracy

Primary check: residual $r=b-Ax$ . In exact arithmetic $r=0$ . In floating point, small $\parallel r\parallel$ relative to $\parallel A\parallel \parallel x\parallel +\parallel b\parallel$ indicates a consistent solve.

Worked Example

Solve

Augmented matrix:

Eliminate column 1:

Eliminate $y$ in row 3. Multiplier $m=5/(-7)=-5/7$ , so

Back substitution:

Solution: $(\frac{4}{3},-\frac{1}{3},\frac{2}{3})$ . Residual:

Common Failure Modes

• Zero/tiny pivot without swapping
• Arithmetic sign errors in multipliers (classic source of wrong $z$ )
• Accepting $x$ without checking $b-Ax$

Connections

• LU Factorization records the same multipliers in $L$
• Iterative Methods for large sparse alternatives
• Numerical Methods/Linear Systems/Solving Linear Systems

References