Lagrange Interpolation Formula

Given n n distinct real values x1,x2,xn x_1, x_2, \ldots x_n and n n real values y1,y2,yn y_1, y_2, \ldots y_n (not necessarily distinct), the Lagrange Interperloation Formula gives a polynomial PP with real coefficients satisfying P(xi)=yi P(x_i)=y_i for i{1,2,n} i \in \{ 1,2, \ldots n \} .

To describe polynomial PP, we first solve the following problem: Given n n distinct real values x1,x2,xn x_1, x_2, \ldots x_n , does there exist a polynomial f f with real coefficients satisfying f(x1)=1 f(x_1)=1 and f(xi)=0 f(x_i)=0 for all values of i1 i \neq 1?

By the Remainder-Factor Theorem, if such a polynomial exists, then for all i1 i\neq 1, (xxi) (x-x_i) must be a factor of the polynomial. Consider the polynomial g(x)=i=2n(xxi) g(x) = \prod \limits_{i=2}^n (x-x_i) . This satisfies the conditions g(xi)=0 g(x_i)=0 . Now let F=g(x1) F = g(x_1) . Then since F0 F \neq 0 (using the condition that the xix_i are distinct), we may divide by F F to obtain polynomial f(x)=g(x)Ff(x) = \frac{g(x)}{F}. We have f(xi)=g(xi)F=0 f(x_i) = \frac {g(x_i)}{F} = 0 and f(x1)=g(x1)F=1 f(x_1) = \frac {g(x_1)} {F} = 1, giving the polynomial desired.

Let Pj(xj) P_j(x_j) be the polynomial with real coefficients satisfying Pj(xj)=1 P_j (x_j)=1 and Pj(xi)=0 P_j (x_i)=0 for all ij i \neq j. Then, P(x)=yiPi(x) P(x) = \sum y_i P_i(x) is a polynomial with real coefficients satisfying P(xi)=yi P(x_i)=y_i for all i{1,2,n} i \in \{ 1,2, \ldots n \} .

Worked Examples

1. If we want to find a polynomial that satisfies

P(1)=1,P(2)=4,P(3)=1,P(4)=5, P(1)=1, P(2)=4, P(3)=1, P(4)=5, what are the polynomials P1(x),P2(x),P3(x),P4(x),P(x) P_1(x), P_2(x), P_3(x), P_4(x), P(x)?

Let f(x)=(x2)(x3)(x4) f(x) = (x-2)(x-3)(x-4). Then

f(1)=(1)(2)(3)=6, so P1(x)=16(x2)(x3)(x4). f(1) = (-1)(-2)(-3)=-6 \text{, so } P_1(x) = -\frac {1}{6}(x-2)(x-3)(x-4).

Let f(x)=(x1)(x3)(x4) f(x) = (x-1)(x-3)(x-4). Then

f(2)=(1)(1)(2)=2, so P2(x)=12(x1)(x3)(x4). f(2) = (1)(-1)(-2) = 2 \text{, so } P_2 (x) = \frac {1}{2} (x-1)(x-3)(x-4).

Let f(x)=(x1)(x2)(x4) f(x) = (x-1)(x-2)(x-4). Then

f(3)=(2)(1)(1)=2, so P3(x)=12(x1)(x2)(x4). f(3) = (2)(1)(-1) = -2 \text{, so } P_3 (x) = -\frac {1}{2} (x-1)(x-2)(x-4).

Let f(x)=(x1)(x2)(x3) f(x) = (x-1)(x-2)(x-3). Then

f(4)=(3)(2)(1)=6, so P4(x)=16(x1)(x2)(x3). f(4) = (3)(2)(1) = 6 \text{, so } P_4 (x) = \frac {1}{6} (x-1)(x-2)(x-3).

Hence,

P(x)=1×(16)(x2)(x3)(x4)+4×12(x1)(x3)(x4) P(x) = 1\times (-\frac {1}{6})(x-2)(x-3)(x-4) + 4\times \frac {1}{2} (x-1)(x-3)(x-4) +1×(12)(x1)(x2)(x4)+5×16(x1)(x2)(x3). + 1\times (-\frac {1}{2}) (x-1)(x-2)(x-4)+ 5 \times \frac {1}{6} (x-1)(x-2)(x-3).

 

2. Show that if we require the polynomial in Lagrange's Interpolation Formula to have degree at most n1 n-1, then there is a unique polynomial satisfying the conditions. Show further that this polynomial is P(x) P(x) itself.

Suppose two polynomials R(x) R(x) and S(x) S(x) satisfy the conditions of Lagrange's Interpolation Formula and have degree at most n1 n-1. Consider the polynomial T(x)=R(x)S(x) T(x) = R(x)-S(x). By the conditions, we have T(xi)=R(xi)S(xi)=yiyi=0 T(x_i) = R(x_i)-S(x_i) = y_i-y_i=0. Hence, by the Remainder-Factor Theorem,, for all values of i i, (xxi) (x-x_i) must be a factor of T(x) T(x). Since the xi x_i are distinct, we have T(x)=U(x)i=1n(xxi) T(x) = U(x) \prod \limits_{i=1}^n(x-x_i). If U(x) U(x) is not the zero polynomial, then the degree on the right hand side is at least n n, while the degree on the left hand side is at most n1 n-1, which is a contradiction. Thus, U(x)=0 U(x)=0, and so T(x)=0 T(x)=0, which gives R(x)=S(x) R(x)=S(x). Hence, there is a unique polynomial which satisfies the conditions in the question. It is clear that each of the Pi(x) P_i(x) has degree at most n1 n-1 (it can have degree 0 if yi=0 y_i=0). Hence, since P(x) P(x) is the linear combination of these polynomials, it also has degree at most n1 n-1.

 

