# Acceleration of convergence

(for an iterative method)

The construction of a modification of the iterative method, by means of that method, that possesses a greater rate of convergence. The acceleration methods (acceleration processes) used are quite varied (see ) and depend both on the problem to be solved and on the type of iterative method. In those cases where the iterative method can be considered as a particular case of a class of iterative methods containing free iteration parameters, acceleration of convergence can be reduced to the problem of the optimal choice of these parameters. The optimization problem can take various forms, and may reduce, for example, to a transition from a method of simple iteration,

$$u^{n+1}=u^n-\tau(Lu^n-f),\label{1}\tag{1}$$

for the solution of a system of linear algebraic equations

$$Lu=f,\quad L=L^*>0,\label{2}\tag{2}$$

either to the Richardson method with Chebyshev parameters or to the method of conjugate gradients. The rate of convergence of similar classical iterative methods depends on the condition number $\nu(L)$ of the matrix $L$ and can be fairly slow for large $\nu(L)$. In such situations, and particularly for the solution of systems of grid equations, modifications of these methods are often used, these can be defined by the fact that they are used not for \eqref{2}, but for an equivalent system

$$B^{-1}Lu=B^{-1}f,$$

where $B=B^*>0$ is a specially selected operator (see ).

The operator $B^{-1}L$ is self-adjoint and positive on some Euclidean space and the rate of convergence of the modifications obtained depends on $\nu(B^{-1}L)$. Similar modifications are also used for more general problems, including non-linear problems (see Non-linear equation, numerical methods). In order to realise these modifications it is important to be able to solve the systems $Bv=g$ effectively, since, for example, modification of \eqref{1} leads to the relation

$$u^{n+1}=u^n-\tau B^{-1}(Lu^n-f)\label{3}\tag{3}$$

One of the traditional general methods for the acceleration of convergence for methods \eqref{1} is the $\delta^2$-process. It is used along with a whole series of other acceleration methods (see ) in iterative methods for the partial eigen value problem.

In solving non-linear problems, acceleration of convergence is often achieved by choosing a special initial approximation on the basis of methods of continuation by a parameter. For these same problems acceleration of convergence is also sometimes realized by the use of iterative methods of a higher order (the Newton–Kantorovich method and others).

Various methods for the acceleration of convergence are also used in probabilistic iterative methods of Monte-Carlo type (see ).

How to Cite This Entry:
Acceleration of convergence. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Acceleration_of_convergence&oldid=44705
This article was adapted from an original article by E.G. D'yakonov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article