= Gaussian elimination
{c}
{wiki}
= Row reduction
{synonym}
Gaussian elimination applies elementary row operations to reduce a linear system to triangular form. Dense elimination uses $O(n^3)$ arithmetic operations.
<Gaussian elimination> solves a <linear system> by removing one unknown from later equations at each step. Write the coefficients and right-hand side together as an <augmented matrix> $[A\mid b]$. Apply the same <elementary row operations> to both parts until the coefficients form a <row echelon form>; for a square <invertible matrix>, this gives an <upper triangular matrix> system. Then <back substitution> recovers the unknowns from the last equation upward. The useful simplification is that each successive equation involves fewer unknowns, while the set of solutions stays the same.
Why do <elementary row operations> preserve solutions? Interchanging equations changes only their order. Multiplying an equation by a nonzero <scalar> can be undone by division. Replacing equation $i$ by itself plus $c$ times equation $j$, with $i\ne j$, can be undone by adding $-c$ times the unchanged equation $j$. Equivalently, an <elementary matrix> $E$ is an <invertible matrix>, so $Ax=b$ if and only if $EAx=Eb$. Applying an operation to $A$ without also applying it to $b$ loses this equivalence.
At step $k$, choose a nonzero <pivot element> $a_{kk}$ after any row interchange. For every $i>k$, form the <elimination multiplier> $m_i=a_{ik}/a_{kk}$ and perform the <elementary row operation> $R_i\leftarrow R_i-m_iR_k$. Its coefficient in column $k$ becomes $a_{ik}-(a_{ik}/a_{kk})a_{kk}=0$ in exact arithmetic. Later operations combine rows that already have zeros in earlier columns, so those zeros survive. If an active column has no nonzero candidate, general <row echelon form> reduction skips it; a square <invertible matrix> always has a candidate at each step with suitable row interchanges. <Partial pivoting> also considers <roundoff error> when selecting the candidate.<Fundamentals of Numerical Computation by Tobin A. Driscoll and others/2.6 Row pivoting>[Fundamentals of Numerical Computation by Tobin A. Driscoll and others; §2.6.1, Definition 2.6.1: select the largest absolute candidate; §2.6.3: permute the right-hand side too]{ref}
For a dense $n\times n$ <matrix> with one right-hand side, the classical <algorithm> uses $\tfrac23n^3+O(n^2)$ <arithmetic operations> over the <real numbers>, counting each <addition>, <subtraction>, <multiplication> and <division> as one. At step $k$, the coefficient update has $(n-k)^2$ entries, each costing one <multiplication> and one <subtraction>; the <elimination multipliers>, right-hand-side updates and <back substitution> contribute lower-order terms. Searching for <partial pivoting> adds $O(n^2)$ comparisons, and storing the dense coefficients uses $O(n^2)$ space. These assumptions exclude the different storage and work patterns of <sparse Gaussian elimination>; the exact loop counts appear in <LU factorization and solve costs>. Here $O$ denotes <Big O notation>.
Recording the same steps as an <LU decomposition> makes <Reusing LU factors for multiple right-hand sides> possible. This is useful whenever the coefficients stay fixed while the forcing <vector> changes: the expensive elimination is done once. The choice of <pivot element> matters even when the <linear system> is well conditioned, as <Tiny-pivot roundoff in Gaussian elimination> demonstrates.
Back to article page
