Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 62 ยท Linear Systems

Iterative Solvers: Jacobi, Gauss-Seidel and Conjugate Gradient

Solve large linear systems without factoring: implement Jacobi, Gauss-Seidel and conjugate gradient, learn the convergence tests and compare speeds in Python.

Gaussian elimination and LU decomposition solve A*x = b exactly (up to rounding) in about n**3 steps. For a 1,000-by-1,000 matrix that is fine. But simulations of heat flow, structures, electrical networks and images produce systems with millions of unknowns, in which each equation touches only a handful of neighbors: the matrix is sparse. Elimination destroys that sparsity (it creates "fill-in") and needs far too much memory and time.

Iterative solvers take another approach. Start with a guess, improve it with a cheap rule, and repeat until the error is small. Each step only needs matrix-vector products, which for a sparse matrix are very fast. This lesson implements the three classic methods: Jacobi, Gauss-Seidel and conjugate gradient, explains when they converge, and compares their speed. It builds on matrix-vector views, eigenvalues and numerical linear algebra. In SciPy these solvers are available as sparse routines, see sparse linear algebra; here we build them from scratch to see how they work.

Splitting the matrix

Write A = D + L + U where D holds the diagonal of A, L the strictly lower part and U the strictly upper part (these L and U are not the LU factors). The equation A*x = b becomes D*x = b - (L + U)*x.

Jacobi's method turns this into an update. In component form, with all old values on the right-hand side:

x_i(new) = ( b_i - sum over j != i of a_ij * x_j(old) ) / a_ii

Each equation is solved for its own unknown, pretending the others are right. All components can be updated at the same time, which makes Jacobi ideal for parallel hardware.

Gauss-Seidel has one small change: use the newest values as soon as they exist. When computing x_i(new), the values x_1(new), ..., x_(i-1)(new) are already available, so use them. It usually converges about twice as fast as Jacobi and needs only one copy of x.

Both are special cases of the fixed-point iteration x_(k+1) = M*x_k + c. For Jacobi M = -D**(-1)*(L + U); for Gauss-Seidel M = -(D + L)**(-1)*U.

Python Jacobi and Gauss-Seidel from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When do they converge?

Subtract the fixed point from the iteration and the error evolves as e_(k+1) = M @ e_k, so e_k = M**k @ e_0. The error goes to zero for every starting guess if and only if the spectral radius rho(M) (the largest eigenvalue magnitude) is below 1. The smaller rho(M), the faster the convergence: the error shrinks by about a factor rho(M) each step.

