Gaussian elimination reduces A x ⃗ = b ⃗ A\vec{x} = \vec{b} A x = b to echelon form by row operations , then solves it by back substitution.
Forward Elimination
The pivot element of a column is the entry used to eliminate the other entries in that column.
Provided a 11 ≠ 0 a_{11} \neq 0 a 11 = 0 , eliminate x 1 x_1 x 1 from equations 2 2 2 through n n n using
More generally, eliminate x i x_i x i below row i i i , for i = 1 , 2 , … , n − 1 i = 1, 2, \ldots, n-1 i = 1 , 2 , … , n − 1 , using
provided a i i ( i ) ≠ 0 a_{ii}^{(i)} \neq 0 a ii ( i ) = 0 . This reduces [ A ∣ b ⃗ ] [A \mid \vec{b}] [ A ∣ b ] to upper triangular form
Back Substitution
Once [ A ∣ b ⃗ ] [A \mid \vec{b}] [ A ∣ b ] is upper triangular, solve from the last row upward. The last row has only x n x_n x n
Then substitute the solved unknowns into each row above
Pivoting
Pivoting is interchanging rows or columns to place a larger entry in the pivot position. The system stays equivalent.
Partial Pivoting
At stage i i i , find the row p ≥ i p \geq i p ≥ i maximizing ∣ a j i ( i ) ∣ |a_{ji}^{(i)}| ∣ a j i ( i ) ∣ for j ≥ i j \geq i j ≥ i , then swap R i ↔ R p R_i \leftrightarrow R_p R i ↔ R p before eliminating. This keeps every multiplier at or below 1 1 1 in magnitude.
Scaled Partial Pivoting
Partial pivoting can pick a poor pivot when an entry is large only because its row is large. Scaled partial pivoting compares entries relative to their row. Before elimination begins, compute the scale factor of each row
At stage i i i , pick the first row p ≥ i p \geq i p ≥ i maximizing ∣ a j i ( i ) ∣ s j \frac{|a_{ji}^{(i)}|}{s_j} s j ∣ a j i ( i ) ∣ and swap R i ↔ R p R_i \leftrightarrow R_p R i ↔ R p . The scale factors s j s_j s j are computed once and carried along with their rows during swaps.
If s j = 0 s_j = 0 s j = 0 , row j j j is all 0 0 0 and the system has no unique solution.
Complete Pivoting
At stage i i i , search the entire remaining submatrix for the entry maximizing ∣ a j k ( i ) ∣ |a_{jk}^{(i)}| ∣ a j k ( i ) ∣ over j ≥ i j \geq i j ≥ i and k ≥ i k \geq i k ≥ i . Swap its row into row i i i and its column into column i i i before eliminating.
Swapping columns reorders the unknowns x i x_i x i , so the column permutation must be tracked and undone after back substitution. Complete pivoting costs O ( n 3 ) O(n^3) O ( n 3 ) comparisons and is rarely needed when partial pivoting suffices.
Pitfalls
Zero Pivot
If a i i ( i ) = 0 a_{ii}^{(i)} = 0 a ii ( i ) = 0 , the multiplier divides by zero even when the system has a unique solution. Swap in a row below with a non-zero entry in that column.
Small Pivot
A small pivot inflates the multipliers a j i ( i ) a i i ( i ) \frac{a_{ji}^{(i)}}{a_{ii}^{(i)}} a ii ( i ) a j i ( i ) , which amplifies rounding error through every later stage.
Ill Conditioning
A problem is ill-conditioned iff a small change in any of its elements causes a large change in its solution. Otherwise the problem is well-conditioned.
Round-off errors slightly change A A A and b ⃗ \vec{b} b . In an ill-conditioned system this gives large errors in the solution, and pivoting cannot prevent it.
Consider
with solution x = 1 , y = 1 x = 1, y = 1 x = 1 , y = 1 . Changing b 2 b_2 b 2 from 2.0001 2.0001 2.0001 to 2.0002 2.0002 2.0002 , a change of 0.0001 0.0001 0.0001 , gives
with solution x = 0 , y = 2 x = 0, y = 2 x = 0 , y = 2 . A 0.0001 0.0001 0.0001 change in b 2 b_2 b 2 moved x x x and y y y by 1 1 1 each. The coefficient matrix is nearly singular, det = 0.0001 \det = 0.0001 det = 0.0001 .
The condition number quantifies this sensitivity.
Cost
Space is for the augmented matrix [ A ∣ b ⃗ ] [A \mid \vec{b}] [ A ∣ b ] , since elimination is done in place. The O ( n 3 ) O(n^3) O ( n 3 ) elimination is repeated for every new b ⃗ \vec{b} b , which LU decomposition avoids.
Worked Examples
Example 1
Solve using Gaussian elimination without pivoting.
Solution Reveal Hide 1 /
[ 2 1 − 1 8 − 3 − 1 2 − 11 − 2 1 2 − 3 ] \left[\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{array}\right] 2 − 3 − 2 1 − 1 1 − 1 2 2 8 − 11 − 3 The pivot is a 11 = 2 a_{11} = 2 a 11 = 2 .
m 21 = − 3 2 = − 1.5 , m 31 = − 2 2 = − 1 m_{21} = \frac{-3}{2} = -1.5, \quad m_{31} = \frac{-2}{2} = -1 m 21 = 2 − 3 = − 1.5 , m 31 = 2 − 2 = − 1 → R 3 + R 1 R 2 + 1.5 R 1 [ 2 1 − 1 8 0 0.5 0.5 1 0 2 1 5 ] \xrightarrow[R_3 + R_1]{R_2 + 1.5R_1}
\left[\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 0.5 & 0.5 & 1 \\ 0 & 2 & 1 & 5 \end{array}\right] R 2 + 1.5 R 1 R 3 + R 1 2 0 0 1 0.5 2 − 1 0.5 1 8 1 5 The pivot is a 22 ( 1 ) = 0.5 a_{22}^{(1)} = 0.5 a 22 ( 1 ) = 0.5 .
m 32 = 2 0.5 = 4 m_{32} = \frac{2}{0.5} = 4 m 32 = 0.5 2 = 4 → R 3 − 4 R 2 [ 2 1 − 1 8 0 0.5 0.5 1 0 0 − 1 1 ] \xrightarrow{R_3 - 4R_2}
\left[\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 0.5 & 0.5 & 1 \\ 0 & 0 & -1 & 1 \end{array}\right] R 3 − 4 R 2 2 0 0 1 0.5 0 − 1 0.5 − 1 8 1 1 x 3 = 1 − 1 = − 1 x_3 = \frac{1}{-1} = -1 x 3 = − 1 1 = − 1 x 2 = 1 − 0.5 ( − 1 ) 0.5 = 3 x_2 = \frac{1 - 0.5(-1)}{0.5} = 3 x 2 = 0.5 1 − 0.5 ( − 1 ) = 3 x 1 = 8 − 1 ( 3 ) − ( − 1 ) ( − 1 ) 2 = 2 x_1 = \frac{8 - 1(3) - (-1)(-1)}{2} = 2 x 1 = 2 8 − 1 ( 3 ) − ( − 1 ) ( − 1 ) = 2 x ⃗ = ( 2 , 3 , − 1 ) T \vec{x} = (2, 3, -1)^T x = ( 2 , 3 , − 1 ) T
Step-by-step working
Example 2
Solve using Gaussian elimination with partial pivoting.
Solution Reveal Hide 1 /
[ 0 3 1 9 2 2 − 1 3 4 2 1 11 ] \left[\begin{array}{ccc|c} 0 & 3 & 1 & 9 \\ 2 & 2 & -1 & 3 \\ 4 & 2 & 1 & 11 \end{array}\right] 0 2 4 3 2 2 1 − 1 1 9 3 11 Column 1 has magnitudes ∣ 0 ∣ |0| ∣0∣ , ∣ 2 ∣ |2| ∣2∣ , and ∣ 4 ∣ |4| ∣4∣ . The largest is ∣ a 31 ∣ = 4 |a_{31}| = 4 ∣ a 31 ∣ = 4 in R 3 R_3 R 3 , so swap R 1 ↔ R 3 R_1 \leftrightarrow R_3 R 1 ↔ R 3 .
→ R 1 ↔ R 3 [ 4 2 1 11 2 2 − 1 3 0 3 1 9 ] \xrightarrow{R_1 \leftrightarrow R_3}
\left[\begin{array}{ccc|c} 4 & 2 & 1 & 11 \\ 2 & 2 & -1 & 3 \\ 0 & 3 & 1 & 9 \end{array}\right] R 1 ↔ R 3 4 2 0 2 2 3 1 − 1 1 11 3 9 m 21 = 2 4 = 0.5 , m 31 = 0 m_{21} = \frac{2}{4} = 0.5, \quad m_{31} = 0 m 21 = 4 2 = 0.5 , m 31 = 0 → R 2 − 0.5 R 1 [ 4 2 1 11 0 1 − 1.5 − 2.5 0 3 1 9 ] \xrightarrow{R_2 - 0.5R_1}
\left[\begin{array}{ccc|c} 4 & 2 & 1 & 11 \\ 0 & 1 & -1.5 & -2.5 \\ 0 & 3 & 1 & 9 \end{array}\right] R 2 − 0.5 R 1 4 0 0 2 1 3 1 − 1.5 1 11 − 2.5 9 Column 2 below row 1 has magnitudes ∣ 1 ∣ |1| ∣1∣ and ∣ 3 ∣ |3| ∣3∣ . The largest is ∣ a 32 ( 1 ) ∣ = 3 |a_{32}^{(1)}| = 3 ∣ a 32 ( 1 ) ∣ = 3 in R 3 R_3 R 3 , so swap R 2 ↔ R 3 R_2 \leftrightarrow R_3 R 2 ↔ R 3 .
→ R 2 ↔ R 3 [ 4 2 1 11 0 3 1 9 0 1 − 1.5 − 2.5 ] \xrightarrow{R_2 \leftrightarrow R_3}
\left[\begin{array}{ccc|c} 4 & 2 & 1 & 11 \\ 0 & 3 & 1 & 9 \\ 0 & 1 & -1.5 & -2.5 \end{array}\right] R 2 ↔ R 3 4 0 0 2 3 1 1 1 − 1.5 11 9 − 2.5 m 32 = 1 3 m_{32} = \frac{1}{3} m 32 = 3 1 → R 3 − 1 3 R 2 [ 4 2 1 11 0 3 1 9 0 0 − 11 6 − 11 2 ] \xrightarrow{R_3 - \frac{1}{3}R_2}
\left[\begin{array}{ccc|c} 4 & 2 & 1 & 11 \\ 0 & 3 & 1 & 9 \\ 0 & 0 & -\frac{11}{6} & -\frac{11}{2} \end{array}\right] R 3 − 3 1 R 2 4 0 0 2 3 0 1 1 − 6 11 11 9 − 2 11 x 3 = − 11 / 2 − 11 / 6 = 3 x_3 = \frac{-11/2}{-11/6} = 3 x 3 = − 11/6 − 11/2 = 3 x 2 = 9 − 1 ( 3 ) 3 = 2 x_2 = \frac{9 - 1(3)}{3} = 2 x 2 = 3 9 − 1 ( 3 ) = 2 x 1 = 11 − 2 ( 2 ) − 1 ( 3 ) 4 = 1 x_1 = \frac{11 - 2(2) - 1(3)}{4} = 1 x 1 = 4 11 − 2 ( 2 ) − 1 ( 3 ) = 1 x ⃗ = ( 1 , 2 , 3 ) T \vec{x} = (1, 2, 3)^T x = ( 1 , 2 , 3 ) T
Step-by-step working
Example 3
Solve using Gaussian elimination with scaled partial pivoting.
Solution Reveal Hide 1 /
[ 4 100 − 50 54 1 1 2 4 2 0 − 1 1 ] \left[\begin{array}{ccc|c} 4 & 100 & -50 & 54 \\ 1 & 1 & 2 & 4 \\ 2 & 0 & -1 & 1 \end{array}\right] 4 1 2 100 1 0 − 50 2 − 1 54 4 1 s 1 = max { 4 , 100 , 50 } = 100 , s 2 = max { 1 , 1 , 2 } = 2 , s 3 = max { 2 , 0 , 1 } = 2 s_1 = \max\{4, 100, 50\} = 100, \quad s_2 = \max\{1, 1, 2\} = 2, \quad s_3 = \max\{2, 0, 1\} = 2 s 1 = max { 4 , 100 , 50 } = 100 , s 2 = max { 1 , 1 , 2 } = 2 , s 3 = max { 2 , 0 , 1 } = 2 Compare the scaled magnitudes in column 1.
∣ a 11 ∣ s 1 = 4 100 = 0.04 , ∣ a 21 ∣ s 2 = 1 2 = 0.5 , ∣ a 31 ∣ s 3 = 2 2 = 1 \frac{|a_{11}|}{s_1} = \frac{4}{100} = 0.04, \quad \frac{|a_{21}|}{s_2} = \frac{1}{2} = 0.5, \quad \frac{|a_{31}|}{s_3} = \frac{2}{2} = 1 s 1 ∣ a 11 ∣ = 100 4 = 0.04 , s 2 ∣ a 21 ∣ = 2 1 = 0.5 , s 3 ∣ a 31 ∣ = 2 2 = 1 Partial pivoting would keep R 1 R_1 R 1 since ∣ 4 ∣ |4| ∣4∣ is largest in column 1, but scaled partial pivoting picks R 3 R_3 R 3 with ratio 1 1 1 and swaps R 1 ↔ R 3 R_1 \leftrightarrow R_3 R 1 ↔ R 3 . The scale factors move with their rows to become ( s 3 , s 2 , s 1 ) = ( 2 , 2 , 100 ) (s_3, s_2, s_1) = (2, 2, 100) ( s 3 , s 2 , s 1 ) = ( 2 , 2 , 100 ) .
→ R 1 ↔ R 3 [ 2 0 − 1 1 1 1 2 4 4 100 − 50 54 ] \xrightarrow{R_1 \leftrightarrow R_3}
\left[\begin{array}{ccc|c} 2 & 0 & -1 & 1 \\ 1 & 1 & 2 & 4 \\ 4 & 100 & -50 & 54 \end{array}\right] R 1 ↔ R 3 2 1 4 0 1 100 − 1 2 − 50 1 4 54 m 21 = 1 2 = 0.5 , m 31 = 4 2 = 2 m_{21} = \frac{1}{2} = 0.5, \quad m_{31} = \frac{4}{2} = 2 m 21 = 2 1 = 0.5 , m 31 = 2 4 = 2 → R 3 − 2 R 1 R 2 − 0.5 R 1 [ 2 0 − 1 1 0 1 2.5 3.5 0 100 − 48 52 ] \xrightarrow[R_3 - 2R_1]{R_2 - 0.5R_1}
\left[\begin{array}{ccc|c} 2 & 0 & -1 & 1 \\ 0 & 1 & 2.5 & 3.5 \\ 0 & 100 & -48 & 52 \end{array}\right] R 2 − 0.5 R 1 R 3 − 2 R 1 2 0 0 0 1 100 − 1 2.5 − 48 1 3.5 52 Compare the remaining rows in column 2 using their original scale factors s 2 = 2 s_2 = 2 s 2 = 2 and s 1 = 100 s_1 = 100 s 1 = 100 .
∣ a 22 ( 1 ) ∣ s 2 = 1 2 = 0.5 , ∣ a 32 ( 1 ) ∣ s 1 = 100 100 = 1 \frac{|a_{22}^{(1)}|}{s_2} = \frac{1}{2} = 0.5, \quad \frac{|a_{32}^{(1)}|}{s_1} = \frac{100}{100} = 1 s 2 ∣ a 22 ( 1 ) ∣ = 2 1 = 0.5 , s 1 ∣ a 32 ( 1 ) ∣ = 100 100 = 1 Swap R 2 ↔ R 3 R_2 \leftrightarrow R_3 R 2 ↔ R 3 .
→ R 2 ↔ R 3 [ 2 0 − 1 1 0 100 − 48 52 0 1 2.5 3.5 ] \xrightarrow{R_2 \leftrightarrow R_3}
\left[\begin{array}{ccc|c} 2 & 0 & -1 & 1 \\ 0 & 100 & -48 & 52 \\ 0 & 1 & 2.5 & 3.5 \end{array}\right] R 2 ↔ R 3 2 0 0 0 100 1 − 1 − 48 2.5 1 52 3.5 m 32 = 1 100 = 0.01 m_{32} = \frac{1}{100} = 0.01 m 32 = 100 1 = 0.01 → R 3 − 0.01 R 2 [ 2 0 − 1 1 0 100 − 48 52 0 0 2.98 2.98 ] \xrightarrow{R_3 - 0.01R_2}
\left[\begin{array}{ccc|c} 2 & 0 & -1 & 1 \\ 0 & 100 & -48 & 52 \\ 0 & 0 & 2.98 & 2.98 \end{array}\right] R 3 − 0.01 R 2 2 0 0 0 100 0 − 1 − 48 2.98 1 52 2.98 x 3 = 2.98 2.98 = 1 x_3 = \frac{2.98}{2.98} = 1 x 3 = 2.98 2.98 = 1 x 2 = 52 − ( − 48 ) ( 1 ) 100 = 1 x_2 = \frac{52 - (-48)(1)}{100} = 1 x 2 = 100 52 − ( − 48 ) ( 1 ) = 1 x 1 = 1 − ( − 1 ) ( 1 ) 2 = 1 x_1 = \frac{1 - (-1)(1)}{2} = 1 x 1 = 2 1 − ( − 1 ) ( 1 ) = 1 x ⃗ = ( 1 , 1 , 1 ) T \vec{x} = (1, 1, 1)^T x = ( 1 , 1 , 1 ) T
Step-by-step working
Example 4
Solve using Gaussian elimination with complete pivoting.
Solution Reveal Hide 1 /
The initial variable order is ( x 1 , x 2 , x 3 ) (x_1, x_2, x_3) ( x 1 , x 2 , x 3 ) .
[ 2 − 1 1 3 1 1 4 15 1 2 − 2 − 1 ] \left[\begin{array}{ccc|c} 2 & -1 & 1 & 3 \\ 1 & 1 & 4 & 15 \\ 1 & 2 & -2 & -1 \end{array}\right] 2 1 1 − 1 1 2 1 4 − 2 3 15 − 1 The largest entry in magnitude across the entire coefficient matrix is ∣ a 23 ∣ = 4 |a_{23}| = 4 ∣ a 23 ∣ = 4 at row 2, column 3. Swap R 1 ↔ R 2 R_1 \leftrightarrow R_2 R 1 ↔ R 2 and C 1 ↔ C 3 C_1 \leftrightarrow C_3 C 1 ↔ C 3 . The variable order becomes ( x 3 , x 2 , x 1 ) (x_3, x_2, x_1) ( x 3 , x 2 , x 1 ) .
→ R 1 ↔ R 2 , C 1 ↔ C 3 [ 4 1 1 15 1 − 1 2 3 − 2 2 1 − 1 ] \xrightarrow{R_1 \leftrightarrow R_2,\; C_1 \leftrightarrow C_3}
\left[\begin{array}{ccc|c} 4 & 1 & 1 & 15 \\ 1 & -1 & 2 & 3 \\ -2 & 2 & 1 & -1 \end{array}\right] R 1 ↔ R 2 , C 1 ↔ C 3 4 1 − 2 1 − 1 2 1 2 1 15 3 − 1 m 21 = 1 4 = 0.25 , m 31 = − 2 4 = − 0.5 m_{21} = \frac{1}{4} = 0.25, \quad m_{31} = \frac{-2}{4} = -0.5 m 21 = 4 1 = 0.25 , m 31 = 4 − 2 = − 0.5 → R 3 + 0.5 R 1 R 2 − 0.25 R 1 [ 4 1 1 15 0 − 1.25 1.75 − 0.75 0 2.5 1.5 6.5 ] \xrightarrow[R_3 + 0.5R_1]{R_2 - 0.25R_1}
\left[\begin{array}{ccc|c} 4 & 1 & 1 & 15 \\ 0 & -1.25 & 1.75 & -0.75 \\ 0 & 2.5 & 1.5 & 6.5 \end{array}\right] R 2 − 0.25 R 1 R 3 + 0.5 R 1 4 0 0 1 − 1.25 2.5 1 1.75 1.5 15 − 0.75 6.5 In the remaining 2 × 2 2 \times 2 2 × 2 submatrix, the largest entry in magnitude is ∣ 2.5 ∣ |2.5| ∣2.5∣ at row 3, column 2. Swap R 2 ↔ R 3 R_2 \leftrightarrow R_3 R 2 ↔ R 3 . The variable order stays ( x 3 , x 2 , x 1 ) (x_3, x_2, x_1) ( x 3 , x 2 , x 1 ) .
→ R 2 ↔ R 3 [ 4 1 1 15 0 2.5 1.5 6.5 0 − 1.25 1.75 − 0.75 ] \xrightarrow{R_2 \leftrightarrow R_3}
\left[\begin{array}{ccc|c} 4 & 1 & 1 & 15 \\ 0 & 2.5 & 1.5 & 6.5 \\ 0 & -1.25 & 1.75 & -0.75 \end{array}\right] R 2 ↔ R 3 4 0 0 1 2.5 − 1.25 1 1.5 1.75 15 6.5 − 0.75 m 32 = − 1.25 2.5 = − 0.5 m_{32} = \frac{-1.25}{2.5} = -0.5 m 32 = 2.5 − 1.25 = − 0.5 → R 3 + 0.5 R 2 [ 4 1 1 15 0 2.5 1.5 6.5 0 0 2.5 2.5 ] \xrightarrow{R_3 + 0.5R_2}
\left[\begin{array}{ccc|c} 4 & 1 & 1 & 15 \\ 0 & 2.5 & 1.5 & 6.5 \\ 0 & 0 & 2.5 & 2.5 \end{array}\right] R 3 + 0.5 R 2 4 0 0 1 2.5 0 1 1.5 2.5 15 6.5 2.5 Back substitution in the permuted order ( x 3 , x 2 , x 1 ) (x_3, x_2, x_1) ( x 3 , x 2 , x 1 ) .
x 1 = 2.5 2.5 = 1 x_1 = \frac{2.5}{2.5} = 1 x 1 = 2.5 2.5 = 1 x 2 = 6.5 − 1.5 ( 1 ) 2.5 = 2 x_2 = \frac{6.5 - 1.5(1)}{2.5} = 2 x 2 = 2.5 6.5 − 1.5 ( 1 ) = 2 x 3 = 15 − 1 ( 2 ) − 1 ( 1 ) 4 = 3 x_3 = \frac{15 - 1(2) - 1(1)}{4} = 3 x 3 = 4 15 − 1 ( 2 ) − 1 ( 1 ) = 3 Restoring the original variable order gives x ⃗ = ( 1 , 2 , 3 ) T \vec{x} = (1, 2, 3)^T x = ( 1 , 2 , 3 ) T .
Step-by-step working