Aitken scheme

A method for computing the value at a point $x$ of the interpolation polynomial $L_n(x)$ with respect to the nodes $x_0,\ldots,x_n$, based on the successive application of the formula $$\label{eq:1} L_k(x) = L_{(0,\ldots,k)}(x) = \frac{1}{x_k - x_0} \left\vert{ \begin{array}{cc} L_{(0,\ldots,k-1)} & x_0 - x \\ L_{(1,\ldots,k)} & x_k - x \end{array} }\right\vert $$ where $L_{(i,\ldots,m)}(x)$ is the interpolation polynomial with interpolation nodes $x_i,\ldots,x_m$, in particular, $L_{(i)}(x) = x_i$ (see Interpolation formula). The process of computations by means of \eqref{eq:1} may finish if the values of two interpolation polynomials of consecutive degrees coincide in the required number of decimal places. The Aitken scheme is convenient for interpolating the values of a function given in the form of a table (of values), by renumbering the interpolation nodes in the order in which $|x - x_i|$ increases.

References

[1]	I.S. Berezin, N.P. Zhidkov, "Computing methods" , 1 , Pergamon (1973) (Translated from Russian)
[2]	N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)

Comments

Aitken published the gist of his method in [a1]. Aitken's scheme is disadvantageous when a number of interpolations must be carried out over the same range. In such cases, an alternative to the computation of the Lagrange polynomials is the use of divided differences in the construction of Newton's interpolation formula.

References

[a1]	A.C. Aitken, "On interpolation by iteration of proportional parts, without the use of differences" Proc. Edinburgh Math. Soc. 3 : 2 (1932) pp. 56–76
[a2]	F.B. Hildebrand, "Introduction to numerical analysis" , McGraw-Hill (1974)