Given distinct $y_0,...,y_m$ in $\mathbb R$, let $N_m(x)$ be the Newton interpolation polynomial of degree $m$. That is, $N_m(x) = \sum_{n=0}^{m}a_nw_n(x)$ where $w_0 = 1$, $w_n(x) = (x-x_o)(x-x_1)...(x-x_{n-1})$ for $n > 0$ and the coefficients $a_n$ satisfies

$a_0 = y_0$

$a_0 + a_1w_1(x_1) = y_1$


$a_0 + a_1w_1(x_m) + ... + a_mw_m(x_m) = y_m$

Prove that $\displaystyle a_n = \sum_{j=0}^n\frac{y_j}{\prod_{k=0, k \neq j}^n(x_j - x_k)}$ for $0 \leq n \leq m$.

Hint is given in the book that $N_n(x) = L_n(x)$, for $0 \leq n \leq m$ where $L_n(x)$ is the Lagrange polynomial that interpolates through $y_o,...,y_m$. However this hint is not helping me much. Any further hints or solution is appreciated.

  • $\begingroup$ Thanks for the edit. Much easier to read now. $\endgroup$ – tsknakamura May 18 '13 at 4:59

$$N_n(x) = \sum_{j=0}^n a_jw_j(x) = \sum_{j=0}^n a_j \prod_{k=0}^{j-1}(x-x_k) = \sum_{j=0}^n y_j \prod_{k=0, k\neq j}^n \frac{(x-x_k)}{(x_j-x_k)}$$ interpolates through the points $$(x_0,y_0), (x_1,y_1), \ldots, (x_{n-1},y_{n-1}), (x_n,y_n)$$ Note that the polynomial on the right side above is the Lagrange interpolation polynomial $L_n(x)$ suggested in the hint. Since $L_n(x)$ also interpolates through these $n+1$ points, it must be the same as $N_n(x)$. Note that $w_n(x)$ is the only polynomial of degree $n$ in the sum on the left while each polynomial in the sum on the right has degree $n$. Comparing the coefficients of $x^n$ on both sides, we get $$a_n = \sum_{j=0}^n \frac{y_j}{\prod_{k=0, k\neq j}^{n}(x_j-x_k)}.$$

  • $\begingroup$ Finally got it.Thanks alot. $\endgroup$ – tsknakamura May 18 '13 at 4:54

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.