Aitken scheme

From Encyclopedia of Mathematics
Jump to: navigation, search

2010 Mathematics Subject Classification: Primary: 65D05 [MSN][ZBL]

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.


[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)


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.


[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)
How to Cite This Entry:
Aitken scheme. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by M.K. Samarin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article