What is the computational benefit of Aitken's $\Delta^2$ process?

Question

Let $(x_n)$ be a linearly convergent sequence. Then $$y_n := x_n - \frac{(x_{n+1}-x_n)^2}{x_{n-2} - 2x_{n+1} + x_n}$$ is called Aitken's $\Delta^2$ process. Remarkably, $(y_n)$ converges faster than $(x_n)$.

I don't understand what computational benefit does it bring us? It seems that we still need to find all the members of $(x_n)$ is the process. So why do they include it in books on numerical methods?

Answer 1

From the Wiki article: "Usually, it is much cheaper to calculate Ax (involving only calculation of differences, one multiplication and one division) than to calculate many more terms of the sequence x. Care must be taken, however, to avoid introducing errors due to insufficient precision when calculating the differences in the numerator and denominator of the expression."

Ideally, all you really need to do is compute the first few terms $x_n$. Upon performing the transformation, for the right sort of sequence, the few $y_n$ coupled with the few $x_n$ will be VERY close to the limit, which may only have been achieved by computing many $x_n$.

The transformation works as follows: if $x_n = L+\epsilon_1^n + \epsilon_2^n$, where $L$ is the limit, then one may find that $y_n = L+\epsilon_1^n$. That is, the transformation eliminates a source of the error.

Also see Bender & Orszag, Ch. 8.1 on the Shanks transformation for an illustration of how the error reduction works. I'll show it for one term.

(By the way, I don't think the transformation is correct as you wrote it.)

Let $x_n = L + a \epsilon^n$. Then

$$y_n = x_n - \frac{(x_{n+1}-x_n)^2}{x_{n+2}-2 x_{n+1}+x_n} = L+a \epsilon^n - \frac{a (\epsilon^{n+1}-\epsilon^n)^2}{\epsilon^{n+2}-2 \epsilon^{n+1}+\epsilon^n} = L+a \epsilon^n - \frac{a \epsilon^n (1-\epsilon)^2}{(1-\epsilon)^2} = L$$

Answer 2

Compare the iterates $x_n=\cos(x_{n-1})$ and $y_n$.

$$\begin{align}0.00000000, \\ 1.00000000, \\ 0.54030231,&\ 0.68507336\\ 0.85755322,&\ 0.72801036\\ 0.65428979,&\ 0.73366516\\ 0.79348036,&\ 0.73690629\\ 0.70136877,&\ 0.73805042\\ 0.76395968,&\ 0.73863610\\ 0.72210243,&\ 0.73887658\\ 0.75041776,&\ 0.73899224\\ 0.73140404,&\ 0.73904251\\ 0.74423735,&\ 0.73906595\\ 0.73560474,&\ 0.73907638\\ 0.74142509,&\ 0.73908118\\ 0.73750689,&\ 0.73908333\\ 0.74014734,&\ 0.73908432\\ 0.73836920,&\ 0.73908476\\ 0.73956720,&\ 0.73908497\\ 0.73876032,&\ 0.73908506\\ 0.73930389,&\ 0.73908510\\ 0.73893776,&\ 0.73908512\\ 0.73918440,&\ 0.73908513\\ 0.73901826,&\ 0.73908513\\ 0.73913018,&\ 0.73908513\\ \end{align}$$

You can stop much earlier with $y_n$.

Answer 3

Other answers already pointed out why using Aitken is useful, let me just mention one surprising property of Aitken's method. In same cases it can even "fix" convergence of sequences which were not convergent in the first place.

For example consider $f(x)=5-x$, which has fixed point $x=2.5$. By using simple iteration method you get the sequence

$$ x_n = 5-x_{n-1} $$

which gives you

\begin{align} n&\ & x_n\\ 0&\ & 1\\ 1&\ & 4\\ 2&\ & 1\\ 3&\ & 4\\ \vdots& & \vdots \end{align} This sequence does not converge apparently. Now if you apply the Aitken's method, you get

\begin{align} n&\ & y_n\\ 0&\ & -\\ 1&\ & 2.5\\ 2&\ & 2.5\\ 3&\ & 2.5\\ \vdots& & \vdots \end{align}

Although it does not look entirely rigorous, I think this is interesting property to mention.