Iterative method 15237 215221206 2008-05-27T06:58:37Z Berland 623074 /* Stationary iterative methods */ en-dash for Gauss-Seidel In [[computational mathematics]], an '''iterative method''' attempts to solve a problem (for example an equation or system of equations) by finding successive [[approximation]]s to the solution starting from an initial guess. This approach is in contrast to '''direct methods''', which attempt to solve the problem by a finite sequence of operations, and, in the absence of [[rounding error]]s, would deliver an exact solution (like solving a linear system of equations ''Ax'' = ''b'' by [[Gaussian elimination]]). Iterative methods are usually the only choice for [[nonlinear equation]]s. 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. ==Newton's method== One of the most familiar iterative methods is [[Newton's method]]. ==Attractive fixed points== If an equation can be put into the form ''f''(''x'') = ''x'', and a solution '''x''' is an attractive [[fixed point (mathematics)|fixed point]] of the function ''f'', then one may begin with a point ''x''<sub>1</sub> in the basin of attraction of '''x''', and let ''x''<sub>''n''+1</sub> = ''f''(''x''<sub>''n''</sub>) for ''n''&nbsp;&ge;&nbsp;1, and the sequence {''x''<sub>''n''</sub>}<sub>''n''&nbsp;&ge;&nbsp;1</sub> will converge to the solution '''x'''. ==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 (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. Examples of stationary iterative methods are the [[Jacobi method]] and the [[Gauss–Seidel method]]. ===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]] (CG). Other methods are the [[generalized minimal residual method]] (GMRES) and the [[biconjugate gradient method]] (BiCG). ===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 an operator|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, [[preconditioning|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 [[Carl Friedrich Gauss|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 equation]]s, especially the elliptic type. == External links == * [http://www.netlib.org/linalg/html_templates/Templates.html Templates for the Solution of Linear Systems] * [http://www-users.cs.umn.edu/~saad/books.html Y. Saad: ''Iterative Methods for Sparse Linear Systems'', 1st edition, PWS 1996] [[Category:Numerical analysis]] [[et:Iteratsioonimeetod]] [[es:Método iterativo]] [[fr:Méthode itérative]] [[ja:反復法 (数値計算)]] [[zh:迭代]]