Jacobi method

Remarks

The error $e_k = x^{(k)} - A^{-1} b$ satisfies $e_{k+1} = G e_k$ with $G = -D^{-1} R$. The $i$-th absolute row sum of $G$ is $\sum_{j \ne i} \abs{a_{ij}} / \abs{a_{ii}}$, which is less than $1$ by diagonal dominance. So the matrix norm $\norm{G}_\infty$ is less than $1$, and $\norm{e_k}_\infty \le \norm{G}_\infty^k \norm{e_0}_\infty \to 0$. In general, the method converges for every $x^{(0)}$ if and only if the spectral radius of $G$ is less than $1$. Example: for $A$ with rows $(2, 1)$ and $(1, 2)$ and $b = (3, 3)$, starting at $0$ gives $(1.5, 1.5)$, $(0.75, 0.75)$, $(1.125, 1.125)$, tending to $(1, 1)$. The error is multiplied by $-1/2$ at each step. Without diagonal dominance the method can diverge. For $A$ with rows $(1, 2)$ and $(2, 1)$, the matrix $G$ has eigenvalues $\pm 2$.

Going deeper

For a student

The Jacobi method is the simplest iterative method built from a splitting $A = M - N$, here with $M = D$. Each step costs one matrix-vector product, and all components can be computed in parallel. It converges slowly on discretized elliptic problems, where the spectral radius tends to $1$ as the mesh is refined. A damped version is still widely used as a smoother in multigrid methods.