### 2 Do these iterative methods always work?

No. It is not difficult to invent examples where the iteration fails to approach the solution of $AX=B$ . The key point is related to matrix norms seen in the preceding Section.

The two iterative methods we encountered above are both special cases of the general form

$\phantom{\rule{2em}{0ex}}{X}^{\left(k+1\right)}=M{X}^{\left(k\right)}+N.$

1. For the Jacobi method we choose $M=-{D}^{-1}\left(L+U\right)$ and $N={D}^{-1}B$ .
2. For the Gauss-Seidel method we choose $M=-{\left(D+L\right)}^{-1}U$ and $N={\left(D+L\right)}^{-1}B$ .

The following Key Point gives the main result.

##### Key Point 13

For the iterative process ${X}^{\left(k+1\right)}=M{X}^{\left(k\right)}+N$ the iteration will converge to a solution if the norm of $M$ is less than 1 .

Care is required in understanding what Key Point 13 says. Remember that there are lots of different ways of defining the norm of a matrix (we saw three of them). If you can find a norm ( any norm ) such that the norm of $M$ is less than 1, then the iteration will converge. It doesn’t matter if there are other norms which give a value greater than 1, all that matters is that there is one norm that is less than 1.

Key Point 13 above makes no reference to the starting “guess" ${X}^{\left(0\right)}$ . The convergence of the iteration is independent of where you start! (Of course, if we start with a really bad initial guess then we can expect to need lots of iterations.)

Show that the Jacobi iteration used to approximate the solution of

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccc}\hfill 4\hfill & \hfill -1\hfill & \hfill -1\hfill \\ \hfill 1\hfill & \hfill -5\hfill & \hfill -2\hfill \\ \hfill -1\hfill & \hfill 0\hfill & \hfill 2\hfill \end{array}\right]\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \\ \hfill {x}_{3}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 2\hfill \\ \hfill 3\hfill \end{array}\right]$

is certain to converge. (Hint: calculate the norm of $-{D}^{-1}\left(L+U\right)$ .)

The Jacobi iteration matrix is

$\begin{array}{rcll}-{D}^{-1}\left(L+U\right)& =& {\left[\begin{array}{ccc}\hfill 4\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill -5\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 2\hfill \end{array}\right]}^{-1}\left[\begin{array}{ccc}\hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill -1\hfill & \hfill 0\hfill & \hfill 2\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right]=\left[\begin{array}{ccc}\hfill 0.25\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill -0.2\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0.5\hfill \end{array}\right]\left[\begin{array}{ccc}\hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill -1\hfill & \hfill 0\hfill & \hfill 2\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right]& \text{}\\ & =& \left[\begin{array}{ccc}\hfill 0\hfill & \hfill 0.25\hfill & \hfill 0.25\hfill \\ \hfill -0.2\hfill & \hfill 0\hfill & \hfill 0.4\hfill \\ \hfill 0.5\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right]& \text{}\end{array}$

and the infinity norm of this matrix is the maximum of $0.25+0.25$ , $0.2+0.4$ and $0.5$ , that is

$\phantom{\rule{2em}{0ex}}∥-{D}^{-1}\left(L+U\right){∥}_{\infty }=0.6$

which is less than 1 and therefore the iteration will converge.

#### 2.1 Guaranteed convergence

If the matrix has the property that it is strictly diagonally dominant , which means that the diagonal entry is larger in magnitude than the absolute sum of the other entries on that row, then both Jacobi and Gauss-Seidel are guaranteed to converge. The reason for this is that if $A$ is strictly diagonally dominant then the iteration matrix $M$ will have an infinity norm that is less than 1.

A small system is the subject of Example 20 below. A large system with slow convergence is the subject of Engineering Example 1 on page 62.

##### Example 20

Show that $A=\left[\begin{array}{ccc}\hfill 4\hfill & \hfill -1\hfill & \hfill -1\hfill \\ \hfill 1\hfill & \hfill -5\hfill & \hfill -2\hfill \\ \hfill -1\hfill & \hfill 0\hfill & \hfill 2\hfill \end{array}\right]$ is strictly diagonally dominant.

##### Solution

Looking at the diagonal entry of each row in turn we see that

