In a previous post I showed some spreadsheet data to demonstrate the Aitken acceleration process. Here, I’ll go through an example where a sequence converges linearly: let where . We use the form (I am too lazy to use the traditional “p-hat” notation). First, note that the denominator works out to
The numerator is a tiny bit more work: the terms cancel and as far as the rest:
which simplifies to a term involving and one that doesn’t. Here is the term involving :
which, of course, is just times the denominator.
Now the terms not involving :
So our fraction is merely
This can be rearranged to
Clearly as goes to infinity, the error goes to zero very quickly. It might be instructive to look at the ratio of the errors for and :
This ratio is
Note that in the right hand factor: both squared factors are fixed and the coefficients go to infinity as goes to infinity. If one multiplies out, one obtains:
. In the limit, the first term decreases to and the second goes to infinity.
Hence the errors in the accelerated sequence are smaller.