Newton polynomial: Difference between revisions

Newton polynomials (named after their inventor Isaac Newton) are polynomials used for polynomial interpolation. Rather than solving the huge Vandermonde matrix equation obtained in the polynomial interpolation by Gaussian elimination, we notice that we can do clever tricks by writing the polynomial in a different way. Given a data set:

$(t_{0},y_{0}),(t_{1},y_{1}),\ldots (t_{n},y_{n})\,$

where no two $t_{i}$ are the same, we assume the $y_{n}$:s are values of a function, $f$, at some certain $t$-points named $f(t_{n})$. We know from Stone-Weierstrass theorem that there exists a unique polynomial of degree $n-1$ that pass through all these points, and we write it thusly:

${\begin{matrix}P(t)&=&c_{0}+c_{1}(t-t_{1})+c_{2}(t-t_{1})(t-t_{2})+\\&&\cdots +c_{n}(t-t_{1})(t-t_{2})\cdots (t-t_{n})\end{matrix}}$

or more formally:

$P(t)=\sum _{i=0}^{n}c_{i}\prod _{j=0}^{i}(t-t_{j})$

We notice that:

$P(t_{k})=f(t_{k}),\forall k$

And the equation may be written:

$c_{0}=f_{1}\,$

$c_{0}+c_{1}(t_{2}-t_{1})=f_{2}\,$

$c_{0}+c_{1}(t_{3}-t_{1})+c_{2}(t_{3}-t_{1})(t_{3}-t_{2})=f_{3}\,$

$\ldots$

And the solution giving the coefficients $c_{i}$ is thus:

$c_{0}=f_{1}\,$

$c_{1}={\frac {f_{2}-f_{1}}{t_{2}-t_{1}}}$

$c_{2}={\frac {f_{3}-f_{1}-{\frac {t_{3}-t_{1}}{t_{2}-t_{1}}}(f_{2}-f_{1})}{(t_{3}-t_{1})(t_{3}-t_{2})}}$

$\ldots$

and this equation system will quickly grow to unrealistic proportions. Thus we need to find a better way to retrieve the coefficients $c_{k}$. It turns out there exists a recusive formula for doing this in an efficient way.

Divided Differences

We see that the polynomial $P_{k}(t)$ for a certain $k$ may be defined recursively, thus:

$P_{0}(t)=c_{0}\,$

$P_{k}(t)=P_{k-1}(t)+c_{k}(t-t_{1})(t-t_{2})\cdots (t-t_{k})\,$

so that $P_{k}$ interpolates the function $f$ in the points $t_{1},t_{2},...t_{n}$. The coefficients $c_{k}$ are dependent only on the obtained function values of $f$ (our $y_{k}$:s), so it is natural to say that as $c_{0}$ only depends on $f_{1}$, $c_{1}$ only on $f_{1},f_{2}$ and $c_{k}$ only on $f_{1},f_{2},...f_{k}$, and we define a notation for the divided differences:

$c_{k}=f[t_{0},t_{1},t_{2},\ldots ,t_{k}]\,$

This definition gives us the formal definition of the divided differences:

$f[t_{i}]=f(t_{i})=f_{i}=y_{i}\,$

$f[t_{1},t_{2},t_{3},\ldots ,t_{k+1}]={\frac {f[t_{2},t_{3},\ldots ,t_{k+1}]-f[t_{1},t_{2},\ldots ,t_{k}]}{t_{k+1}-t_{1}}}\,$

So that for example:

$f[t_{1},t_{2}]={\frac {f_{2}-f_{1}}{t_{2}-t_{1}}}$

$f[t_{1},t_{2},t_{3}]={\frac {f[t_{2},t_{3}]-f[t_{1},t_{2}]}{t_{3}-t_{1}}}$

These are not easily grasped when put like this, but once the functions are arranged in a tabular form, things look simpler. Here for example, for a data set of $(t_{1},y_{1}),(t_{2},y_{2}),(t_{3},y_{3}),(t_{4},y_{4}),(t_{5},y_{5})$ (and we know that $f_{k}=y_{k}$ for all $k$):

$t_{1}\,$	$f_{1}\,$
$t_{2}\,$	$f_{2}\,$	$f[t_{1},t_{2}]\,$
$t_{3}\,$	$f_{3}\,$	$f[t_{2},t_{3}]\,$	$f[t_{1},t_{2},t_{3}]\,$
$t_{4}\,$	$f_{4}\,$	$f[t_{3},t_{4}]\,$	$f[t_{2},t_{3},t_{4}]\,$	$f[t_{1},t_{2},t_{2},t_{4}]\,$
$t_{5}\,$	$f_{5}\,$	$f[t_{4},t_{5}]\,$	$f[t_{3},t_{4},t_{5}]\,$	$f[t_{2},t_{3},t_{4},t_{5}]\,$	$f[t_{1},t_{2},t_{3},t_{4},t_{5}]\,$

On the diagonal of this table you will find the coefficients, as $c_{0}=f_{1},c_{1}=f[t_{1},t_{2}],c_{2}=f[t_{1},t_{2},t_{3}],c_{3}=f[t_{1},t_{2},t_{3},t_{4}],c_{4}=f[t_{1},t_{2},t_{3},t_{4},t_{5}]$. Insert these into the formula at the top and you have your unique interpolation polynomial:

$P_{n}(t)=\sum _{i=0}^{n}f[t_{i}]\prod _{j=0}^{i}(t-t_{j})$

expanding into:

$P_{n}(t)=f_{1}+f[t_{1},t_{2}](t-t_{1})+\cdots +f[t_{1},\ldots ,t_{n}](t-t_{1})\cdots (t-t_{n})\,$

This is usually called the common Newtonian interpolation polynomial.

Example

to be written

See Also

• Neville's schema
• Polynomial interpolation
• Lagrange polynomials
• Bernstein polynomials