Iterative methods — Jacobi, Gauss-Seidel, convergence: Exercises

Throughout, $A x = b$ is the system, $x^{(k)}$ the $k$ -th guess, $x^{(0)} = 0$ unless stated. We use the splitting $A = D - L - U$ from the parent note ( $D$ = diagonal, $- L$ = strictly-lower part, $- U$ = strictly-upper part).

L1 · Recognition

Exercise 1.1 — Read off $D$ , $L$ , $U$

Given $A = 510 - 2 4 - 3 0 - 1 6,$ write down $D$ , $L$ , and $U$ so that $A = D - L - U$ (remember $- L$ is the strictly-lower part).

Recall Solution 1.1

WHAT we do: copy the diagonal into $D$ , the below-diagonal entries (negated) into $L$ , the above-diagonal entries (negated) into $U$ . $D = 500040006 .$ Below-diagonal entries of $A$ are $a_{21} = 1, a_{32} = - 3$ . Since $A$ 's strictly-lower part is $- L$ , we set $L = - 010 00 - 3 000 = 0 - 1 0 003000$ . Above-diagonal entries are $a_{12} = - 2, a_{23} = - 1$ , so $U = - 000 - 2 00 0 - 1 0 = 000200010$ . Check: $D - L - U = 510 - 2 4 - 3 0 - 1 6 = A .$ ✓

Exercise 1.2 — Is it strictly diagonally dominant?

For the same $A$ , decide whether it is strictly diagonally dominant (SDD): $∣ a_{ii} ∣ > \sum_{j \neq = i} ∣ a_{ij} ∣$ in every row.

Recall Solution 1.2

Row 1: $∣5∣ > ∣ - 2∣ + ∣0∣ = 2$ ✓
Row 2: $∣4∣ > ∣1∣ + ∣ - 1∣ = 2$ ✓
Row 3: $∣6∣ > ∣0∣ + ∣ - 3∣ = 3$ ✓ All rows pass, so $A$ is SDD. By the parent's sufficient condition, both Jacobi and Gauss-Seidel converge for any start.

Exercise 1.3 — Match method to iteration matrix

State which method has iteration matrix $T_{J} = D^{- 1} (L + U)$ and which has $T_{GS} = (D - L)^{- 1} U$ , and say in one sentence what physical difference the formulas encode.

Recall Solution 1.3

$T_{J} = D^{- 1} (L + U)$ is Jacobi; $T_{GS} = (D - L)^{- 1} U$ is Gauss-Seidel. Difference: Jacobi inverts only $D$ (all old values used together); Gauss-Seidel inverts the whole lower-triangular $D - L$ , i.e. it absorbs the just-updated components into the same sweep.

L2 · Application

Exercise 2.1 — Two Jacobi sweeps

