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 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)
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
where (G) is the spectral radius of the matrix G,
The error in the approximation ^{ (k)} can be estimated by the formula
(3)
because
||^{ (k)} - || = ||^{ (k)} - ^{ (k + 1)} + ^{ (k + 1)} - || | |
||^{ (k + 1)} - ^{ (k)}|| + ||^{ (k + 1)} - || | |
||G|| ||^{ (k)} - ^{ (k - 1)}|| + ||G|| ||^{ (k)} - ||. | |