1 Iterative methods

Suppose we have the system of equations

$AX=B.$

The aim here is to find a sequence of approximations which gradually approach $X$ . We will denote these approximations

$X^{\left(0\right)},X^{\left(1\right)},X^{\left(2\right)},\dots ,X^{\left(k\right)},\dots$

where $X^{\left(0\right)}$ is our initial “guess", and the hope is that after a short while these successive iterates will be so close to each other that the process can be deemed to have converged to the required solution $X$ .

It is convenient to split the matrix $A$ into three parts. We write

$A=L+D+U$

where $L$ consists of the elements of $A$ strictly below the diagonal and zeros elsewhere; $D$ is a diagonal matrix consisting of the diagonal entries of $A$ ; and $U$ consists of the elements of $A$ strictly above the diagonal. Note that $L$ and $U$ here are not the same matrices as appeared in the $LU$ decomposition! The current $L$ and $U$ are much easier to find.

For example

$\begin{array}{ccccccc}\hfill \underset{⏟}{\left[\begin{array}{cc}\hfill 3\hfill & \hfill -4\hfill \\ \hfill 2\hfill & \hfill 1\hfill \end{array}\right]}\hfill & \hfill =\hfill & \hfill \underset{⏟}{\left[\begin{array}{cc}\hfill 0\hfill & \hfill 0\hfill \\ \hfill 2\hfill & \hfill 0\hfill \end{array}\right]}\hfill & \hfill +\hfill & \hfill \underset{⏟}{\left[\begin{array}{cc}\hfill 3\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill \end{array}\right]}\hfill & \hfill +\hfill & \hfill \underset{⏟}{\left[\begin{array}{cc}\hfill 0\hfill & \hfill -4\hfill \\ \hfill 0\hfill & \hfill 0\hfill \end{array}\right]}\hfill \\ \hfill \uparrow \hfill & \hfill \hfill & \hfill \uparrow \hfill & \hfill \hfill & \hfill \uparrow \hfill & \hfill \hfill & \hfill \uparrow \hfill \\ \hfill A\hfill & \hfill =\hfill & \hfill L\hfill & \hfill +\hfill & \hfill D\hfill & \hfill +\hfill & \hfill U\hfill \\ \hfill \hfill \end{array}$

and

$\begin{array}{ccccccc}\hfill \underset{⏟}{\left[\begin{array}{ccc}\hfill 2\hfill & \hfill -6\hfill & \hfill 1\hfill \\ \hfill 3\hfill & \hfill -2\hfill & \hfill 0\hfill \\ \hfill 4\hfill & \hfill -1\hfill & \hfill 7\hfill \end{array}\right]}\hfill & \hfill =\hfill & \hfill \underset{⏟}{\left[\begin{array}{ccc}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 3\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 4\hfill & \hfill -1\hfill & \hfill 0\hfill \end{array}\right]}\hfill & \hfill +\hfill & \hfill \underset{⏟}{\left[\begin{array}{ccc}\hfill 2\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill -2\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 7\hfill \end{array}\right]}\hfill & \hfill +\hfill & \hfill \underset{⏟}{\left[\begin{array}{ccc}\hfill 0\hfill & \hfill -6\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right]}\hfill \\ \hfill \uparrow \hfill & \hfill \hfill & \hfill \uparrow \hfill & \hfill \hfill & \hfill \uparrow \hfill & \hfill \hfill & \hfill \uparrow \hfill \\ \hfill A\hfill & \hfill =\hfill & \hfill L\hfill & \hfill +\hfill & \hfill D\hfill & \hfill +\hfill & \hfill U\hfill \\ \hfill \hfill \end{array}$ and, more generally for $3\times 3$ matrices

