Interpolating Polynomials

A polynomial of \(n\)-th degree is uniquely determined, given its values at \(n+1\) points. So, suppose that \(P\) is an \(n\)-th degree polynomial and that \(P(x_i)=y_i\) in different points \(x_0,x_1, \dots,x_n\). There exist unique polynomials \(E_0,E_1,\dots,E_n\) of \(n\)-th degree such that \(E_i(x_i)=1\) and \(E_i(x_j)=0\) for \(j\neq i\). Then the polynomial \[P(x)=y_0E_0(x)+y_1E_1(x)+\cdots+ y_nE_n(x)\] has the desired properties: indeed, \(P(x_i)=\sum_j y_jE_j (x_i)=y_iE_i(x_i)=y_i\). It remains to find the polynomials \(E_0,\dots,E_n\). A polynomial that vanishes at the \(n\) points \(x_j\), \(j\neq i\), is divisible by \(\prod_{j\neq i}(x-x_j)\), from which we easily obtain \(E_i(x)=\prod_{j\neq i}\frac {(x-x_j)}{(x_i-x_j)}\). This shows that:

In order to compute the value of a polynomial given in this way in some point, sometimes we do not need to determine its Newton’s polynomial. In fact, Newton’s polynomial has an unpleasant property of giving the answer in a complicated form.

Instead, it is often useful to consider the finite difference of polynomial \(P\), defined by \(P^{[1]}(x)=P(x+1)-P(x)\), which has the degree by 1 less than that of \(P\). Further, we define the \(k\)-th finite difference, \(P^{[k]}=(P^{[k-1]})^{[1]}\), which is of degree \(n-k\) (where \(\deg P=n\)). A simple induction gives a general formula \[P^{[k]}=\sum_{i=0}^k (-1)^{k-i}\binom ki P(x+i).\] In particular, \(P^{[n]}\) is constant and \(P^{[n+1]}=0\), which leads to