Open Educational Resources

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}|\]

is sufficient for the convergence of the Jacobi. This completes the proof \blacksquare.

Lecture Video

The following video covers the convergence of the Jacobi and Gauss-Seidel Methods.

Leave a Reply

Your email address will not be published. Required fields are marked *