Associated Topics || Dr. Math Home || Search Dr. Math

### Lagrange Interpolation

```Date: 08/20/2003 at 03:09:19
From: Ricky Wu
Subject: Lagrange interpolation

Dear Dr. Math,

I am trying to learn Lagrange interpolation.

1. Could you please give me a detailed explanation of Lagrange
interpolation?

2. Could you tell me is there any theory that underlies the method?
```

```
Date: 08/20/2003 at 19:44:02
From: Doctor Fenton
Subject: Re: Lagrange interpolation

Hi Ricky,

Thanks for writing to Dr. Math. The idea of interpolation is to find
a function of a specified form which passes through a given list of
points. Lagrange interpolation uses polynomials. You should already
know that given two points (x1,y1) and (x2,y2), there is exactly one
line through the two points.

It is also true that given three points, (x1,y1), (x2,y2), and
(x3,y3), with different x-coordinates, either the three points lie in
a line, or else there is exactly one parabola (second degree
polynomial y = ax^2 + bx + c) through the three points. If the three
points lie in a line, then there is a line y=bx+c passing through the
points. We can say that in any case, there is a polynomial of degree
at most 2 passing through the three points.

In general, given a list of n points, (x(1),y(1)),(x(2),y(2)),...,
(x(n),y(n)), with all the x-coordinates different, there will be a
polynomial of degree at most (n-1) passing through the given points.
If you have four points, there will be a cubic (at most)
polynomial through them; if you have 10 points, there will be a
polynomial of degree at most 9 through them.

You can see that this is the case by using the following kind of
argument: in fact, you can write an explicit formula for the
polynomial.

First, look at the line through two points (x1,y1) and (x2,y2).  You
probably know the two-point formula for a line, but let us take
another approach. The polynomial P(x) = x-x2 is a first degree
polynomial which is 0 at x2: P(x2) = 0.  P(x1) = x1 - x2, so the
polynomial

x - x2
P1(x) = ------
x1-x2

is a first degree polynomial which has the value 1 at x1 and 0 at x2.

Similarly,

x - x1
P2(x) = ------    has P2(x1) = 0 and P2(x2) = 1.
x2-x1

Then

P(x) = y1*P1(x) + y2*P2(x)

is again a polynomial of degree 1 (the y's are just numbers),
and

P(x1) = y1*P1(x1) + y2*P2(x1)

= y1*1 + y2*0

= y1 ,

while

P(x2) = y1*P1(x2) + y2*P2(x2)

= y2 .

Given three points (x1,y1), (x2,y2), and (x3,y3), we can find a
quadratic polynomial P1(x) which is equal to 1 at x1 and equal to 0
at x2 and x3. The Factor Theorem says that a polynomial P(x) is
divisible by a linear factor (x-r) if and only if P(r) = 0, that is,
if r is a root of P(x)=0.  This means that P1(x), since P1(x2)=0 and
P1(x3)=0, must be of the form

P1(x) = A1(x-x2)(x-x3) .

Since

P1(x1) = 1 ,

then

1 = A(x1-x2)(x1-x3) ,

which tells us that

1
A = -------------- ,
(x1-x2)(x1-x3)

so
(x-x2)(x-x3)
P1(x) = -------------- .
(x1-x2)(x1-x3)

Similarly, we can find quadratic polynomials P2(x) and P3(x) such
that

P2(x1) = 0 , P2(x2) = 1, P2(x3) = 0 ,

and

P3(x1) = 0 , P2(x2) = 0, P2(x3) = 1 .

In fact,
(x-x1)(x-x3)                 (x-x1)(x-x2)
P2(x) = --------------  and  P3(x) = --------------   .
(x2-x1)(x2-x3)               (x3-x1)(x3-x2)

Then

P(x) = y1*P1(x) + y2*P2(x) + y3*P3(x)

is a polynomial of degree at most 3 which passes through (x1,y1),
(x2,y2), and (x3,y3).

The same idea works for any list of points
(x(1),y(1)), (x(2),y(2)), ..., (x(n),y(n)) .

This gives you a formula for the polynomial, called the Lagrange
Form of the Interpolating Polynomial.  There are other possible forms,
but the Lagrange form is probably the simplest.

Lagrange Polynomial Interpolation
http://mathforum.org/library/drmath/view/53057.html

and

http://mathforum.org/library/drmath/view/62552.html

If you have any questions, please write back and I will try to explain
further.

- Doctor Fenton, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 08/22/2003 at 04:46:06
From: Ricky Wu
Subject: Lagrange interpolation

To Dr. Math,

1) I have seen two things in the textbook called Lagrange remainder
and Lagrange multipliers. Do they relate to Lagrange interpolation?

2) Could you please show me how to use Excel to work Lagrange
interpolation? (If there is any difficulties to show the steps in the

3) Is there any theory which underlies the method?

Regards,
Ricky Wu
```