$\begin{array}{rcll}4& >& |-1|+|-1|=2\phantom{\rule{1em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}& \text{}\\ \left|-5\right|& >& 1+\left|-2\right|=3& \text{}\\ 2& >& \left|-1\right|+0=1& \text{}\end{array}$

and this means that the matrix is strictly diagonally dominant.

Given that $A$ above is strictly diagonally dominant it is certain that both Jacobi and Gauss-Seidel will converge.

#### 2.2 What’s so special about strict diagonal dominance?

In many applications we can be certain that the coefficient matrix $A$ will be strictly diagonally dominant. We will see examples of this in HELM booklet  32 and HELM booklet  33 when we consider approximating solutions of differential equations.

##### Exercises
1. Consider the system

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{cc}\hfill 2\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 2\hfill \end{array}\right]\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 2\hfill \\ \hfill -5\hfill \end{array}\right]$

1. Use the starting guess ${X}^{\left(0\right)}=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill -1\hfill \end{array}\right]$ in an implementation of the Jacobi method to show that ${X}^{\left(1\right)}=\left[\begin{array}{c}\hfill 1.5\hfill \\ \hfill -3\hfill \end{array}\right]$ . Find ${X}^{\left(2\right)}$ and ${X}^{\left(3\right)}$ .
2. Use the starting guess ${X}^{\left(0\right)}=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill -1\hfill \end{array}\right]$ in an implementation of the Gauss-Seidel method to show that ${X}^{\left(1\right)}=\left[\begin{array}{c}\hfill 1.5\hfill \\ \hfill -3.25\hfill \end{array}\right]$ . Find ${X}^{\left(2\right)}$ and ${X}^{\left(3\right)}$ .

(Hint: it might help you to know that the exact solution is $\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 3\hfill \\ \hfill -4\hfill \end{array}\right]$ .)

1. Show that the Jacobi iteration applied to the system

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{cccc}\hfill 5\hfill & \hfill -1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill -1\hfill & \hfill 5\hfill & \hfill -1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 5\hfill & \hfill -1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -1\hfill & \hfill 5\hfill \end{array}\right]\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \\ \hfill {x}_{3}\hfill \\ \hfill {x}_{4}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 7\hfill \\ \hfill -10\hfill \\ \hfill -6\hfill \\ \hfill 16\hfill \end{array}\right]$

can be written

$\phantom{\rule{2em}{0ex}}{X}^{\left(k+1\right)}=\left[\begin{array}{cccc}\hfill 0\hfill & \hfill 0.2\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0.2\hfill & \hfill 0\hfill & \hfill 0.2\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0.2\hfill & \hfill 0\hfill & \hfill 0.2\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0.2\hfill & \hfill 0\hfill \end{array}\right]{X}^{\left(k\right)}+\left[\begin{array}{c}\hfill 1.4\hfill \\ \hfill -2\hfill \\ \hfill -1.2\hfill \\ \hfill 3.2\hfill \end{array}\right].$

2. Show that the method is certain to converge and calculate the first three iterations using

zero starting values.

(Hint: the exact solution to the stated problem is $\left[\begin{array}{c}\hfill 1\hfill \\ \hfill -2\hfill \\ \hfill 1\hfill \\ \hfill 3\hfill \end{array}\right]$ .)

1. $\phantom{\rule{2em}{0ex}}2{x}_{1}^{\left(1\right)}=2-1{x}_{2}^{\left(0\right)}=2$

and therefore ${x}_{1}^{\left(1\right)}=1.5$

$\phantom{\rule{2em}{0ex}}2{x}_{2}^{\left(1\right)}=-5-1{x}_{1}^{\left(0\right)}=-6$

which implies that ${x}_{2}^{\left(1\right)}=-3$ . These two values give the required entries in ${X}^{\left(1\right)}$ . A second and third iteration follow in a similar way to give

$\phantom{\rule{2em}{0ex}}{X}^{\left(2\right)}=\left[\begin{array}{c}\hfill 2.5\\ \hfill -3.25\end{array}\right]\phantom{\rule{2em}{0ex}}\text{and}\phantom{\rule{2em}{0ex}}{X}^{\left(3\right)}=\left[\begin{array}{c}\hfill 2.625\\ \hfill -3.75\end{array}\right]$

2. $\phantom{\rule{2em}{0ex}}2{x}_{1}^{\left(1\right)}=2-1{x}_{2}^{\left(0\right)}=3$

and therefore ${x}_{1}^{\left(1\right)}=1.5$ . This new approximation to ${x}_{1}$ is used straight away when finding a new approximation to ${x}_{2}^{\left(1\right)}$ .

$\phantom{\rule{2em}{0ex}}2{x}_{2}^{\left(1\right)}=-5-1{x}_{1}^{\left(1\right)}=-6.5$

which implies that ${x}_{2}^{\left(1\right)}=-3.25$ . These two values give the required entries in ${X}^{\left(1\right)}$ . A second and third iteration follow in a similar way to give

