Aitken's delta-squared process
Aitken's delta-squared process
In numerical analysis, Aitken's delta-squared process or Aitken Extrapolation is a series acceleration method, used for accelerating the rate of convergence of a sequence. It is named after Alexander Aitken, who introduced this method in 1926.[1] Its early form was known to Seki Kōwa (end of 17th century) and was found for rectification of the circle, i.e. the calculation of π. It is most useful for accelerating the convergence of a sequence that is converging linearly.
Definition
which can, with improved numerical stability, also be written as
or equivalently as
where
and
Properties
Aitken's delta-squared process is a method of acceleration of convergence, and a particular case of a nonlinear sequence transformation.
Example calculations
n | x = iterated value | Ax |
0 | 1 | 1.4285714 |
1 | 1.5 | 1.4141414 |
2 | 1.4166667 | 1.4142136 |
3 | 1.4142157 | -- |
4 | 1.4142136 | -- |
It is worth noting here that Aitken's method does not save two iteration steps; computation of the first three Ax values required the first five x values. Also, the second Ax value is decidedly inferior to the 4th x value, mostly due to the fact that Aitken's process assumes linear, rather than quadratic, convergence.
n | term | x = partial sum | Ax |
0 | 1 | 1 | 0.79166667 |
1 | −0.33333333 | 0.66666667 | 0.78333333 |
2 | 0.2 | 0.86666667 | 0.78630952 |
3 | −0.14285714 | 0.72380952 | 0.78492063 |
4 | 0.11111111 | 0.83492063 | 0.78567821 |
5 | −9.0909091×10−2 | 0.74401154 | 0.78522034 |
6 | 7.6923077×10−2 | 0.82093462 | 0.78551795 |
7 | -6.6666667×10−2 | 0.75426795 | -- |
8 | 5.8823529×10−2 | 0.81309148 | -- |
In this example, Aitken's method is applied to a sublinearly converging series, accelerating convergence considerably. It is still sublinear, but much faster than the original convergence: the first Ax value, whose computation required the first three x values, is closer to the limit than the eighth x value.
Example pseudocode for Aitken extrapolation
See also
Rate of convergence
Limit of a sequence
Fixed point iteration
Richardson extrapolation
Sequence transformation
Shanks transformation
Steffensen's method