Worked examples — Iterative methods — Jacobi, Gauss-Seidel, convergence

The scenario matrix

Here is every case class a Jacobi / Gauss-Seidel problem can throw at you. Each worked example below is tagged with the cell(s) it covers.

We build a decision tree first so you know which lever to pull when a matrix lands on your desk. (One acronym appears in the last box: SOR = Successive Over-Relaxation, an accelerated cousin of Gauss-Seidel — a fallback when reordering alone won't tame $\rho$.)

Case A — SDD, both methods converge

Step 1 — write the update rules. Why? Each equation is "solve for the variable on its own diagonal." $x=\frac{6-y}{4},y=\frac{7-x}{3}.$

Step 2 — Jacobi uses only OLD values. Why this step? Jacobi freezes the whole old vector, then updates everything at once.

• $k=1$: $x=\frac{6-0}{4}=1.5$, $y=\frac{7-0}{3}=2.3333$.
• $k=2$: $x=\frac{6-2.3333}{4}=0.9167$, $y=\frac{7-1.5}{3}=1.8333$.
• $k=3$: $x=\frac{6-1.8333}{4}=1.0417$, $y=\frac{7-0.9167}{3}=2.0278$.

Step 3 — Gauss-Seidel uses NEW $x$ inside $y$. Why this step? By the time we compute $y$, a better $x$ already exists — waste not.

• $k=1$: $x=\frac{6-0}{4}=1.5$; $y=\frac{7-1.5}{3}=1.8333$.
• $k=2$: $x=\frac{6-1.8333}{4}=1.0417$; $y=\frac{7-1.0417}{3}=1.9861$.
• $k=3$: $x=\frac{6-1.9861}{4}=1.0035$; $y=\frac{7-1.0035}{3}=1.9988$.

Verify: GS after 3 sweeps is $(1.0035,1.9988)$ — error $\approx 0.004$. Jacobi is $(1.0417,2.0278)$ — error $\approx 0.05$. GS is $\approx 10\times$ closer, as forecast. Plug $(1,2)$ into the originals: $4(1)+2=6$ ✓, $1+3(2)=7$ ✓.

Case B — forecast the speed from $\rho (T_J)$

Forecast: SDD ($|2|>|-1|$ both rows) so it converges; the question is how fast.

Step 1 — build $T_J=D^{-1}(L+U)$. Why? The parent note proved ${\mathbf{e}}^{(k)}=T_J^k{\mathbf{e}}^{(0)}$ (with ${\mathbf{e}}^{(k)}$ the error vector defined at the top); the error's fate lives entirely in $T_J$. $D=\left(\begin{array}{cc}2& 0\\ 0& 2\end{array}\right),L+U=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),T_J=\frac{1}{2}\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right).$

Step 2 — eigenvalues of $T_J$. Why this step? $\rho (T_J)=\max |\lambda |$ is the per-step shrink factor. For $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ the eigenvalues are $\pm 1$, so $T_J$ has $\lambda =\pm \frac{1}{2}$.

Step 3 — read off the rate. $\rho (T_J)=\frac{1}{2}<1$. Interpretation: every sweep roughly halves the length $\Vert {\mathbf{e}}^{(k)}\Vert$ of the error. To gain one decimal digit ($10\times$) you need about ${\log }_{10}(1/2{)}^{-1}\approx 3.3$ sweeps.

Verify: $\det (T_J-\lambda I)={\lambda }^2-\frac{1}{4}=0\Rightarrow \lambda =\pm \frac{1}{2}$ ✓. $\rho =0.5$ — one sweep should cut error in half; that's exactly the "closing in" we saw in Ex 1's SDD systems.

The figure above makes the forecast visual: with $\rho =0.5$ (green) the error length $\Vert {\mathbf{e}}^{(k)}\Vert$ halves each sweep and dives to zero, while a matrix with $\rho \approx 2.449$ (red, the next case) sees its error multiplied each sweep and blow up. The yellow dashed line marks the starting error size.

Case C — not SDD, it diverges

Forecast: Row 1: $|1|<|2|$ — not dominant. Suspicion: it blows up.

Step 1 — form $T_J$. Why? Same reason always — convergence is a property of $T_J$, not of $A$ directly. Here $a_{11}=a_{22}=1$ so $D^{-1}=I$: $T_J=D^{-1}(L+U)=\left(\begin{array}{cc}0& -2\\ -3& 0\end{array}\right).$ (The off-diagonals of $A$ are $2$ and $3$; in the $A=D-L-U$ convention $L+U$ carries their negatives.)

Step 2 — eigenvalues. Why? We need $\rho$. Characteristic equation $\det (T_J-\lambda I)={\lambda }^2-6=0$, so $\lambda =\pm \sqrt{6}\approx \pm 2.449$.

Step 3 — verdict. $\rho (T_J)=\sqrt{6}\approx 2.449>1$. Error is multiplied by $\approx 2.4$ each sweep ⇒ diverges.

Step 4 — the fix. Why? Swapping rows changes which coefficient sits on the diagonal: $\left(\begin{array}{cc}3& 1\\ 1& 2\end{array}\right),\text{now }|3|>|1|,|2|>|1|\text{— SDD, converges.}$

Verify: ${\lambda }^2-6=0\Rightarrow \lambda =\pm \sqrt{6}$, $\rho =\sqrt{6}\approx 2.449>1$ ✓ diverges. After swap $T_J^{\prime }=\left(\begin{array}{cc}0& -1/3\\ -1/2& 0\end{array}\right)$ has ${\lambda }^2=\frac{1}{6}$, $\rho =1/\sqrt{6}\approx 0.408<1$ ✓ converges.

Case D — not SDD, yet it CONVERGES

Forecast: The tempting (wrong) answer: "not SDD, so diverges." Let's check $\rho$, because SDD is only sufficient.

Step 1 — build $T_J$. Why? SDD failed, so the shortcut is off the table; we must compute the real criterion. With $a_{11}=a_{22}=1$, $D^{-1}=I$, and $L+U$ carries the negatives of the off-diagonals ($2$ above, $-\frac{1}{4}$ below): $T_J=D^{-1}(L+U)=\left(\begin{array}{cc}0& -2\\ \frac{1}{4}& 0\end{array}\right).$

Step 2 — eigenvalues. For a $2\times 2$ matrix with zero diagonal, $\det (T_J-\lambda I)={\lambda }^2-(\text{product of the two off-diagonals})$. Here the product is $(-2)(\frac{1}{4})=-\frac{1}{2}$, so $\det (T_J-\lambda I)={\lambda }^2-(-\frac{1}{2})={\lambda }^2+\frac{1}{2}=0$. Thus ${\lambda }^2=-\frac{1}{2}$, $\lambda =\pm i/\sqrt{2}$ — a complex pair.

Step 3 — take magnitudes. Why this step? $\rho$ uses the absolute value of complex eigenvalues: $|\lambda |=\sqrt{(0{)}^2+(1/\sqrt{2}{)}^2}=\frac{1}{\sqrt{2}}\approx 0.707<1$.

Step 4 — verdict. $\rho (T_J)\approx 0.707<1$ ⇒ converges, even though $A$ is not diagonally dominant. Moral: SDD is a friendly sufficient flag, never a death sentence when absent.

Verify: ${\lambda }^2+\frac{1}{2}=0\Rightarrow |\lambda |=1/\sqrt{2}\approx 0.7071<1$ ✓ converges despite non-SDD.

Case E — zero on the diagonal (degenerate)

Forecast: Both methods divide by $a_{ii}$. Here $a_{11}=0$ — division by zero. It's undefined before it even starts.

Step 1 — spot the illegal step. Why? The update $x_1=\frac{1}{a_{11}}(b_1-a_{12}{x}_2)$ has $\frac{1}{0}$. Stop.

Step 2 — permute rows. Why this step? Reordering equations doesn't change the solution, but moves a nonzero onto the diagonal: $\left(\begin{array}{cc}3& 1\\ 0& 2\end{array}\right)\mathbf{x}=\left(\begin{array}{c}5\\ 4\end{array}\right).$ Now $a_{11}=3\ne 0$, $a_{22}=2\ne 0$: division legal. Bonus — it's SDD, so it also converges.

Step 3 — solve the reordered system (exact, to have a target). From row 2: $2y=4\Rightarrow y=2$. From row 1: $3x+2=5\Rightarrow x=1$.

Verify: Original equations: $2y=4\Rightarrow y=2$ ✓ and $3x+y=5\Rightarrow 3(1)+2=5$ ✓. The permuted diagonal is nonzero, so Jacobi is now well-defined.

Case F — Jacobi converges but Gauss-Seidel diverges

Forecast: Everyone "knows" GS is faster. Watch it fail.

Step 1 — Jacobi's $T_J$. Why compute $T_J$ first? To establish the baseline. The diagonal is all $1$'s so $D^{-1}=I$, and $L+U$ carries the negatives of all off-diagonal entries: $T_J=D^{-1}(L+U)=\left(\begin{array}{ccc}0& -2& 2\\ -1& 0& -1\\ -2& -2& 0\end{array}\right).$

Step 2 — why its characteristic polynomial is ${\lambda }^3$. Why this step? We need $\rho (T_J)$. Expand $\det (T_J-\lambda I)$. Writing it out (cofactor along the first row) the constant, ${\lambda }^1$, and ${\lambda }^2$ coefficients all cancel — the trace is $0$ (kills ${\lambda }^2$), the sum of $2\times 2$ principal minors is $0$ (kills ${\lambda }^1$), and $\det T_J=0$ (kills the constant). What survives is $\det (T_J-\lambda I)=-{\lambda }^3$. So all three eigenvalues are $0$: $\rho (T_J)=0$. Jacobi converges in at most 3 steps — spectacular.

Step 3 — Gauss-Seidel's $T_{GS}=(D-L{)}^{-1}U$. Why? GS uses $M=D-L$. From $A=D-L-U$ we read off $D-L=\left(\begin{array}{ccc}1& 0& 0\\ 1& 1& 0\\ 2& 2& 1\end{array}\right),U=\left(\begin{array}{ccc}0& -2& 2\\ 0& 0& -1\\ 0& 0& 0\end{array}\right).$ Inverting the lower-triangular $D-L$ and multiplying gives $T_{GS}=(D-L{)}^{-1}U=\left(\begin{array}{ccc}0& -2& 2\\ 0& 2& -3\\ 0& 0& 2\end{array}\right).$ This is upper-triangular, so its eigenvalues sit on the diagonal: $0,2,2$. Hence $\rho (T_{GS})=2>1$: diverges.

Step 4 — moral. Why this matters: freshness of information is usually good but not guaranteed good. The order in which you overwrite can amplify certain error directions.

Verify: $\det (T_J-\lambda I)=-{\lambda }^3$ so $\rho (T_J)=0$ ✓; and $T_{GS}$ has diagonal eigenvalues $0,2,2$ so $\rho (T_{GS})=2>1$ ✓. "Usually faster," never "always converges." (For the safe families — SPD or SDD — GS does win; this is the pathological counter-example.)

Case G — a real-world word problem (tiny PDE grid)

Forecast: Physics says heat spreads to a straight line, so the exact answer should be equally spaced: $7.5,15,22.5$.

Step 1 — recognise the structure. Why? Rearranged, the system matrix is $A=\left(\begin{array}{ccc}2& -1& 0\\ -1& 2& -1\\ 0& -1& 2\end{array}\right),\mathbf{b}=\left(\begin{array}{c}0\\ 0\\ 30\end{array}\right).$ This is a sparse tridiagonal system — exactly what iterative methods love. It is only weakly diagonally dominant (row 2 has $|2|=|-1|+|-1|$, equality), so weak dominance alone proves nothing; we must compute $\rho (T)$ to justify convergence.

Step 2 — compute $\rho (T_J)$ to prove convergence. Why this step? This is the real WHY behind "it converges." With $D=2I$, $T_J=D^{-1}(L+U)=\frac{1}{2}\left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 1\\ 0& 1& 0\end{array}\right).$ For an $m\times m$ tridiagonal matrix with $0$ on the diagonal and $1$ just off it, the eigenvalues are known exactly: $2\cos \frac{m^{\prime }\pi }{m+1}$ for $m^{\prime }=1,\dots ,m$. Here $m=3$, so those inner eigenvalues are $2\cos \frac{\pi }{4},2\cos \frac{2\pi }{4},2\cos \frac{3\pi }{4}=\sqrt{2},0,-\sqrt{2}$. Multiply by the $\frac{1}{2}$ out front: $T_J$ has eigenvalues $\frac{\sqrt{2}}{2},0,-\frac{\sqrt{2}}{2}$. The largest magnitude is $\rho (T_J)=\frac{\sqrt{2}}{2}\approx 0.7071<1$ ⇒ converges (and Gauss-Seidel, being ${\rho }_{GS}={\rho }_J^2=\frac{1}{2}=0.5$ for this model matrix, is even faster).