$\phantom{\rule{2em}{0ex}}{X}^{\left(2\right)}=\left[\begin{array}{c}\hfill 2.625\\ \hfill -3.8125\end{array}\right]\phantom{\rule{2em}{0ex}}\text{and}\phantom{\rule{2em}{0ex}}{X}^{\left(3\right)}=\left[\begin{array}{c}\hfill 2.906250\\ \hfill -3.953125\end{array}\right]$

where ${X}^{\left(3\right)}$ is given to 6 decimal places

1. In this case $D=\left[\begin{array}{cccc}\hfill 5\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 5\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 5\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 5\hfill \end{array}\right]$ and therefore ${D}^{-1}=\left[\begin{array}{cccc}\hfill 0.2\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0.2\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0.2\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0.2\hfill \end{array}\right]$ .

So the iteration matrix $M\phantom{\rule{0.3em}{0ex}}=\phantom{\rule{0.3em}{0ex}}{D}^{-1}\left[\begin{array}{cccc}\hfill 0\hfill & \hfill -1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill -1\hfill & \hfill 0\hfill & \hfill -1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 0\hfill & \hfill -1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -1\hfill & \hfill 0\hfill \end{array}\right]\phantom{\rule{0.3em}{0ex}}=\phantom{\rule{0.3em}{0ex}}\left[\phantom{\rule{0.3em}{0ex}}\begin{array}{cccc}\hfill 0\hfill & \hfill 0.2\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0.2\hfill & \hfill 0\hfill & \hfill 0.2\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0.2\hfill & \hfill 0\hfill & \hfill 0.2\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0.2\hfill & \hfill 0\hfill \end{array}\phantom{\rule{0.3em}{0ex}}\right]$

and that the Jacobi iteration takes the form

$\phantom{\rule{2em}{0ex}}{X}^{\left(k+1\right)}=M{X}^{\left(k\right)}+{M}^{-1}\left[\begin{array}{c}\hfill 7\hfill \\ \hfill -10\hfill \\ \hfill -6\hfill \\ \hfill 16\hfill \end{array}\right]=\left[\begin{array}{cccc}\hfill 0\hfill & \hfill 0.2\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0.2\hfill & \hfill 0\hfill & \hfill 0.2\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0.2\hfill & \hfill 0\hfill & \hfill 0.2\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0.2\hfill & \hfill 0\hfill \end{array}\right]{X}^{\left(k\right)}+\left[\begin{array}{c}\hfill 1.4\hfill \\ \hfill -2\hfill \\ \hfill -1.2\hfill \\ \hfill 3.2\hfill \end{array}\right]$

as required.

2. Using the starting values ${x}_{1}^{\left(0\right)}={x}_{2}^{\left(0\right)}={x}_{3}^{\left(0\right)}={x}_{4}^{\left(0\right)}=0$ , the first iteration of the Jacobi method gives $\begin{array}{rcll}{x}_{1}^{1}& =& 0.2{x}_{2}^{0}+1.4=1.4& \text{}\\ {x}_{2}^{1}& =& 0.2\left({x}_{1}^{0}+{x}_{3}^{0}\right)-2=-2& \text{}\\ {x}_{3}^{1}& =& 0.2\left({x}_{2}^{0}+{x}_{4}^{0}\right)-1.2=-1.2\phantom{\rule{1em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}& \text{}\\ {x}_{4}^{1}& =& 0.2{x}_{3}^{0}+3.2=3.2& \text{}\end{array}$

The second iteration is

$\begin{array}{rcll}{x}_{1}^{2}& =& 0.2{x}_{2}^{1}+1.4=1& \text{}\\ {x}_{2}^{2}& =& 0.2\left({x}_{1}^{1}+{x}_{3}^{1}\right)-2=-1.96& \text{}\\ {x}_{3}^{2}& =& 0.2\left({x}_{2}^{1}+{x}_{4}^{1}\right)-1.2=-0.96\phantom{\rule{1em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}& \text{}\\ {x}_{4}^{2}& =& 0.2{x}_{3}^{1}+3.2=2.96& \text{}\end{array}$

And the third iteration is

$\begin{array}{rcll}{x}_{1}^{3}& =& 0.2{x}_{2}^{2}+1.4=1.008& \text{}\\ {x}_{2}^{3}& =& 0.2\left({x}_{1}^{2}+{x}_{3}^{2}\right)-2=-1.992\phantom{\rule{1em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}& \text{}\\ {x}_{3}^{3}& =& 0.2\left({x}_{2}^{2}+{x}_{4}^{2}\right)-1.2=-1& \text{}\\ {x}_{4}^{3}& =& 0.2{x}_{3}^{2}+3.2=3.008& \text{}\end{array}$