A simple, checkable sufficient condition: if A is strictly diagonally dominant, meaning |a_ii| > sum of |a_ij| over j != i in every row, then both Jacobi and Gauss-Seidel converge. Physically the diagonal term (each unknown's own coefficient) outweighs the neighbors' influence, so each update is a contraction. For symmetric positive definite matrices Gauss-Seidel converges as well.

Row order can matter. Take the system x + 2y = 5, 3x + y = 5 (solution x = 1, y = 2). In this order the matrix [[1, 2], [3, 1]] is not diagonally dominant, and Jacobi diverges (rho = sqrt(6)). Swap the equations to 3x + y = 5, x + 2y = 5 and the matrix becomes dominant and the iteration converges.

Python Spectral radius decides convergence

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The step-by-step error ratios in the last block alternate between 0.373 and 0.447. Their geometric mean, about 0.408, is the spectral radius of the Jacobi matrix for that system, which is what the long-run rate settles to.

Conjugate gradient

Jacobi and Gauss-Seidel are slow on the kinds of matrices that arise from physical grids: their spectral radius creeps toward 1 as the grid gets finer. For symmetric positive definite (SPD) matrices there is a far better method, conjugate gradient (CG).

Solving A*x = b with SPD A is equivalent to minimizing the bowl-shaped function f(x) = (1/2)*x^T*A*x - b^T*x, because its gradient is A*x - b. The plain "steepest descent" method walks downhill along the gradient and zigzags badly in long narrow valleys. CG fixes this by choosing search directions p_k that are A-conjugate (p_i^T A p_j = 0 for i != j), so progress made along one direction is never undone by the next. In exact arithmetic it reaches the exact solution in at most n steps, and in practice it gets an excellent answer far sooner.

The algorithm needs one matrix-vector product per step and a few vector operations:

  1. r = b - A x, p = r
  2. repeat: alpha = (r.r) / (p.A p), x += alpha p, r_new = r - alpha A p, beta = (r_new.r_new)/(r.r), p = r_new + beta p

The error shrinks like ((sqrt(kappa) - 1)/(sqrt(kappa) + 1))**k where kappa is the condition number. The square root is the key: CG is much more forgiving of ill-conditioning than Jacobi, whose rate depends on kappa directly. A preconditioner, an approximate inverse of A, lowers kappa further.

flowchart LR
    A["SPD system A x = b"] --> B["minimize f(x) =<br/>x^T A x / 2 - b^T x"]
    B --> C["A-conjugate<br/>search directions"]
    C --> D["one matvec per step"]
    D --> E["converges in at most n steps,<br/>usually far fewer"]

CG minimizes a quadratic bowl with directions that never undo each other's progress.

Python Compare Jacobi, Gauss-Seidel and CG on a 1-D grid

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In a run, CG finishes in 30 steps (at most n = 60), while Jacobi needs about 17,000 and Gauss-Seidel about 8,800: half as many as Jacobi, as promised. On a finer grid the gap grows dramatically: a grid with 10 times as many points makes Jacobi about 100 times slower and CG only about 10 times slower.

Choosing a method

Situation Choice
Small or medium dense system direct: np.linalg.solve or LU
Large sparse, SPD (heat, elasticity, Poisson) conjugate gradient, with a preconditioner
Large sparse, non-symmetric GMRES or BiCGSTAB
Quick prototype, strongly diagonally dominant Jacobi or Gauss-Seidel
Parallel hardware, smoothing inside multigrid Jacobi (and its variants)

Jacobi and Gauss-Seidel are rarely the final solver today, but they are used as smoothers inside multigrid methods, and they teach the idea behind all iterative solvers: reduce the residual r = b - A*x cheaply, many times.

Common mistakes

  • Using CG on a matrix that is not symmetric positive definite. It may stagnate or give nonsense; use GMRES or BiCGSTAB instead.
  • Applying Jacobi or Gauss-Seidel without checking convergence conditions (diagonal dominance or rho(M) < 1).
  • Stopping on the change between iterates alone. A slowly converging method can have small steps while still far from the answer; check the residual norm(b - A x) relative to norm(b).
  • Forming the explicit inverse. Iterative methods exist so that you only ever multiply by A.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the main difference between Jacobi and Gauss-Seidel?

    Jacobi uses only values from the previous iteration; Gauss-Seidel uses the already-updated components, which usually speeds convergence.
  2. 2. Which condition guarantees that Jacobi and Gauss-Seidel converge for every starting guess?

    The error evolves as M^k e_0, which vanishes for every e_0 exactly when rho(M) < 1. Strict diagonal dominance is a convenient sufficient condition.
  3. 3. For which matrices is the conjugate gradient method designed?

    CG minimizes the quadratic x^T A x / 2 - b^T x, which has a unique bowl-shaped minimum only when A is symmetric positive definite.
  4. 4. Why are iterative solvers preferred for huge sparse systems?

    Each step multiplies by the sparse matrix, which costs little time and memory; factorizations destroy sparsity.

Summary

  • Iterative methods improve a guess with cheap steps (matrix-vector products), ideal for large sparse systems.
  • Jacobi solves each equation for its own unknown using old values; Gauss-Seidel uses new values immediately and typically needs about half the iterations.
  • Convergence holds for any start iff the spectral radius of the iteration matrix is below 1; strict diagonal dominance is a quick sufficient test.
  • Conjugate gradient solves SPD systems using A-conjugate directions, in at most n steps in exact arithmetic and far fewer in practice; its rate depends on sqrt(kappa).
  • Judge convergence by the relative residual, and precondition hard problems.

Next: widen your view from matrices to higher-dimensional arrays in Tensors, Kronecker Products and Einsum.