View source for Iteration algorithm

A recursive algorithm realizing a sequence of point-to-set mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i0530101.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i0530102.png" /> is a topological space, that can be used to compute for an initial point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i0530103.png" /> a sequence of points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i0530104.png" /> by the formulas

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i0530105.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

The operation (1) is called an iteration, while the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i0530106.png" /> is called an iterative sequence.

Iteration methods (or methods of iterative approximation) are used both for finding a solution to an operator equation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i0530107.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

a minimum of a functional, eigen values and eigen vectors of an equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i0530108.png" />, etc., as well as for proving the existence of solutions to these problems. An iteration method (1) is called convergent for the initial approximation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i0530109.png" /> to a solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301010.png" /> of a problem considered if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301011.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301012.png" />.

Operators <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301013.png" /> for solving (2), given on a metric linear space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301014.png" />, are usually constructed by the formulas

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301015.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301016.png" /> is some sequence of operators determined by the type of the iteration method. The [[Contracting-mapping principle|contracting-mapping principle]] and its generalizations, or variational minimization methods for a functional related to the problem, lie at the basis of constructing iteration methods of type (1), (3). Various methods for constructing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301017.png" /> are used, e.g. variants of the [[Newton method|Newton method]] or method of descent (cf. [[Descent, method of|Descent, method of]]). One tries to choose the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301018.png" /> so that a fast convergence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301019.png" /> is ensured under the conditions that the numerical realization of the operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301020.png" />, for a given amount of computer memory, is sufficiently simple, has as low complexity as possible and is numerically stable. Iteration methods for solving linear problems have been well-developed and were well-studied. The iteration methods are divided here into linear and non-linear ones. The [[Gauss method|Gauss method]], the [[Seidel method|Seidel method]], the successive overrelaxation method (cf. [[Relaxation method|Relaxation method]]), and iteration methods with Chebyshev parameters belong to the linear methods; variational methods belong to the non-linear methods (e.g. the methods of steepest descent and conjugate gradients, the [[Minimal discrepancy method|minimal discrepancy method]], etc., cf. [[Steepest descent, method of|Steepest descent, method of]]; [[Conjugate gradients, method of|Conjugate gradients, method of]]). One of the efficient iteration methods is the method using Chebyshev parameters, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301021.png" /> is a self-adjoint operator with spectrum on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301022.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301023.png" />. This method provides an optimum (for given information on the boundaries of the spectrum) estimate of the convergence at a pre-assigned <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301024.png" />-th step. The method can be written in the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301025.png" /></td> </tr></table>

where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301026.png" /></td> </tr></table>

and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301027.png" /> is the expected number of iterations, and one uses in it a special permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301028.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301029.png" /> that mixes well for the stability of the roots of the Chebyshev polynomials. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301030.png" /> the permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301031.png" /> can, e.g., be constructed as follows: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301032.png" />, and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301033.png" /> has already been constructed, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301034.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301035.png" /> it has the form (1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11).

There exist iteration methods using <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301036.png" /> previous approximations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301037.png" />. They are called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i053/i053010/i05301038.png" />-step methods and have an increased rate of convergence.

Iteration methods are extensively used in solving multi-dimensional problems in mathematical physics, and for some classes of problems there exist special fast-converging iteration methods. Examples are: the method of variable directions, the methods explained in [[#References|[7]]] for elliptic boundary-initial value problems, and some methods for the problem of particle transfer or radiation (cf. [[#References|[1]]]–[[#References|[7]]]; [[Variable-directions method|Variable-directions method]]).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  L.V. Kantorovich,   G.P. Akilov,   "Functionalanalysis in normierten Räumen" , Akademie Verlag  (1964)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  L. Collatz,   "Funktionalanalysis und numerische Mathematik" , Springer  (1964)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  G.I. Marchuk,   V.I. Lebedev,   "Numerical methods in the theory of neutron transport" , Harwood  (1986)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  N.S. Bakhvalov,   "Numerical methods: analysis, algebra, ordinary differential equations" , MIR  (1977)  (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  M.A. Krasnosel'skii,   G.M. Vainikko,   P.P. Zabreiko,   et al.,   "Approximate solution of operator equations" , Wolters-Noordhoff  (1972)  (Translated from Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  V.I. Lebedev,   "Optimization in iteration methods" , ''Proc. 2nd Math. School Optim. Organ. Comp. 1971'' , Inst. Kibernet. Akad. Nauk SSSR  (1972)  pp. 109–135  (In Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  R.P. Fedorenko,   "Iterative methods for elliptic difference equations"  ''Russian Math. Surveys'' , '''2'''  (1973)  pp. 129–195  ''Uspekhi Mat. Nauk'' , '''28'''  (1973)  pp. 121–182</TD></TR></table>



====Comments====
See also the editorial comments to [[Chebyshev iteration method|Chebyshev iteration method]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  D.M. Young,   "Iterative solution of large linear systems" , Acad. Press  (1971)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  A. George,   J.W.-H. Liu,   "Computer solution of large sparse positive definite systems" , Prentice-Hall  (1981)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J.E., jr. Dennis,   R. Schnable,   "Least change secant updates for quasi-Newton methods"  ''SIAM Review'' , '''21'''  (1979)  pp. 443–459</TD></TR><TR><TD valign="top">[a4]</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">[a5]</TD> <TD valign="top">  W.C. Rheinboldt,   "Methods for solving systems of nonlinear equations" , SIAM  (1970)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  J.F. Traub,   "Iterative methods for the solution of equations" , Prentice-Hall  (1964)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  R. Wait,   "The numerical solution of algebraic equations" , Wiley  (1979)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  E. Wasserstrom,   "Numerical solution by the continuation method"  ''SIAM Review'' , '''15'''  (1973)  pp. 89–119</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  R.S. Varga,   "Matrix iterative analysis" , Prentice-Hall  (1962)</TD></TR></table>