# Iterative method

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Iterative_method
> Markdown URL: https://mediated.wiki/source/Iterative_method.md
> Source: https://en.wikipedia.org/wiki/Iterative_method
> Source revision: 1340088545
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Numerical approximation algorithm

In [computational mathematics](/source/Computational_mathematics), an **iterative method** is a [mathematical procedure](/source/Algorithm) that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the *i*-th approximation (called an "iterate") is derived from the previous ones.

A specific implementation with [termination](/source/Algorithm#Termination) criteria for a given iterative method like [gradient descent](/source/Gradient_descent), [hill climbing](/source/Hill_climbing), [Newton's method](/source/Newton's_method), or [quasi-Newton methods](/source/Quasi-Newton_method) like [BFGS](/source/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm), is an [algorithm](/source/Algorithm) of an iterative method or a **method of successive approximation**. An iterative method is called *[convergent](/source/Convergent_series)* if the corresponding sequence converges for given initial approximations. A mathematically rigorous convergence analysis of an iterative method is usually performed; however, [heuristic](/source/Heuristic)-based iterative methods are also common.

In contrast, **direct methods** attempt to solve the problem by a finite sequence of operations. In the absence of [rounding errors](/source/Rounding_error), direct methods would deliver an exact solution (for example, solving a linear system of equations A x = b {\displaystyle A\mathbf {x} =\mathbf {b} } by [Gaussian elimination](/source/Gaussian_elimination)). Iterative methods are often the only choice for [nonlinear equations](/source/Nonlinear_equation). However, iterative methods are often useful even for linear problems involving many variables (sometimes on the order of millions), where direct methods would be prohibitively expensive (and in some cases impossible) even with the best available computing power.[1]

## Attractive fixed points

If an equation can be put into the form *f*(*x*) = *x*, and a solution **x** is an attractive [fixed point](/source/Fixed_point_(mathematics)) of the function *f*, then one may begin with a point *x*1 in the [basin of attraction](/source/Basin_of_attraction) of **x**, and let *x**n*+1 = *f*(*x**n*) for *n* ≥ 1, and the sequence {*x**n*}*n* ≥ 1 will converge to the solution **x**. Here *x**n* is the *n*th approximation or iteration of *x* and *x**n*+1 is the next or *n* + 1 iteration of *x*. Alternately, superscripts in parentheses are often used in numerical methods, so as not to interfere with subscripts with other meanings. (For example, *x*(*n*+1) = *f*(*x*(*n*)).) If the function *f* is [continuously differentiable](/source/Continuously_differentiable), a sufficient condition for convergence is that the [spectral radius](/source/Spectral_radius) of the derivative is strictly bounded by one in a neighborhood of the fixed point. If this condition holds at the fixed point, then a sufficiently small neighborhood (basin of attraction) must exist.[*[citation needed](https://en.wikipedia.org/wiki/Wikipedia:Citation_needed)*]

## Linear systems

In the case of a [system of linear equations](/source/System_of_linear_equations), the two main classes of iterative methods are the **stationary iterative methods**, and the more general [Krylov subspace](/source/Krylov_subspace) methods.

### Stationary iterative methods

#### Introduction

Stationary iterative methods solve a linear system with an [operator](/source/Operator_(mathematics)) approximating the original one; and based on a measurement of the error in the result ([the residual](/source/Residual_(numerical_analysis))), form a "correction equation" for which this process is repeated. While these methods are simple to derive, implement, and analyze, convergence is only guaranteed for a limited class of matrices.

#### Definition

An *iterative method* is defined by x k + 1 := Ψ ( x k ) , k ≥ 0 {\displaystyle \mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k}),\quad k\geq 0} and for a given linear system A x = b {\displaystyle A\mathbf {x} =\mathbf {b} } with exact solution x ∗ {\displaystyle \mathbf {x} ^{*}} the *error* by e k := x k − x ∗ , k ≥ 0. {\displaystyle \mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x} ^{*},\quad k\geq 0.} An iterative method is called *linear* if there exists a matrix C ∈ R n × n {\displaystyle C\in \mathbb {R} ^{n\times n}} such that e k + 1 = C e k ∀ k ≥ 0 {\displaystyle \mathbf {e} ^{k+1}=C\mathbf {e} ^{k}\quad \forall k\geq 0} and this matrix is called the *iteration matrix*. An iterative method with a given iteration matrix C {\displaystyle C} is called *convergent* if the following holds lim k → ∞ C k = 0. {\displaystyle \lim _{k\to \infty }C^{k}=0.}

An important theorem states that for a given iterative method and its iteration matrix C {\displaystyle C} it is convergent if and only if its [spectral radius](/source/Spectral_radius) ρ ( C ) {\displaystyle \rho (C)} is smaller than unity, that is, ρ ( C ) < 1. {\displaystyle \rho (C)<1.}

