Gauss–Seidel Iteration

See how using each freshly updated coordinate changes an iterative linear solve and its convergence.

Gauss–Seidel Iteration Theory

Concept Overview

The Gauss–Seidel method is an iterative technique for solving a square system of linear equations of the form Ax = b. Unlike the Jacobi method, which uses the values from the previous iteration to compute all updates for the current iteration, the Gauss–Seidel method uses the newly updated values as soon as they are available.

For a system with a matrix A = D - L - U, where D is diagonal, L is strictly lower triangular, and U is strictly upper triangular, the iteration is given by (D - L)x^(k+1) = Ux^(k) + b. This sequentially updates each component using the most recent information, generally leading to faster convergence than Jacobi when the method converges.

Worked Example

Consider the system defined by A = [[4, 2], [2, 3]] and b = [3, -1]. We start with an initial guess of [1, -1] and perform 2 sweeps. The exact solution to this system is [11/8, -5/4] (which is [1.375, -1.25]).

Sweep Calculation Steps:

Initial Guess: x⁽⁰⁾ = 1, y⁽⁰⁾ = -1
Sweep 1:
Update x: x⁽¹⁾ = (b₁ - c·y⁽⁰⁾) / 4 = (3 - 2(-1)) / 4 = 5/4
Update y: y⁽¹⁾ = (b₂ - c·x⁽¹⁾) / 3 = (-1 - 2(5/4)) / 3 = (-1 - 5/2) / 3 = -7/6
Result of Sweep 1: [5/4, -7/6]
Sweep 2:
Update x: x⁽²⁾ = (b₁ - c·y⁽¹⁾) / 4 = (3 - 2(-7/6)) / 4 = (3 + 7/3) / 4 = 16/12 = 4/3
Update y: y⁽²⁾ = (b₂ - c·x⁽²⁾) / 3 = (-1 - 2(4/3)) / 3 = (-1 - 8/3) / 3 = -11/9
Result of Sweep 2: [4/3, -11/9]

After 2 sweeps, the iterate is [4/3, -11/9]. The residual is computed as b - Ax = [3 - (4(4/3) + 2(-11/9)), -1 - (2(4/3) + 3(-11/9))]. This simplifies to [3 - (16/3 - 22/9), -1 - (8/3 - 33/9)] = [3 - 26/9, -1 + 1] = [1/9, 0]. The infinity norm of the residual is max(|1/9|, |0|) = 1/9.

The spectral radius of the iteration matrix is ρ = c² / 12 = 4 / 12 = 1/3. Since ρ < 1, the method converges for every starting point.

Interactive Experiment

You can try out this method yourself in the Gauss–Seidel Iteration module.

Change the Coupling c to see how the off-diagonal entries affect the spectral radius and convergence.
Adjust b1 and b2 to change the target vector b.
Modify the Initial x and Initial y to start the iteration from different points in the plane.
Increase the number of Sweeps to trace the sequence of iterates and observe how they approach the exact solution or diverge.

Limitations

The Gauss–Seidel method has several theoretical and practical limitations:

Convergence is not always guaranteed: It is guaranteed to converge for strictly diagonally dominant or symmetric positive-definite matrices. For other matrices, it may diverge if the spectral radius of the iteration matrix is > 1.
Sequential nature limits parallelization: Because each component's update depends on the already updated values of the previous components, it is much harder to parallelize effectively compared to the Jacobi method.
Slow convergence for some problems: Even when it converges, it may do so very slowly for large systems, necessitating acceleration techniques like Successive Over-Relaxation (SOR) or more advanced methods like Conjugate Gradient.

References

For further reading and a more formal treatment of classical iterative methods, you can review the following external resources. They cover the theoretical foundations distinguishing sequential updates like Gauss-Seidel from simultaneous ones like Jacobi.

Stanford MATH 114: Classical Iteration (Gauss-Seidel and Jacobi)

Gauss–Seidel Iteration