Visual walkthrough — Iterative methods — Jacobi, Gauss-Seidel, convergence

---

Step 0 — The words we will use (nothing assumed)

Before any formula, three plain ideas.

• A system $A\mathbf{x}=\mathbf{b}$ is just several straight-line equations that must all be true at once. Their meeting point is the true solution, which we name ${\mathbf{x}}^{\ast }$ (the star means "the real answer we are hunting").
• A guess ${\mathbf{x}}^{(k)}$ is any point we propose as the answer. The little $(k)$ on top is a step counter, not a power — ${\mathbf{x}}^{(0)}$ is our first guess, ${\mathbf{x}}^{(1)}$ the next, and so on.
• The error ${\mathbf{e}}^{(k)}={\mathbf{x}}^{(k)}-{\mathbf{x}}^{\ast }$ is the arrow that points from the true answer to our current guess. If that arrow shrinks to nothing, our guess has landed on the answer.

Look at the figure: the black dot is ${\mathbf{x}}^{\ast }$, the open dot is our guess, and the red arrow is the error ${\mathbf{e}}^{(k)}$. Everything below is one question: how does that red arrow change from step to step?

---

Step 1 — Rewrite the problem so "new" sits alone on the left

WHAT. We split $A$ into an easy part $M$ and a leftover part $N$, so that $A=M-N$, and we insist $M$ is a matrix we can cheaply undo (invert).

WHY. We cannot invert $A$ cheaply — that is the whole reason we abandoned Gaussian Elimination. But if $M$ is diagonal or triangular, "solving $M\mathbf{y}=\text{something}$" is trivial. So we push all the hard stuff to the right side, where it multiplies an old guess we already have numbers for.

Start from the exact statement and substitute the split:

$$A\mathbf{x}=\mathbf{b}⟺\underset{\text{this is }A}{\underbrace{(M-N)}}\mathbf{x}=\mathbf{b}⟺\underset{\text{easy piece}}{\underbrace{M\mathbf{x}}}=\underset{\text{leftover + data}}{\underbrace{N\mathbf{x}+\mathbf{b}}}.$$

Reading term by term: $M\mathbf{x}$ is the part we can solve instantly; $N\mathbf{x}$ is the "coupling" we will feed with an old guess; $\mathbf{b}$ is the fixed data vector. Now freeze the right side at the old guess ${\mathbf{x}}^{(k)}$ and let the left side produce the new guess ${\mathbf{x}}^{(k+1)}$:

$$M{\mathbf{x}}^{(k+1)}=N{\mathbf{x}}^{(k)}+\mathbf{b}.$$

PICTURE. The figure shows the "conveyor belt": old guess enters the right box, gets multiplied by $N$ and nudged by $\mathbf{b}$, then $M$ is undone to spit out the new guess.

---

Step 2 — Name the single machine that does one step: $T$

WHAT. Undo $M$ on both sides. That collapses one full step into a single multiply-and-shift.

WHY. We want to see the machine that turns any guess into the next guess, because studying that one machine tells us everything about the long run.

$${\mathbf{x}}^{(k+1)}=\underset{\text{call this }T}{\underbrace{M^{-1}N}}{\mathbf{x}}^{(k)}+\underset{\text{call this }\mathbf{c}}{\underbrace{M^{-1}\mathbf{b}}}.$$

Term by term: $M^{-1}$ is "undo the easy part"; $M^{-1}N=T$ is the iteration matrix — the fixed multiplier applied every step; $M^{-1}\mathbf{b}=\mathbf{c}$ is a constant offset that never changes. So every method (Jacobi, Gauss-Seidel, SOR) is the same shape:

$${\mathbf{x}}^{(k+1)}=T{\mathbf{x}}^{(k)}+\mathbf{c}.$$

PICTURE. The two boxes of Step 1 fuse into one labelled box $T$, with a small constant $\mathbf{c}$ added on.

---

Step 3 — Subtract the truth to watch the error, not the guess

WHAT. The true answer ${\mathbf{x}}^{\ast }$ is a fixed point: feeding it in gives it back. So it obeys the same rule, ${\mathbf{x}}^{\ast }=T{\mathbf{x}}^{\ast }+\mathbf{c}$.

WHY. The constant $\mathbf{c}$ clutters things. If we subtract the truth's equation from the guess's equation, the $\mathbf{c}$ cancels and we are left with a clean law for the error arrow alone.