The basic iterative methods work by [splitting](/source/Matrix_splitting) the matrix A {\displaystyle A} into A = M − N {\displaystyle A=M-N} and here the matrix M {\displaystyle M} should be easily [invertible](/source/Invertible_matrix). The iterative methods are now defined as M x k + 1 = N x k + b , k ≥ 0 , {\displaystyle M\mathbf {x} ^{k+1}=N\mathbf {x} ^{k}+\mathbf {b} ,\quad k\geq 0,} or, equivalently, x k + 1 = x k + M − 1 ( b − A x k ) , k ≥ 0. {\displaystyle \mathbf {x} ^{k+1}=\mathbf {x} ^{k}+M^{-1}\left(\mathbf {b} -A\mathbf {x} ^{k}\right),\quad k\geq 0.} From this follows that the iteration matrix is given by C = I − M − 1 A = M − 1 N . {\displaystyle C=I-M^{-1}A=M^{-1}N.}

#### Examples

Basic examples of stationary iterative methods use a splitting of the matrix A {\displaystyle A} such as A = D + L + U , D := diag ⁡ ( ( a i i ) i ) {\displaystyle A=D+L+U\,,\quad D:=\operatorname {diag} ((a_{ii})_{i})} where D {\displaystyle D} is only the diagonal part of A {\displaystyle A} , and L {\displaystyle L} is the strict lower [triangular part](/source/Triangular_matrix) of A {\displaystyle A} . Respectively, U {\displaystyle U} is the strict upper triangular part of A {\displaystyle A} .

- [Richardson method](/source/Modified_Richardson_iteration): M := 1 ω I ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}I\quad (\omega \neq 0)}

- [Jacobi method](/source/Jacobi_method): M := D {\displaystyle M:=D}

- [Damped Jacobi method](/source/Jacobi_method#Weighted_Jacobi_method): M := 1 ω D ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D\quad (\omega \neq 0)}

- [Gauss–Seidel method](/source/Gauss%E2%80%93Seidel_method): M := D + L {\displaystyle M:=D+L}

- [Successive over-relaxation method](/source/Successive_over-relaxation) (SOR): M := 1 ω D + L ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)}

- [Symmetric successive over-relaxation](/source/Symmetric_successive_over-relaxation) (SSOR): M := 1 ω ( 2 − ω ) ( D + ω L ) D − 1 ( D + ω U ) ( ω ∉ { 0 , 2 } ) {\displaystyle M:={\frac {1}{\omega \left(2-\omega \right)}}\left(D+\omega L\right)D^{-1}\left(D+\omega U\right)\quad (\omega \not \in \{0,2\})}

Linear stationary iterative methods are also called [relaxation methods](/source/Relaxation_(iterative_method)).

### Krylov subspace methods

Krylov subspace methods[2] work by forming a [basis](/source/Basis_(linear_algebra)) of the sequence of successive matrix powers times the initial residual (the **Krylov sequence**). The approximations to the solution are then formed by minimizing the residual over the subspace formed. The prototypical method in this class is the [conjugate gradient method](/source/Conjugate_gradient_method) (CG) which assumes that the system matrix A {\displaystyle A} is [symmetric](/source/Symmetric_matrix) [positive-definite](/source/Positive-definite_matrix). For symmetric (and possibly indefinite) A {\displaystyle A} one works with the [minimal residual method](/source/Minimal_residual_method) (MINRES). In the case of non-symmetric matrices, methods such as the [generalized minimal residual method](/source/Generalized_minimal_residual_method) (GMRES) and the [biconjugate gradient method](/source/Biconjugate_gradient_method) (BiCG) have been derived.

#### Convergence of Krylov subspace methods

