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. 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. Given a sequence formula_1, one associates with this sequence the new sequence which can, with improved  numerical stability, also be written as or equivalently as where and for formula_7 Obviously, formula_8 is ill-defined if formula_9 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 formula_8 restricted to indices formula_11 with a sufficiently large formula_12. 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 Δ² operation may cancel too many significant digits. (It would be better for numerical calculation to use formula_13 rather than formula_14 .) Properties. Aitken's delta-squared process is a method of acceleration of convergence, and a particular case of a nonlinear sequence transformation. formula_15 will converge linearly to formula_16 if there exists a number μ ∈ (0, 1) such that Aitken's method will accelerate the sequence formula_18 if formula_19 formula_20 is not a linear operator, but a  constant term drops out, viz: formula_21, if formula_16 is a constant. This is clear from the expression of formula_23 in terms of the finite difference operator formula_24. Although the new process does not in general converge quadratically, it can be shown that for a fixed point process, that is, for an iterated function sequence formula_25 for some function formula_26, 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 formula_27 , where <math>0: The sequence formula_23 will then go to the limit like formula_29 goes to zero. Geometrically, the graph of an exponential function formula_30 that satisfies formula_31, formula_32 and formula_33 has an horizontal asymptote at formula_34 (if formula_35). One can also show that if formula_36 goes to its limit formula_16 at a rate strictly greater than 1, formula_23 does not have a better rate of convergence. (In practice, one rarely has e.g. quadratic convergence which would mean over 30 resp. 100 correct decimal places after 5 resp. 7 iterations (starting with 1 correct digit); usually no acceleration is needed  in that case.) In practice, formula_23 converges much faster to the limit than formula_36 does, as demonstrated by the example calculations below. Usually, it is much cheaper to calculate formula_23 (involving only calculation of differences, one multiplication and one division) than to calculate many more terms of the sequence formula_36. 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. Example calculations. Example 1: The value of formula_43 can be approximated by assuming an initial value for formula_44 and iterating the following: Starting with formula_46  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. Example 2: The value of formula_47 may be calculated as an infinite sum: 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. The following is an example of using the Aitken extrapolation to help find the limit of the sequence formula_49 when given some initial formula_50 where the limit of this sequence is assumed to be a fixed point formula_26 (say formula_52). For instance, if the sequence is given by formula_53 with starting point formula_54 then the function will be formula_55 which has formula_56 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 formula_57. The Aitken extrapolates will be denoted by codice_1. 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 codice_2. 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 codice_3 of the true value. %These choices depend on the problem being solved x0 = 1 %The initial value f(x) = (1/2)*(x + 2/x) %The function that finds the next element in the sequence tolerance = 10^-10 %10 digit accuracy is desired epsilon = 10^-16 %Do not divide by a number smaller than this maxIterations = 20 %Do not allow the iterations to continue indefinitely haveWeFoundSolution = false %Were we able to find the solution to within the desired tolerance? not yet for i = 1 : maxIterations end if (haveWeFoundSolution  == false) %If we were not able to find a solution to within the desired tolerance end