View source for Aitken scheme

A method for computing the value at a point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011220/a0112201.png" /> of the interpolation polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011220/a0112202.png" /> with respect to the nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011220/a0112203.png" />, based on the successive application of the formula

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011220/a0112204.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011220/a0112205.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011220/a0112206.png" /> is the interpolation polynomial with interpolation nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011220/a0112207.png" />, in particular, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011220/a0112208.png" /> (see [[Interpolation formula]]). The process of computations by means of (*) 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011220/a0112209.png" /> 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. Edingburgh 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>