346 CHAPTER 13. NORMS

and so, multiplying by the inverse of the matrix on the left, the iteration reduces to thefollowing in terms of matrix multiplication.

xr+1 = −

0 4 0 0

0 −1 14 0

0 25 − 1

1015

0 − 15

120 − 1

10

xr +

1141234

 .

This time, I will pick an initial vector close to the answer. Let x1 =(

6 −1 1 12

)T.

This is very close to the answer. Now lets see what the Gauss Seidel iteration does to it.

x2 = −

0 4 0 0

0 −1 14 0

0 25 − 1

1015

0 − 15

120 − 1

10



6

−1

112

+

1141234

 =

5.0

−1.0

. 9

. 55

It appears that it moved the initial guess far from the solution even though you startedwith one which was initially close to the solution. This is discouraging. However, you can’texpect the method to work well after only one iteration. Unfortunately, if you do multipleiterations, the iterates never seem to get close to the actual solution. Why is the processwhich worked so well in the other examples not working here? A better question might be:Why does either process ever work at all?

Both iterative procedures for solving

Ax = b (13.18)

are of the formBxr+1 = −Cxr + b

where A = B + C. In the Jacobi procedure, the matrix C was obtained by setting thediagonal of A equal to zero and leaving all other entries the same while the matrix B wasobtained by making every entry of A equal to zero other than the diagonal entries which areleft unchanged. In the Gauss Seidel procedure, the matrix B was obtained from A by makingevery entry strictly above the main diagonal equal to zero and leaving the others unchanged,and C was obtained from A by making every entry on or below the main diagonal equal tozero and leaving the others unchanged. Thus in the Jacobi procedure, B is a diagonal matrixwhile in the Gauss Seidel procedure, B is lower triangular. Using matrices to explicitly solvefor the iterates, yields

xr+1 = −B−1Cxr +B−1b. (13.19)

This is what you would never have the computer do but this is what will allow the statementof a theorem which gives the condition for convergence of these and all other similar methods.Recall the definition of the spectral radius of M,ρ (M) , in Definition 13.3.1 on Page 335.

Theorem 13.5.6 Suppose ρ(B−1C

)< 1. Then the iterates in 13.19 converge to the unique

solution of 13.18.

I will prove this theorem in the next section. The proof depends on analysis which shouldnot be surprising because it involves a statement about convergence of sequences.

What is an easy to verify sufficient condition which will imply the above holds? It is easyto give one in the case of the Jacobi method. Suppose the matrix A is diagonally dominant.