Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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? –  Srivatsan Nov 11 '11 at 4:55
    
@Srivatsan - there are two major part in that article, but i can't follow both –  Victor Nov 11 '11 at 4:57
    
@Srivatsan - yes, i want more intuition behind the formula –  Victor Nov 11 '11 at 4:58
    
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. –  J. M. Nov 11 '11 at 5:09
    
@J.M. - Why do you have to use logarthmic differentiation and what is that? –  Victor Nov 11 '11 at 16:11

2 Answers 2

up vote 7 down vote accepted

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*}$$

share|improve this answer
    
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. –  Patrick Da Silva Nov 11 '11 at 6:07
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. –  Arturo Magidin Nov 11 '11 at 6:08
    
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! –  Patrick Da Silva Nov 11 '11 at 6:09
    
@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 impressed –  Victor Nov 11 '11 at 15:57
    
@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? –  Victor Nov 11 '11 at 15:58

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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