$\begin{array}{ccccccc}\hfill \underset{⏟}{\left[\begin{array}{ccc}\hfill \bullet \hfill & \hfill \bullet \hfill & \hfill \bullet \hfill \\ \hfill \bullet \hfill & \hfill \bullet \hfill & \hfill \bullet \hfill \\ \hfill \bullet \hfill & \hfill \bullet \hfill & \hfill \bullet \hfill \end{array}\right]}\hfill & \hfill =\hfill & \hfill \underset{⏟}{\left[\begin{array}{ccc}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill \bullet \hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill \bullet \hfill & \hfill \bullet \hfill & \hfill 0\hfill \end{array}\right]}\hfill & \hfill +\hfill & \hfill \underset{⏟}{\left[\begin{array}{ccc}\hfill \bullet \hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill \bullet \hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill \bullet \hfill \end{array}\right]}\hfill & \hfill +\hfill & \hfill \underset{⏟}{\left[\begin{array}{ccc}\hfill 0\hfill & \hfill \bullet \hfill & \hfill \bullet \hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill \bullet \hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right]}.\hfill \\ \hfill \uparrow \hfill & \hfill \hfill & \hfill \uparrow \hfill & \hfill \hfill & \hfill \uparrow \hfill & \hfill \hfill & \hfill \uparrow \hfill \\ \hfill A\hfill & \hfill =\hfill & \hfill L\hfill & \hfill +\hfill & \hfill D\hfill & \hfill +\hfill & \hfill U.\hfill \\ \hfill \hfill \end{array}$

1.1 The Jacobi iteration

The simplest iterative method is called Jacobi iteration and the basic idea is to use the $A=L+D+U$ partitioning of $A$ to write $AX=B$ in the form

$DX=-\left(L+U\right)X+B.$

We use this equation as the motivation to define the iterative process

$D{X}^{\left(k+1\right)}=-\left(L+U\right)X^{\left(k\right)}+B$

which gives $X^{\left(k+1\right)}$ as long as $D$ has no zeros down its diagonal, that is as long as $D$ is invertible. This is Jacobi iteration.

Example 18

Use the Jacobi iteration to approximate the solution $X=\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \\ \hfill x_3\hfill \end{array}\right]$ of $\left[\begin{array}{ccc}\hfill 8\hfill & \hfill 2\hfill & \hfill 4\hfill \\ \hfill 3\hfill & \hfill 5\hfill & \hfill 1\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill 4\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 -16\hfill \\ \hfill 4\hfill \\ \hfill -12\hfill \end{array}\right].$

Use the initial guess $X^{\left(0\right)}=\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \end{array}\right]$ .

Solution

In this case $D=\left[\begin{array}{ccc}\hfill 8\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 5\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 4\hfill \end{array}\right]$ and $L+U=\left[\begin{array}{ccc}\hfill 0\hfill & \hfill 2\hfill & \hfill 4\hfill \\ \hfill 3\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill 0\hfill \end{array}\right]$ .

First iteration .

The first iteration is $D{X}^{\left(1\right)}=-\left(L+U\right)X^{\left(0\right)}+B$ , or in full

$\left[\begin{array}{ccc}\hfill 8\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 5\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 4\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1^{\left(1\right)}\hfill \\ \hfill x_2^{\left(1\right)}\hfill \\ \hfill x_3^{\left(1\right)}\hfill \end{array}\right]=\left[\begin{array}{ccc}\hfill 0\hfill & \hfill -2\hfill & \hfill -4\hfill \\ \hfill -3\hfill & \hfill 0\hfill & \hfill -1\hfill \\ \hfill -2\hfill & \hfill -1\hfill & \hfill 0\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1^{\left(0\right)}\hfill \\ \hfill x_2^{\left(0\right)}\hfill \\ \hfill x_3^{\left(0\right)}\hfill \end{array}\right]+\left[\begin{array}{c}\hfill -16\hfill \\ \hfill 4\hfill \\ \hfill -12\hfill \end{array}\right]=\left[\begin{array}{c}\hfill -16\hfill \\ \hfill 4\hfill \\ \hfill -12\hfill \end{array}\right],$

since the initial guess was $x_1^{\left(0\right)}=x_2^{\left(0\right)}=x_3^{\left(0\right)}=0$ .

