- Aitken's delta-squared process
numerical analysis, Aitken's delta-squared process is a series accelerationmethod, used for accelerating the rate of convergenceof a sequence. It is named after Alexander Aitken, who introduced this method in 1926 [Alexander Aitken, "On Bernoulli's numerical solution of algebraic equations", "Proceedings of the Royal Society of Edinburgh" (1926) 46 pp. 289-305.] . It is most useful for accelerating the convergence of a sequence that is converging linearly.
Given a sequence , one associates to this sequence the new sequence
which can also be written as
(To use this nice operator notation, one has to allow for the indices to start from "n" = 2 on, or apply a translation operator which first shifts the sequence indices by two, or to adopt the convention that "xn" = 0 for all "n" < 0.)
Obviously, "Ax" is ill-defined if Δ²x contains a zero element, or equivalently, if the sequence of
first differences has a repeating term. From a theoretical point of view, assuming that this occurs only for a finite number of indices, one could easily agree to consider the sequence "Ax" restricted to indices "n>n0" with a sufficiently large "n0". 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 become too important in the denominator, where the Δ² operation may cancel too many significant digits.
Aitken's delta-squared process is a method of
acceleration of convergence, and a particular case of a nonlinear sequence transformation.
When converges linearly to , then
is not a linear operator, but a constant term drops out, viz: , if is a constant. This is clear from the expression of in terms of the
finite differenceoperator .
Although the new process does not in general converge quadratically, it can be shown that for a
fixed pointprocess, that is, for an iterated functionsequence for some function , converging to a fixed point, the convergence is quadratic. In this case, the technique is known as Steffensen's method.
Empirically, the A-operation eliminates the "most important error term". One can check this by considering a sequence of the form , where
Wikimedia Foundation. 2010.
Look at other dictionaries:
Alexander Aitken — Alexander Craig Aitken, FRS FRSE FRSL (1 April 1895 – 3 November 1967) was one of New Zealand s greatest mathematicians. He studied for a PhD at the University of Edinburgh, where his dissertation, Smoothing of Data , was considered so impressive … Wikipedia
Del squared (disambiguation) — Del squared may refer to: The Laplace operator, a differential operator often denoted by the symbol ∇2. Aitken s delta squared process, a numerical analysis technique used for accelerating the rate of convergence of a sequence. See also Del, a… … Wikipedia
Series acceleration — In mathematics, series acceleration is one of a collection of sequence transformations for improving the rate of convergence of a series. Techniques for series acceleration are often applied in numerical analysis, where they are used to improve… … Wikipedia
List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra … Wikipedia
Seki Kōwa — Infobox Scientist name = Kōwa Seki (Takakazu Seki) image width = 200px caption = Kōwa Seki (Takakazu Seki) birth date = March(?), 1642(?) death date = December 5, 1708 (Gregorian calendar) residence = nationality = ese birth place = Edo or… … Wikipedia
Fixed point iteration — In numerical analysis, fixed point iteration is a method of computing fixed points of iterated functions.More specifically, given a function f defined on the real numbers with real values and given a point x 0 in the domain of f, the fixed point… … Wikipedia
Richardson extrapolation — In numerical analysis, Richardson extrapolation is a sequence acceleration method, used to improve the rate of convergence of a sequence. It is named after Lewis Fry Richardson, who introduced the technique in the early 20th century. [cite… … Wikipedia
List of mathematics articles (A) — NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A … Wikipedia
Rate of convergence — In numerical analysis, the speed at which a convergent sequence approaches its limit is called the rate of convergence. Although strictly speaking, a limit does not give information about any finite first part of the sequence, this concept is of… … Wikipedia
Sequence transformation — In mathematics, a sequence transformation is an operator acting on a given space of sequences. Sequence transformations include linear mappings such as convolution with another sequence, and resummation of a sequence and, more generally, are… … Wikipedia