5
$\begingroup$

How do I prove the Lagrange interpolation formula is true as stated in this link?

I ask this because the article isn't self contained on intuition of each step in the proof, please don't use things too advanced because I am just a high school student. Thanks in advance.

  • 0
    The key is exploiting $\log(ab)=\log\,a+\log\,b$ and $\frac{\mathrm d}{\mathrm dx}\log(f(x))=\frac{f^\prime (x)}{f(x)}$...2011-11-11

2 Answers 2

15

Here's the intuition:

You are given a finite set of points, $x_1,\ldots,x_n$, and a corresponding set of values, $y_1,\ldots,y_n$. You want to find a polynomial $p(x)$ such that $p(x_i) = y_i$ for $i=1,\ldots,n$.

As a preliminary step, we want to find a polynomial $p_1(x)$ that is $0$ at $x_2,\ldots,x_n$, and is $1$ at $x_1$. Then a polynomial $p_2(x)$ that is $0$ at $x_1,x_3,\ldots,x_n$, and $1$ at $x_2$; then a polynomial $p_3(x)$ that is $0$ at $x_1,x_2,x_4,\ldots,x_n$, and $1$ at $x_3$; etc. Then we can get the polynomial we want by taking $y_1p_1(x) + \cdots + y_np_n(x),$ since evaluating at each $x_i$, the only summand that is not equal to $0$ is $y_ip_i(x_i) = y_i$.

To get a polynomial that is $0$ at $x_2,x_3,\ldots,x_n$, we just need it to be a multiple of $(x-x_2)(x-x_3)\cdots(x-x_n).$ What to do to get it to be $1$ at $x_1$? If we just plug in $x_1$, we will get $(x_1-x_2)(x_1-x_3)\cdots (x_1-x_n);$ so we just divide the polynomial we had by this constant to ensure the value at $x_1$ is $1$. This is the simplest polynomial we can find that is $0$ at each of $x_2,\ldots,x_n$, and is $1$ at $x_1$.

That is, we take $p_1(x) = \left(\frac{1}{(x_1-x_2)(x_1-x_3)\cdots(x_1-x_n)}\right)(x-x_2)(x-x_3)\cdots (x-x_n).$ Similarly, for $p_i(x)$, we take $\begin{align*} p_i(x) &= \left(\frac{1}{(x_i-x_1)(x_i-x_2)\cdots (x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_n)}\right)\\ \\ &\qquad \times (x-x_1)(x-x_2)\cdots(x-x_{i-1})(x-x_{i+1})\cdots(x_i-x_n). \end{align*}$

Then just take $p(x) = y_1p_1(x) + y_2p_2(x)+\cdots+y_np_n(x).$

The only thing left is to note that the formula with the derivatives agrees with this, because \begin{align*} \Bigl( (x-x_1)\cdots(x-x_n)\Bigr)' &= (x-x_1)'(x-x_2)\cdots(x-x_n) \\ &\qquad + (x-x_1)(x-x_2)'(x-x_3)\cdots (x-x_n)\\ &\qquad + \cdots + (x-x_1)\cdots(x-x_{n-1})(x-x_n)'\\ &= (x-x_2)\cdots(x-x_n) + (x-x_1)(x-x_3)\cdots(x-x_n) \\ &\qquad + \cdots + (x-x_1)\cdots(x-x_{n-1}). \end{align*}

  • 0
    @ArturoMagidin -appreciate for your effort!2011-11-11
3

I first saw Lagrange's interpolation formula in tenth grade and calculus was not part of the tenth grade curriculum. However, the second form is fairly straight forward:

$ p(x)=\sum_{i=1}^n\;y_i\prod_{\genfrac{}{}{0}{1}{j\not=i}{j=1}}^n\frac{x-x_j}{x_i-x_j}\tag{1} $

For each $i$, consider $ q_i(x)=\prod_{\genfrac{}{}{0}{1}{j\not=i}{j=1}}^n\frac{x-x_j}{x_i-x_j}\tag{2} $ Plug in $x=x_j$ where $j\not=i$. Since $\dfrac{x-x_j}{x_i-x_j}$ is a factor in $(2)$, $q_i(x_j)=0$.

Plug in $x=x_i$. Each term in $(2)$ is then $\dfrac{x_i-x_j}{x_i-x_j}=1$; thus, $q_i(x_i)=1$.

Therefore, $\displaystyle p(x_i)=\sum_{j=1}^n\;y_jq_j(x_i)=y_i$.