Since these methods form a basis, it is evident that the method converges in *N* iterations, where *N* is the system size. However, in the presence of rounding errors this statement does not hold; moreover, in practice *N* can be very large, and the iterative process reaches sufficient accuracy already far earlier. The analysis of these methods is hard, depending on a complicated function of the [spectrum](/source/Spectrum_of_an_operator) of the operator.[*[citation needed](https://en.wikipedia.org/wiki/Wikipedia:Citation_needed)*]

### Preconditioners

The approximating operator that appears in stationary iterative methods can also be incorporated in Krylov subspace methods such as [GMRES](/source/GMRES) (alternatively, [preconditioned](/source/Preconditioning) Krylov methods can be considered as accelerations of stationary iterative methods), where they become transformations of the original operator to a presumably better conditioned one. The construction of preconditioners is a large research area.[*[citation needed](https://en.wikipedia.org/wiki/Wikipedia:Citation_needed)*]

## Methods of successive approximation

Mathematical methods relating to successive approximation include:

- [Babylonian method](/source/Babylonian_method), for finding square roots of numbers[3]

- [Fixed-point iteration](/source/Fixed-point_iteration)[4]

- Means of finding zeros of functions: - [Halley's method](/source/Halley's_method) - [Newton's method](/source/Newton's_method)

- Differential-equation matters: - [Picard–Lindelöf theorem](/source/Picard%E2%80%93Lindel%C3%B6f_theorem), on existence of solutions of differential equations - [Runge–Kutta methods](/source/Runge%E2%80%93Kutta_methods), for numerical solution of differential equations

### History

[Jamshīd al-Kāshī](/source/Jamsh%C4%ABd_al-K%C4%81sh%C4%AB) used iterative methods to calculate the sine of 1° and π in *The Treatise of Chord and Sine* to high precision. An early iterative method for [solving a linear system](/source/Gauss%E2%80%93Seidel_method) appeared in a letter of [Gauss](/source/Carl_Friedrich_Gauss) to a student of his. He proposed solving a 4-by-4 system of equations by repeatedly solving the component in which the residual was the largest [*[citation needed](https://en.wikipedia.org/wiki/Wikipedia:Citation_needed)*].

The theory of stationary iterative methods was solidly established with the work of [D.M. Young](/source/D.M._Young) starting in the 1950s. The conjugate gradient method was also invented in the 1950s, with independent developments by [Cornelius Lanczos](/source/Cornelius_Lanczos), [Magnus Hestenes](/source/Magnus_Hestenes) and [Eduard Stiefel](/source/Eduard_Stiefel), but its nature and applicability were misunderstood at the time. Only in the 1970s was it realized that conjugacy based methods work very well for [partial differential equations](/source/Partial_differential_equation), especially the elliptic type.[*[citation needed](https://en.wikipedia.org/wiki/Wikipedia:Citation_needed)*]

## See also

- [Mathematics portal](https://en.wikipedia.org/wiki/Portal:Mathematics)

- [Closed-form expression](/source/Closed-form_expression)

- [Iterative refinement](/source/Iterative_refinement)

- [Kaczmarz method](/source/Kaczmarz_method)

- [Non-linear least squares](/source/Non-linear_least_squares)

- [Numerical analysis](/source/Numerical_analysis)

- [Root-finding algorithm](/source/Root-finding_algorithm)

## References

1. **[^](#cite_ref-1)** Amritkar, Amit; de Sturler, Eric; Świrydowicz, Katarzyna; Tafti, Danesh; Ahuja, Kapil (2015). "Recycling Krylov subspaces for CFD applications and a new hybrid recycling solver". *Journal of Computational Physics*. **303**: 222. [arXiv](/source/ArXiv_(identifier)):[1501.03358](https://arxiv.org/abs/1501.03358). [Bibcode](/source/Bibcode_(identifier)):[2015JCoPh.303..222A](https://ui.adsabs.harvard.edu/abs/2015JCoPh.303..222A). [doi](/source/Doi_(identifier)):[10.1016/j.jcp.2015.09.040](https://doi.org/10.1016%2Fj.jcp.2015.09.040).

1. **[^](#cite_ref-2)** Charles George Broyden and Maria Terasa Vespucci: *Krylov Solvers for Linear Algebraic Systems: Krylov Solvers*, Elsevier, ISBN 0-444-51474-0, (2004).

1. **[^](#cite_ref-3)** ["Babylonian mathematics"](https://mathshistory.st-andrews.ac.uk/HistTopics/Babylonian_mathematics/). *Babylonian mathematics*. December 1, 2000.

1. **[^](#cite_ref-4)** day, Mahlon (November 2, 1960). *Fixed-point theorems for compact convex sets*. Mahlon M day.

## External links

Wikimedia Commons has media related to [Iterative methods](https://commons.wikimedia.org/wiki/Category:Iterative_methods).

- [Templates for the Solution of Linear Systems](http://www.netlib.org/linalg/html_templates/Templates.html)

- [Y. Saad: *Iterative Methods for Sparse Linear Systems*, 1st edition, PWS 1996](http://www-users.cs.umn.edu/~saad/books.html)

v t e Optimization: Algorithms, methods, and heuristics Unconstrained nonlinear Functions Golden-section search Powell's method Line search Nelder–Mead method Successive parabolic interpolation Gradients Convergence Trust region Wolfe conditions Quasi–Newton Berndt–Hall–Hall–Hausman Broyden–Fletcher–Goldfarb–Shanno and L-BFGS Davidon–Fletcher–Powell Symmetric rank-one (SR1) Other methods Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell's dog leg method Truncated Newton Hessians Newton's method Optimization computes maxima and minima. Constrained nonlinear General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming Convex optimization Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-exchange Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke Active-set method Combinatorial Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch and bound/cut Graph algorithms Minimum spanning tree Borůvka Prim Kruskal Shortest path Bellman–Ford SPFA Dijkstra Floyd–Warshall Network flows Dinic Edmonds–Karp Ford–Fulkerson Push–relabel maximum flow Metaheuristics Evolutionary algorithm Hill climbing Local search Parallel metaheuristics Simulated annealing Spiral optimization algorithm Tabu search Software

Authority control databases International GND National United States Czech Republic Israel Other Yale LUX

---
Adapted from the Wikipedia article [Iterative method](https://en.wikipedia.org/wiki/Iterative_method) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Iterative_method?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.