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.
If instead we set  
\[\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.

Add comment

Security code
Refresh