Iterative method

Iterative method

In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method. 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 the problems of finding the root of an equation (or a solution of a system of equations), an iterative method uses an initial guess to generate successive approximations to a solution. 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 (like solving a linear system of equations Ax = 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 a large number of variables (sometimes of the order of millions), where direct methods would be prohibitively expensive (and in some cases impossible) even with the best available computing power.

Contents

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. 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

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. Examples of stationary iterative methods are the Jacobi method, Gauss–Seidel method and the Successive over-relaxation method.

Krylov subspace methods

Krylov subspace methods work by forming 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 (CG). Other methods are the generalized minimal residual method (GMRES) and the biconjugate gradient method (BiCG).

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 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.

History

Probably the first 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.

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.

See also

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • iterative method — iteracinis metodas statusas T sritis automatika atitikmenys: angl. iteration method; iterative approach; iterative method vok. Iterationsmethode, f; iterative Methode, f rus. итерационный метод, m; метод итераций, m pranc. méthode d itération, f; …   Automatikos terminų žodynas

  • iterative method — iteracijų metodas statusas T sritis fizika atitikmenys: angl. iteration method; iterative method vok. Iterationsmethode, f; iterative Methode, f rus. итерационный метод, m; метод итераций, m pranc. méthode d’itération, f; méthode itérative, f …   Fizikos terminų žodynas

  • iterative method — iteracijų metodas statusas T sritis Standartizacija ir metrologija apibrėžtis Matematinio veiksmo pakartotinio panaudojimo rezultato metodas. atitikmenys: angl. iteration method; iterative method vok. Iterationsmethode, f; iterative Methode, f… …   Penkiakalbis aiškinamasis metrologijos terminų žodynas

  • Iterative proportional fitting — The iterative proportional fitting procedure (IPFP, also known as biproportional fitting in statistics, RAS algorithm[1] in economics and matrix raking or matrix scaling in computer science) is an iterative algorithm for estimating cell values of …   Wikipedia

  • iterative Methode — iteracinis metodas statusas T sritis automatika atitikmenys: angl. iteration method; iterative approach; iterative method vok. Iterationsmethode, f; iterative Methode, f rus. итерационный метод, m; метод итераций, m pranc. méthode d itération, f; …   Automatikos terminų žodynas

  • iterative approach — iteracinis metodas statusas T sritis automatika atitikmenys: angl. iteration method; iterative approach; iterative method vok. Iterationsmethode, f; iterative Methode, f rus. итерационный метод, m; метод итераций, m pranc. méthode d itération, f; …   Automatikos terminų žodynas

  • iterative Methode — iteracijų metodas statusas T sritis fizika atitikmenys: angl. iteration method; iterative method vok. Iterationsmethode, f; iterative Methode, f rus. итерационный метод, m; метод итераций, m pranc. méthode d’itération, f; méthode itérative, f …   Fizikos terminų žodynas

  • iterative Methode — iteracijų metodas statusas T sritis Standartizacija ir metrologija apibrėžtis Matematinio veiksmo pakartotinio panaudojimo rezultato metodas. atitikmenys: angl. iteration method; iterative method vok. Iterationsmethode, f; iterative Methode, f… …   Penkiakalbis aiškinamasis metrologijos terminų žodynas

  • Iterative and incremental development — is a cyclic software development process developed in response to the weaknesses of the waterfall model. It is an essential part of the Rational Unified Process, the Dynamic Systems Development Method, Extreme Programming and generally the agile… …   Wikipedia

  • Iterative learning control — (ILC) is a method of tracking control for systems that work in a repetitive mode. Examples of systems that operate in a repetitive manner include robot arm manipulators, chemical batch processes and reliability testing rigs. In each of these… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”