$$\begin{array}{rcl}{\mathbf{x}}^{(k+1)}& =& T{\mathbf{x}}^{(k)}+\mathbf{c}\\ -({\mathbf{x}}^{\ast }& =& T{\mathbf{x}}^{\ast }+\mathbf{c})\\ \underset{={\mathbf{e}}^{(k+1)}}{\underbrace{{\mathbf{x}}^{(k+1)}-{\mathbf{x}}^{\ast }}}& =& T\underset{={\mathbf{e}}^{(k)}}{\underbrace{({\mathbf{x}}^{(k)}-{\mathbf{x}}^{\ast })}}.\end{array}$$

The $\mathbf{c}$ appeared identically in both rows, so it vanished. What remains is startlingly simple:

$$\boxed{{\mathbf{e}}^{(k+1)}=T{\mathbf{e}}^{(k)}.}$$

Each symbol: ${\mathbf{e}}^{(k+1)}$ is next step's error arrow; $T$ is the same machine as before; ${\mathbf{e}}^{(k)}$ is this step's error arrow. The error is fed through the identical machine $T$.

PICTURE. Same $T$ box, but now the red error arrow goes in and a (hopefully shorter) red error arrow comes out.

---

Step 4 — Unroll: the error is $T$ applied $k$ times

WHAT. Apply the boxed law repeatedly, all the way back to the start.

WHY. We want a formula for the error at any step in terms of the initial error, so we can ask "does it die?"

$${\mathbf{e}}^{(1)}=T{\mathbf{e}}^{(0)},{\mathbf{e}}^{(2)}=T{\mathbf{e}}^{(1)}=T^2{\mathbf{e}}^{(0)},\dots \boxed{{\mathbf{e}}^{(k)}=T^k{\mathbf{e}}^{(0)}.}$$

Here $T^k$ means "apply the machine $k$ times" (an honest matrix power now). So the entire question of convergence becomes one question about a matrix power:

Does $T^k{\mathbf{e}}^{(0)}\to 0$ as $k\to \infty$, for every possible starting error ${\mathbf{e}}^{(0)}$?

PICTURE. A chain of $T$-boxes; the red error arrow gets shorter each box — or, if we are unlucky, longer.

---

Step 5 — Look at $T$ through its own natural directions (eigenvectors)

WHAT. A matrix multiply is hard to picture in general — it rotates and stretches. But every diagonalizable $T$ has special directions, called eigenvectors ${\mathbf{v}}_i$, along which it does nothing but stretch by a number ${\lambda }_i$ (its eigenvalue): $T{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$.

WHY. These are the tool for exactly this job. See Eigenvalues and Eigenvectors. Why eigenvectors and not, say, the raw matrix entries? Because along an eigen-direction, applying $T$ a hundred times is just multiplying by ${\lambda }_i$ a hundred times — a scalar we understand completely. The tangled matrix becomes a bag of independent scalars.

Write the starting error as a combination of these directions (any vector can be, if the ${\mathbf{v}}_i$ span the space):

$${\mathbf{e}}^{(0)}=c_1{\mathbf{v}}_1+c_2{\mathbf{v}}_2+\cdots +c_n{\mathbf{v}}_n.$$

The numbers $c_i$ say "how much of the error points along direction $i$." Now hit it with $T^k$. Along each eigen-direction, $T$ just multiplies by ${\lambda }_i$, so $T^k$ multiplies by ${\lambda }_i^k$:

$${\mathbf{e}}^{(k)}=T^k{\mathbf{e}}^{(0)}=c_1{\lambda }_1^k{\mathbf{v}}_1+c_2{\lambda }_2^k{\mathbf{v}}_2+\cdots +c_n{\lambda }_n^k{\mathbf{v}}_n.$$

Each piece of the error is scaled by ${\lambda }_i^k$ — a plain number raised to the $k$-th power.

PICTURE. The error arrow drawn as a sum of two eigen-arrows; each is stretched by its own $\lambda$ when $T$ acts.

---

Step 6 — When does ${\lambda }^k$ die? The whole answer in one number

WHAT. Each component's fate is decided by ${\lambda }_i^k$. A number raised to higher and higher powers goes to zero iff its absolute value is below 1.

WHY. This is the heart. Look at three cases of one component (figure):

• $|{\lambda }_i|<1$: ${\lambda }_i^k\to 0$. That piece of the error dies. ✓
• $|{\lambda }_i|=1$: ${\lambda }_i^k$ stays the same size forever. The error stalls — never converges. ✗
• $|{\lambda }_i|>1$: ${\lambda }_i^k$ blows up. The error explodes (diverges). ✗

For the whole error to vanish, every component must die. So we must have $|{\lambda }_i|<1$ for all $i$. The worst (largest) one is the bottleneck — and that largest absolute eigenvalue has a name.

$$\boxed{\rho (T)<1⟺{\mathbf{e}}^{(k)}\to 0\text{for every start}⟺\text{the iteration converges.}}$$

And the speed: once the small components are gone, the error is dominated by the biggest $\lambda$, so each step shrinks the error by roughly the factor $\rho (T)$. Smaller $\rho$ ⇒ faster.

PICTURE. Three shrinking/steady/growing staircases of ${\lambda }^k$ for the three cases.

---

Step 7 — The degenerate cases you must not skip

WHAT & WHY. The derivation assumed a few things. Here is what happens when they fail.

• A zero diagonal entry, $a_{ii}=0$. Both methods divide by $a_{ii}$, so $M=D$ (Jacobi) or $M=D-L$ (Gauss-Seidel) is not invertible — Step 2 collapses. Fix: permute rows to put nonzeros on the diagonal before forming $T$.
• $T$ has a repeated eigenvalue and cannot be diagonalized. Step 5's clean split fails. The honest statement uses the Spectral Radius anyway: $T^k\to 0⟺\rho (T)<1$ still holds (via the Jordan form, where a polynomial-times-${\lambda }^k$ factor still dies whenever $|\lambda |<1$). So the boxed result survives.
• Boundary $\rho (T)=1$. The error neither dies nor grows in the worst direction — the iteration does not converge (it may cycle or drift). This case belongs firmly on the "fail" side.
• Non-strictly-dominant matrices. Strict diagonal dominance is only a sufficient shortcut. A matrix can flunk it yet still have $\rho (T)<1$ and converge. The eigenvalue test is the true judge.

PICTURE. A flowchart-style figure: check $a_{ii}\ne 0$ → form $T$ → measure $\rho$ → verdict.

---

Step 8 — Watch it on a real matrix (numbers you can check)

WHAT. Take $A=\left(\begin{array}{cc}2& -1\\ -1& 2\end{array}\right)$, the classic 1-D finite-difference block from a sparse PDE grid.

Split: $D=2I$, and $L+U=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, so the Jacobi machine is

$$T_J=D^{-1}(L+U)=\frac{1}{2}\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right).$$

