Newtonpolynom

Newtonpolynom, also known as Newton polynomial or Newton form of a polynomial, is a way to represent a polynomial that is particularly useful for interpolation. Instead of the standard power basis (like $1, x, x^2, \dots$), it uses a basis of Newton polynomials. For a set of distinct points $(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)$, the Newton polynomial that interpolates these points is given by:

$P(x) = c_0 + c_1(x-x_0) + c_2(x-x_0)(x-x_1) + \dots + c_n(x-x_0)(x-x_1)\dots(x-x_{n-1})$

The coefficients $c_i$ are called divided differences. They can be computed recursively. The 0-th divided difference is $c_0 = f[x_0] = y_0$. The first divided difference is $c_1 = f[x_0, x_1] = \frac{f[x_1] - f[x_0]}{x_1 - x_0}$. In general, the $k$-th divided difference $f[x_0, x_1, \dots, x_k]$ is defined as:

$f[x_0, x_1, \dots, x_k] = \frac{f[x_1, \dots, x_k] - f[x_0, \dots, x_{k-1}]}{x_k - x_0}$

This recursive definition allows for efficient calculation of the coefficients. A key advantage of the Newton polynomial is that if a new point is added to the interpolation set, the existing Newton polynomial can be easily extended without recomputing all the previous coefficients. This makes it advantageous for incremental polynomial interpolation. The Newton polynomial is guaranteed to be unique for a given set of points.