The algorithm
Given a set of n+1 data points (xi, yi) where no two xi are the same, the interpolating polynomial is the polynomial p of degree at most n with the property
- p(xi) = yi for all i = 0,…,n
This polynomial exists and it is unique. Neville’s algorithm evaluates the polynomial at some point x.
Let pi,j denote the polynomial of degree j − i which goes through the points (xk, yk) for k = i, i + 1, …, j. The pi,j satisfy the recurrence relation
This recurrence can calculate p0,n(x), which is the value being sought. This is Neville’s algorithm.
For instance, for n = 4, one can use the recurrence to fill the triangular tableau below from the left to the right.
This process yields p0,4(x), the value of the polynomial going through the n + 1 data points (xi, yi) at the point x.
This algorithm needs O(n2) floating point operations.
The derivative of the polynomial can be obtained in the same manner, i.e: