GuideNonlinear equationsintermediate

Fixed-point iteration

Rewrite $f(x)=0$ as $x=\phi(x)$ and iterate: when it converges ( $|\phi'(\alpha)|<1$ ), how fast, and the theorem giving the method's order from which derivatives of $\phi$ vanish at the solution.

From f(x)=0 to x=φ(x)

Every equation $f(x)=0$ can be rewritten (in many ways) as a fixed-point problem $x=\phi(x)$ : the solution $\alpha$ satisfies $\phi(\alpha)=\alpha$ . The method is to iterate the function:

x_{k+1}=\phi(x_k),\qquad k=0,1,2,\dots

The order depends on the derivatives of φ

DerivationDerivation: fixed-point convergence and orderView as its own page →

Let $e_k=x_k-\alpha$ . Expand $\phi(x_k)$ by Taylor around $\alpha$ and use $\phi(\alpha)=\alpha$ :
$x_{k+1}=\phi(x_k)=\alpha+\phi'(\alpha)\,e_k+\frac{\phi''(\alpha)}{2}\,e_k^2+\frac{\phi'''(\alpha)}{6}\,e_k^3+\cdots$
Subtracting $\alpha$ leaves the error equation of the fixed-point iteration:
$e_{k+1}=\phi'(\alpha)\,e_k+\frac{\phi''(\alpha)}{2}\,e_k^2+\frac{\phi'''(\alpha)}{6}\,e_k^3+\cdots$
If $\phi'(\alpha)\ne 0$ , the dominant term is linear: $e_{k+1}\approx\phi'(\alpha)e_k$ . Errors contract if $|\phi'(\alpha)|<1$ (linear convergence with factor $|\phi'(\alpha)|$ ) and grow if $|\phi'(\alpha)|>1$ : that is the local convergence criterion.
If moreover $\phi'(\alpha)=\phi''(\alpha)=\dots=\phi^{(p-1)}(\alpha)=0$ and $\phi^{(p)}(\alpha)\ne 0$ , all earlier terms vanish and the first surviving one fixes the order: this is the order theorem for a fixed-point method.
$e_{k+1}=\frac{\phi^{(p)}(\alpha)}{p!}\,e_k^p+\mathcal{O}\bigl(e_k^{p+1}\bigr)$
Immediate application: for Newton, $\phi=x-\frac{f}{f'}$ and $\phi'=\frac{f f''}{(f')^2}$ , which vanishes at a simple root ( $f(\alpha)=0$ ). Since in general $\phi''(\alpha)\ne 0$ , Newton has order 2, agreeing with the direct proof.

This theorem explains why Newton is second order: its iteration function $\phi=x-\frac{f}{f'}$ satisfies $\phi'(\alpha)=0$ at a simple root. The general definition of order and its practical measurement are covered in Convergence order and efficiency.

Example: slow convergence

ExampleIterating φ(x)=cos²x

Solve $x=\cos^2 x$ by directly iterating $x_{k+1}=\cos^2(x_k)$ from $x_0=0.3$ , and estimate the convergence speed.

The first iterates oscillate around the solution: $x_1=0.9127$ , $x_2=0.3741$ , $x_3=0.8665$ , $x_4=0.4193$ , $x_5=0.8343,\dots$ approaching $\alpha=0.641714$ very slowly.
The speed is set by the derivative at the fixed point: $\phi'(x)=-2\cos x\sin x=-\sin 2x$ , and at $\alpha$ :
$|\phi'(\alpha)|=|\sin(2\cdot 0.641714)|=0.959<1$

It converges (the negative sign explains the oscillation), but with factor $0.959$ : 455 iterations are needed to reach an error of $10^{-9}$ . Newton solves the same equation in 5 iterations; this shows the difference between order 1 and order 2.