2
$\begingroup$

To interpolate a polynomial of degree $n$ using the Lagrange form,

$$p(x)=\sum_{i=0}^ny_iL_i(x)$$ with $$L_i(x)=\frac{\prod_{i\not=j}(x-x_j)}{\prod_{i\not=j}(x_i-x_j)}$$

How can I show that for $y_i=x^j_i$ for $j=0, 1, ..., n$ $$\sum_{i=0}^nx_i^jL_i(x)=x^j$$

I read through this question which is the same identity, but the answers were unclear. I tried proving by expanding, so $$p(x)=\sum_{i=0}^n x_i^j \frac{\prod_{i\ne j} (x - x_j)}{\prod_{i \ne j} (x_i - x_j)}=\sum_{i=0}^n x_i^j \frac{(x - x_0)(x - x_1)...(x - x_{i-1})(x - x_{i+1})...(x - x_n)} {(x_i - x_0)(x_i - x_1)...(x_i - x_{i-1})(x_i - x_{i+1})...(x_i - x_n)}$$ but since the top product has $x$ where the denominator product has $x_i$, nothing seems to cancel out... but if I let $x=x_k$ as suggested in the link would that mean $x_i=x_k$ as well, leaving $\sum x_k^j=x_k^j$?

$\endgroup$
  • $\begingroup$ For me it is not clear what do you mean by $y_i=x_i^j$ for $j = 0, 1,\dots , n$? $\endgroup$ – Navaro Jun 23 '16 at 3:44
  • $\begingroup$ Suppose it is meant ".. for all the points which falls on a polynomial of degree less than or equal to $n$". Is my interpretation correct ? $\endgroup$ – G Cab Jul 7 '16 at 23:36
0
$\begingroup$

So we are speaking of "over-interpolation", meaning that we are interpolating $(n+1)$ points laying on a polynomial curve of degree $q$ ($q \le n$) with a polynomial of higher degree, which then will reduce to having degree $q$.

In fact, in general, interpolating $n+1$ points will produce a polynomial of degree at most $n$. $$ p_{\,n} (x) = \sum\limits_{0 \le \,\,i\, \le \,n} {y_{\,i} \frac{{\prod\limits_{j\;:\;0 \le \,j\, \ne \,i\, \le \,n} {\left( {x - x_{\,j} } \right)} }}{{\prod\limits_{j\;:\;0 \le \,j\, \ne \,i\, \le \,n} {\left( {x_{\,i} - x_{\,j} } \right)} }}} \quad \Rightarrow \quad \deg \left( {p_{\,n} (x)} \right) \le n $$ and if the points are actually laying on a polynomial of degree <= $n$, we will get exactly that polynomial. $$ y_{\,i} = p_{\,q} (x_{\,i} )\quad \left| \begin{array}{l} \;0 \le q \le n \\ \;\forall i\;:\;0 \le i \le n \\ \end{array} \right.\quad \Rightarrow \quad p_{\,n} (x) = \sum\limits_{0 \le \,\,i\, \le \,n} {p_{\,q} (x_{\,i} )\frac{{\prod\limits_{j\;:\;0 \le \,j\, \ne \,i\, \le \,n} {\left( {x - x_{\,j} } \right)} }}{{\prod\limits_{j\;:\;0 \le \,j\, \ne \,i\, \le \,n} {\left( {x_{\,i} - x_{\,j} } \right)} }}} \quad = p_{\,q} (x) $$ In particular
$$ x^{\,q} \quad \left| {\;0 \le q \le n\;} \right.\quad = \sum\limits_{0 \le \,\,i\, \le \,n} {x_{\,i} ^{\,q} \frac{{\prod\limits_{j\;:\;0 \le \,j\, \ne \,i\, \le \,n} {\left( {x - x_{\,j} } \right)} }}{{\prod\limits_{j\;:\;0 \le \,j\, \ne \,i\, \le \,n} {\left( {x_{\,i} - x_{\,j} } \right)} }}} $$

The algebric demonstration is not straightforward, it requires to expand the product in ${\left( {x - x_{\,j} } \right)}$, recurring to Vieta's formulas and then collect the terms of the summation in $x^0$, $x^1$, and/or recurring to Divided Differences, …
But we can take a blick on what is going on, if we take the simple case of interpolating the points $\left\{ {\left( {0,0} \right), \ldots ,\left( {k,k^{\,q} } \right), \ldots ,\left( {n,n^{\,q} } \right)} \right\}$ and limit our attention to the coefficient of $x^n$ $$ \begin{array}{l} \left[ {x^{\,n} } \right]p_{\,n} (x) = \sum\limits_{0 \le \,\,i\, \le \,n} {\frac{{i^{\,q} }}{{\prod\limits_{j\;:\;0 \le \,j\, \ne \,i\, \le \,n} {\left( {i - j} \right)} }}} = \\ = \sum\limits_{0 \le \,\,i\, \le \,n} {\frac{{i^{\,q} }}{{\prod\limits_{0 \le \,j\,\, \le \,i - 1} {\left( {i - j} \right)} \prod\limits_{i + 1 \le \,j\,\, \le \,n} {\left( {i - j} \right)} }}} = \\ = \sum\limits_{0 \le \,\,i\, \le \,n} {\frac{{i^{\,q} }}{{i!\prod\limits_{1 \le \,k\, \le \,n - i} {\left( { - k} \right)} }}} = \sum\limits_{0 \le \,\,i\, \le \,n} {\left( { - 1} \right)^{\,n - i} \frac{{i^{\,q} }}{{i!\left( {n - i} \right)!}}} = \\ = \frac{1}{{n!}}\sum\limits_{0 \le \,\,i\, \le \,n} {\left( { - 1} \right)^{\,n - i} \left( \begin{array}{c} n \\ i \\ \end{array} \right)i^{\,q} = } \frac{1}{{n!}}\Delta _{\,x} ^n \,x^{\,q} \left| {_{x\, = \,0} } \right. = \\ = n{\rm th}\,{\rm coefficient}\,{\rm in}\,{\rm Newton}\,{\rm expansion}\,{\rm of}\,x^{\,q} = \\ = \left\{ \begin{array}{l} 0\;\;q < n \\ 1\;\;q = n \\ \end{array} \right. \\ \end{array} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.