Fixed-Point Iteration

1. Definition and Principle

To solve an equation $f(x) = 0$, we rewrite it in the equivalent form

and, starting from an initial value $x_0$, perform the iteration

to find the solution (a fixed point). This method is called fixed-point iteration.

For example, to solve $f(x) = x^2 - 3x + 1 = 0$, one can set $x = \dfrac{x^2 + 1}{3}$ (i.e. $g(x) = \dfrac{x^2+1}{3}$) and iterate. Note, however, that the choice of $g$ determines whether the iteration converges or diverges.

2. Convergence Conditions

Whether the iteration $x_{n+1} = g(x_n)$ converges to a fixed point $x^*$ can be decided from the magnitude of the derivative of $g$.

Intuitively, if $|g'(x^*)| < 1$ then $g$ is "contractive" near the fixed point, so the error shrinks at every iteration. Conversely, when $|g'(x^*)| > 1$ the iteration diverges.

Geometric interpretation

• $0 < g'(x^*) < 1$: the iterates approach the fixed point monotonically (from one side).
• $-1 < g'(x^*) < 0$: the iterates converge while oscillating around the fixed point.
• $|g'(x^*)| > 1$: the iterates move away from the fixed point and diverge.
• $|g'(x^*)| = 1$: a borderline case; convergence or divergence depends on higher-order terms.

3. The Banach Fixed-Point Theorem

The theoretical foundation of fixed-point iteration is the Banach fixed-point theorem (the contraction-mapping principle).

From this theorem we also obtain an a priori and an a posteriori error bound.

A priori error bound

A posteriori error bound

The a posteriori bound is important in practice: it lets us estimate the current error from the difference of two consecutive iterates.

4. Algorithm

Pseudocode follows.

function fixedPointIteration(g, x0, tol, maxIter):
    x = x0
    for i = 1 to maxIter:
        x_new = g(x)
        if |x_new - x| < tol:
            return x_new
        x = x_new
    return x  // did not converge

5. Order of Convergence

The value of the derivative of $g$ at the fixed point $x^*$ determines the order of convergence.

Linear convergence

When $g'(x^*) \neq 0$ and $|g'(x^*)| < 1$, the error $e_n = |x_n - x^*|$ satisfies

so the convergence is linear (first order). The smaller $|g'(x^*)|$ is, the faster the convergence.

Quadratic convergence

When $g'(x^*) = 0$ and $g''(x^*) \neq 0$,

so the convergence is quadratic. Newton's method constructs $g$ precisely so that this condition holds.

General condition for order p

When $g'(x^*) = g''(x^*) = \cdots = g^{(p-1)}(x^*) = 0$ and $g^{(p)}(x^*) \neq 0$, the order of convergence is $p$.

6. Worked Examples

7. Relationship with Newton's Method

Newton's method is the special case of fixed-point iteration with $g(x) = x - \dfrac{f(x)}{f'(x)}$. For this $g$,

so when $f(x^*) = 0$ we have $g'(x^*) = 0$, which guarantees quadratic convergence.

Likewise, the secant method, Steffensen's method and others can all be understood within the fixed-point iteration framework.

8. FAQ

9. References

• Wikipedia, "Fixed-point iteration"
• Wikipedia, "Banach fixed-point theorem"
• R. L. Burden & J. D. Faires, Numerical Analysis, 10th ed., Cengage, 2016.
• W. H. Press et al., Numerical Recipes, 3rd ed., Cambridge, 2007.