Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 37 ยท Linear Systems

Jacobi and Gauss-Seidel Methods

Solve large linear systems iteratively with the Jacobi, Gauss-Seidel and SOR methods: update formulas, diagonal dominance, spectral radius, convergence tests and runnable code.

Gaussian elimination costs O(nยณ) and, worse, it fills in zeros: a sparse matrix with a million rows and only five non-zeros per row may have a dense factorisation that does not fit in memory. For such problems (common in simulations of heat, fluids and electric fields) we use iterative methods. They start from a guess for x and improve it repeatedly, touching only the non-zero entries of A at each pass.

This lesson covers the two classic stationary iterations, Jacobi and Gauss-Seidel, and the accelerated SOR variant. They are simple, they illustrate every convergence idea of this chapter, and they are the ancestors of modern multigrid and Krylov solvers.

The Jacobi method

Split each equation to isolate its diagonal unknown. Equation i reads sum_j a_ij x_j = b_i, so

x_i = (b_i - sum over j โ‰  i of a_ij x_j) / a_ii

Jacobi computes a whole new vector from the old one:

x_i^(k+1) = (b_i - sum over j โ‰  i of a_ij x_j^(k)) / a_ii

Every component uses only values from the previous iteration, so all components can be updated in parallel.

Python The Jacobi method

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 exact solution is (1, 2, -1, 1). The method needs a few dozen sweeps here, and every sweep costs only one matrix-vector product.

The Gauss-Seidel method

Gauss-Seidel makes a small but powerful change: use the newest values as soon as they are available.

x_i^(k+1) = (b_i - sum over j < i of a_ij x_j^(k+1) - sum over j > i of a_ij x_j^(k)) / a_ii

Within one sweep, component i already sees the freshly computed components 1..i-1. It usually converges about twice as fast as Jacobi, and needs only one copy of x, but the updates are sequential.

Python Jacobi versus Gauss-Seidel

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.

Gauss-Seidel needs roughly half the iterations. Now the important question: when do these methods converge?

Convergence

Write A = D + L + U (diagonal, strictly lower, strictly upper parts). Each method has the form x^(k+1) = T x^(k) + c, where T is the iteration matrix:

  • Jacobi: T_J = -Dโปยน (L + U)
  • Gauss-Seidel: T_GS = -(D + L)โปยน U

The error satisfies e^(k+1) = T e^(k), so the method converges for every starting vector if and only if the spectral radius ฯ(T) (the largest absolute eigenvalue of T) is less than 1. The smaller ฯ(T), the faster the convergence: the error shrinks by about ฯ(T) per sweep.

Eigenvalues are not always easy to compute, so a simpler sufficient condition is used: if A is strictly diagonally dominant, meaning

|a_ii| > sum over j โ‰  i of |a_ij| for every row,

then both Jacobi and Gauss-Seidel converge. Symmetric positive definite matrices also guarantee Gauss-Seidel convergence.

Python Check dominance and spectral radius

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.

For the second matrix both radii exceed 1, so both iterations diverge. Sometimes reordering the equations turns a non-dominant matrix into a dominant one: swap rows before iterating.

Successive over-relaxation (SOR)

Gauss-Seidel can be sped up by overshooting. Compute the Gauss-Seidel value xฬƒ_i, then move further in the same direction using a relaxation factor ฯ‰:

x_i^(new) = (1 - ฯ‰) x_i^(old) + ฯ‰ xฬƒ_i

With ฯ‰ = 1 this is Gauss-Seidel; 1 < ฯ‰ < 2 is over-relaxation. For symmetric positive definite matrices SOR converges for all 0 < ฯ‰ < 2, and a well-chosen ฯ‰ can reduce the iteration count by an order of magnitude.

Python SOR and the best relaxation factor

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 iteration count falls sharply as ฯ‰ approaches about 1.8 and then rises again; for this matrix the optimum is near 2 / (1 + sin(ฯ€/(n+1))) โ‰ˆ 1.8. Finding the best ฯ‰ automatically is hard in general, which is one reason Krylov methods such as conjugate gradients (next lesson) are popular.

Which method when?

Method Per sweep Parallel? Typical speed
Jacobi one mat-vec yes slowest
Gauss-Seidel one mat-vec no (sequential) about 2x Jacobi
SOR one mat-vec no much faster with the right ฯ‰
Conjugate gradient one mat-vec plus a few dots yes fastest for SPD systems

Stop when the residual โ€–b - A xโ€– is small relative to โ€–bโ€–, not only when the step is small: a slowly converging iteration can take tiny steps while still far from the solution.

If an iteration misbehaves, print the residual norm at each sweep. A residual that falls geometrically is converging; one that grows tells you ฯ(T) > 1.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

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

    Jacobi uses only values from the previous sweep; Gauss-Seidel uses updated values as soon as they exist.
  2. 2. When is convergence guaranteed for Jacobi and Gauss-Seidel?

    Strict diagonal dominance gives spectral radius below 1 for both methods.
  3. 3. The method x_new = T x + c converges from every start if and only if

    The error evolves as e_new = T e, which decays iff all eigenvalues of T lie inside the unit circle.
  4. 4. What does the relaxation parameter omega do in SOR?

    x_new = (1 - omega) x_old + omega x_gs; omega = 1 is plain Gauss-Seidel.
  5. 5. Why prefer iterative methods for very large sparse systems?

    Matrix-vector products with a sparse matrix are cheap, while LU factors may become dense.

Summary

  • Iterative methods improve a guess repeatedly and suit large sparse systems.
  • Jacobi updates every component from the previous sweep; Gauss-Seidel uses new values immediately (about twice as fast); SOR adds over-relaxation with factor ฯ‰.
  • They converge from any start iff the spectral radius of the iteration matrix is below 1; strict diagonal dominance guarantees it.
  • Monitor the residual and stop on a relative residual tolerance.
  • Krylov methods like conjugate gradients usually beat these classics.

Next: Special Systems: Cholesky, Tridiagonal and Conjugate Gradient