# Is there some intuition for Lagrange interpolation formula?

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.

-
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

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

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

-