Solve ${10 x + 2 y = 12 x + 5 y = 6$ by Jacobi, starting from $(0, 0)$ . Report $x^{(1)}$ and $x^{(2)}$ to 4 decimals. (Exact solution is $(1, 1)$ .)

Recall Solution 2.1

Jacobi rearranges each row for its own variable using only old values: $x = \frac{12 - 2 y}{10}, y = \frac{6 - x}{5} .$

$k = 1$ (from $(0, 0)$ ): $x = \frac{12 - 0}{10} = 1.2000$ , $y = \frac{6 - 0}{5} = 1.2000$ . So $x^{(1)} = (1.2000, 1.2000)$ .
$k = 2$ (from $(1.2, 1.2)$ ): $x = \frac{12 - 2 ( 1.2 )}{10} = \frac{9.6}{10} = 0.9600$ , $y = \frac{6 - 1.2}{5} = \frac{4.8}{5} = 0.9600$ . So $x^{(2)} = (0.9600, 0.9600)$ . Already bracketing $(1, 1)$ .

Exercise 2.2 — Two Gauss-Seidel sweeps (same system)

Repeat Exercise 2.1 with Gauss-Seidel. Report $x^{(1)}$ and $x^{(2)}$ .

Recall Solution 2.2

Gauss-Seidel uses the fresh $x$ inside the $y$ -equation: $x = \frac{12 - 2 y _{old}}{10}, y = \frac{6 - x _{new}}{5} .$

$k = 1$ : $x = \frac{12 - 0}{10} = 1.2000$ ; then $y = \frac{6 - 1.2}{5} = 0.9600$ . So $x^{(1)} = (1.2000, 0.9600)$ .
$k = 2$ : $x = \frac{12 - 2 ( 0.96 )}{10} = \frac{10.08}{10} = 1.0080$ ; then $y = \frac{6 - 1.008}{5} = 0.9984$ . So $x^{(2)} = (1.0080, 0.9984)$ . Compare with Jacobi's $(0.9600, 0.9600)$ : Gauss-Seidel is already within $0.008$ of the answer — visibly faster.

Exercise 2.3 — Compute a residual and decide to stop

Using the Gauss-Seidel iterate $x^{(2)} = (1.008, 0.9984)$ , compute the residual $r = b - A x^{(2)}$ and its max-norm $∥ r ∥_{\infty} = max_{i} ∣ r_{i} ∣$ . With tolerance $ε = 0.05$ , do we stop?

Recall Solution 2.3

$A x^{(2)} = (10 (1.008) + 2 (0.9984) 1.008 + 5 (0.9984)) = (12.0768 6.0) .$ $r = b - A x^{(2)} = (126) - (12.0768 6.0) = (- 0.0768 0) .$ Recall $∥ r ∥_{\infty}$ = biggest absolute component = $max (∣ - 0.0768∣, ∣0∣) = 0.0768$ . Since $0.0768 > 0.05$ , we do not stop yet — one more sweep is needed.

L3 · Analysis

Exercise 3.1 — Predict convergence by eigenvalues

For $A = (3113)$ build $T_{J}$ , find its eigenvalues and $ρ (T_{J})$ , and state whether Jacobi converges and roughly how fast.

Recall Solution 3.1

$D = 3 I$ , $L + U = (0 - 1 - 1 0)$ (off-diagonal entries of $A$ , since $A = D - L - U$ ). $T_{J} = D^{- 1} (L + U) = \frac{1}{3} (0 - 1 - 1 0) = (0 - \frac{1}{3} - \frac{1}{3} 0) .$ Why these eigenvalues (show the characteristic polynomial): for a $2 \times 2$ matrix $T_{J} - λ I = (- λ - \frac{1}{3} - \frac{1}{3} - λ)$ , set $det = 0$ : $det = (- λ) (- λ) - (- \frac{1}{3}) (- \frac{1}{3}) = λ^{2} - \frac{1}{9} = 0 \Rightarrow λ = \pm \frac{1}{3} .$ So $ρ (T_{J}) = \frac{1}{3} < 1$ ⇒ converges, and the error shrinks by a factor $\approx \frac{1}{3}$ each sweep. Rate as digits per sweep: one decimal digit means dividing the error by $10$ ; each sweep multiplies by $\frac{1}{3}$ , so we need $m$ sweeps with $(\frac{1}{3})^{m} \leq \frac{1}{10}$ , i.e. $m \geq \frac{lo g _{10} 10}{lo g _{10} 3} = \frac{1}{lo g _{10} 3} \approx \frac{1}{0.477} \approx 2.1$ sweeps per digit.

Exercise 3.2 — A borderline non-SDD matrix

$A = (1 \frac{1}{2} \frac{1}{2} 1)$ . First test SDD, then compute $ρ (T_{J})$ and decide whether Jacobi converges. Finally, give a genuinely non-SDD companion matrix that still converges, to see that SDD is only sufficient.

Recall Solution 3.2

SDD test on the given $A$ : Row 1: $∣1∣ > ∣ \frac{1}{2} ∣$ ✓; Row 2: $∣1∣ > ∣ \frac{1}{2} ∣$ ✓. So this $A$ is strictly diagonally dominant (barely, but strictly), and convergence is already guaranteed by the sufficient condition. Compute $ρ (T_{J})$ for the given $A$ : $D = I$ , so $T_{J} = D^{- 1} (L + U) = (0 - \frac{1}{2} - \frac{1}{2} 0)$ (the off-diagonal entries, negated per $A = D - L - U$ ). Characteristic polynomial: $T_{J} - λ I = (- λ - \frac{1}{2} - \frac{1}{2} - λ)$ , so $det = λ^{2} - (- \frac{1}{2}) (- \frac{1}{2}) = λ^{2} - \frac{1}{4} = 0 \Rightarrow λ = \pm \frac{1}{2} .$ Hence $ρ (T_{J}) = \frac{1}{2} < 1$ ⇒ Jacobi converges (error roughly halves per sweep), consistent with the SDD guarantee. Now the "sufficient not necessary" point. Take the genuinely non-SDD companion $B = (1 \frac{1}{4} 11)$ : Row 1 gives $∣1∣ \neq > ∣1∣$ , so $B$ is not SDD. Its Jacobi matrix is $T_{J}^{B} = (0 - \frac{1}{4} - 1 0)$ , with $T_{J}^{B} - λ I = (- λ - \frac{1}{4} - 1 - λ)$ and $det = λ^{2} - (- 1) (- \frac{1}{4}) = λ^{2} - \frac{1}{4} = 0 \Rightarrow λ = \pm \frac{1}{2},$ so $ρ (T_{J}^{B}) = \frac{1}{2} < 1$ — converges even though SDD failed. That is the whole lesson of L3.

Exercise 3.3 — Forecast-then-verify a divergence

$A = (1231)$ . Forecast from diagonal dominance, then compute $ρ (T_{J})$ to confirm, and give a one-row-swap fix.

Recall Solution 3.3

Forecast: Row 1: $∣1∣ < ∣3∣$ — badly non-dominant, likely diverges. $T_{J} = (0 - 2 - 3 0)$ (since $a_{11} = a_{22} = 1$ ). Why these eigenvalues: $T_{J} - λ I = (- λ - 2 - 3 - λ)$ , so $det = λ^{2} - (- 3) (- 2) = λ^{2} - 6 = 0 \Rightarrow λ = \pm 6 \approx \pm 2.449.$ Hence $ρ = 6 > 1$ ⇒ diverges. ✓ Fix: swap the two rows to get $(2113)$ , which is SDD ( $2 > 1$ , $3 > 1$ ) — now it converges.

The three L3 cases live on one picture. The teal and orange curves ( $ρ = \frac{1}{3}$ and $ρ = \frac{1}{2}$ ) collapse toward zero — that is convergence — while the plum curve ( $ρ = 6$ ) rockets upward off the plot: divergence. The dashed line marks error $= 1$ ; a method converges exactly when its bounding curve dives below and stays below it. This is the visual meaning of " $ρ < 1$ ."

Figure — Iterative methods — Jacobi, Gauss-Seidel, convergence

L4 · Synthesis

Exercise 4.1 — Compare Jacobi vs Gauss-Seidel spectral radii

For $A = (2 - 1 - 1 2)$ compute both $ρ (T_{J})$ and $ρ (T_{GS})$ , and verify the model-problem relation $ρ (T_{GS}) = ρ (T_{J})^{2}$ .

Recall Solution 4.1

$D = 2 I$ , $L = (0100)$ , $U = (0010)$ . Jacobi: $T_{J} = \frac{1}{2} (0110)$ . Why its eigenvalues: $T_{J} - λ I = (- λ \frac{1}{2} \frac{1}{2} - λ)$ , so $det = λ^{2} - \frac{1}{4} = 0 \Rightarrow λ = \pm \frac{1}{2}$ , giving $ρ (T_{J}) = \frac{1}{2}$ . Gauss-Seidel: $D - L = (2 - 1 02)$ , $(D - L)^{- 1} = \frac{1}{4} (2102)$ . $T_{GS} = (D - L)^{- 1} U = \frac{1}{4} (2102) (0010) = (00 \frac{1}{2} \frac{1}{4}) .$ Why its eigenvalues: $T_{GS}$ is upper-triangular, so its eigenvalues sit on the diagonal — $0$ and $\frac{1}{4}$ (formally $det (- λ 0 \frac{1}{2} \frac{1}{4} - λ) = (- λ) (\frac{1}{4} - λ) = 0$ ). Thus $ρ (T_{GS}) = \frac{1}{4}$ . Indeed $ρ (T_{GS}) = \frac{1}{4} = (\frac{1}{2})^{2} = ρ (T_{J})^{2}$ ✓ — Gauss-Seidel converges twice as fast (in digit terms) here.

Exercise 4.2 — Build the update for a $3 \times 3$ Gauss-Seidel sweep

For the SDD matrix of Exercise 1.1 with $b = (3, 6, 3)^{⊤}$ , perform one Gauss-Seidel sweep from $(0, 0, 0)$ . Report $x^{(1)}$ to 4 decimals.

Recall Solution 4.2

Rows: $5 x - 2 y = 3$ , $x + 4 y - z = 6$ , $- 3 y + 6 z = 3$ . Gauss-Seidel, in order, always using the newest available:

$x = \frac{3 + 2 y _{old}}{5} = \frac{3 + 0}{5} = 0.6000$ .
$y = \frac{6 - x _{new} + z _{old}}{4} = \frac{6 - 0.6 + 0}{4} = \frac{5.4}{4} = 1.3500$ .
$z = \frac{3 + 3 y _{new}}{6} = \frac{3 + 3 ( 1.35 )}{6} = \frac{7.05}{6} = 1.1750$ . So $x^{(1)} = (0.6000, 1.3500, 1.1750)$ .

L5 · Mastery

Exercise 5.1 — Prove the error recurrence gives geometric decay

Let $x^{(k + 1)} = T x^{(k)} + c$ with fixed point $x^{*} = T x^{*} + c$ . Show $∥ e^{(k)} ∥ \leq ∥ T ∥^{k} ∥ e^{(0)} ∥$ for any induced norm, and explain why $ρ (T) < 1$ is the sharp condition even when $∥ T ∥ \geq 1$ .

Recall Solution 5.1

Subtract the fixed-point equation from the iteration: $x^{(k + 1)} - x^{*} = T (x^{(k)} - x^{*}) \Rightarrow e^{(k + 1)} = T e^{(k)} \Rightarrow e^{(k)} = T^{k} e^{(0)} .$ Taking any induced (operator) norm and using sub-multiplicativity $∥ T v ∥ \leq ∥ T ∥ ∥ v ∥$ repeatedly: $∥ e^{(k)} ∥ = ∥ T^{k} e^{(0)} ∥ \leq ∥ T ∥^{k} ∥ e^{(0)} ∥.$ If $∥ T ∥ < 1$ this already forces $e^{(k)} \to 0$ . But $∥ T ∥$ can exceed $1$ while the iteration still converges: the sharp fact is $lim_{k \to \infty} ∥ T^{k} ∥^{1/ k} = ρ (T)$ (Gelfand's formula). Hence $T^{k} \to 0 ⟺ ρ (T) < 1$ , independent of any single norm. The norm bound is a convenient sufficient handle; $ρ (T) < 1$ is the exact truth.

Exercise 5.2 — Design $ω$ intuition for SOR

Successive Over-Relaxation (SOR — Successive Over-Relaxation) blends the old iterate with a Gauss-Seidel step: $x^{(k + 1)} = (1 - ω) x^{(k)} + ω x_{GS}^{(k)}$ . For the model matrix of Exercise 4.1, Gauss-Seidel has $ρ = \frac{1}{4}$ . Argue qualitatively why a well-chosen $ω > 1$ ("over-relaxation") can beat $ω = 1$ , and state the range of $ω$ that keeps SOR convergent for a symmetric positive-definite matrix.

Recall Solution 5.2

Why over-relax ( $ω > 1$ )? Gauss-Seidel takes a "safe" step toward the solution. If the successive corrections keep pointing the same direction — which they do for smooth SPD problems, where the error is dominated by one slowly-decaying eigenvector — then each safe step is systematically too short. Multiplying the correction by $ω > 1$ extrapolates further along that consistent direction, so we cover the remaining distance in fewer sweeps. Setting $ω = 1$ recovers plain Gauss-Seidel; $ω < 1$ ("under-relaxation") shortens the step, useful only when Gauss-Seidel would overshoot. Convergence range (Ostrowski–Reich): for a symmetric positive-definite $A$ , the SOR iteration converges if and only if $0 < ω < 2.$ Outside that band the extrapolation overshoots so hard that $ρ (T_{ω}) \geq 1$ and the error grows. Inside it there is a single optimal $ω^{⋆} \in (1, 2)$ that minimises $ρ (T_{ω})$ ; for the 2D model-Laplacian grid, $ω^{⋆} \to 2$ as the mesh is refined, giving a dramatic speedup over Gauss-Seidel. Such large sparse systems are exactly where iterating beats Gaussian Elimination — see Finite Difference Methods for PDEs for their origin and Sparse Matrices for why the per-sweep cost stays near $O (n)$ .

Recap

Recall Which is faster on the model matrix

$(2 - 1 - 1 2)$ , and by how much? Gauss-Seidel: $ρ (T_{GS}) = \frac{1}{4}$ vs Jacobi $ρ (T_{J}) = \frac{1}{2}$ , so $ρ_{GS} = ρ_{J}^{2}$ — twice as many correct digits per sweep.

Recall What is the exact necessary-and-sufficient convergence condition?

$ρ (T) < 1$ (spectral radius below one); SDD is only a sufficient shortcut.