Gauss Elimination and Gauss-Seidel
CSIR NET numerical analysis: Gauss elimination, pivoting, LU, operation counts, Jacobi and Gauss-Seidel iteration, spectral radius and convergence tests.
- 21 min
On this page · 12 sections
Prerequisites
- Iteration, Newton-Raphson and Rate of Convergence: Jacobi and Gauss-Seidel are fixed-point iterations \( x^{(k+1)} = Tx^{(k)} + c \); the role of \( \lvert g'(\alpha) \rvert \) is played by the spectral radius of \( T \).
- Linear algebra: row operations, determinants, eigenvalues and positive definite matrices. The chapter on vector spaces and linear maps is in the Mathematical Sciences unit list.
- Metric Spaces and Several Variables: norms on \( \mathbb{R}^n \) and the contraction mapping theorem.
The Hook: Two Methods, Opposite Verdicts
Direct Methods: Gauss Elimination
The algorithm
For \( Ax = b \) with \( A \) an \( n \times n \) non-singular matrix, form the augmented matrix \( [A \mid b] \).
- Forward elimination. For \( k = 1, \dots, n - 1 \): with pivot \( a_{kk}^{(k)} \ne 0 \), compute the multipliers \( m_{ik} = \frac{a_{ik}^{(k)}}{a_{kk}^{(k)}} \) for \( i > k \) and replace row \( i \) by row \( i - m_{ik} \times \) row \( k \). This creates zeros below the pivot.
- Back substitution. The result is upper triangular \( Ux = c \); solve
Operation counts
| Task | Multiplications/divisions (leading term) |
|---|---|
| Forward elimination of \( A \) | \( \frac{n^3}{3} \) |
| Back substitution | \( \frac{n^2}{2} \) |
| Gauss elimination, whole solve | \( \frac{n^3}{3} \) |
| Gauss-Jordan (reduce to identity) | \( \frac{n^3}{2} \) |
| Solving with a known \( LU \), each new \( b \) | \( n^2 \) |
| One Jacobi or Gauss-Seidel sweep (full \( A \)) | \( n^2 \) |
| Tridiagonal system (Thomas algorithm) | proportional to \( n \) |
So doubling \( n \) multiplies the elimination cost by about 8, and Gauss-Jordan costs about 50% more than Gauss elimination with back substitution. Once \( A = LU \) is known, each further right-hand side costs only \( O(n^2) \).
Pivoting
If a pivot is zero, elimination stops; if it is small, the multipliers are large and rounding errors are amplified.
Partial pivoting: at step \( k \), swap rows so that the pivot is the entry of largest absolute value in column \( k \) on or below the diagonal. Then every \( \lvert m_{ik} \rvert \le 1 \). Complete pivoting searches the whole remaining submatrix (row and column swaps); it is more stable in theory and more expensive.
Pivoting is unnecessary (elimination is stable without it) when \( A \) is strictly diagonally dominant by rows or columns, or symmetric positive definite.
LU factorisation
Gauss elimination without row swaps factorises \( A = LU \), with \( U \) the final upper triangular matrix and \( L \) unit lower triangular holding the multipliers:
$$L = \begin{pmatrix} 1 & 0 & 0 \\ m_{21} & 1 & 0 \\ m_{31} & m_{32} & 1 \end{pmatrix}.$$For the worked example, \( L = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -1 & 1 \end{pmatrix} \), \( U = \begin{pmatrix} 2 & 1 & 1 \\ 0 & -8 & -2 \\ 0 & 0 & 1 \end{pmatrix} \).
| Variant | Normalisation | When |
|---|---|---|
| Doolittle | \( L \) has unit diagonal | the form produced by Gauss elimination |
| Crout | \( U \) has unit diagonal | same work, different bookkeeping |
| Cholesky | \( A = LL^T \), \( L \) with positive diagonal | \( A \) symmetric positive definite; about half the work of LU |
| With pivoting | \( PA = LU \), \( P \) a permutation | every non-singular \( A \) |
Solving with \( LU \): first \( Ly = b \) (forward substitution), then \( Ux = y \) (back substitution).
Conditioning
Even exact algorithms cannot fix a badly posed problem. The condition number is \( \kappa(A) = \lVert A \rVert \, \lVert A^{-1} \rVert \ge 1 \), and
$$\frac{\lVert \delta x \rVert}{\lVert x \rVert} \le \kappa(A)\, \frac{\lVert \delta b \rVert}{\lVert b \rVert}.$$Example: \( x + y = 2 \), \( x + 1.0001y = 2.0001 \) has solution \( (1, 1) \). Change the second right-hand side to \( 2.0002 \) (a change of about \( 0.005\% \)) and the solution jumps to \( (0, 2) \). Here \( \kappa_\infty(A) \approx 4 \times 10^4 \). Large \( \kappa \) means ill-conditioned; a near-zero determinant alone is not the test (scaling \( A \) by \( 10^{-3} \) shrinks the determinant without changing \( \kappa \)).
Iterative Methods: Jacobi and Gauss-Seidel
Split \( A = L + D + U \): \( D \) the diagonal, \( L \) the strictly lower part and \( U \) the strictly upper part (these \( L \), \( U \) are not the LU factors). Assume every \( a_{ii} \ne 0 \).
Jacobi
Solve equation \( i \) for \( x_i \), using only old values:
$$x_i^{(k+1)} = \frac{1}{a_{ii}}\Big(b_i - \sum_{j \ne i} a_{ij} x_j^{(k)}\Big), \qquad x^{(k+1)} = \underbrace{-D^{-1}(L + U)}_{T_J} x^{(k)} + D^{-1}b.$$Gauss-Seidel
Use each new component as soon as it is computed:
$$x_i^{(k+1)} = \frac{1}{a_{ii}}\Big(b_i - \sum_{j < i} a_{ij} x_j^{(k+1)} - \sum_{j > i} a_{ij} x_j^{(k)}\Big), \qquad x^{(k+1)} = \underbrace{-(D + L)^{-1}U}_{T_{GS}} x^{(k)} + (D + L)^{-1}b.$$Gauss-Seidel needs only one storage vector (overwrite in place); Jacobi needs two but its components can be updated in parallel. Gauss-Seidel depends on the order of the equations; Jacobi does not.
The convergence theorem
Both methods are \( x^{(k+1)} = Tx^{(k)} + c \). The error satisfies \( e^{(k+1)} = Te^{(k)} \), so \( e^{(k)} = T^k e^{(0)} \).
Sufficient conditions you can check by eye
| Condition on \( A \) | Jacobi | Gauss-Seidel |
|---|---|---|
| Strictly diagonally dominant by rows: \( \lvert a_{ii} \rvert > \sum_{j \ne i} \lvert a_{ij} \rvert \) for every \( i \) | converges | converges |
| Strictly diagonally dominant by columns | converges | converges |
| Symmetric positive definite | not guaranteed (converges iff \( 2D - A \) is also positive definite) | converges |
| Tridiagonal with non-zero diagonal | converges iff GS converges | \( \rho(T_{GS}) = \rho(T_J)^2 \) |
For row dominance, \( \lVert T_J \rVert_\infty = \max_i \sum_{j \ne i} \frac{\lvert a_{ij} \rvert}{\lvert a_{ii} \rvert} < 1 \), which proves the Jacobi case immediately.
The 2 by 2 case, once and for all
For \( A = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \) with \( ad \ne 0 \):
$$T_J = \begin{pmatrix} 0 & -\frac{b}{a} \\ -\frac{c}{d} & 0 \end{pmatrix}, \quad \rho(T_J) = \sqrt{\left\lvert \frac{bc}{ad} \right\rvert}; \qquad T_{GS} = \begin{pmatrix} 0 & -\frac{b}{a} \\ 0 & \frac{bc}{ad} \end{pmatrix}, \quad \rho(T_{GS}) = \left\lvert \frac{bc}{ad} \right\rvert.$$So both converge iff \( \lvert bc \rvert < \lvert ad \rvert \), and then Gauss-Seidel’s rate is the square of Jacobi’s: one Gauss-Seidel sweep is worth two Jacobi sweeps. For \( \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix} \): \( \rho(T_J) = \frac{1}{2} \), \( \rho(T_{GS}) = \frac{1}{4} \). For \( \begin{pmatrix} 1 & 2 \\ 3 & 1 \end{pmatrix} \): \( \rho(T_J) = \sqrt 6 \), \( \rho(T_{GS}) = 6 \), both diverge.
The two hook matrices
| \( A \) | \( \rho(T_J) \) | \( \rho(T_{GS}) \) | Verdict |
|---|---|---|---|
| \( \begin{pmatrix} 1 & 2 & -2 \\ 1 & 1 & 1 \\ 2 & 2 & 1 \end{pmatrix} \) | 0 (\( T_J^3 = 0 \)) | 2 | Jacobi converges (in 3 steps), GS diverges |
| \( \begin{pmatrix} 2 & -1 & 1 \\ 2 & 2 & 2 \\ -1 & -1 & 2 \end{pmatrix} \) | \( \frac{\sqrt 5}{2} \approx 1.118 \) | \( \frac{1}{2} \) | Jacobi diverges, GS converges |
For the first matrix, \( T_{GS} = \begin{pmatrix} 0 & -2 & 2 \\ 0 & 2 & -3 \\ 0 & 0 & 2 \end{pmatrix} \) is upper triangular with eigenvalues \( 0, 2, 2 \). For the second, \( T_{GS} = \begin{pmatrix} 0 & \frac{1}{2} & -\frac{1}{2} \\ 0 & -\frac{1}{2} & -\frac{1}{2} \\ 0 & 0 & -\frac{1}{2} \end{pmatrix} \) with eigenvalues \( 0, -\frac{1}{2}, -\frac{1}{2} \).
Direct vs Iterative
| Gauss elimination | Jacobi / Gauss-Seidel | |
|---|---|---|
| Result | exact in exact arithmetic, after a fixed number of steps | approximate; stop when a tolerance is met |
| Cost | about \( \frac{n^3}{3} \) | about \( n^2 \) per sweep (less for sparse \( A \)) |
| Works for | any non-singular \( A \) (with pivoting) | only if \( \rho(T) < 1 \) |
| Fill-in | zeros of a sparse \( A \) can fill in | keeps \( A \) untouched; ideal for large sparse systems |
| Rounding | errors accumulate; pivoting controls them | self-correcting: an error in one sweep is damped by later sweeps |
Memory Tricks
Don’t Confuse
| This | vs | That |
|---|---|---|
| \( L, U \) in the splitting \( A = L + D + U \) (strict parts of \( A \)) | \( L, U \) in the factorisation \( A = LU \) | |
| \( \rho(T) < 1 \): necessary and sufficient | diagonal dominance, \( \lVert T \rVert < 1 \): sufficient only | |
| Partial pivoting: row swaps, column max | complete pivoting: row and column swaps, submatrix max | |
| Ill-conditioned: large \( \kappa(A) \) | small determinant (scale-dependent, not a test) | |
| Doolittle: unit diagonal in \( L \) | Crout: unit diagonal in \( U \) | |
| Gauss elimination: triangular, then back substitution | Gauss-Jordan: diagonal (identity), no back substitution, more work |
Common Mistakes
Practice
All questions below are original practice questions written for this page. They are not from any CSIR NET paper. In Level 3, as in Part C, one or more options may be correct.
Level 1: Foundation
- Write the Jacobi and Gauss-Seidel iteration matrices in terms of the splitting \( A = L + D + U \).
- What is the leading term of the number of multiplications in Gauss elimination for an \( n \times n \) system?
- State the necessary and sufficient condition for \( x^{(k+1)} = Tx^{(k)} + c \) to converge for every \( x^{(0)} \).
Answers
- \( T_J = -D^{-1}(L + U) \), \( T_{GS} = -(D + L)^{-1}U \).
- \( \frac{n^3}{3} \).
- \( \rho(T) < 1 \).
Level 2: Part B Style
Practice Q1. For \( 4x + y = 6 \), \( 2x + 5y = 9 \), Gauss-Seidel from \( (0, 0) \) gives after two sweeps:
(a) \( (1.5, 1.2) \) (b) \( (1.2, 1.32) \) (c) \( (1.2, 1.2) \) (d) \( (1.125, 1.35) \)
Answer: (b)
Sweep 1: \( x = \frac{6 - 0}{4} = 1.5 \), \( y = \frac{9 - 2(1.5)}{5} = 1.2 \). Sweep 2: \( x = \frac{6 - 1.2}{4} = 1.2 \), \( y = \frac{9 - 2(1.2)}{5} = 1.32 \). (Exact solution \( \left(\frac{7}{6}, \frac{4}{3}\right) \approx (1.167, 1.333) \). Option (a) is the result after one sweep.)
Practice Q2. For \( A = \begin{pmatrix} 3 & 1 \\ 2 & 4 \end{pmatrix} \), the spectral radius of the Gauss-Seidel iteration matrix is
(a) \( \frac{1}{6} \) (b) \( \frac{1}{\sqrt 6} \) (c) \( \frac{1}{3} \) (d) \( \frac{2}{3} \)
Answer: (a)
For a 2 by 2 matrix, \( \rho(T_{GS}) = \left\lvert \frac{bc}{ad} \right\rvert = \frac{1 \cdot 2}{3 \cdot 4} = \frac{1}{6} \). Option (b) is \( \rho(T_J) = \sqrt{\frac{1}{6}} \).
Practice Q3. Gauss elimination without pivoting is applied to \( A = \begin{pmatrix} 2 & 1 & 1 \\ 4 & -6 & 0 \\ -2 & 7 & 2 \end{pmatrix} \). The multiplier \( m_{32} \) and the third pivot are
(a) \( -1 \) and 1 (b) 1 and \( -1 \) (c) \( -1 \) and 2 (d) \( 2 \) and 1
Answer: (a)
After step 1 (\( m_{21} = 2 \), \( m_{31} = -1 \)), rows 2 and 3 are \( (0, -8, -2) \) and \( (0, 8, 3) \). Then \( m_{32} = \frac{8}{-8} = -1 \), and row 3 becomes \( (0, 0, 3 - 2) = (0, 0, 1) \). Check: product of pivots \( 2 \times (-8) \times 1 = -16 = \det A \).
Practice Q4. Solving an \( n \times n \) dense system by Gauss elimination takes 2 seconds for \( n = 1000 \) on a certain computer. The expected time for \( n = 3000 \) on the same computer is about
(a) 6 s (b) 18 s (c) 54 s (d) 162 s
Answer: (c)
The cost grows like \( \frac{n^3}{3} \), so tripling \( n \) multiplies it by \( 3^3 = 27 \): \( 2 \times 27 = 54 \) s. (Back substitution, \( O(n^2) \), is negligible at this size.)
Level 3: Part C Style
Practice Q5. Let \( A = \begin{pmatrix} 4 & 1 & 0 \\ 1 & 4 & 1 \\ 0 & 1 & 4 \end{pmatrix} \) and \( b \in \mathbb{R}^3 \). Which statements are true?
(a) The Jacobi iteration for \( Ax = b \) converges for every starting vector. (b) \( \rho(T_J) = \frac{\sqrt 2}{4} \). (c) \( \rho(T_{GS}) = \frac{1}{8} \). (d) \( A \) has an LU factorisation with \( L \) unit lower triangular.
Answer: all four, (a), (b), (c) and (d)
- (a) True. \( A \) is strictly diagonally dominant by rows (\( 4 > 1 \), \( 4 > 2 \), \( 4 > 1 \)).
- (b) True. \( T_J = -\frac{1}{4}\begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \). The bracketed matrix has eigenvalues \( 0, \pm\sqrt 2 \), so \( \rho(T_J) = \frac{\sqrt 2}{4} \approx 0.354 \).
- (c) True. \( A \) is tridiagonal, so \( \rho(T_{GS}) = \rho(T_J)^2 = \frac{2}{16} = \frac{1}{8} \).
- (d) True. Leading principal minors are \( 4 \), \( 15 \), \( 4 \cdot 15 - 4 = 56 \), all non-zero (\( A \) is also symmetric positive definite, so Cholesky works too).
Practice Q6. Let \( A = \begin{pmatrix} 1 & 2 & -2 \\ 1 & 1 & 1 \\ 2 & 2 & 1 \end{pmatrix} \). Which statements are true?
(a) \( A \) is strictly diagonally dominant. (b) The Jacobi iteration matrix \( T_J \) satisfies \( T_J^3 = 0 \), so Jacobi reaches the exact solution in at most three sweeps from any start. (c) The Gauss-Seidel iteration converges for every starting vector. (d) \( \rho(T_{GS}) = 2 \).
Answer: (b) and (d)
- (a) False. Row 1: \( 1 < 2 + 2 \).
- (b) True. \( T_J = -\begin{pmatrix} 0 & 2 & -2 \\ 1 & 0 & 1 \\ 2 & 2 & 0 \end{pmatrix} \). Its characteristic polynomial is \( \lambda^3 \) (trace 0, sum of principal 2 by 2 minors \( -2 + 4 - 2 = 0 \), determinant 0), so by Cayley-Hamilton \( T_J^3 = 0 \). Since \( e^{(k)} = T_J^k e^{(0)} \), the error is zero from \( k = 3 \) on.
- (c) False and (d) True. \( T_{GS} = -(D + L)^{-1}U = \begin{pmatrix} 0 & -2 & 2 \\ 0 & 2 & -3 \\ 0 & 0 & 2 \end{pmatrix} \), upper triangular with eigenvalues \( 0, 2, 2 \). So \( \rho = 2 > 1 \) and Gauss-Seidel diverges for a generic start.
Practice Q7. A student solves \( x + y = 2 \), \( x + 1.0001y = 2.0001 \) and reports \( (1, 1) \). A second student, whose right-hand side was mistyped as \( 2.0002 \), reports \( (0, 2) \). Which statements are true?
(a) Both reported solutions are correct for the systems the students actually solved. (b) The system is ill-conditioned: \( \kappa_\infty(A) \) is of order \( 10^4 \). (c) Partial pivoting would have made the second student’s answer close to \( (1, 1) \). (d) The relative change in \( x \) is far larger than the relative change in \( b \), consistent with \( \frac{\lVert \delta x \rVert}{\lVert x \rVert} \le \kappa(A)\frac{\lVert \delta b \rVert}{\lVert b \rVert} \).
Answer: (a), (b) and (d)
- (a) True. Substitute: \( 1 + 1 = 2 \), \( 1 + 1.0001 = 2.0001 \); and \( 0 + 2 = 2 \), \( 0 + 2.0002 = 2.0002 \).
- (b) True. \( A^{-1} = \frac{1}{0.0001}\begin{pmatrix} 1.0001 & -1 \\ -1 & 1 \end{pmatrix} \), so \( \lVert A^{-1} \rVert_\infty = 20001 \), \( \lVert A \rVert_\infty = 2.0001 \), \( \kappa_\infty \approx 4.0 \times 10^4 \).
- (c) False. The sensitivity belongs to the problem, not the algorithm. Pivoting controls rounding growth; it cannot change the exact solution \( (0, 2) \) of the mistyped system.
- (d) True. \( \frac{\lVert \delta b \rVert_\infty}{\lVert b \rVert_\infty} = \frac{0.0001}{2.0001} \approx 5 \times 10^{-5} \) while \( \frac{\lVert \delta x \rVert_\infty}{\lVert x \rVert_\infty} = 1 \): an amplification of about \( 2 \times 10^4 \), within the bound \( \kappa_\infty \approx 4 \times 10^4 \).
Quick Revision Table
| Idea | Fact |
|---|---|
| Gauss elimination | multipliers \( m_{ik} = \frac{a_{ik}}{a_{kk}} \); cost \( \frac{n^3}{3} \); \( \det A = \) product of pivots \( \times (-1)^{\text{swaps}} \) |
| Partial pivoting | largest \( \lvert a_{ik} \rvert \) in the column; \( \lvert m_{ik} \rvert \le 1 \) |
| LU | exists (unit \( L \)) and unique if all leading principal minors \( \ne 0 \); else \( PA = LU \) |
| Cholesky | SPD \( A = LL^T \) |
| Jacobi | \( T_J = -D^{-1}(L + U) \) |
| Gauss-Seidel | \( T_{GS} = -(D + L)^{-1}U \) |
| Convergence | iff \( \rho(T) < 1 \); rate \( \rho(T) \) |
| Diagonally dominant | both converge |
| SPD | Gauss-Seidel converges |
| Tridiagonal, 2 by 2 | \( \rho(T_{GS}) = \rho(T_J)^2 \) |
| Condition number | \( \kappa = \lVert A \rVert \lVert A^{-1} \rVert \); \( \frac{\lVert \delta x \rVert}{\lVert x \rVert} \le \kappa \frac{\lVert \delta b \rVert}{\lVert b \rVert} \) |
Key Takeaways
What’s Next
- Finite Differences and Interpolation: cubic splines lead to a tridiagonal, diagonally dominant system, solved by exactly the methods above.
- Iteration, Newton-Raphson and Rate of Convergence: the scalar version of “contraction implies convergence”.
- Numerical Analysis: Quick Revision.