Incomputational mathematics, aniterative method is amathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which thei-th approximation (called an "iterate") is derived from the previous ones.

A specific implementation withtermination criteria for a given iterative method likegradient descent,hill climbing,Newton's method, orquasi-Newton methods likeBFGS, is analgorithm of an iterative method or amethod of successive approximation. An iterative method is calledconvergent if the corresponding sequence converges for given initial approximations. A mathematically rigorous convergence analysis of an iterative method is usually performed; however,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 ofrounding errors, direct methods would deliver an exact solution (for example, solving a linear system of equations${\displaystyle A\mathbf{x}=\mathbf{b}}$ byGaussian elimination). Iterative methods are often the only choice fornonlinear equations. 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]

If an equation can be put into the formf(x) =x, and a solutionx is an attractivefixed point of the functionf, then one may begin with a pointx₁ in thebasin of attraction ofx, and letx_n+1 =f(x_n) forn ≥ 1, and the sequence {x_n}_n ≥ 1 will converge to the solutionx. Herex_n is thenth approximation or iteration ofx andx_n+1 is the next orn + 1 iteration ofx. Alternately, superscripts in parentheses are often used in numerical methods, so as not to interfere with subscripts with other meanings. (For example,x⁽ⁿ⁺¹⁾ =f(x⁽ⁿ⁾).) If the functionf iscontinuously differentiable, a sufficient condition for convergence is that thespectral 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]}

In the case of asystem of linear equations, the two main classes of iterative methods are thestationary iterative methods, and the more generalKrylov subspace methods.

Stationary iterative methods solve a linear system with anoperator approximating the original one; and based on a measurement of the error in the result (the residual), 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.

Aniterative method is defined by$${\displaystyle {\mathbf{x}}^{k+1}:=\mathrm{\Psi }({\mathbf{x}}^k),k\ge 0}$$and for a given linear system${\displaystyle A\mathbf{x}=\mathbf{b}}$ with exact solution${\displaystyle {\mathbf{x}}^{\ast }}$ theerror by$${\displaystyle {\mathbf{e}}^k:={\mathbf{x}}^k-{\mathbf{x}}^{\ast },k\ge 0.}$$An iterative method is calledlinear if there exists a matrix${\displaystyle C\in {\mathbb{R}}^{n\times n}}$ such that$${\displaystyle {\mathbf{e}}^{k+1}=C{\mathbf{e}}^k\mathrm{\forall }k\ge 0}$$and this matrix is called theiteration matrix.An iterative method with a given iteration matrix${\displaystyle C}$ is calledconvergent if the following holds$${\displaystyle \underset{k\to \mathrm{\infty }}{lim}{C}^k=0.}$$

An important theorem states that for a given iterative method and its iteration matrix${\displaystyle C}$ it is convergent if and only if itsspectral radius${\displaystyle \rho (C)}$ is smaller than unity, that is,

The basic iterative methods work bysplitting the matrix${\displaystyle A}$ into$${\displaystyle A=M-N}$$and here the matrix${\displaystyle M}$ should be easilyinvertible.The iterative methods are now defined as$${\displaystyle M{\mathbf{x}}^{k+1}=N{\mathbf{x}}^k+\mathbf{b},k\ge 0,}$$or, equivalently,$${\displaystyle {\mathbf{x}}^{k+1}={\mathbf{x}}^k+M^{-1}\left(\mathbf{b}-A{\mathbf{x}}^k\right),k\ge 0.}$$From this follows that the iteration matrix is given by$${\displaystyle C=I-M^{-1}A=M^{-1}N.}$$

Basic examples of stationary iterative methods use a splitting of the matrix${\displaystyle A}$ such as$${\displaystyle A=D+L+U,D:=\mathrm{diag}((a_{ii}{)}_i)}$$where${\displaystyle D}$ is only the diagonal part of${\displaystyle A}$, and${\displaystyle L}$ is the strict lowertriangular part of${\displaystyle A}$.Respectively,${\displaystyle U}$ is the strict upper triangular part of${\displaystyle A}$.

• Richardson method:$${\displaystyle M:=\frac{1}{\omega }I(\omega \ne 0)}$$
• Jacobi method:$${\displaystyle M:=D}$$
• Damped Jacobi method:$${\displaystyle M:=\frac{1}{\omega }D(\omega \ne 0)}$$
• Gauss–Seidel method:$${\displaystyle M:=D+L}$$
• Successive over-relaxation method (SOR):$${\displaystyle M:=\frac{1}{\omega }D+L(\omega \ne 0)}$$
• Symmetric successive over-relaxation (SSOR):$${\displaystyle M:=\frac{1}{\omega \left(2-\omega \right)}\left(D+\omega L\right)D^{-1}\left(D+\omega U\right)(\omega \notin \{0,2\})}$$

Linear stationary iterative methods are also calledrelaxation methods.

Krylov subspace methods^[2] work by forming abasis of the sequence of successive matrix powers times the initial residual (theKrylov sequence).The approximations to the solution are then formed by minimizing the residual over the subspace formed.The prototypical method in this class is theconjugate gradient method (CG) which assumes that the system matrix${\displaystyle A}$ issymmetricpositive-definite.For symmetric (and possibly indefinite)${\displaystyle A}$ one works with theminimal residual method (MINRES).In the case of non-symmetric matrices, methods such as thegeneralized minimal residual method (GMRES) and thebiconjugate gradient method (BiCG) have been derived.

Since these methods form a basis, it is evident that the method converges inN iterations, whereN is the system size. However, in the presence of rounding errors this statement does not hold; moreover, in practiceN 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 thespectrum of the operator.^{[citation needed]}

The approximating operator that appears in stationary iterative methods can also be incorporated in Krylov subspace methods such asGMRES (alternatively,preconditioned 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]}

Mathematical methods relating to successive approximation include:

• Babylonian method, for finding square roots of numbers^[3]
• Fixed-point iteration^[4]
• Means of finding zeros of functions:
  • Halley's method
  • Newton's method
• Differential-equation matters:
  • Picard–Lindelöf theorem, on existence of solutions of differential equations
  • Runge–Kutta methods, for numerical solution of differential equations

Jamshīd al-Kāshī used iterative methods to calculate the sine of 1° andπ inThe Treatise of Chord and Sine to high precision.An early iterative method forsolving a linear system appeared in a letter ofGauss 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]}.

The theory of stationary iterative methods was solidly established with the work ofD.M. Young starting in the 1950s. The conjugate gradient method was also invented in the 1950s, with independent developments byCornelius Lanczos,Magnus Hestenes andEduard 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 forpartial differential equations, especially the elliptic type.^{[citation needed]}

• Closed-form expression
• Iterative refinement
• Kaczmarz method
• Non-linear least squares
• Numerical analysis
• Root-finding algorithm

Wikimedia Commons has media related toIterative methods.

• Templates for the Solution of Linear Systems
• Y. Saad:Iterative Methods for Sparse Linear Systems, 1st edition, PWS 1996

• Iterative methods
• Numerical analysis

• Articles with short description
• Short description is different from Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from December 2025
• Articles with unsourced statements from December 2019
• Commons category link is on Wikidata