where A is an n×n matrix. In many applications, the matrix A is huge and composed mainly of
zeros. For such matrices, the method of Gauss elimination (row operations) is not a good way to
solve the system because the row operations can destroy the zeros and storing all those zeros takes
a lot of room in a computer. These systems are called sparse. To solve them, it is common to use
an iterative technique. I am following the treatment given to this subject by Nobel and Daniel
[21].
Definition 13.5.1The Jacobi iterative technique, also called the method of simultaneouscorrectionsis defined as follows. Let x^{1}be an initial vector, say the zero vector or someother vector. The method generates a succession of vectors, x^{2},x^{3},x^{4},
⋅⋅⋅
and hopefullythis sequence of vectors will converge to the solution to 13.12. The vectors in this listare called iterates and they are obtained according to the following procedure. LettingA =
The matrix on the left in 13.14 is obtained by retaining the main diagonal of A and
setting every other entry equal to zero. The matrix on the right in 13.14 is obtained
from A by setting every diagonal entry equal to zero and retaining all the other entries
unchanged.
Example 13.5.2Use the Jacobi method to solve the system
Of course this is solved most easily using row reductions. The Jacobi method is useful when
the matrix is very large. This example is just to illustrate how the method works. First lets solve it
using row operations. The exact solution from row reduction is
( 6- 11- 8- 25 )
29 29 29 29
, which in
terms of decimals is approximately equal to
( )
0.207 0.379 0.276 0.862 T .
In terms of the matrices, the Jacobi iteration is of the form
You can keep going like this. Recall the solution is approximately equal to
( )T
0.206 0.379 0.275 0.862
so you see that with no care at all and only 6 iterations, an approximate solution has been
obtained which is not too far off from the actual solution.
Definition 13.5.3The Gauss Seidel method,also called the method of successive corrections isgiven as follows. For A =
(aij)
, the iterates for the problem Ax = bare obtained according to theformula
i n
∑ a xr+1= − ∑ a xr+ b . (13.16)
j=1 ij j j=i+1 ij j i
In words, you set every entry in the original matrix which is strictly above the main diagonal
equal to zero to obtain the matrix on the left. To get the matrix on the right, you set every entry
of A which is on or below the main diagonal equal to zero. Using the iteration procedure of 13.16
directly, the Gauss Seidel method makes use of the very latest information which is available at
that stage of the computation.
The following example is the same as the example used to illustrate the Jacobi
method.
Example 13.5.4Use the Gauss Seidel method to solve the system
This is fairly close to the answer. You could continue doing these iterates and it appears they
converge to the solution. Now consider the following example.
Example 13.5.5Use the Gauss Seidel method to solve the system
It appears that it moved the initial guess far from the solution even though you started with one
which was initially close to the solution. This is discouraging. However, you can’t expect the
method to work well after only one iteration. Unfortunately, if you do multiple iterations, the
iterates never seem to get close to the actual solution. Why is the process which 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)
(13.18)
are of the form
r+1 r
Bx = − Cx + b
where A = B + C. In the Jacobi procedure, the matrix C was obtained by setting the diagonal of
A equal to zero and leaving all other entries the same while the matrix B was obtained by making
every entry of A equal to zero other than the diagonal entries which are left unchanged. In the
Gauss Seidel procedure, the matrix B was obtained from A by making every 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 to zero and leaving the others
unchanged. Thus in the Jacobi procedure, B is a diagonal matrix while in the Gauss Seidel
procedure, B is lower triangular. Using matrices to explicitly solve for the iterates,
yields
r+1 −1 r −1
x = − B Cx + B b. (13.19)
(13.19)
This is what you would never have the computer do but this is what will allow the statement of a
theorem which gives the condition for convergence of these and all other similar methods.
Recall the definition of the spectral radius of M,ρ
< 1.Then the iterates in 13.19converge to the uniquesolution of 13.18.
I will prove this theorem in the next section. The proof depends on analysis which should not
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 easy to
give one in the case of the Jacobi method. Suppose the matrix A is diagonally dominant. That is
|aii|
>∑_{j≠i}
|aij|
. Then B would be the diagonal matrix consisting of the entries a_{ii}. You need to
find the size of λ where
−1
B Cx = λx
Thus you need
(λB − C)x = 0
Now if
|λ|
≥ 1, then the matrix λB − C is diagonally dominant and so this matrix will be
invertible so λ is not an eigenvalue. Hence the only eigenvalues have absolute value less than
1.
You might try a similar argument in the case of the Gauss Seidel method.