HOME

TheInfoList



OR:

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 numerical analysis, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better soluti ...
,
Newton's method In numerical analysis, the Newton–Raphson method, also known simply as Newton's method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a ...
, or quasi-Newton methods like BFGS, is an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
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\mathbf=\mathbf by
Gaussian elimination In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of row-wise operations performed on the corresponding matrix of coefficients. This method can a ...
). 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 ''x''1 in the basin of attraction of x, and let ''x''''n''+1 = ''f''(''x''''n'') for ''n'' ≥ 1, and the sequence ''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, a sufficient condition for convergence is that the
spectral radius ''Spectral'' is a 2016 Hungarian-American military science fiction action film co-written and directed by Nic Mathieu. Written with Ian Fried (screenwriter), Ian Fried & George Nolfi, the film stars James Badge Dale as DARPA research scientist Ma ...
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 In mathematics, a system of linear equations (or linear system) is a collection of two or more linear equations involving the same variable (math), variables. For example, : \begin 3x+2y-z=1\\ 2x-2y+4z=-2\\ -x+\fracy-z=0 \end is a system of th ...
, 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 : \mathbf^ := \Psi ( \mathbf^k ), \quad k \geq 0 and for a given linear system A\mathbf x= \mathbf b with exact solution \mathbf^* the ''error'' by : \mathbf^k := \mathbf^k - \mathbf^*, \quad k \geq 0. An iterative method is called ''linear'' if there exists a matrix C \in \R^ such that : \mathbf^ = C \mathbf^k \quad \forall k \geq 0 and this matrix is called the ''iteration matrix''. An iterative method with a given iteration matrix C is called ''convergent'' if the following holds : \lim_ C^k=0. An important theorem states that for a given iterative method and its iteration matrix C it is convergent if and only if its
spectral radius ''Spectral'' is a 2016 Hungarian-American military science fiction action film co-written and directed by Nic Mathieu. Written with Ian Fried (screenwriter), Ian Fried & George Nolfi, the film stars James Badge Dale as DARPA research scientist Ma ...
\rho(C) is smaller than unity, that is, : \rho(C) < 1. The basic iterative methods work by splitting the matrix A into : A = M - N and here the matrix M should be easily
invertible In mathematics, the concept of an inverse element generalises the concepts of opposite () and reciprocal () of numbers. Given an operation denoted here , and an identity element denoted , if , one says that is a left inverse of , and that ...
. The iterative methods are now defined as : M \mathbf^ = N \mathbf^k + b, \quad k \geq 0, or, equivalently, : \mathbf^ = \mathbf^k + M^ (b - A \mathbf^k), \quad k \geq 0. From this follows that the iteration matrix is given by : C = I - M^A = M^N.


Examples

Basic examples of stationary iterative methods use a splitting of the matrix A such as : A = D+L+U\,,\quad D := \text( (a_)_i) where D is only the diagonal part of A , and L is the strict lower triangular part of A . Respectively, U is the strict upper triangular part of A . * Richardson method: M:=\frac I \quad (\omega \neq 0) * Jacobi method: M:=D * Damped Jacobi method: M:=\fracD \quad (\omega \neq 0) * Gauss–Seidel method: M:=D+L * Successive over-relaxation method (SOR): M:=\fracD+L \quad (\omega \neq 0) * Symmetric successive over-relaxation (SSOR): M := \frac (D+\omega L) D^ (D+\omega U) \quad (\omega \not \in \) Linear stationary iterative methods are also called relaxation methods.


Krylov subspace 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 A is symmetric positive-definite. For symmetric (and possibly indefinite) 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.


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 A spectrum (: spectra or spectrums) is a set of related ideas, objects, or properties whose features overlap such that they blend to form a continuum. The word ''spectrum'' was first used scientifically in optics to describe the rainbow of co ...
of the operator.


Preconditioners

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.


Methods of successive approximation

Mathematical methods relating to successive approximation include: * Babylonian method, for finding square roots of numbers * Fixed-point iteration * Means of finding zeros of functions: ** Halley's method **
Newton's method In numerical analysis, the Newton–Raphson method, also known simply as Newton's method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a ...
* Differential-equation matters: ** Picard–Lindelöf theorem, on existence of solutions of differential equations **
Runge–Kutta methods In numerical analysis, the Runge–Kutta methods ( ) are a family of Explicit and implicit methods, implicit and explicit iterative methods, List of Runge–Kutta methods, which include the Euler method, used in temporal discretization for the a ...
, for numerical solution of differential equations


History

Jamshīd al-Kāshī 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 appeared in a letter of
Gauss Johann Carl Friedrich Gauss (; ; ; 30 April 177723 February 1855) was a German mathematician, astronomer, Geodesy, geodesist, and physicist, who contributed to many fields in mathematics and science. He was director of the Göttingen Observat ...
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 . 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 equation In mathematics, a partial differential equation (PDE) is an equation which involves a multivariable function and one or more of its partial derivatives. The function is often thought of as an "unknown" that solves the equation, similar to ho ...
s, especially the elliptic type.


See also

*
Closed-form expression In mathematics, an expression or equation is in closed form if it is formed with constants, variables, and a set of functions considered as ''basic'' and connected by arithmetic operations (, and integer powers) and function composition. ...
* Iterative refinement * Kaczmarz method * Non-linear least squares *
Numerical analysis Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
* Root-finding algorithm


References


External links


Templates for the Solution of Linear Systems
{{Authority control Numerical analysis