Taking this information row by row we see that

Thus the first Jacobi iteration gives us $X^{\left(1\right)}=\left[\begin{array}{c}\hfill x_1^{\left(1\right)}\hfill \\ \hfill x_2^{\left(1\right)}\hfill \\ \hfill x_3^{\left(1\right)}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill -2\hfill \\ \hfill 0.8\hfill \\ \hfill -3\hfill \end{array}\right]$ as an approximation to $X$ .

Second iteration .

The second iteration is $D{X}^{\left(2\right)}=-\left(L+U\right)X^{\left(1\right)}+B$ , or in full

$\left[\begin{array}{ccc}\hfill 8\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 5\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 4\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1^{\left(2\right)}\hfill \\ \hfill x_2^{\left(2\right)}\hfill \\ \hfill x_3^{\left(2\right)}\hfill \end{array}\right]=\left[\begin{array}{ccc}\hfill 0\hfill & \hfill -2\hfill & \hfill -4\hfill \\ \hfill -3\hfill & \hfill 0\hfill & \hfill -1\hfill \\ \hfill -2\hfill & \hfill -1\hfill & \hfill 0\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1^{\left(1\right)}\hfill \\ \hfill x_2^{\left(1\right)}\hfill \\ \hfill x_3^{\left(1\right)}\hfill \end{array}\right]+\left[\begin{array}{c}\hfill -16\hfill \\ \hfill 4\hfill \\ \hfill -12\hfill \end{array}\right].$

Taking this information row by row we see that

Therefore the second iterate approximating $X$ is $X^{\left(2\right)}=\left[\begin{array}{c}\hfill x_1^{\left(2\right)}\hfill \\ \hfill x_2^{\left(2\right)}\hfill \\ \hfill x_3^{\left(2\right)}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill -0.7\hfill \\ \hfill 2.6\hfill \\ \hfill -2.2\hfill \end{array}\right]$ .

Third iteration .

The third iteration is $D{X}^{\left(3\right)}=-\left(L+U\right)X^{\left(2\right)}+B$ , or in full

$\left[\begin{array}{ccc}\hfill 8\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 5\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 4\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1^{\left(3\right)}\hfill \\ \hfill x_2^{\left(3\right)}\hfill \\ \hfill x_3^{\left(3\right)}\hfill \end{array}\right]=\left[\begin{array}{ccc}\hfill 0\hfill & \hfill -2\hfill & \hfill -4\hfill \\ \hfill -3\hfill & \hfill 0\hfill & \hfill -1\hfill \\ \hfill -2\hfill & \hfill -1\hfill & \hfill 0\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1^{\left(2\right)}\hfill \\ \hfill x_2^{\left(2\right)}\hfill \\ \hfill x_3^{\left(2\right)}\hfill \end{array}\right]+\left[\begin{array}{c}\hfill -16\hfill \\ \hfill 4\hfill \\ \hfill -12\hfill \end{array}\right]$

Taking this information row by row we see that

Therefore the third iterate approximating $X$ is $X^{\left(3\right)}=\left[\begin{array}{c}\hfill x_1^{\left(3\right)}\hfill \\ \hfill x_2^{\left(3\right)}\hfill \\ \hfill x_3^{\left(3\right)}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill -1.55\hfill \\ \hfill 1.66\hfill \\ \hfill -3.3\hfill \end{array}\right]$ .

More iterations ...

Three iterations is plenty when doing these calculations by hand! But the repetitive nature of the process is ideally suited to its implementation on a computer. It turns out that the next few iterates are

$X^{\left(4\right)}=\left[\begin{array}{c}\hfill -0.765\hfill \\ \hfill 2.39\hfill \\ \hfill -2.64\hfill \end{array}\right],X^{\left(5\right)}=\left[\begin{array}{c}\hfill -1.277\hfill \\ \hfill 1.787\hfill \\ \hfill -3.215\hfill \end{array}\right],X^{\left(6\right)}=\left[\begin{array}{c}\hfill -0.839\hfill \\ \hfill 2.209\hfill \\ \hfill -2.808\hfill \end{array}\right],$