3. Given n n distinct complex values x1,x2,xn x_1, x_2, \ldots x_n and n n (not necessarily distinct) complex values y1,y2,yn y_1, y_2, \ldots y_n, does there exist a polynomial with complex coefficients satisfying P(xi)=yi P(x_i)=y_i for all values of i i?

Solution: Repeat the above discussion by replacing "real" with "complex". Then P(x)=yiPi(x) P(x)= \sum y_i P_i(x) is a polynomial with complex coefficients.

Note by Calvin Lin
5 years, 2 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

@Calvin Lin Many a time I have seen people using Lagrange Multipliers[edit] where I generally use AM-GM. How is that done? And how do we find the next term of 1,2,3,4,5,? be Lagrange Interpolation? Trevor said me that it's something weird which I don't remember. Thanks!

Satvik Golechha - 4 years, 4 months ago

Log in to reply

Lagrange interpolation is about finding a polynomial. AM-GM is Arithemtic Mean - Geometric Mean inequality. I do not see how they are related.

Are you asking about Method of Differences? If so, MOD only works when the values that you are given are consecutive (constant width apart), whereas LI is much more general and works for any set of x x values. E.g. find a quadratic polynomial such that f(1)=1,f(2)=2,f(10)=11 f(1) = 1, f(2) = 2, f(10) = 11 would be easy with LI, but hard with MOD.

Calvin Lin Staff - 4 years, 4 months ago

Log in to reply

Oops! Sorry, it was Lagrange Multipliers not Lagrange Interpolation.

And Trevor once told me that by Lagrange Interpolation, the next term in the sequence 1,2,3,4,5,6, __ is something like π100icos2.9\sqrt{\pi}^{100i\cos{2.9}}. I don't get how. @Calvin Lin

Satvik Golechha - 4 years, 4 months ago

Log in to reply

i only understood a bit of it, can you please elaborate it.....

Dheeraj Agarwal - 5 years, 2 months ago

Log in to reply

Basically, if we want a polynomial running through points a,b,c,d, we need a degree 3 function.

We make a polynomial with 4 "parts"

[p(xa)(xb)]+[q(xa)(xc)]+[r(xb)(xc)][p(x-a)(x-b)]+[q(x-a)(x-c)]+[r(x-b)(x-c)]

Note how each part (I've separated them by []) have different 0's. The first part has 0's at x=a,b. Now, we plug in d into the function for x. Notice also how everyother part of the function becomes 0 when plugging in 0.


Let's say we want a function going through (1,2), (2,3), and (3,5)

In this case, a=1, b=2, c=3

y=(xa)(xb)+q(xa)(xc)+r(xb)(xc)y=(x-a)(x-b)+q(x-a)(x-c)+r(x-b)(x-c)

y=p(x1)(x2)+q(x1)(x3)+r(x2)(x3)y=p(x-1)(x-2)+q(x-1)(x-3)+r(x-2)(x-3)

Plugging in x=a=1

y=p(11)(12)+q(11)(13)+r(12)(13)y=p(1-1)(1-2)+q(1-1)(1-3)+r(1-2)(1-3)

y=p(\color{\blue}{0})(-1)+q(\color{\blue}{0})(-2)+r(-1)(-2)

y=2ry=2r

Remember, we want our function to go through (1,2), so y=2

2=2rr=12=2r\Rightarrow r=1

Now we have

y=p(x1)(x2)+q(x1)(x3)+1(x2)(x3)y=p(x-1)(x-2)+q(x-1)(x-3)+\color{green}{1}(x-2)(x-3)

Repeating this process for x=2

y=p(21)(22)+q(21)(23)+r(22)(23)y=p(2-1)(2-2)+q(2-1)(2-3)+r(2-2)(2-3)

y=p(1)(0)+q(1)(1)+r(0)(1)y=p(1)(\color{blue}{0})+q(1)(-1)+r(\color{blue}{0})(-1)

y=qy=-q

In this case y=3

3=qq=33=-q\Rightarrow q=-3

Now we have

y=p(x1)(x2)+(3)(x1)(x3)+1(x2)(x3)y=p(x-1)(x-2)+(\color{green}{-3})(x-1)(x-3)+1(x-2)(x-3)

Finally, repeating this for x=3, we know that the second and third parts of our eq will be 0 so I won't show those parts.

y=p(2)(1)y=p(2)(1)

We want our function to go through (3,5), so y=5.

5=2pp=525=2p\Rightarrow p=\frac{5}{2}

Thus our function is

y=52(x1)(x2)3(x1)(x3)+(x2)(x3)y=\frac{5}{2}(x-1)(x-2)-3(x-1)(x-3)+(x-2)(x-3)

Trevor Arashiro - 4 years, 5 months ago

Log in to reply

can you please elaborate

Kartica Modi - 5 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...