Step 3 — Gauss-Seidel sweeps (average form, use freshest neighbour). Why this step? Each row already gives $T_i$ as an average, so GS is just "recompute averages left-to-right using latest values."

• $k=1$: $T_1=\frac{0+0}{2}=0$; $T_2=\frac{0+0}{2}=0$; $T_3=\frac{0+30}{2}=15$.
• $k=2$: $T_1=\frac{0+0}{2}=0$; $T_2=\frac{0+15}{2}=7.5$; $T_3=\frac{7.5+30}{2}=18.75$.
• $k=3$: $T_1=\frac{0+7.5}{2}=3.75$; $T_2=\frac{3.75+18.75}{2}=11.25$; $T_3=\frac{11.25+30}{2}=20.625$.
• $k=4$: $T_1=\frac{0+11.25}{2}=5.625$; $T_2=\frac{5.625+20.625}{2}=13.125$; $T_3=\frac{13.125+30}{2}=21.5625$.

Step 4 — watch it march toward $(7.5,15,22.5)$; it climbs steadily each sweep, exactly as the $\rho \approx 0.71$ from Step 2 promised.

Verify: Exact solution: plug $(7.5,15,22.5)$: $2(7.5)-15=0$ ✓, $-7.5+2(15)-22.5=0$ ✓, $-15+2(22.5)=30$ ✓. Units: all in ${}^{\circ }$C, endpoints $0$ and $30$ bracket every interior value ✓.

Case H — exam twist: choose a value to guarantee convergence

Forecast: Bigger diagonal = safer. There should be a threshold on $|c|$.

Step 1 — write the SDD inequality per row. Why? SDD demands $|a_{ii}|>{\sum }_{j\ne i}|a_{ij}|$. Every row here has diagonal $c$ and two off-diagonal $1$'s: $|c|>1+1=2.$

Step 2 — solve. Why this step? $|c|>2$ means $c>2$ or $c<-2$.

Step 3 — sanity-probe a value. Take $c=3$: $T_J=D^{-1}(L+U)=-\frac{1}{3}\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}\right)$. The inner matrix $\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}\right)$ has eigenvalues $2,-1,-1$, so $T_J$ has $\lambda =-\frac{2}{3},\frac{1}{3},\frac{1}{3}$, giving $\rho (T_J)=\frac{2}{3}<1$ ✓ converges.

Verify: $|c|>2⟺c\in (-\infty ,-2)\cup (2,\infty )$. For $c=3$: $\rho (T_J)=\frac{2}{3}\approx 0.667<1$ ✓. For the boundary $c=2$: $\rho (T_J)=\frac{2}{2}=1$ — not guaranteed to converge (borderline), confirming the strict inequality is genuinely needed.

Recall