to 3 d.p. Carrying on even further $X^{\left(20\right)}=\left[\begin{array}{c}\hfill x_1^{\left(20\right)}\hfill \\ \hfill x_2^{\left(20\right)}\hfill \\ \hfill x_3^{\left(20\right)}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill -0.9959\hfill \\ \hfill 2.0043\hfill \\ \hfill -2.9959\hfill \end{array}\right]$ , to 4 d.p. After about 40 iterations successive iterates are equal to 4 d.p. Continuing the iteration even further causes the iterates to agree to more and more decimal places. The method converges to the exact answer

$X=\left[\begin{array}{c}\hfill -1\hfill \\ \hfill 2\hfill \\ \hfill -3\hfill \end{array}\right]$ .

The following Task involves calculating just two iterations of the Jacobi method.

Task!

Carry out two iterations of the Jacobi method to approximate the solution of

$\left[\begin{array}{ccc}\hfill 4\hfill & \hfill -1\hfill & \hfill -1\hfill \\ \hfill -1\hfill & \hfill 4\hfill & \hfill -1\hfill \\ \hfill -1\hfill & \hfill -1\hfill & \hfill 4\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]$

with the initial guess $X^{\left(0\right)}=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \\ \hfill 1\hfill \end{array}\right]$ .

Answer

The second iteration is $D{X}^{\left(1\right)}=-\left(L+U\right)X^{\left(0\right)}+B$ , that is,

$\left[\begin{array}{ccc}\hfill 4\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 4\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 4\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1^{\left(2\right)}\hfill \\ \hfill x_2^{\left(2\right)}\hfill \\ \hfill x_3^{\left(2\right)}\hfill \end{array}\right]=\left[\begin{array}{ccc}\hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1^{\left(0\right)}\hfill \\ \hfill x_2^{\left(0\right)}\hfill \\ \hfill x_3^{\left(0\right)}\hfill \end{array}\right]+\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 2\hfill \\ \hfill 3\hfill \end{array}\right]$

from which it follows that $X^{\left(2\right)}=\left[\begin{array}{c}\hfill 0.8125\hfill \\ \hfill 1\hfill \\ \hfill 1.1875\hfill \end{array}\right]$ .

Notice that at each iteration the first thing we do is get a new approximation for $x_1$ and then we continue to use the old approximation to $x_1$ in subsequent calculations for that iteration! Only at the next iteration do we use the new value. Similarly, we continue to use an old approximation to $x_2$ even after we have worked out a new one. And so on.

Given that the iterative process is supposed to improve our approximations why not use the better values straight away? This observation is the motivation for what follows.

1.2 Gauss-Seidel iteration

The approach here is very similar to that used in Jacobi iteration. The only difference is that we use new approximations to the entries of $X$ as soon as they are available. As we will see in the Example below, this means rearranging $\left(L+D+U\right)X=B$ slightly differently from what we did for Jacobi. We write

$\left(D+L\right)X=-UX+B$

and use this as the motivation to define the iteration

$\left(D+L\right)X^{\left(k+1\right)}=-U{X}^{\left(k\right)}+B.$

Example 19 which follows revisits the system of equations we saw earlier in this Section in Example 18.

Example 19

Use the Gauss-Seidel iteration to approximate the solution $X=\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \\ \hfill x_3\hfill \end{array}\right]$ of $\left[\begin{array}{ccc}\hfill 8\hfill & \hfill 2\hfill & \hfill 4\hfill \\ \hfill 3\hfill & \hfill 5\hfill & \hfill 1\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill 4\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 -16\hfill \\ \hfill 4\hfill \\ \hfill -12\hfill \end{array}\right].$ Use the initial guess $X^{\left(0\right)}=\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \end{array}\right]$ .

Solution

