## Condition For Convergence of Jacobi and Gauss - Seidel Procedures for Solution of Simultaneous Linear Equations

Suppose we have a system of linear equations written in matrix form
$A \mathbf{x}= \mathbf{b}$
or
$\left( \begin{array}{cccc} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ddots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \ldots & a_{nn} \end{array} \right) \begin{pmatrix}x_1\\x_2\\ \vdots \\x_n\end{pmatrix} = \begin{pmatrix}b_1\\b_2\\ \vdots \\b_n\end{pmatrix}$

Every square matrix can be written as a sum of an upper triangular matrix
$U$
, a lower triangular matrix
$L$
and a diagonal matrix
$D$
so we can write
$A=U+L+D$
and the linear system can be written
$(U+L+D) \mathbf{x} =\mathbf{b}$

We can rearrange to give
$\mathbf{x}=-D^{-1}L \mathbf{x}- D^{-1}U \mathbf{x}+ D^{-1} \mathbf{b}$
then write down the recurrence relation
$\mathbf{x}^{(n+1)}=-D^{-1}(L+U) \mathbf{x}^{(n)}+ D^{-1} \mathbf{b}$
.
When we set
$\mathbf{x}^{(0)} = \mathbf{0}$
this is the Jacobi iteration method.
$\mathbf{x}^{(n+1)}=-D^{-1}L \mathbf{x}^{(n+1)}-D^{-1}U \mathbf{x}^{(n+1)}+ D^{-1} \mathbf{b}$
with
$x_i= b_i/a_{ii}$
then we have the Gauss - Seidel iteration method.
For analysing convergence write the Jacobi and Gauss - Seidel formulae as to give
$\mathbf{x}^{(n+1)}$
in terms of
$\mathbf{x}^{(n)}$
.
Jacobi:
$\mathbf{x}^{(n+1)}=-D^{-1}(L+U) \mathbf{x}^{(n)}+D^{-1} \mathbf{b}$

Gauss - Seidel:
$\mathbf{x}^{(n+1)}=-(D+L)^{-1}U \mathbf{x}^{(n)}+(D+L)^{-1} \ma+hbf{b}$

For the Gauss - Seidel procedure to converge we need
$lim_{n+1 \rightarrow \infty} \mathbf{x}^{(n+1)} = lim_{n \rightarrow \infty} \mathbf{x}^{(n)}= A^{-1} \mathbf{b}$

Both of these are of the form
$\mathbf{x}^{(n+1)}=M \mathbf{x}^{(n)} + \mathbf{c}$
(1)
Then fixed points of
$\mathbf{x}$
must satisfy
$\mathbf{x}=M \mathbf{x} + \mathbf{c}$

Let the error in the ith solution be
$\mathbf{e}^{(n)}= \mathbf{x}^{(n)}- \mathbf{x}$

Subtract this from (1) to give
$\mathbf{e}^{(n+1)}= M \mathbf{e}^{(n)}=M^n \mathbf{e}^{(0)}$

For the solution to converge we need the error to iterate to zero, hence the condition for convergence is
$lim_{n \rightarrow \infty} M^n =0$

A necessary and sufficient convergence for the above to hold is that the eigenvalues of
$M$
are all less than 1 in magnitude.