Skip to content

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 read
  • Updated
On this page · 12 sections
  1. Prerequisites
  2. The Hook: Two Methods, Opposite Verdicts
  3. Direct Methods: Gauss Elimination
  4. Iterative Methods: Jacobi and Gauss-Seidel
  5. Direct vs Iterative
  6. Memory Tricks
  7. Don’t Confuse
  8. Common Mistakes
  9. Practice
  10. Quick Revision Table
  11. Key Takeaways
  12. What’s Next

Prerequisites

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] \).

  1. 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.
  2. Back substitution. The result is upper triangular \( Ux = c \); solve
$$x_n = \frac{c_n}{u_{nn}}, \qquad x_i = \frac{1}{u_{ii}}\Big(c_i - \sum_{j > i} u_{ij} x_j\Big), \quad i = n - 1, \dots, 1.$$

Operation counts

TaskMultiplications/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} \).

VariantNormalisationWhen
Doolittle\( L \) has unit diagonalthe form produced by Gauss elimination
Crout\( U \) has unit diagonalsame 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 permutationevery 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 \)JacobiGauss-Seidel
Strictly diagonally dominant by rows: \( \lvert a_{ii} \rvert > \sum_{j \ne i} \lvert a_{ij} \rvert \) for every \( i \)convergesconverges
Strictly diagonally dominant by columnsconvergesconverges
Symmetric positive definitenot guaranteed (converges iff \( 2D - A \) is also positive definite)converges
Tridiagonal with non-zero diagonalconverges 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 \))2Jacobi 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 eliminationJacobi / Gauss-Seidel
Resultexact in exact arithmetic, after a fixed number of stepsapproximate; stop when a tolerance is met
Costabout \( \frac{n^3}{3} \)about \( n^2 \) per sweep (less for sparse \( A \))
Works forany non-singular \( A \) (with pivoting)only if \( \rho(T) < 1 \)
Fill-inzeros of a sparse \( A \) can fill inkeeps \( A \) untouched; ideal for large sparse systems
Roundingerrors accumulate; pivoting controls themself-correcting: an error in one sweep is damped by later sweeps

Memory Tricks

Don’t Confuse

ThisvsThat
\( 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 sufficientdiagonal dominance, \( \lVert T \rVert < 1 \): sufficient only
Partial pivoting: row swaps, column maxcomplete 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 substitutionGauss-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

  1. Write the Jacobi and Gauss-Seidel iteration matrices in terms of the splitting \( A = L + D + U \).
  2. What is the leading term of the number of multiplications in Gauss elimination for an \( n \times n \) system?
  3. State the necessary and sufficient condition for \( x^{(k+1)} = Tx^{(k)} + c \) to converge for every \( x^{(0)} \).
Answers
  1. \( T_J = -D^{-1}(L + U) \), \( T_{GS} = -(D + L)^{-1}U \).
  2. \( \frac{n^3}{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

IdeaFact
Gauss eliminationmultipliers \( m_{ik} = \frac{a_{ik}}{a_{kk}} \); cost \( \frac{n^3}{3} \); \( \det A = \) product of pivots \( \times (-1)^{\text{swaps}} \)
Partial pivotinglargest \( \lvert a_{ik} \rvert \) in the column; \( \lvert m_{ik} \rvert \le 1 \)
LUexists (unit \( L \)) and unique if all leading principal minors \( \ne 0 \); else \( PA = LU \)
CholeskySPD \( A = LL^T \)
Jacobi\( T_J = -D^{-1}(L + U) \)
Gauss-Seidel\( T_{GS} = -(D + L)^{-1}U \)
Convergenceiff \( \rho(T) < 1 \); rate \( \rho(T) \)
Diagonally dominantboth converge
SPDGauss-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