DerivationNonlinear equationsadvanced

Derivation: fixed-point convergence and order

Expanding $\phi$ by Taylor around the fixed point yields the method's error equation and proves both the $|\phi'(\alpha)|<1$ criterion and the order theorem.

Taylor of φ around the fixed point

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.