Engineering at Alberta Courses » Convergence of Jacobi and Gauss-Seidel Methods

Iterative Methods: Convergence of Jacobi and Gauss-Seidel Methods

If the matrix $A$ is diagonally dominant, i.e., the values in the diagonal components are large enough, then this is a sufficient condition for the two methods to converge. In particular, if every diagonal component satisfies $|A_{ii}|>\sum_{j=1,j\neq i}^n|A_{ij}|$ , then, the two methods are guaranteed to converge. Generally, when these methods are used, the programmer should first use pivoting (exchanging the rows and/or columns of the matrix $A$ ) to ensure the largest possible diagonal components. Use the code above and see what happens after 100 iterations for the following system when the initial guess is $x_1=x_2=0$ :

$\begin{split}x_1-5x_2&=-4\\7x_1-x_2&=6\end{split}$

The system above can be manipulated to make it a diagonally dominant system. In this case, the columns are interchanged and so the variables order is reversed:

$\begin{split}-5x_2+x_1&=-4\\-x_2+7x_1&=6\end{split}$

This system will now converge for any choice of an initial guess!

To show how the condition on the diagonal components $A$ is a sufficient condition for the convergence of the iterative methods (solving $Ax=b$ ), the proof for the aforementioned condition is presented for the Jacobi method as follows. The proof for the Gauss-Seidel method has the same nature.

We want to prove that if $|A_{ii}|>\sum_{j=1, j\ne i}^n|A_{ij}|$ , then the Jacobi method (essentially) converges.

To this end, consider the formulation of the Jacobi method, i.e.,

$x = D^{-1}(b-Rx)$

Therefore, $x_i^{(k+1)}$ , being the approximate solution for $x_i$ at iteration $k+1$ , is,

$x_i^{(k+1)}=\frac{1}{A_{ii}}\left(b_i-\sum_{j=1}^{n}R_{ij}x_j^{(k)}\right)$

Since $R_{ii}=0$ (the diagonal components of $R$ are zero), the above equation can be written as,

$x_i^{(k+1)}=\frac{1}{A_{ii}}\left(b_i-\sum_{j=1, j\ne i}^{n}A_{ij}x_j^{(k)}\right)$

Defining the error of $x_i^{(k+1)}$ as,

$e_i^{k+1}:=x_i^{(k+1)}-x_i$

we can write,

$\begin{split}e_i^{k+1}&=\frac{1}{A_{ii}}\left(b_i-\sum_{j=1,j\ne i}^{n}A_{ij}x_j^{(k)}\right)-\frac{1}{A_{ii}}\left(b_i-\sum_{j=1,j\ne i}^{n}A_{ij}x_j\right)\\&=\frac{1}{A_{ii}}\sum_{j=1,j\ne i}^{n}A_{ij}(x_j-x_j^{(k)})\end{split}$

which, by the triangular inequality, implies

$|e_i^{k+1}|\le\frac{1}{|A_{ii}|}\sum_{j=1, j\ne i}^{n}|A_{ij}||(x_j-x_j^{(k)})|$

Letting $e_j^{(k)}:=x_j-x_j^{(k)}$ , we can write,

$|e_i^{k+1}|\le\frac{1}{|A_{ii}|}\sum_{j=1,j\ne i}^{n}|R_{ij}||e_j^{(k)}|$

where $|e_j^{(k)}|$ is the absolute value of the error of $x_j^{(k)}$ (at the k-th iteration). Because $j\ne i$ , the term $e_j^{(k)}$ does not account for $e_i^{(k)}$ being the error of $x_i^{(k)}$ .

Now let $E^k$ be the maximum of the absolute values of the errors of $x_j^k$ for $j=1,\dots ,n$ ; in a mathematical notation $E^k$ is expressed as,

$E^k:=\max |e_j^{(k)}|, \quad j=1,2,\dots, n$

Note that $e_i^{(k)}$ , the error of $x_i^{(k)}$ , is also involved in calculating $E^k$ .

Consequently,

$|e_i^{k+1}|\le\frac{1}{|A_{ii}|}\sum_{j=1,j\ne i}^{n}|A_{ij}||e_j^{(k)}|\le\frac{1}{|A_{ii}|}\sum_{j=1, j\ne i}^{n}|A_{ij}|E^k$

or,

$|e_i^{k+1}|\le\left(\sum_{j=1, j\ne i}^{n}\frac{|A_{ij}|}{|A_{ii}|}\right)E^k$

This indicates that if the positive value $\sum_{j=1, j\ne i}^{n}\frac{|A_{ij}|}{|A_{ii}|}<1$ , then,

$|e_i^{k+1}|<E^k$

which reads the error at $k+1$ iteration is strictly less than the error at k-th iteration. Progressively, the error decreases through the iterations and convergence occurs.

In summary, the “diagonal dominance” condition $\sum_{j=1, j\ne i}^{n}\frac{|A_{ij}|}{|A_{ii}|}<1$ which can also be written as

$|A_{ii}|>\sum_{j=1, j\ne i}^{n}|A_{ij}|$