Gauss–Seidel Method

Summary

Gauss–Seidel is the in-place sibling of Jacobi: each new component is used immediately in later equations of the same sweep. It often converges faster than Jacobi on the same matrix, but its iteration matrix differs.

Prerequisites

• Gauss-Jacobi Method
• Iterative Methods

Problem Type

Iteratively solve $Ax=b$ with $a_{ii}\ne 0$ .

Method Definition

With $A=D+L+U$ (standard splitting),

componentwise

Iteration matrix: $T_{GS}=-(D+L{)}^{-1}U$ .^[1]

Assumptions / Requirements

• Nonzero diagonals
• Do not use $T_J=D^{-1}(L+U)$ when analyzing Gauss–Seidel

Algorithm

1. Start from $x^{(0)}$ .
2. For $i=1,\dots ,n$ , overwrite $x_i$ with the formula above.
3. After a full sweep, test $\parallel x^{(k+1)}-x^{(k)}\parallel$ and/or residual.

Convergence

• $\rho (T_{GS})<1$ is necessary and sufficient for convergence of this stationary iteration
• Strict diagonal dominance of $A$ is a sufficient condition
• Sassenfeld criterion (useful hand test for GS): define

If $\underset{i}{max}{\beta }_i<1$ , Gauss–Seidel converges.

Error / Accuracy

Same practical stops as Jacobi: step size and residual norms.

Worked Example

Sassenfeld:

$max{\beta }_i=0.5<1$ ⇒ Gauss–Seidel converges.

For comparison only, Jacobi’s $T_J=-D^{-1}(L+U)$ has

so Jacobi also converges here—but that bound is about Jacobi, not a substitute for $T_{GS}$ .

One GS sweep from $x^{(0)}=0$ :

Common Failure Modes

• Analyzing GS with Jacobi’s iteration matrix alone
• Zero pivots on the diagonal
• Confusing SOR ( $\omega \ne 1$ ) with plain GS

Connections

• Iterative Methods (includes SOR)
• Gauss-Jacobi Method
• Numerical Methods/Linear Systems/Solving Linear Systems

References