Application to solution of linear system of equations

We will apply the fixed point theorem to show the convergence of Jacobi iterations for the numerical solution of the linear algebraic system

$$Ax = b$$

under the condition that the matrix $A$ is diagonally dominant. Assuming that the diagonal elements are non-zero, define the diagonal matrix

$$D = \textrm{diag}(A_{11}, A_{22}, ...., A_{NN})$$ (8)

and rewriting we get

$$x = D^{-1} [ b - (A-D)x]$$ (9)

which is now in the form of a fixed point problem with

$$F(x) = D^{-1} [ b - (A-D)x]$$

For measuring the distance between two vectors let us choose the maximum norm

$$d(x,y) = \max_{j} \vert x_j - y_j \vert$$

We must show that $F$ is a contraction mapping in this norm. Now

$$F(x) - F(y) = - D^{-1}(A-D)(x-y)$$

so that the j'th component is given by

$$[F(x) - F(y)]_j = \sum_{k \ne j} \frac{ A_{jk} }{ A_{jj}} (x_k - y_k)$$

From this we get

$$\vert [F(x) - F(y)]_j \vert \le \max_k \vert x_k - y_k \vert \sum_{k \ne j} \left\vert \frac{ A_{jk} }{ A_{jj}} \right\vert$$

and

$$d( F(x), F(y) ) \le d(x,y)\max_j \sum_{k \ne j} \left\vert \frac{ A_{jk} }{ A_{jj}} \right\vert$$

Hence the mapping is contractive if

$$\sum_{k \ne j} \vert A_{jk} \vert < \vert A_{jj} \vert, 1 \le j \le N$$ (10)

which is just the condition of diagonal dominance of matrix $A$. Hence if the matrix is diagonally dominant then the fixed point theorem assures us that the Jacobi iterations will converge.