NEVILLES ALGORITHM

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

  p_{{i,i}}(x)=y_{i},\,  0\leq i\leq n,\,
 p_{{i,j}}(x)={\frac {(x_{j}-x)p_{{i,j-1}}(x)+(x-x_{i})p_{{i+1,j}}(x)}{x_{j}-x_{i}}},\,  0\leq i<j\leq n.\,

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.

 p_{{0,0}}(x)=y_{0}\,
 p_{{0,1}}(x)\,
 p_{{1,1}}(x)=y_{1}\,  p_{{0,2}}(x)\,
 p_{{1,2}}(x)\,  p_{{0,3}}(x)\,
 p_{{2,2}}(x)=y_{2}\,  p_{{1,3}}(x)\,  p_{{0,4}}(x)\,
 p_{{2,3}}(x)\,  p_{{1,4}}(x)\,
 p_{{3,3}}(x)=y_{3}\,  p_{{2,4}}(x)\,
 p_{{3,4}}(x)\,
 p_{{4,4}}(x)=y_{4}\,

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:

 p'_{{i,i}}(x)=0,\,  0\leq i\leq n,\,
 p'_{{i,j}}(x)={\frac {(x_{j}-x)p'_{{i,j-1}}(x)-p_{{i,j-1}}(x)+(x-x_{i})p'_{{i+1,j}}(x)+p_{{i+1,j}}(x)}{x_{j}-x_{i}}},\,  0\leq i<j\leq n.\,