```
Date: 08/22/2003 at 08:23:23
From: Doctor Fenton
Subject: Re: Lagrange interpolation

Hi Ricky,

I'm not sure what you mean by "Lagrange remainder."  There is a
term "Lagrange form of the remainder" used in Taylor polynomials, and
if that is what you mean, then the answer is no in both cases.
Taylor polynomials do compute a polynomial that in many cases does
approximate the function, but it uses the value of the function
and its derivatives at one point, not the value of the function at
many points.

Lagrange multipliers are used in "constrained optimization": you want
to find the largest value of a function of several values, e.g.
f(x,y), on a curve g(x,y)=0.  This does not involve interpolation.

Lagrange was a very great and prolific mathematician, and he did a lot
of work, so you see his name in many different areas of mathematics.

For actual computation, I would use one of the other forms I mentioned
in my reply, the Newton form.  You have to compute what are called
"divided differences".  Given a list of points, x(0),x(1),...,x(n),
and function values f(x(i)) at each of those points, the divided
differences f[x(0),x(1),...,x(k)] are defined recursively:

f[x(i)] = f(x(i))  (note the square bracket on the left side;
that quantity is being DEFINED).

Second divided differences are defined by

f[x(1)] - f[x(0)]
f[x(0),x(1)] = ----------------- , etc.
x(1) - x(0)

f(x(1)) - f(x(0))
= -----------------
x(1) - x(0)     .

Third divided differences are defined by

f[x(1),x(2)] - f[x(0),x(1)]
f[x(0),x(1),x(2)] = ----------------------------   , etc.
x(2) - x(0)

that is, third divided differences are divided differences of second
divided differences.  You make a Divided Difference Table:

x(0)  f[x(0)]
f[x(0),x(1)]
x(1)  f[x(1)]               f[x(0),x(1),x(2)]
f[x(1),x(2)]                   f[x(0),x(1),x(2),x(3)]
x(2)  f[x(2)]               f[x(0),x(1),x(2)]
f[x(2),x(3)]
x(3)  f[x(3)]

This table would work for cubic interpolation through 4 points. As an
example, I'll do one for a quadratic through 3 points: you first
compute the first column of divided differences (which will be the
third column in the table:

0  1                        0  1
(3-1)/(1-0)                 2
1  3                   or   1  3
(7-3)/(2-1)                 4
2  7                        2  7

and then compute the second column of divided differences

0  1                        0  1
2                           2
1  3     (4-2)/(2-0)  or    1  3     1
4                           4
2  7                        2  7             .

Starting in the second column, we read the coefficients down
the diagonal: 1,2,1

0  (1)
(2)
1   3     (1)
4
2   7                            .

Then the interpolating polynomial is

p(x)=f[x(0)]+f[x(0),x(1)](x-x(0))+f[x(0),x(1),x(2)](x-x(0))(x-x(1))

or

p(x) = 1 + 2(x-0) + 1(x-0)(x-1)

= 1 + 2x + x(x-1)

= 1 + 2x + x^2 - x

= 1 + x + x^2 .

You can check that this polynomial does indeed produce the values you
were interpolating: p(0)=1, p(1)=3, and p(2)=7.

The same basic idea works for any degree. A good description of all
this can be found in any elementary numerical analysis book. My
favorite is Conte and De Boor, _Elementary Numerical Analysis_.

It is probably not a good idea to use very high degree polynomials,
so if you have 20 points, don't use a 19th degree interpolating
polynomial. Instead, use some form of "piecewise polynomial"
interpolation: for example, to interpolate a value at x, pick the
four closest points in the given list to x, x(i-1),x(i),x(i+1),x(1+2),
and use a cubic through these four points.

I'm not sure what kind of "theory" you are looking for.  I have
outlined the proof that given a list of (n+1) distinct x values,
there is a unique polynomial of degree n through those points: I
essentially wrote the formula for it. The remaining theory deals
mostly with the question of how well the interpolating polynomial fits
the function between the interpolating points. Conte and DeBoor give
advanced texts. There are whole books devoted to the subject of
interpolation, and Lagrange interpolation is only one method.

- Doctor Fenton, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Statistics
High School Polynomials
High School Statistics

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search