View source for Simple-iteration method

<!--
s0852501.png
$#A+1 = 42 n = 0
$#C+1 = 42 : ~/encyclopedia/old_files/data/S085/S.0805250 Simple\AAhiteration method
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

A method for approximately solving a system of linear algebraic equations  $  Ax = b $
that can be transformed to the form  $  x = Bx + c $
and whose solution is looked for as the limit of a sequence  $  x  ^ {k+1} = B x  ^ {k} + c $, 
$  k = 0 , 1 \dots $
where  $  x  ^ {0} $
is an initial approximation. In order that the simple-iteration method converges for any initial approximation  $  x  ^ {0} $
it is necessary and sufficient that all eigenvalues of  $  B $
are less than one in modulus; it is sufficient that some norm of  $  B $
is less than one. If in some norm, compatible with the norm of a vector  $  x $, 
$  B $
satisfies  $  \| B \| \leq  \rho < 1 $, 
then the simple-iteration method converges at the rate of a geometric series and the estimate

$$ 
\| x  ^ {m} - x \|  \leq   \rho  ^ {m} \| x  ^ {0} - x \|
$$

holds for its error.

In the case of a cubic, octahedral or spherical vector norm, the condition  $  \| B \| \leq  \rho $
is fulfilled if

1)  $  \sum _ {j=1}  ^ {n} | b _ {ij} | \leq  \rho $, 
$  i = 1 \dots n $;

2)  $  \sum _ {i=1}  ^ {n} | b _ {ij} | \leq  \rho $, 
$  j = 1 \dots n $;

3)  $  \sum _ {i , j = 1 }   ^ {n} b _ {ij}  ^ {2} \leq  \rho  ^ {2} $.

The simplest version of the method corresponds to the case when one takes  $  I - A $, 
where  $  I $
is the identity matrix, for  $  B $. 
If all diagonal entries of  $  A $
are non-zero, then, choosing  $  b = D  ^ {-1} ( D - A ) $
and  $  c = D  ^ {-1} b $, 
where  $  D $
is the diagonal matrix with as diagonal entries those of  $  A $, 
one obtains the [[Jacobi method|Jacobi method]] or the method of simultaneous displacement.

A particular case of the simple-iteration method is the method with  $  B = I - \tau A $
and  $  c = \tau b $, 
where  $  \tau $
is an iteration parameter, chosen from the condition that the norm of  $  I - \tau A $
is minimal with respect to  $  \tau $. 
If  $  \gamma _ {1} $
and  $  \gamma _ {2} $
are the minimal and maximal eigenvalues of a symmetric positive-definite matrix  $  A $
and  $  \tau = 2 / ( \gamma _ {1} + \gamma _ {2} ) $, 
then one has for the matrix  $  B $
in the spherical norm the estimate  $  \| B \| \leq  \rho $, 
with  $  \rho = ( \gamma _ {2} - \gamma _ {1} ) / ( \gamma _ {2} + \gamma _ {1} ) < 1 $.

For a system of non-linear algebraic equations

$$ 
\phi _ {i} ( x)  =  0 ,\  1 \leq  i \leq  n ,\  x = ( x _ {1} \dots x _ {n} ) ,
$$

the simple-iteration method has the form

$$ 
x _ {i}  ^ {k+1}  =  x _ {i}  ^ {k} - \tau \phi _ {i} ( x  ^ {k} ) ,\  1 \leq 
i \leq  n ,\  k \geq  0 .
$$

The problem of choosing the iteration parameter  $  \tau $
is solved in dependence on the differentiability properties of the  $  \phi _ {i} $. 
Often it is subjected to the requirement that the method converges locally in a neighbourhood of a solution.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  D.K. Faddeev,   V.N. Faddeeva,   "Computational methods of linear algebra" , Freeman  (1963)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  I.S. Berezin,   N.P. Zhidkov,   "Computing methods" , Pergamon  (1973)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  J.M. Ortega,   W.C. Rheinboldt,   "Iterative solution of non-linear equations in several variables" , Acad. Press  (1970)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.A. Samarskii,   E.S. Nikolaev,   "Numerical methods for grid equations" , '''1–2''' , Birkhäuser  (1989)  (Translated from Russian)</TD></TR></table>