Jacobi and Gauss-Seidel Methods — Mathematics Knowledge System

Overview

The Jacobi and Gauss-Seidel methods are iterative alternatives to Gaussian elimination for solving Ax = b: instead of directly triangularizing the matrix, they start from a guess and repeatedly refine it until the residual is negligibly small. Both methods split A = D − L − U into its diagonal part D and its below-diagonal (−L) and above-diagonal (−U) parts, then solve each equation i for xᵢ in terms of the other current variables. Jacobi updates every component simultaneously using only values from the previous iteration, while Gauss-Seidel immediately reuses freshly updated components within the same sweep, which typically makes it converge roughly twice as fast. Both methods are only guaranteed to converge under conditions such as strict diagonal dominance of A, but when applicable — as with the large, sparse matrices that arise from discretizing partial differential equations — they are far cheaper per iteration than direct elimination, since each sweep costs only O(n²) (or O(n) for sparse systems) rather than the O(n³) of full elimination.

Intuition

Imagine three people around a table, each responsible for one unknown, each holding their own equation. In Jacobi's method, everyone looks at everyone else's current guess, computes their own new best guess in their head, and then — on a synchronized signal — everyone updates simultaneously; nobody sees anyone else's update until the next round. In Gauss-Seidel, the first person updates and immediately announces the new value out loud, so the second person's calculation already uses that fresher number, and the third person benefits from both updated neighbors. Because Gauss-Seidel always works with the freshest information available, it typically 'catches up' to the true answer in about half as many rounds as Jacobi needs.

Formal Definition

Definition

Writing A = D − L − U (D diagonal, L strictly lower, U strictly upper, with signs chosen so L and U are nonnegative when A has that structure), the Jacobi update solves each row for xᵢ using only the previous iterate x^(k), while Gauss-Seidel substitutes already-updated components immediately:

x_i^{(k+1)} = \dfrac{1}{a_{ii}}\left(b_i - \sum_{j \ne i} a_{ij}\,x_j^{(k)}\right) \quad \text{(Jacobi)}

Jacobi update — uses only iteration k values

x_i^{(k+1)} = \dfrac{1}{a_{ii}}\left(b_i - \sum_{j < i} a_{ij}\,x_j^{(k+1)} - \sum_{j > i} a_{ij}\,x_j^{(k)}\right) \quad \text{(Gauss-Seidel)}

Gauss-Seidel update — reuses already-updated components

x^{(k+1)} = T x^{(k)} + c, \qquad \text{converges iff } \rho(T) < 1

Matrix form and convergence criterion (spectral radius of iteration matrix T)

Worked Examples

Solve each equation for its own variable using only the previous iterate (all zero initially).
$x^{(1)} = \tfrac{12-0-0}{10} = 1.2,\quad y^{(1)} = \tfrac{13-0-0}{10} = 1.3,\quad z^{(1)} = \tfrac{14-0-0}{10} = 1.4$
Second iteration: use only x⁽¹⁾, y⁽¹⁾, z⁽¹⁾ (all from the same previous sweep) on the right-hand side.
$x^{(2)} = \tfrac{12 - 1.3 - 1.4}{10} = 0.93$
Compute y⁽²⁾ and z⁽²⁾ the same way, using only iteration-1 values.
$y^{(2)} = \tfrac{13 - 2(1.2) - 1.4}{10} = 0.92,\qquad z^{(2)} = \tfrac{14 - 2(1.2) - 2(1.3)}{10} = 0.90$

Answer: x⁽¹⁾=(1.2, 1.3, 1.4); x⁽²⁾=(0.93, 0.92, 0.90) — approaching the true solution (1, 1, 1).

Practice Problems

Difficulty 4/10

For the system 10x+y+z=12, 2x+10y+z=13, 2x+2y+10z=14, compute the Jacobi first iterate x⁽¹⁾ starting from x⁽⁰⁾=(0,0,0) (just the x-component).

Difficulty 5/10

Using Gauss-Seidel on the same system with x⁽⁰⁾=(0,0,0), compute y⁽¹⁾ (after x⁽¹⁾=1.2 has already been updated in this sweep).

Difficulty 7/10

A large sparse system from discretizing a 2D heat-conduction PDE has a diagonally dominant coefficient matrix with millions of unknowns. Why would an engineer prefer Jacobi or Gauss-Seidel iteration over Gaussian elimination here?

Quiz

Summary

Jacobi and Gauss-Seidel are iterative methods for Ax=b that repeatedly solve each equation for its own variable using current estimates of the others.
Jacobi uses only the previous full iterate; Gauss-Seidel immediately reuses updated components, so it typically converges roughly twice as fast, e.g. reaching (0.999, 1.005, 0.999) vs (0.93, 0.92, 0.90) after 2 sweeps on the same system.
Convergence is guaranteed when A is strictly diagonally dominant (sufficient condition), formally when the iteration matrix's spectral radius ρ(T) < 1.
Each sweep costs O(n) to O(n²) rather than the O(n³) of Gaussian elimination, making these methods the practical choice for the large, sparse matrices arising from PDE discretization.

References

WebsiteWikipedia — Jacobi method
WebsiteWikipedia — Gauss-Seidel method
BookBurden, R. L. & Faires, J. D. Numerical Analysis, 10th ed. Cengage, 2015.