Graphical Derivation of Aitken's $\Delta ^2$-Method

  

Figure: Aitken's $\Delta ^2$-Method

Join two successive iteration points on the graph of y=g(x) (see Fig. ) by a straight line, and extrapolate until it meets the line y=x. Similar triangles give

$$\frac{x_n^A-x_n}{\Delta x_n}=\frac{x_n^A-x_{n+1}}{\Delta x_{n+1}},$$

which may be solved for x_n^A to obtain

$$\begin{array} {lcl}x_n^A & = & \frac{x_n\Delta x_{n+1}-x_{n+... ..._n}\\ & = & x_n-\frac{(\Delta x_n)^2}{\Delta ^2x_n}\end{array}$$

as before.

The interesting thing is that Aitken's method can even give a better approximation to a root when the function iteration diverges, as can be seen from Figure . Note however that it is not converging to the answer in any sense.

  

Figure: Aitken's $\Delta ^2$-Method for a Divergent Iteration

Example Solve x²-3x+2=0 using Aitken's method to extrapolate the function iteration $x_{n+1}=\frac{1}{3}(x_n^2-2)$.

The result of 2 iterations are:

$$\begin{array} {cccc} n & 0 & 1 & 2\\ x_n & 3 & 11/3 & 139/27... ...ta x_n & 2/3 & 40/27 & \\ \Delta ^x_n & 22/27 & & \end{array},$$

from which we find

$$x_0^A=3-\frac{(2/3)^2}{22/27}=2\frac{5}{11}.$$

This is a better answer than any of the functional iterations which diverge.

We establish a measure of the effectiveness of Aitken's $\Delta ^2$-method in the following theorem.

Theorem 3643

Let $\left( x_n \right)$ be any sequence with limit $\alpha$such that $e_n=x_n-\alpha$ satisfies for $n=0,1,\ldots ,$

$$e_{n+1}=(L+\epsilon _n)e_n,\quad e_n\not= 0,$$

where L is a constant satisfying $\left\vert \kern.05em L \kern.05em \right\vert<1$ and $\epsilon _n\to 0$ as $n\to \infty$. Then the sequence $\left( x_n^A \right)$ defined by

$$x_n^A=x_n-\frac{(\Delta x_n)^2}{\Delta ^2x_n}$$

is defined for large enough n and converges to $\alpha$ faster than $\left( x_n \right)$ in the sense that

$$\frac{x_n^A-\alpha }{x_n-\alpha }\to 0\mbox{ as }n\to \infty .$$

This applies directly to the functional iteration x_n+1=g(x_n), for which

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

if g' is continuous, where $\epsilon _n\to 0$ as $n\to \infty$.If the iteration is convergent $\left\vert \kern.05em g'(\alpha ) \kern.05em \right\vert<1$ and we can take $L=g'(\alpha )$ in the theorem.