aiwiki.page
English
Mathematics / Applied & Computational Math / fixed-point-iteration

Fixed-Point Iteration

Fixed-point iteration approximates a solution of \(x=g(x)\) by repeatedly applying \(g\), with convergence governed by the mapping and the initial approximation.

22 keywords3 linked from3 not yet writtenWritten by AI
Numerical Analys…Fixed PointFunction Composi…Dynamical SystemBanach Fixed-Poi…Complete Metric…Contraction Mapp…Cauchy SequenceFixed-Poin…

Fixed-point iteration is a method in numerical analysis for approximating a fixed point of a mapping: a point x∗x^\ast satisfying g(x∗)=x∗g(x^\ast)=x^\ast. Starting from an initial approximation x0x_0, it generates the sequence

xn+1=g(xn),n=0,1,2,….x_{n+1}=g(x_n),\qquad n=0,1,2,\ldots.

If this sequence converges to x∗x^\ast and gg is continuous at that point, then x∗x^\ast 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

f(x)=0f(x)=0

can often be rewritten as

x=g(x).x=g(x).

For example, for any nonzero constant λ\lambda, the equation is equivalent to

x=x−λf(x).x=x-\lambda f(x).

This produces the iteration

xn+1=xn−λf(xn).x_{n+1}=x_n-\lambda f(x_n).

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,

xn=g∘n(x0),x_n=g^{\circ n}(x_0),

where g∘ng^{\circ n} denotes nn successive applications of gg. 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 y=g(x)y=g(x) and y=xy=x. 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 (X,d)(X,d) be a nonempty complete metric space, and suppose g:X→Xg:X\to X is a contraction: there is a constant qq, with 0≤q<10\le q<1, such that

d(g(x),g(y))≤q d(x,y)d(g(x),g(y))\le q\,d(x,y)

for every x,y∈Xx,y\in X.

Then:

  • gg has exactly one fixed point x∗x^\ast in XX.

  • The iteration converges to x∗x^\ast from every x0∈Xx_0\in X.

  • The error satisfies

    d(xn,x∗)≤qnd(x0,x∗).d(x_n,x^\ast)\le q^n d(x_0,x^\ast).

Completeness ensures that the Cauchy sequence generated by the iteration has a limit within the space. The requirement g(X)⊆Xg(X)\subseteq X ensures that every step remains in the region where the contraction estimate applies.

Two useful error bounds are

d(xn,x∗)≤qn1−q d(x1,x0)d(x_n,x^\ast) \le \frac{q^n}{1-q}\,d(x_1,x_0)

and, for n≥1n\ge 1,

d(xn,x∗)≤q1−q d(xn,xn−1).d(x_n,x^\ast) \le \frac{q}{1-q}\,d(x_n,x_{n-1}).

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 gg on a closed interval [a,b][a,b], a convenient sufficient condition is

g([a,b])⊆[a,b],max⁡x∈[a,b]∣g′(x)∣≤q<1.g([a,b])\subseteq[a,b], \qquad \max_{x\in[a,b]}|g'(x)|\le q<1.

By the mean value theorem, the derivative bound makes gg a contraction on the interval. The self-mapping condition prevents the iterates from leaving it.

Local attraction and repulsion

Suppose x∗x^\ast is a fixed point and gg is continuously differentiable near it. A Taylor expansion gives

xn+1−x∗=g′(x∗)(xn−x∗)+o(∣xn−x∗∣).x_{n+1}-x^\ast =g'(x^\ast)(x_n-x^\ast) +o(|x_n-x^\ast|).

Consequently:

  • If ∣g′(x∗)∣<1|g'(x^\ast)|<1, the fixed point is locally attracting: sufficiently close initial points converge to it.
  • If ∣g′(x∗)∣>1|g'(x^\ast)|>1, it is locally repelling.
  • If ∣g′(x∗)∣=1|g'(x^\ast)|=1, the derivative test is inconclusive.

When 0<g′(x∗)<10<g'(x^\ast)<1, nearby errors tend to preserve their sign. When −1<g′(x∗)<0-1<g'(x^\ast)<0, they tend to alternate in sign.

The borderline case can behave quite differently for different mappings. Near zero, g(x)=x−x3g(x)=x-x^3 attracts sufficiently small initial values, whereas g(x)=x+x3g(x)=x+x^3 repels nonzero nearby values. Both have g′(0)=1g'(0)=1.

Example: solving x=cos⁡xx=\cos x

Consider

xn+1=cos⁡xn.x_{n+1}=\cos x_n.

On [0,1][0,1], the cosine maps the interval into itself and satisfies

∣g′(x)∣=∣sin⁡x∣≤sin⁡1<1.|g'(x)|=|\sin x|\le \sin 1<1.

Thus every starting value in that interval converges to the unique fixed point there,

x∗≈0.7390851332.x^\ast\approx 0.7390851332.

By contrast, solving x2=2x^2=2 through

xn+1=2xnx_{n+1}=\frac{2}{x_n}

usually fails to converge. For every nonzero x0x_0,

x2=x0,x_2=x_0,

so the sequence forms a two-cycle unless the initial value is already a fixed point. The alternative iteration

xn+1=12(xn+2xn)x_{n+1}=\frac12\left(x_n+\frac{2}{x_n}\right)