In this case $D+L=\left[\begin{array}{ccc}\hfill 8\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 3\hfill & \hfill 5\hfill & \hfill 0\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill 4\hfill \end{array}\right]$ and $U=\left[\begin{array}{ccc}\hfill 0\hfill & \hfill 2\hfill & \hfill 4\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right]$ .

First iteration .

The first iteration is $\left(D+L\right)X^{\left(1\right)}=-U{X}^{\left(0\right)}+B$ , or in full

$\left[\begin{array}{ccc}\hfill 8\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 3\hfill & \hfill 5\hfill & \hfill 0\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill 4\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1^{\left(1\right)}\hfill \\ \hfill x_2^{\left(1\right)}\hfill \\ \hfill x_3^{\left(1\right)}\hfill \end{array}\right]=\left[\begin{array}{ccc}\hfill 0\hfill & \hfill -2\hfill & \hfill -4\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1^{\left(0\right)}\hfill \\ \hfill x_2^{\left(0\right)}\hfill \\ \hfill x_3^{\left(0\right)}\hfill \end{array}\right]+\left[\begin{array}{c}\hfill -16\hfill \\ \hfill 4\hfill \\ \hfill -12\hfill \end{array}\right]=\left[\begin{array}{c}\hfill -16\hfill \\ \hfill 4\hfill \\ \hfill -12\hfill \end{array}\right],$

since the initial guess was $x_1^{\left(0\right)}=x_2^{\left(0\right)}=x_3^{\left(0\right)}=0$ .

Taking this information row by row we see that

(Notice how the new approximations to $x_1$ and $x_2$ were used immediately after they were found.)

Thus the first Gauss-Seidel iteration gives us $X^{\left(1\right)}=\left[\begin{array}{c}\hfill x_1^{\left(1\right)}\hfill \\ \hfill x_2^{\left(1\right)}\hfill \\ \hfill x_3^{\left(1\right)}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill -2\hfill \\ \hfill 2\hfill \\ \hfill -2.5\hfill \end{array}\right]$ as an approximation to $X$ .

Solution

Second iteration .

The second iteration is $\left(D+L\right)X^{\left(2\right)}=-U{X}^{\left(1\right)}+B$ , or in full

$\left[\begin{array}{ccc}\hfill 8\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 3\hfill & \hfill 5\hfill & \hfill 0\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill 4\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1^{\left(2\right)}\hfill \\ \hfill x_2^{\left(2\right)}\hfill \\ \hfill x_3^{\left(2\right)}\hfill \end{array}\right]=\left[\begin{array}{ccc}\hfill 0\hfill & \hfill -2\hfill & \hfill -4\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1^{\left(1\right)}\hfill \\ \hfill x_2^{\left(1\right)}\hfill \\ \hfill x_3^{\left(1\right)}\hfill \end{array}\right]+\left[\begin{array}{c}\hfill -16\hfill \\ \hfill 4\hfill \\ \hfill -12\hfill \end{array}\right]$

Taking this information row by row we see that

Therefore the second iterate approximating $X$ is $X^{\left(2\right)}=\left[\begin{array}{c}\hfill x_1^{\left(2\right)}\hfill \\ \hfill x_2^{\left(2\right)}\hfill \\ \hfill x_3^{\left(2\right)}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill -1.25\hfill \\ \hfill 2.05\hfill \\ \hfill -2.8875\hfill \end{array}\right]$ .

Third iteration .

The third iteration is $\left(D+L\right)X^{\left(3\right)}=-U{X}^{\left(2\right)}+B$ , or in full

$\left[\begin{array}{ccc}\hfill 8\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 3\hfill & \hfill 5\hfill & \hfill 0\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill 4\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1^{\left(3\right)}\hfill \\ \hfill x_2^{\left(3\right)}\hfill \\ \hfill x_3^{\left(3\right)}\hfill \end{array}\right]=\left[\begin{array}{ccc}\hfill 0\hfill & \hfill -2\hfill & \hfill -4\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1^{\left(2\right)}\hfill \\ \hfill x_2^{\left(2\right)}\hfill \\ \hfill x_3^{\left(2\right)}\hfill \end{array}\right]+\left[\begin{array}{c}\hfill -16\hfill \\ \hfill 4\hfill \\ \hfill -12\hfill \end{array}\right].$

