Neville's algorithm

Summary

Neville's algorithm computes the value at one point $x$ of the interpolation polynomial through given data, without computing its coefficients. It builds a triangular table. Each entry is the value at $x$ of the interpolation polynomial through a block of consecutive nodes. It is computed from two entries for shorter blocks. It costs $O(n^2)$ operations for $n + 1$ nodes. It is often used for extrapolation, for example to the limit $h \to 0$ in Richardson-type methods.