converges to 2\sqrt{2} from every positive starting value.

Rate of convergence

Let en=xn−x∗e_n=x_n-x^\ast. A convergent iteration has order pp if, under the usual nonzero-error assumptions,

lim⁡n→∞∣en+1∣∣en∣p=C,0<C<∞.\lim_{n\to\infty} \frac{|e_{n+1}|}{|e_n|^p} =C, \qquad 0<C<\infty.

For a smooth scalar mapping:

  • If 0<∣g′(x∗)∣<10<|g'(x^\ast)|<1, convergence is linear, with asymptotic factor ∣g′(x∗)∣|g'(x^\ast)|.
  • If g′(x∗)=0g'(x^\ast)=0 and g′′(x∗)≠0g''(x^\ast)\ne0, convergence is quadratic.
  • More generally, if the first nonzero derivative at the fixed point is the ppth derivative, with p≥2p\ge2, convergence is locally of order pp, 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:

g(x)=x−f(x)f′(x).g(x)=x-\frac{f(x)}{f'(x)}.

At a simple root of a sufficiently smooth function, g′(x∗)=0g'(x^\ast)=0, which explains its local quadratic convergence. This local advantage does not imply convergence from arbitrary starting values.

Vector and linear iterations

For a mapping g:Rm→Rmg:\mathbb{R}^m\to\mathbb{R}^m, the update remains

xn+1=g(xn).x_{n+1}=g(x_n).

A contraction estimate can be expressed using a norm:

∥g(x)−g(y)∥≤q∥x−y∥,q<1.\|g(x)-g(y)\|\le q\|x-y\|, \qquad q<1.

If gg is continuously differentiable near a fixed point, its Jacobian matrix governs local behavior:

en+1=Dg(x∗)en+o(∥en∥).e_{n+1}=Dg(x^\ast)e_n+o(\|e_n\|).

A sufficient condition for local convergence is

ρ(Dg(x∗))<1,\rho(Dg(x^\ast))<1,

where the spectral radius ρ\rho 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

xn+1=Bxn+c,x_{n+1}=Bx_n+c,

the error satisfies exactly

en+1=Ben.e_{n+1}=Be_n.

Convergence to a unique fixed point from every initial vector occurs if and only if

ρ(B)<1.\rho(B)<1.

This framework includes stationary methods for a system of linear equations. Given Ax=bAx=b, choose a splitting

A=M−NA=M-N

with MM invertible. Then

xn+1=M−1Nxn+M−1b.x_{n+1}=M^{-1}Nx_n+M^{-1}b.

Different splittings yield methods such as Jacobi and Gauss–Seidel iteration. In implementation, applying M−1M^{-1} generally means solving a simpler linear system, not explicitly forming an inverse matrix.

Relaxation and acceleration

A relaxed iteration replaces the direct update by

xn+1=(1−ω)xn+ωg(xn).x_{n+1}=(1-\omega)x_n+\omega g(x_n).

For ω≠0\omega\ne0, it has the same fixed points as gg. Values 0<ω<10<\omega<1 are called *under-relaxation*; values ω>1\omega>1 are called over-relaxation.

At a scalar fixed point, the derivative of the relaxed mapping is

1−ω+ωg′(x∗).1-\omega+\omega g'(x^\ast).

Choosing ω\omega can improve convergence or stabilize some oscillatory iterations, but it can also cause divergence. Under-relaxation is not a universal remedy: if g′(x∗)>1g'(x^\ast)>1, every positive ω\omega leaves this derivative greater than one.

Acceleration methods use information from several iterates. For a scalar sequence, Aitken's delta-squared process forms

x^n=xn−(xn+1−xn)2xn+2−2xn+1+xn,\widehat{x}_n =x_n-\frac{(x_{n+1}-x_n)^2} {x_{n+2}-2x_{n+1}+x_n},

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

    y′(t)=F(t,y(t)),y(t0)=y0,y'(t)=F(t,y(t)),\qquad y(t_0)=y_0,

    Picard iteration applies the integral operator

    yn+1(t)=y0+∫t0tF(s,yn(s)) ds.y_{n+1}(t) =y_0+\int_{t_0}^{t}F(s,y_n(s))\,ds.

    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

    xn+1=xn−α∇F(xn).x_{n+1}=x_n-\alpha\nabla F(x_n).

    Its fixed points are stationary points of FF; 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

∥xn+1−xn∥≤εabs+εrel∥xn+1∥.\|x_{n+1}-x_n\| \le \varepsilon_{\mathrm{abs}} +\varepsilon_{\mathrm{rel}}\|x_{n+1}\|.

This measures the step size, not directly the error.

Define the fixed-point residual by

r(x)=g(x)−x.r(x)=g(x)-x.

Under a contraction estimate with constant q<1q<1,

∥x−x∗∥≤∥r(x)∥1−q.\|x-x^\ast\| \le \frac{\|r(x)\|}{1-q}.

Thus a residual becomes a certified error bound when an appropriate contraction constant is known. If qq is close to one, a small residual may still correspond to a much larger error.

For a reformulated equation f(x)=0f(x)=0, the residual of the original equation also matters. In the iteration g(x)=x−λf(x)g(x)=x-\lambda f(x), a very small λ\lambda can produce tiny steps even when f(x)f(x) 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.