Proof that Jacobi method will converge to the solution of a system Ax=b

Question

Can anyone show me a statement that this works and a proof? Thanks

Answer 1

To fix notation, let's write $A = L + D + R$, where $L$ is the left lower part of $A$, $D$ the diagonal part and $R$ the right upper part. Then the Jacobi method is the iteration $$ x_{n+1} = D^{-1}\bigl(b- (L+U)x_n\bigr) \color{red}{\biggl( = D^{-1}b + D^{-1}(D-A)x_n\biggr) }$$ Now the iteration converges for every $x_0$ by Banach's fixed point theorem if for a matrix norm $\|D^{-1}(D-A)\| < 1$, which holds if the spectral radius we have $\rho(D^{-1}(D-A)) < 1$, which for example is true if $A$ is stricly diagonal dominant, i. e. $$ \def\abs#1{\left|#1\right|} \abs{a_{ii}} > \sum_{j\ne i} \abs{a_{ij}}, \quad \text{ every $i$} $$ (as then $\|D^{-1}(D-A)\| < 1$ for the column sum norm.

A fixed point $x$ of the given iteration has $$ Dx = b + (D-A)x \iff 0 = b- Ax \iff Ax = b $$