Its eigenvalues: the inner matrix $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ swaps components, so its eigenvalues are $\pm 1$; halving gives $\lambda (T_J)=\pm \frac{1}{2}$. Therefore

$$\rho (T_J)=\frac{1}{2}<1\Rightarrow \text{converges, error halves each sweep.}$$

Contrast with the parent's diverging example $A=\left(\begin{array}{cc}1& 2\\ 3& 1\end{array}\right)$: there $\rho (T_J)=\sqrt{6}\approx 2.449>1$, so the red error arrow grows — exactly the "explode" staircase of Step 6.

---

The one-picture summary

Everything on this page in one frame: the split makes the machine $T$ (Step 2); subtracting the truth turns the guess-law into the error-law ${\mathbf{e}}^{(k+1)}=T{\mathbf{e}}^{(k)}$ (Step 3); unrolling gives ${\mathbf{e}}^{(k)}=T^k{\mathbf{e}}^{(0)}$ (Step 4); eigen-directions turn the matrix power into scalars ${\lambda }_i^k$ (Step 5); and those scalars die exactly when the biggest, $\rho (T)$, is under 1 (Step 6).

Recall Feynman retelling — say it like a story

We have a true answer sitting somewhere, and a guess with a red arrow pointing from the answer to the guess. We built a machine, $T$, that takes any guess and makes a new one. Because the true answer stays put when fed through the machine, subtracting it shows the arrow obeys the same machine: each step, the red arrow gets sent through $T$. Do that $k$ times and the arrow has been through $T$ exactly $k$ times. Now the trick: every machine has favorite directions where it only stretches, by a factor $\lambda$. Split the arrow into those directions; along each one, $k$ steps just means multiplying by $\lambda$ that many times. A number below 1, multiplied by itself forever, fades to zero; a number above 1 explodes; a number equal to 1 sits there stubbornly. The arrow vanishes only if every one of its pieces fades — so the biggest stretch factor, $\rho (T)$, must be under 1. That single number decides both whether we win and how fast.

Recall Rapid self-check

Why does the constant $\mathbf{c}$ vanish in the error law? ::: The true solution obeys ${\mathbf{x}}^{\ast }=T{\mathbf{x}}^{\ast }+\mathbf{c}$; subtracting it from the guess equation cancels $\mathbf{c}$. Convergence iff which single number is below 1? ::: $\rho (T)$, the spectral radius (largest $|\lambda |$). What is the approximate per-step error shrink factor? ::: $\rho (T)$ itself. What must you fix before $T$ even exists? ::: A zero diagonal entry — permute rows so $M$ is invertible.

---

Parent: 4.8.20 Iterative methods — Jacobi, Gauss-Seidel, convergence (Hinglish)