Quadratic or Second Order Convergence

Since the asymptotic convergence factor is $g'(\alpha )$, the optimum value of this must be zero, for then the error would (eventually) become zero on one iteration. However, the actual convergence factor depends on n and will not be truly zero. Nevertheless, it approaches its asymptotic value, so that making this zero should lead to a rapidly convergent method. Assuming that $g'(\alpha )=0$, and using the Taylor expansion of g about $\alpha$ with $\xi _n\in (\alpha ,x_n)$, the error at the n+1th iteration is

$$\begin{array} {lcl}x_{n+1}-\alpha & = & g(x_n)-g(\alpha )\\ ... ...n )\\ & = & \frac{1}{2}(x_n-\alpha )^2g''(\xi _n ),\end{array}$$

so that the error at the n+1th iteration is proportional to the square of the error at the nth iteration.

Definition 3665

A method for which

$$\renewcommand {\arraystretch}{0.8} \begin{array} {c}\lim \\ n \to \infty \end{array} \frac{x_{n+1}-\alpha }{(x_n-\alpha )^p}$$

takes a finite nonzero value is called a pth order method. When p=2 or 3 it is often said to be quadratically convergent or cubically convergent.

Theorem 3674

Let $g\in C^1[a,b]$ be such that x=g(x) has a root $\alpha \in (a,b)$, with $g'(\alpha )=0$. Then there is a number d>0 such that the functional iteration x_n+1=g(x_n) converges to $\alpha$ for any choice of $x_0\in [\alpha -d, \alpha +d]$. (in other words, a second order method always converges provided we start near enough to the solution.)