Neville Interpolating Polynomial

Neville-Aikten's algorithm allows us to interpolate a set of points $ (x_i,y_i) $ and, if necessary, obtain the expression of the interpolating polynomial.

The method relies on a recursive construction of polynomials $ P_{ij}(x) $ that progressively approach the final polynomial.

Neville interpolation uses 3 steps:

1 - Initialize zero-degree polynomials: $ P_i(x) = y_i $ for each point $ (x_i,y_i) $.

2 - Construct the higher-order polynomials using the recurrence relation: $$ P_{ij}(x) = \frac{(x_j-x)P_i(x) + (x-x_i)P_j(x)}{x_j-x_i} $$

3 - Iterate until the final polynomial is obtained

The algorithm can be represented as a pyramid, with each level combining two polynomials from the previous level until the final interpolation polynomial (the interpolation function) is obtained.

Neville-Aikten interpolation has several practical limitations. The calculations quickly become expensive as the number of points increases, because the algorithm requires the construction of O(n^2) intermediate values.

These constraints lead dCode to limit the number of distinct ordinates in the set Q.

Neville's algorithm recursively applies the barycentric formula that underlies Lagrange interpolation. The final polynomial constructed by Neville is algebraically identical to the Lagrange polynomial. However, Neville provides a numerically more stable method for evaluating this polynomial at a given point, without requiring the sum of the Lagrange terms to be specified.