Iterative Methods for Linear Systems

Summary

Stationary iterative methods rewrite $A x = b$ as $x = T x + c$ and generate $x^{(k + 1)} = T x^{(k)} + c$ . Convergence hinges on the iteration matrix $T$ .

Prerequisites

Matrix norms and spectral radius
Numerical Methods/Linear Systems/Solving Linear Systems
Splitting intuition from Gauss-Jacobi Method and Gauss-Seidel Method

Problem Type

Approximate $x$ in $A x = b$ by a convergent sequence, especially for large sparse $A$ .

Method Definition

Split $A = M - N$ with $M$ easy to invert. Then

M x^{(k + 1)} = N x^{(k)} + b \Leftrightarrow x^{(k + 1)} = T x^{(k)} + c,

where $T = M^{- 1} N$ and $c = M^{- 1} b$ .^[1]

Common choices:

Method	$M$	Notes
Jacobi	$D = diag (A)$	Uses only $x^{(k)}$
Gauss–Seidel	$D + L$ (lower incl. diagonal)	Uses newest components
SOR	extrapolated Gauss–Seidel	Successive over-relaxation with parameter $ω$

Successive over-relaxation (SOR) (not “seasonal relaxation”):

x_{i}^{(k + 1)} = (1 - ω) x_{i}^{(k)} + \frac{ω}{a_{i i}} (b_{i} - \sum_{j < i} a_{i j} x_{j}^{(k + 1)} - \sum_{j > i} a_{i j} x_{j}^{(k)}) .

For $ω = 1$ this is Gauss–Seidel; typically $0 < ω < 2$ .

Assumptions / Requirements

$a_{i i} \neq 0$ for Jacobi/GS/SOR component updates
Convergence requires $ρ (T) < 1$ (necessary and sufficient for stationary iterations)
$∥ T ∥ < 1$ for some matrix norm is a convenient sufficient condition

Convergence

$ρ (T) < 1$ $\Leftrightarrow$ $x^{(k)} \to x^{*}$ for every start
Strict diagonal dominance of $A$ is a sufficient condition for Jacobi and Gauss–Seidel
SPD structure helps conjugate-gradient type methods (nonstationary; mentioned only for orientation)

Error / Accuracy

Stop when $∥ x^{(k + 1)} - x^{(k)} ∥ < ε$ and/or residual $∥ b - A x^{(k)} ∥ < ε$ .

Worked Example (fixed-point form)

A = (\begin{matrix} 4 & - 1 \\ - 1 & 3 \end{matrix}), b = (\begin{matrix} 2 \\ 5 \end{matrix})

Jacobi updates:

x_{1}^{(k + 1)} = \frac{1}{4} (2 + x_{2}^{(k)}), x_{2}^{(k + 1)} = \frac{1}{3} (5 + x_{1}^{(k)})

T_{J} = (\begin{matrix} 0 & 1 / 4 \\ 1 / 3 & 0 \end{matrix}), c = (\begin{matrix} 1 / 2 \\ 5 / 3 \end{matrix}) .

Gauss–Seidel uses the new $x_{1}^{(k + 1)}$ immediately in the second equation:

x_{2}^{(k + 1)} = \frac{1}{3} (5 + x_{1}^{(k + 1)}) .

Its iteration matrix is not $T_{J}$ ; do not reuse the Jacobi matrix when claiming Seidel convergence rates.

Common Failure Modes

Using Jacobi’s $T$ to conclude Gauss–Seidel convergence without recomputing $T_{G S}$
$ω \notin (0, 2)$ for SOR
Ignoring that $ρ (T) < 1$ is the sharp criterion, while diagonal dominance is only sufficient

Connections

References

Y. Saad, Iterative Methods for Sparse Linear Systems; also Burden & Faires; NIST DLMF Ch. 3, https://dlmf.nist.gov/3 ↩︎