Neville's algorithm

Neville's algorithm is a numerical method for polynomial interpolation. Given n + 1 data points with no two x values the same, there is exactly one polynomial of degree at most n that passes through all of them, and the algorithm evaluates that polynomial at a chosen point without first working out its coefficients. The mathematician Eric Harold Neville derived it in 1934. It fills a triangular table of lower degree interpolating polynomials, each fitted to a run of consecutive points, and combines neighbouring entries with a recurrence relation until a single value remains, the value of the polynomial through all the points. The method rests on the Newton form of the interpolating polynomial and on the recursion relation for divided differences, and it is similar to Aitken's algorithm, which is nowadays not used. Interpolating a single point takes on the order of n squared floating point operations. The derivative of the polynomial can be computed in the same loop, and in 1966 Lyness and Moler showed that a variant with undetermined coefficients gives numerical approximations to derivatives of a function at the origin.