# College Math Teaching

## February 17, 2014

### Aitken acceleration: another “easy” example for the students

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 $p_n = L +a^n + b^n$ where $0 < a < b < 1$. We use the form $q_n = \frac{p_{n+2}p_{n} -(p_{n+1})^2}{p_{n+2} - 2p_{n+1} + p_n}$ (I am too lazy to use the traditional “p-hat” notation). First, note that the denominator works out to $a^n(1-a)^2 +b^n(1-b)^2$

The numerator is a tiny bit more work: the $L^2$ terms cancel and as far as the rest:
$L(a^{n+2} + b^{n+2}) + L(a^n + b^n) +(a^{n+2}+b^{n+2})(a^n + b^2)-2L(a^{n+1}+b^{n+1})-(a^{n+1}+b^{n+1})^2$
which simplifies to a term involving $L$ and one that doesn’t. Here is the term involving $L$:

$L(a^{n+2}-2a^{n+1} + a^n + b^{n+2} -2b^{n+1} +b^n) = L(a^n(1-a)^2 +b^n(1-b)^2)$

which, of course, is just $L$ times the denominator.

Now the terms not involving $L$: $(a^{n+2}+b^{n+2})(a^n+b^n) - (a^{n+1} + b^{n+1})^2 = b^na^n(b^2+a^2-2ab) = b^na^n(b-a)^2$

So our fraction is merely

$\frac{L((a^n(1-a)^2 +b^n(1-b)^2)) + b^na^n(b-a)^2}{a^n(1-a)^2 +b^n(1-b)^2}$ $= L + \frac{b^na^n(b-a)^2}{a^n(1-a)^2 +b^n(1-b)^2}$

This can be rearranged to $L + \frac{(b-a)^2}{\frac{(1-a)^2}{b^n} + \frac{(1-b)^2}{a^n}}$

Clearly as $n$ goes to infinity, the error goes to zero very quickly. It might be instructive to look at the ratio of the errors for $p_n$ and $q_n$:

This ratio is
$(a^n + b^n)\frac{a^n(1-a)^2 + b^n(1-b)^2}{a^nb^n(b-a)^2} =$$(a^n +b^n)(\frac{1}{b^n}(\frac{1-a}{b-a})^2 + \frac{1}{a^n}(\frac{1-b}{b-a})^2)$

Note that in the right hand factor: both squared factors are fixed and the coefficients go to infinity as $n$ goes to infinity. If one multiplies out, one obtains:

$((\frac{a}{b})^n +1)(\frac{1-a}{b-a})^2 + ((\frac{b}{a})^n +1)(\frac{1-b}{b-a})^2$. In the limit, the first term decreases to $(\frac{1-a}{b-a})^2$ and the second goes to infinity.

Hence the errors in the accelerated sequence are smaller.