Newton Interpolating Polynomial

Newton interpolation refers to a method for constructing an interpolation polynomial passing through a set of points $(x_i,y_i)$. It is based on the calculus of divided differences and provides a polynomial in a factored form that allows for the easy addition of new points without recalculating everything.

To find the Newton interpolation polynomial associated with points $ (x_i,y_i) $, use divided differences to construct the Newton form of the polynomial. From $ n+1 $ known points, the polynomial can be written

$$ P(x)= [y_0] + [y_0,y_1] (x-x_0) + \ldots + [y_0,\ldots ,y_n] (x-x_0) \ldots (x-x_{n-1}) $$

with the notation $ [y_i] $ for divided differences.

Each coefficient $ [y_0,\ldots,y_k] $ is calculated using the values $ (x_i,y_i) $.

Newton Divided Differences are noted $ [y_i] $ and computed by the formula $$ [y_0,\dots ,y_k]=\sum_{j=0}^k {\frac{y_j}{\prod_{0\leq i\leq k,\,i\neq j}(x_j-x_i)}} $$ they intervene in the computation of Newton's interpolation.

Both forms describe the same interpolation polynomial. The Lagrange form uses basic polynomials $ L_i(x) $, while the Newton form relies on factored products $ (x-x_0)\ldots(x-x_{k-1}) $. The two constructions are algebraically equivalent, but the Newton form is more convenient for adding a point without a complete recalculation.