Iterative method

related topics
{math, number, function}
{math, energy, light}
{school, student, university}
{theory, work, human}

In computational mathematics, an iterative method attempts to solve a problem (for example, finding the root of an equation or system of equations) by finding successive approximations 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 errors, 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 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.

Full article ▸

related documents
Elliptic function
Cofinality
Semi-continuity
Ternary numeral system
Upper and lower bounds
Conjugacy class
Division ring
Lambert W function
Homomorphism
Infimum
ZPP
Principal ideal domain
Pointless topology
Shannon–Fano coding
Counting sort
Five lemma
Dedekind cut
Distributivity
Intermediate value theorem
Arithmetic function
Multiplication table
Cyclone (programming language)
Möbius function
Soundness
Linear cryptanalysis
Commutator
Pseudocode
Group isomorphism
Banach algebra
Arithmetic shift