Fixed-point iteration is a method in numerical analysis for approximating a fixed point of a mapping: a point satisfying . Starting from an initial approximation , it generates the sequence
If this sequence converges to and is continuous at that point, then is a fixed point. The method applies to real numbers, vectors, functions, and more general mathematical objects. Its simplicity makes it a basic computational technique, but its success depends strongly on the chosen mapping and starting point.
Formulation and interpretation
A root-finding problem
can often be rewritten as
For example, for any nonzero constant , the equation is equivalent to
This produces the iteration
Equivalent equations need not produce equally effective algorithms. One rearrangement may converge rapidly, another slowly, and another not at all. The computational problem is therefore not merely to identify a fixed-point equation, but to choose a mapping whose repeated application approaches the desired solution.
In terms of function composition,
where denotes successive applications of . The same construction defines a discrete dynamical system, in which a fixed point may attract or repel nearby trajectories.
For a real-valued mapping, a graphical interpretation uses the curves and . Their intersections are fixed points. Repeated vertical and horizontal movements between the two curves form a cobweb diagram, illustrating convergence, oscillation, or divergence.
Convergence under a contraction condition
The principal general convergence result is the Banach fixed-point theorem. Let be a nonempty complete metric space, and suppose is a contraction: there is a constant , with , such that
for every .
Then:
has exactly one fixed point in .
The iteration converges to from every .
The error satisfies
Completeness ensures that the Cauchy sequence generated by the iteration has a limit within the space. The requirement ensures that every step remains in the region where the contraction estimate applies.
Two useful error bounds are
and, for ,
The first is an a priori bound based on the initial step; the second is an a posteriori bound based on computed iterates.
The contraction condition is sufficient, not necessary. Some noncontractive mappings have convergent iterations. Conversely, the existence or even uniqueness of a fixed point alone does not guarantee convergence to it.
Real-valued iterations
For a continuously differentiable mapping on a closed interval , a convenient sufficient condition is
By the mean value theorem, the derivative bound makes a contraction on the interval. The self-mapping condition prevents the iterates from leaving it.
Local attraction and repulsion
Suppose is a fixed point and is continuously differentiable near it. A Taylor expansion gives
Consequently:
- If , the fixed point is locally attracting: sufficiently close initial points converge to it.
- If , it is locally repelling.
- If , the derivative test is inconclusive.
When , nearby errors tend to preserve their sign. When , they tend to alternate in sign.
The borderline case can behave quite differently for different mappings. Near zero, attracts sufficiently small initial values, whereas repels nonzero nearby values. Both have .
Example: solving
Consider
On , the cosine maps the interval into itself and satisfies
Thus every starting value in that interval converges to the unique fixed point there,
By contrast, solving through
usually fails to converge. For every nonzero ,
so the sequence forms a two-cycle unless the initial value is already a fixed point. The alternative iteration
converges to from every positive starting value.
Rate of convergence
Let . A convergent iteration has order if, under the usual nonzero-error assumptions,
For a smooth scalar mapping:
- If , convergence is linear, with asymptotic factor .
- If and , convergence is quadratic.
- More generally, if the first nonzero derivative at the fixed point is the th derivative, with , convergence is locally of order , provided the iteration does not reach the solution in finitely many steps.
A linear factor close to one gives slow convergence. Thus an iteration may satisfy a rigorous convergence theorem while remaining computationally inefficient.
Newton's method is an important special case:
At a simple root of a sufficiently smooth function, , which explains its local quadratic convergence. This local advantage does not imply convergence from arbitrary starting values.
Vector and linear iterations
For a mapping , the update remains
A contraction estimate can be expressed using a norm:
If is continuously differentiable near a fixed point, its Jacobian matrix governs local behavior:
A sufficient condition for local convergence is
where the spectral radius is the largest absolute value of the matrix's eigenvalues. If the spectral radius exceeds one, the fixed point is unstable; equality to one requires further analysis.
For the affine iteration
the error satisfies exactly
Convergence to a unique fixed point from every initial vector occurs if and only if
This framework includes stationary methods for a system of linear equations. Given , choose a splitting
with invertible. Then
Different splittings yield methods such as Jacobi and Gauss–Seidel iteration. In implementation, applying generally means solving a simpler linear system, not explicitly forming an inverse matrix.
Relaxation and acceleration
A relaxed iteration replaces the direct update by
For , it has the same fixed points as . Values are called *under-relaxation*; values are called over-relaxation.
At a scalar fixed point, the derivative of the relaxed mapping is
Choosing can improve convergence or stabilize some oscillatory iterations, but it can also cause divergence. Under-relaxation is not a universal remedy: if , every positive leaves this derivative greater than one.
Acceleration methods use information from several iterates. For a scalar sequence, Aitken's delta-squared process forms
when the denominator is nonzero. It can remove the dominant geometric error in a linearly convergent sequence, although a small denominator can make the calculation sensitive to roundoff.
For vector problems, Anderson acceleration combines previous iterates and residuals through a small least-squares problem. Its effectiveness depends on the mapping, the stored history, and implementation safeguards.
Applications
Fixed-point iteration provides both algorithms and existence proofs.
Differential equations. For an initial-value problem
Picard iteration applies the integral operator
Under suitable continuity and Lipschitz conditions, this is a contraction on an appropriate function space over a sufficiently short interval. It is fundamental to local existence and uniqueness theory for ordinary differential equations.
Optimization. Gradient descent is the fixed-point iteration
Its fixed points are stationary points of ; whether they are minimizers and whether iteration converges require additional assumptions.
Dynamic programming. Value iteration repeatedly applies a Bellman operator. In standard discounted models with bounded rewards, this operator is a contraction in the supremum norm.
Nonlinear models and discretized equations. Coupled equilibrium equations and discretizations of nonlinear differential equations can often be solved by repeatedly evaluating a mapping or solving a simpler subproblem.
The name Picard iteration is especially common for successive approximation in differential equations, while fixed-point iteration is used more broadly.
Stopping criteria and limitations
A common stopping rule is
This measures the step size, not directly the error.
Define the fixed-point residual by
Under a contraction estimate with constant ,
Thus a residual becomes a certified error bound when an appropriate contraction constant is known. If is close to one, a small residual may still correspond to a much larger error.
For a reformulated equation , the residual of the original equation also matters. In the iteration , a very small can produce tiny steps even when remains large.
Other limitations include dependence on the initial approximation, convergence to an unintended fixed point, periodic cycles, departure from the mapping's domain, and slow convergence. In floating-point arithmetic, computed iterates may stagnate because successive values round to the same number. Finite-precision termination is therefore not, by itself, evidence that the exact solution has been reached.