Home > Iterative method
An iterative method attempts to solve a problem, for example an equation or system of equations, by finding successive approximations to the solution starting from an initial guess. These are in contrast to direct methods which attempt to solve the problem in one-shot (like solving a linear system of equations Ax=b by finding the inverse of the matrix A). Iterative methods are useful for problems involving large number of variables (could be of the order of millions) where direct methods would be prohibitively expensive and in some cases impossible even with the best available computing power.In the case of a linear system the two main classes are the stationary iterative methods, and the more general Krylov subspace methods.
1 Stationary iterative methods
Stationary iterative methods solve a system with an operator approximating the original one; and based on a measurement of the error (the residual) form a correction equation for which this process is repeated. While these methods are simple to derive, implement, and analyse, convergence is only guaranteed for a limited class of matrices.
2 Krylov subspace methods
Krylov subspace methods form an orthogonal 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 .
3 Convergence
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.
4 Preconditioners
The approximating operator that appears in stationary Iterative methods can also be incorporated in Krylov subspace methods (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.
5 History
- 1671, 1690, 1736 The Newton-Raphson method explicitly iterates a formula to arrive at a solution.
- Also, the iterative method 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 largest.
- The theory of Stationary Iterative methods was solidly established with the work of D.M. Young starting the 1950s. The Conjugate Gradient method was also invented in the 1950s, with independent developments by Cornelius Lanczos and David Hestenes and Stiefel , but its nature and applicability was minunderstood at the time. Only in the 1970s was it realized that conjugacy based methods work very well for partial differential equations, especially of elliptic type.
In the 1900s, Emil Post, Alonzo Church and others published the relationship of iterationIteration is the repetition of a process, typically within a computer program. Confusingly, it can be used both as a general term, synonymous with repetition, and to describe a specific form of repetition with mutable state. When used in the first sense, to recursionIn mathematics and computer science, recursion is a particular way of specifying (or constructing) a class of objects (or an object from a certain class) with the help of a reference to other objects of the class: a recursive definition defines objects in. For example, the Scheme programming languageThe Scheme programming language is a functional programming language and a dialect of Lisp. It was developed by Guy L. Steele and Gerald Jay Sussman in the 1970s and introduced to the academic world via a series of papers now referred to as Sussman and St expresses iterationIteration is the repetition of a process, typically within a computer program. Confusingly, it can be used both as a general term, synonymous with repetition, and to describe a specific form of repetition with mutable state. When used in the first sense, with tail- recursionIn mathematics and computer science, recursion is a particular way of specifying (or constructing) a class of objects (or an object from a certain class) with the help of a reference to other objects of the class: a recursive definition defines objects in.
