Free account · your comment posts right after signup
Also known as Aitken extrapolation, Aitken's Δ² 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 as part of an extension to Bernoulli's method. It is most useful for accelerating the convergence of a sequence that is converging linearly. A precursor form was known to Seki Kōwa and applied to the rectification of the circle, i.e., to the calculation of π.
Article
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 as part of an extension to Bernoulli's method. It is most useful for accelerating the convergence of a sequence that is converging linearly. 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 π.
Contents
Definition
Given a sequence
X
=
(
x
n
)
{\displaystyle X={(x_{n})}}
with
n
=
0
,
1
,
2
,
3
,
…
,
{\displaystyle n=0,1,2,3,\ldots ,}
Aitken's delta-squared process associates to this sequence the new sequence
Both are the same sequence algebraically but the latter has improved numerical stability in computational implementation.
A
[
X
]
{\textstyle A[X]}
is ill-defined if the sequence
Δ
2
[
X
]
=
(
Δ
2
x
n
)
{\textstyle \Delta ^{2}[X]=(\Delta ^{2}x_{n})}
contains a zero element, which occurs if the sequence of forward differences,
Δ
[
X
]
=
(
Δ
x
n
)
,
{\textstyle \Delta [X]=(\Delta x_{n}),}
has any repeated term. 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
X
{\displaystyle X}
with indices
n
>
n
0
{\displaystyle n>n_{0}}
such that
n
0
{\displaystyle n_{0}}
is the last index for which the sequence
Δ
[
X
]
{\textstyle \Delta [X]}
repeats. 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
Δ
2
{\textstyle \Delta ^{2}}
sequence transformation may cancel significant digits.
Properties
Aitken's delta-squared process is an acceleration of convergence method and a particular case of a nonlinear sequence transformation.
A sequence
X
=
(
x
n
)
{\textstyle X=(x_{n})}
that converges to a limiting value
ℓ
{\textstyle \ell }
is said to converge linearly, or more technically Q-linearly, if there is some number
μ
∈
(
0
,
1
)
{\textstyle \mu \in (0,1)}
for which
lim
n
→
∞
|
x
n
+
1
Example calculations
Example 1: The value of
2
≈
1.4142136
{\displaystyle {\sqrt {2}}\approx 1.4142136}
can be approximated by assuming an initial value for
x
0
{\displaystyle x_{0}}
and iterating the following sequence, called Heron's method:
This means that asymptotically, the distance between the sequence and its limit shrinks by nearly the same proportion,
μ
,
{\displaystyle \mu ,}
on every step and the ratio of reduction becomes closer and closer to that proportion. This is also sometimes called "geometric convergence," since it is a characteristic property for geometric series, or "exponential convergence," since it is convergence like
μ
n
=
exp
(
n
ln
μ
)
.
{\displaystyle \mu ^{n}=\exp(n\ln \mu ).}
Aitken's method will accelerate the convergence of a sequence
does not have a better rate of convergence. (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.)
In practice,
A
[
X
]
{\displaystyle A[X]}
often converges much faster to the limit than
X
{\displaystyle X}
does, as demonstrated by the example calculations below.
Usually, it is much cheaper to calculate
A
[
X
]
{\displaystyle A[X]}
(involving only calculation of differences, one multiplication and one division) than to calculate many more terms of the sequence
X
{\displaystyle X}
. 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.
It is worth noting here that Aitken's method does not save the cost of calculating two iterations here; computation of the first three
A
[
X
]
{\textstyle A[X]}
values required the first five
X
{\textstyle X}
values. Also, the second
A
[
X
]
{\textstyle A[X]}
value is less accurate than the 4th
X
{\textstyle X}
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.
Example 2: The value of
π
4
{\displaystyle {\frac {\pi }{4}}}
may be calculated as an infinite sum via the Leibniz formula for π:
In this example, Aitken's method is applied to a sublinearly converging series and accelerates convergence considerably. The convergence is still sublinear, but much faster than the original convergence: the first
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
f
′
(
α
)
{\displaystyle f^{\prime }(\alpha )}
. 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. This small number will be denoted by epsilon. 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.
