In computational mathematics, an iterative method is a mathematical procedure 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 criteria for a given iterative method like gradient descent, hill climbing, Newton's method, or quasi-Newton methods like BFGS, is an algorithm of an iterative method or a method of successive approximation. An iterative method is called convergent 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 of rounding errors, 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). Iterative methods are often the only choice for nonlinear 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.
Attractive fixed points 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 x1 in the basin of attraction of x, and let xn+1 = f(xn) for n ≥ 1, and the sequence {xn}n ≥ 1 will converge to the solution x. Here xn is the nth approximation or iteration of x and xn+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, 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.
Linear systems 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
Introduction 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.
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 ρ ( C ) {\displaystyle \rho (C)} is smaller than unity, that is,
ρ ( C ) < 1. {\displaystyle \rho (C)<1.}
The basic iterative methods work by 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. The iterative methods are now defined as
… excerpt ends here. Continue reading the full article.
