# Aitken scheme

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.

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