View source for Aitken scheme

{{TEX|done}}{{MSC|65D05}}

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====
<table>
<TR><TD valign="top">[1]</TD> <TD valign="top">  I.S. Berezin,   N.P. Zhidkov,   "Computing methods" , '''1''' , Pergamon  (1973)  (Translated from Russian)</TD></TR>
<TR><TD valign="top">[2]</TD> <TD valign="top">  N.S. Bakhvalov,   "Numerical methods: analysis, algebra, ordinary differential equations" , MIR  (1977)  (Translated from Russian)</TD></TR>
</table>



====Comments====
Aitken published the gist of his method in [[#References|[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 difference]]s in the construction of [[Newton interpolation formula|Newton's interpolation formula]].

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  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</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top">  F.B. Hildebrand,   "Introduction to numerical analysis" , McGraw-Hill  (1974)</TD></TR>
</table>