Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Aitken's delta-squared process
Summary
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. 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.
Given a sequence , one associates with this sequence the new sequence
which can, with improved numerical stability, also be written as
or equivalently as
where
and
for .
Obviously, is ill-defined if contains a zero element, or equivalently, if the sequence of first differences has a repeating term.
From a theoretical point of view, if that occurs only for a finite number of indices, one could easily agree to consider the sequence restricted to indices with a sufficiently large . From a practical point of view, one does in general rather consider only the first few terms of the sequence, which usually provide the needed precision. Moreover, when numerically computing the sequence, one has to take care to stop the computation when rounding errors in the denominator become too large, where the Δ2 operation may cancel too many significant digits. (It would be better for numerical calculation to use rather than .)
Aitken's delta-squared process is a method of acceleration of convergence, and a particular case of a nonlinear sequence transformation.
Convergence of to limit is called "linear" if there is some number μ ∈ (0, 1) for which
Which means that the distance between the sequence and its limit shrinks by nearly the same proportion on every step, and that rate of reduction becomes closer to being constant with every step. (This is also called "geometric convergence"; this form of convergence is common for power series.)
Aitken's method will accelerate the sequence if
is not a linear operator, but a constant term drops out, viz: if is a constant.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.