Simple-iteration method

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 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

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