Taking this information row by row we see that

to 4 d.p. Therefore the third iterate approximating $X$ is

$X^{\left(3\right)}=\left[\begin{array}{c}\hfill x_1^{\left(3\right)}\hfill \\ \hfill x_2^{\left(3\right)}\hfill \\ \hfill x_3^{\left(3\right)}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill -1.0687\hfill \\ \hfill 2.0187\hfill \\ \hfill -2.9703\hfill \end{array}\right].$

More iterations ...

Again, there is little to be learned from pushing this further by hand. Putting the procedure on a computer and seeing how it progresses is instructive, however, and the iteration continues as follows:

$X^{\left(4\right)}=\left[\begin{array}{c}\hfill -1.0195\hfill \\ \hfill 2.0058\hfill \\ \hfill -2.9917\hfill \end{array}\right],X^{\left(5\right)}=\left[\begin{array}{c}\hfill -1.0056\hfill \\ \hfill 2.0017\hfill \\ \hfill -2.9976\hfill \end{array}\right],X^{\left(6\right)}=\left[\begin{array}{c}\hfill -1.0016\hfill \\ \hfill 2.0005\hfill \\ \hfill -2.9993\hfill \end{array}\right],$

$X^{\left(7\right)}=\left[\begin{array}{c}\hfill -1.0005\hfill \\ \hfill 2.0001\hfill \\ \hfill -2.9998\hfill \end{array}\right],X^{\left(8\right)}=\left[\begin{array}{c}\hfill -1.0001\hfill \\ \hfill 2.0000\hfill \\ \hfill -2.9999\hfill \end{array}\right],X^{\left(9\right)}=\left[\begin{array}{c}\hfill -1.0000\hfill \\ \hfill 2.0000\hfill \\ \hfill -3.0000\hfill \end{array}\right]$

(to 4 d.p.). Subsequent iterates are equal to $X^{\left(9\right)}$ to this number of decimal places. The Gauss-Seidel iteration has converged to 4 d.p. in 9 iterations. It took the Jacobi method almost 40 iterations to achieve this!

Task!

Carry out two iterations of the Gauss-Seidel method to approximate the solution of

$\left[\begin{array}{ccc}\hfill 4\hfill & \hfill -1\hfill & \hfill -1\hfill \\ \hfill -1\hfill & \hfill 4\hfill & \hfill -1\hfill \\ \hfill -1\hfill & \hfill -1\hfill & \hfill 4\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]$

with the initial guess $X^{\left(0\right)}=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \\ \hfill 1\hfill \end{array}\right]$ .

Answer

The second iteration is $\left(D+L\right)X^{\left(1\right)}=-U{X}^{\left(0\right)}+B$ , that is,

$\left[\begin{array}{ccc}\hfill 4\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill -1\hfill & \hfill 4\hfill & \hfill 0\hfill \\ \hfill -1\hfill & \hfill -1\hfill & \hfill 4\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1^{\left(2\right)}\hfill \\ \hfill x_2^{\left(2\right)}\hfill \\ \hfill x_3^{\left(2\right)}\hfill \end{array}\right]=\left[\begin{array}{ccc}\hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1^{\left(1\right)}\hfill \\ \hfill x_2^{\left(1\right)}\hfill \\ \hfill x_3^{\left(1\right)}\hfill \end{array}\right]+\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 2\hfill \\ \hfill 3\hfill \end{array}\right]$

from which it follows that $X^{\left(2\right)}=\left[\begin{array}{c}\hfill 0.7773\hfill \\ \hfill 0.9873\hfill \\ \hfill 1.1912\hfill \end{array}\right]$ .