Neville's Algorithm

An interpolation Algorithm which proceeds by first fitting a Polynomial $P_k$ of degree 0 through the points $(x_k,y_k)$ for $k=0,$ ..., $n$, i.e., $P_k=y_k$. A second iteration is then performed in which $P_{12}$ is 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

$$\matrix{P_1\cr P_2\cr P_3\cr P_4\cr} \matrix{P_{12}\cr P_{23}\cr P_{34}\cr}\matrix{P_{123}\cr P_{234}\cr} P_{1234}.$$

The final result is

$$P_{i(i+1)\cdots(i+m)} = {(x-x_{i+m})P_{i(i+1)\cdots(i+m-1)}\... ...-x_{i+m}}+{(x_i-x)P_{(i+1)(i+2)\cdots(i+m)}\over x_i-x_{i+m}}.$$

See also Bulirsch-Stoer Algorithm