Previous section

5.2. Iteration methods of the form (k + 1) = G(k) +

Assume that the coefficient matrix A of a system of equations, A = , is a regular n x n matrix. Then the system of equations has a unique solution . Convert the equation A = (in same way or another) into the form

(1)

= G + .

G is a so-called iteration matrix. G and can be chosen in different ways so that we obtain different iteration methods. Form the following iteration formula:

(2)

(k + 1) = G (k) + ,    k = 0, 1, 2, ....

Proposition 2. If the matrix equations A = ja = G + are equivalent and if ||G|| 1, then the sequence ( (k)) of vectors defined by (2) converges to the solution of the equation A = .

Proof.

||(k + 1) - || = ||G (k) + - ||
= ||G (k) - G|| = ||G ( (k) - )||
||G|| || (k) - ||
||G|| 2 || (k - 1) - ||
:
||G||k + 1 || (0) - || - > 0,    k - > .

The condition ||G|| 1 is sufficient for the convergence, but not necessary, i.e., the iteration sequence may converge even if ||G|| 1.

It can be shown that a necessary and sufficient condition for convergence is

(G) < 1

where (G) is the spectral radius of the matrix G,

(G) = max {| | : is an eigenvalue of G}.

The error in the approximation (k) can be estimated by the formula

(3)

|| (k) - || [ ||G|| / ( 1 - ||G|| ) ] || (k) - (k - 1)||

because

|| (k) - || = || (k) - (k + 1) + (k + 1) - ||
|| (k + 1) - (k)|| + || (k + 1) - ||
||G|| || (k) - (k - 1)|| + ||G|| || (k) - ||.


Exercises: E54
Previous section
Contents
Next section