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.

  • 3
    The article *is* self-contained. Do you want a more detailed explanation or the intuition behind the formula? Can you point out exactly which parts of it you do not follow?2011-11-11
  • 0
    @Srivatsan - there are two major part in that article, but i can't follow both2011-11-11
  • 0
    @Srivatsan - yes, i want more intuition behind the formula2011-11-11
  • 0
    Looks pretty transparent to me. If you want to know how to differentiate $(x-x_1)(x-x_2)\cdots(x-x_n)$, you use logarithmic differentiation here.2011-11-11
  • 0
    @J.M. - Why do you have to use logarthmic differentiation and what is that?2011-11-11
  • 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

12

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
    I don't know for you guys, but in my high school I had never heard of derivatives. I'd like to see how OP reacts to this answer ; if he understands what is written here or not.2011-11-11
  • 1
    @PatrickDaSilva: Well, I'm only using the derivatives because they use that notation (probably to save space) in the page the OP links to; if you take for granted the formula for the derivative I write, it's just a matter of checking some algebra.2011-11-11
  • 0
    I was not commenting on the quality of your answer, I was more impressed that a high school student is interested in such questions. Never seen one like that before!2011-11-11
  • 0
    @PatrickDaSilva - i think it once appear in the solution of AMC high school competition from a aops user, after i saw it, i reconized this is a powerful tool, and i am pretty impressed2011-11-11
  • 0
    @ArturoMagidin - i don't understand the last derivative part, please expain a little about how to get to the result? i guess you are using the chain rule, right?2011-11-11
  • 0
    @Victor: No, I'm using the product rule. For two factors, $(fg)' = f'g +fg'$. For three factors, $(fgh)' = f'gh + fg'h + fgh'$. For four factors, $(fghk)' = f'ghk + fg'hk + fgh'k + fghk'$. Lather, rinse, and repeat.2011-11-11
  • 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$.