Neville's Algorithm
Neville's algorithm is an interpolation algorithm which proceeds by first fitting a polynomial of degree 0 through the point (x_k,y_k) for k=1, ..., n, i.e., P_k(x)=y_k. A second iteration is then performed in which P_i and P_(i+1) are combined to fit through pairs of points, yielding P_(12), P_(23), .... The procedure is repeated, generating a "pyramid" of approximations until the final result is reached
The final result is
| P_(i(i+1)...(i+m))=((x-x_(i+m))P_(i(i+1)...(i+m-1)))/(x_i-x_(i+m))+((x_i-x)P_((i+1)(i+2)...(i+m)))/(x_i-x_(i+m)). |
See also
Bulirsch-Stoer AlgorithmExplore with Wolfram|Alpha
WolframAlpha
More things to try:
Cite this as:
Weisstein, Eric W. "Neville's Algorithm." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/NevillesAlgorithm.html