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.
A precursor form was known to Seki Kōwa (1642 – 1708) and applied to the rectification of the circle, i.e., to the calculation of π.
Both are the same sequence algebraically but the latter has improved numerical stability in computational implementation.
contains a zero element, which occurs if the sequence of forward differences,
From a theoretical point of view, if that occurs only for a finite number of indices, one could apply the Aitken process to only the part of the sequence
In practice, the first few terms of the sequence usually provide desired precision; also, when numerically computing the sequence, one has to take care to stop the computation before rounding errors in the denominator become too large, as the
sequence transformation may cancel significant digits.
Aitken's delta-squared process is an acceleration of convergence method and a particular case of a nonlinear sequence transformation.
is said to converge linearly, or more technically Q-linearly, if there is some number
This means that asymptotically, the distance between the sequence and its limit shrinks by nearly the same proportion,
Aitken's method will accelerate the convergence of a sequence
in terms of the finite difference operator
The new process does not in general converge quadratically, but for an iterated function sequence satisfying
In this case, the technique is known as Steffensen's method.
Empirically, the A-operation eliminates the "most important error term".
Geometrically, the graph of an exponential function
(In practice, one rarely has e.g. quadratic convergence which would mean over 30 (respectively 100) correct decimal places after 5 (respectively 7) iterations (starting with 1 correct digit); usually no acceleration is needed in that case.)
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.
and iterating the following sequence, called Heron's method:
It is worth noting here that Aitken's method does not save the cost of calculating two iterations here; computation of the first three
value, which is not surprising due to the fact that Aitken's process is best suited for sequences that converge linearly, rather than quadratically, and Heron's method for calculating square roots converges quadratically.
may be calculated as an infinite sum via the Leibniz formula for π:
The following is an example of using the Aitken extrapolation to help find the limit of the sequence
where the limit of this sequence is assumed to be a fixed point
as a fixed point (see Methods of computing square roots); it is this fixed point whose value will be approximated.
This pseudo code also computes the Aitken approximation to
The Aitken extrapolates will be denoted by aitkenX.
During the computation of the extrapolate, it is important to check if the denominator becomes too small, which could happen if we already have a large amount of accuracy; without this check, a large amount of error could be introduced by the division.
Because the binary representation of the fixed point could be infinite (or at least too large to fit in the available memory), the calculation will stop once the approximation is within tolerance of the true value.