Newton polynomial

In the mathematical field of numerical analysis, a Newton polynomial, named after its inventor Isaac Newton, is an interpolation polynomial for a given set of data points. The Newton polynomial is sometimes called Newton's divided differences interpolation polynomial because the coefficients of the polynomial are calculated using Newton's divided differences method.

Given a set of k + 1 data points

where no two x_j are the same, the Newton interpolation polynomial is a linear combination of Newton basis polynomials

with the Newton basis polynomials defined as

for j > 0 and ${\displaystyle n_{0}(x)\equiv 1}$.

The coefficients are defined as

where ${\displaystyle [y_{0},\ldots ,y_{j}]}$ are the divided differences defined as $${\displaystyle {\begin{aligned}{\mathopen {[}}y_{k}]&:=y_{k},&&k\in \{0,\ldots ,n\}\\{\mathopen {[}}y_{k},\ldots ,y_{k+j}]&:={\frac {[y_{k+1},\ldots ,y_{k+j}]-[y_{k},\ldots ,y_{k+j-1}]}{x_{k+j}-x_{k}}},&&k\in \{0,\ldots ,n-j\},\ j\in \{1,\ldots ,n\}.\end{aligned}}}$$

Thus the Newton polynomial can be written as