Iterative method

If an equation can be put into the form f(x) = x, and a solution x is an attractive fixed point of the function f, then one may begin with a point x₁ in the basin of attractionofx, 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 nth 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⁽ⁿ⁺¹⁾ = f(x⁽ⁿ⁾).) If the function fiscontinuously differentiable, a sufficient condition for convergence is that the 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.

In the case of a system of linear equations, the two main classes of iterative methods are the stationary iterative methods, and the more general Krylov subspace methods.

Stationary iterative methods solve a linear system with an operator 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}:=\Psi (\mathbf {x} ^{k})\,,\quad k\geq 0}$ 

and for a given linear system ${\displaystyle A\mathbf {x} =\mathbf {b} }$  with exact solution ${\displaystyle \mathbf {x} ^{*}}$  the errorby

${\displaystyle \mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x} ^{*}\,,\quad k\geq 0\,.}$ 

An iterative method is called linear if there exists a matrix ${\displaystyle C\in \mathbb {R} ^{n\times n}}$  such that

${\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 ${\displaystyle C}$  is called convergent if the following holds

${\displaystyle \lim _{k\rightarrow \infty }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 its spectral radius ${\displaystyle \rho ($C)}   is smaller than unity, that is,

${\displaystyle \rho ($C)<1\,.}  

The basic iterative methods work by splitting the matrix ${\displaystyle A}$  into

${\displaystyle A=M-N}$ 

and here the matrix ${\displaystyle M}$  should be easily invertible. The iterative methods are now defined as

${\displaystyle M\mathbf {x} ^{k+1}=N\mathbf {x} ^{k}+b\,,\quad k\geq 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\,,\quad D:={\text{diag}}((a_{ii})_{i})}$ 

where ${\displaystyle D}$  is only the diagonal part of ${\displaystyle A}$ , and ${\displaystyle L}$  is the strict lower triangular partof${\displaystyle A}$ . Respectively, ${\displaystyle U}$  is the strict upper triangular part of ${\displaystyle A}$ .

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

Linear stationary iterative methods are also called relaxation methods.

Krylov subspace methods work by forming a basis 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 (CG) which assumes that the system matrix ${\displaystyle A}$ issymmetric positive-definite. For symmetric (and possibly indefinite) ${\displaystyle A}$  one works with the minimal residual method (MINRES). In the case of non-symmetric matrices, methods such as the generalized minimal residual method (GMRES) and the biconjugate gradient method (BiCG) have been derived.

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 of the operator.

The approximating operator that appears in stationary iterative methods can also be incorporated in Krylov subspace methods such as GMRES (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.

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 for solving a linear system appeared in a letter of 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]}.

The theory of stationary iterative methods was solidly established with the work of D.M. Young starting in the 1950s. The conjugate gradient method was also invented in the 1950s, with independent developments by Cornelius Lanczos, Magnus Hestenes and 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, especially the elliptic type.

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

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