Jacobi Iteration

For a large system with mostly zero entries, elimination's $\frac{2}{3}n^{3}$ flops (see The Cost of Elimination) can be far too many. An iterative method starts from a guess and improves it using only cheap products with $A$. Jacobi's method is the simplest, and it is a Fixed-Point Iteration in disguise.

Solve equation $i$ for $x_i$, and put the previous values on the right: $$x_i^{(k+1)} = \frac{1}{a_{ii}}\left(b_i - \sum_{j \ne i}a_{ij}x_j^{(k)}\right).$$ In matrix form, with $A = D + L + U$ (diagonal, strictly lower, strictly upper parts), $\mathbf{x}^{(k+1)} = D^{-1}\big(\mathbf{b} - (L + U)\mathbf{x}^{(k)}\big)$.

Key idea

Jacobi updates every variable at once from the previous sweep. It converges from any start when $A$ is strictly diagonally dominant by rows: $|a_{ii}| > \sum_{j \ne i}|a_{ij}|$ in every row. The error shrinks by about the spectral radius $\rho(T)$ of $T = -D^{-1}(L + U)$ per sweep.

Why it works

The exact solution satisfies the same formula, so subtracting gives $\mathbf{e}^{(k+1)} = T\mathbf{e}^{(k)}$ for the error. Row $i$ of $T$ has absolute sum $\sum_{j \ne i}\frac{|a_{ij}|}{|a_{ii}|}$, which is less than 1 for every row exactly when $A$ is strictly diagonally dominant. Then $\lVert T\rVert_\infty < 1$ and $\lVert\mathbf{e}^{(k)}\rVert_\infty \le \lVert T\rVert_\infty^{k}\lVert\mathbf{e}^{(0)}\rVert_\infty \to 0$, just as $|g'| < 1$ made fixed-point iteration converge.

Worked example: Three sweeps

Apply Jacobi to $4x + y = 6$, $2x + 5y = 9$ from $(0, 0)$. (The solution is $(\frac{7}{6}, \frac{4}{3}) \approx (1.167, 1.333)$.)

Iteration: $x \leftarrow \frac{6 - y}{4}$, $y \leftarrow \frac{9 - 2x}{5}$, both from the old values.
Sweep 1: $(\frac{6}{4}, \frac{9}{5}) = (1.5, 1.8)$.
Sweep 2: $(\frac{6 - 1.8}{4}, \frac{9 - 3}{5}) = (1.05, 1.2)$.
Sweep 3: $(\frac{6 - 1.2}{4}, \frac{9 - 2.1}{5}) = (1.2, 1.38)$, closing in on the solution from both sides.

Answer: $(1.2, 1.38)$ after three sweeps

The same two lines, listed in the two possible orders. In one order Jacobi spirals out; in the other it closes in on the crossing.

Worked example: The order of the equations matters

Someone lists the same system as $2x + 5y = 9$, $4x + y = 6$ and solves the first equation for $x$, the second for $y$.

Iteration: $x \leftarrow \frac{9 - 5y}{2}$, $y \leftarrow 6 - 4x$. Neither row is diagonally dominant.
From $(0, 0)$: $(4.5, 6)$, then $(-10.5, -12)$, then $(34.5, 48), \ldots$ It diverges.
Here $\rho(T) = \sqrt{\frac{5}{2} \cdot 4} = \sqrt{10} > 1$. Swapping the equations gives $\rho = \sqrt{\frac{1}{4} \cdot \frac{2}{5}} = \sqrt{0.1} \approx 0.32$.

Answer: it diverges; swap the equations

One sweep costs about two flops per nonzero entry of $A$, so for a sparse matrix with a few nonzeros per row a sweep is cheap, far cheaper than elimination. In practice the iteration stops when the residual $\lVert\mathbf{b} - A\mathbf{x}^{(k)}\rVert$ is small compared with $\lVert\mathbf{b}\rVert$, or when successive iterates barely change. Diagonal dominance is enough for convergence but not necessary; what matters exactly is whether $\rho(T) < 1$.

Common mistake

Running the iteration on the equations as given, even when another order would make the system diagonally dominant. Before iterating, put each equation where its largest coefficient (in size) lands on the diagonal. Reordering equations never changes the solution, but it can turn a diverging iteration into a converging one.

Jacobi Iteration

Practice

Builds on

Leads to

Sources and further reading