Alexander Aitken
(1895 - 1967)
A remarkable formula
Slices of life
Here is a very peculiar and too much underestimated man... I hope that this site will make its tremendous formula of acceleration of the convergence, Delta2, more famous !
But let's rather dive in the story of this uncommon mathematician:
Alexander Aitken was born in New Zealand in 1895. Studying languages and mathematics from 1913, he is wounded at the battle of the Somme during first world war. Schocked by this event, he sets in Edinburgh in Scotland after 3 months of hospital. Endowed with an extraordinary memory (he knows 2000 digits of Pi and is able to give any digit at the n-th place!!), he develops the famous *Delta2* accelerating series in an optimal way. But this first-rate memory too often calls him back the battle of the Somme and traumatizes him. He writes then his memories but they also aggravate his relative mental madness and he finally died in 1967.
About
We said *Delta2* accelerates certain series in an optimal way . It is conceived to better work with geometrical sequences. With those series, it directly gives limit at the end of 3 iterations, otherwise it tries to guess the limit of this series. If it does not find it, it will increase at least convergence.
Delta2's properties are rather extraordinary, let us take for example series for
ln(1+x)=
valid on *]-1,1]* as each knows. If one makes *x=2*, series is going to diverge, naturally. Well this dear *Delta2*
is going to make it converge during a little while !!! Look rather:
*ln(3)=1,0986*...
With the series at rank *8*, we obtain *-19,31* (!)
With *Delta2* iterated twice, at rank *8*, we obtain *1,09**79*
Later we go away from the real value. But the completely fake values in the series give a good value with the *Delta2*,
it is somewhat fabulous, isn't it?
Generally,*Delta2* accelerates all the series whose ratio of two consecutive differences converges to a limit included between 1 and -1, that is naturally the case of geometrical sequences.
Aitken's Delta2 is numerically very unstable because numerator and the denominator are close to 0 and it is so necessary to calculate with a great amount of digits ! The second member of the formula will be rather used, being more stable...
Proof
Formally, if we build *t*_{n} from *x*_{n} , this last one converging towards *L*, we say that there is acceleration of the convergence if we have:
That is easy to understand, intuitively...
We are going to build *Delta2* and show that it verifies this property...
Let's take a series *x*_{n} converging towards *L* with an error *e*_{n}=x_{n}-L verifying
(1)
We are going to build a series *t*_{n} from *x*_{n} which will converge faster. That is not very long, and very interesting, you will see!
**Construction :**
Let us suppose that eq (1) is exact for every *n* (without going to infinity) , that is *e*_{n+1}=Ae_{n} (2)
*Now, we have *e*_{n}=x_{n}-L by definition so we immediately obtain:
*x*_{n+2}-x_{n+1}=A(x_{n+1}-x_{n}) (3)
*Let *x*_{n}=x_{n+1}-x_{n}. (4)
According to (2) and the definition of *e*_{n} , it comes *x*_{n+1}-L=A(x_{n}-L) and so *L(1-A)=x*_{n+1}-Ax_{n} and finally :
*=x*_{n}- (5)
*Let's compute ^{2}*x*_{n}=(x_{n})=x_{n+1}-x_{n}=x_{n+2}-2x_{n+1}+x_{n}. (6)
Now, we have *1-A=1-* so, we deduct from it:
*L=x*_{n}-
But because the starting hypothesis (1) is only true at the limit, a new series is introduced:
*t*_{n}=x_{n}- (7)
with *t*_{n} tending to *L* in the infinity
Proof of the theorem:
Being good architects, having built this series, let us now verify that this series indeed converges faster !
Because we are not anymore at the limit, let us write e_{n+1}=(A+ß_{n})e_{n} where *ß*_{n} tends to *0*
*A small computation gives:
*e*_{n}=x_{n+1}-L-x_{n}+L=x_{n}
^{2}e_{n}=e_{n}+2-2e_{n+1}+e_{n}=x_{n+2}-2x_{n+1}+x_{n}=^{2}x_{n}
Let us express e_{n} and ^{2}e_{n} , which will give x_{n} and ^{2}x_{n} :
*On one hand, e_{n+2}=(A+ß_{n+1})e_{n+1}=(A+ß_{n+1})(A+ß_{n})e_{n} and so
^{2}e_{n}=e_{n+2}-2e_{n+1}+e_{n}=(A+ß_{n+1})(A+ß_{n})e_{n}-2(A+ß_{n})e_{n}+e_{n}=(A-1)^{2}e_{n}+ß_{n}'e_{n}
where ß_{n}'=Aß_{n}+Aß_{n+1}+ß_{n+1}ß_{n}-2ß_{n} tends to *0* at infinity
*On the other hand,
e_{n}=e_{n+1}-e_{n}=(A+ß_{n})e_{n}-e_{n}=(A-1+ß_{n})e_{n}
We replace now in (5) and we obtain :
*t*_{n}=x_{n}- and by dividing by *x*_{n}-L=e_{n}#0 :
And theorem is eventually proved, there is acceleration of the convergence.
It only remains to express *x*_{n} and* *^{2}x_{n} in *t*_{n} like in (4) and (6) to find the formula of Aitken's *Delta2*. After this proof, I hope that everyone will have realized where the name *Delta2* comes from !
Thanks to David Jelgersma for original translation
back to home page |