## Lagrange interpolation

*
See also* -
Interpolator

**What is interpolation?**

Interpolation is the process of finding values intermediate to those given in a table.

**Can you explain more?**

Suppose, for example, I find in a book a table which gives me the distance from Earth to Mars at midnight on five consecutive days. If I then wanted to find the distance between Earth and Mars for some time other than midnight during this period, I would use interpolation.

**What is Lagrange interpolation?**

Lagrange interpolation is a method of interpolating which uses the values in the table (which are treated as (

*x*,

*y*) coordinate pairs) to construct a polynomial curve that runs through all these points. The interpolation can then be performed by reading off points on this curve.

Ok, so what's the formula for the Lagrange polynomial?

Ok, so what's the formula for the Lagrange polynomial?

**And now in English?**

The polynomial curve is of the form

*y*=

*y*1L1 +

*y*2L2 + ... +

*y*nLn

where

*n*is the number of (

*x*,

*y*) coordinate pairs you have.

L1, L2, ..., Ln are polynomial expressions. If we denote these by Li (where

*i*can range from 1 to

*n*depending on whether we are dealing with L1, L2, etc), then Li is given by

This means that for each Li, you need to calculate

(

for every

Suppose we have the following data:

Hence

Therefore we know the Lagrange polynomial is of the form

or, equivalently,

To calculate L1, we need to calculate

(-1 -

for

(-1 - 0) (-1 - 1) (-1 - 3)

Multiplying these together, we have

(-1 - 0)(-1 - 1)(-1 - 3)

which simplifies to

8

To calculate L2, we need to work out

(0 -

for

(0 - -1) (0 - 1) (0 - 3)

Multiplying the terms gives

3

For L3, we need to find the product of

(1 -

when

4

And similarly, we find that L4 is given by

24

We now have expressions for L1, L2, L3 and L4. We can therefore substitute these back into the expression we found earlier, that is

which gives us

((

*x*__-__*x*j)(

*x*i -*x*j)for every

*j*ranging from 1 to*n*, excluding the case where*j*=*i*(as this would result in you dividing by zero), and then multiply all these expressions together.**Can you give me an example to show how its done?**Suppose we have the following data:

*x*-1 0 1 3*y*1 3 1 9Hence

*n*= 4 (as we have 4 (*x*,*y*) coordinate pairs), and we have*x*1 = -1*x*2 = 0*x*3 = 1*x*4 = 3*y*1 = 1*y*2 = 3*y*3 = 1*y*4 = 9Therefore we know the Lagrange polynomial is of the form

*= 1 x L1 + 3 x L2 + 1 x L3 + 9 x L4*

yy

or, equivalently,

*= L1 + 3L2 + L3 + 9L4*

yy

To calculate L1, we need to calculate

((

*x*__-__*x*j)(-1 -

*x*j)for

*j*= 2 to 4 (we don't calculate it for*j*= 1, since then we would have*i*=*j*). This gives us

((

*x*- 0)__(__*x*- 1)__(__*x*- 3)(-1 - 0) (-1 - 1) (-1 - 3)

Multiplying these together, we have

__(__*x*- 0)(*x*- 1)(*x*- 3)(-1 - 0)(-1 - 1)(-1 - 3)

which simplifies to

--

*x*(*x*- 1)(*x*- 3)8

To calculate L2, we need to work out

((

*x*-*x*j)(0 -

*x*j)for

*j*= 1,*j*= 3 and*j*= 4. This gives

((

*x*- -1)__(__*x*- 1)__(__*x*- 3)(0 - -1) (0 - 1) (0 - 3)

Multiplying the terms gives

__(__*x*+ 1)(*x*- 1)(*x*- 3)3

For L3, we need to find the product of

__(__*x*-*x*j)(1 -

*x*j)when

*j*= 1,*j*= 2 and*j*= 4. We get__-__*x*(*x*+ 1)(*x*- 3)4

And similarly, we find that L4 is given by

*x*(*x*+ 1)(*x*- 1)24

We now have expressions for L1, L2, L3 and L4. We can therefore substitute these back into the expression we found earlier, that is

*y*= L1 + 3L2 + L3 + 9L4which gives us

**How do you do the actual interpolation?**

Now that we've got the equation of the polynomial curve, this is very easy. Suppose in the example above, we want to know what

*y*is when

*x*= 2. Then we simply plug

*x*= 2 into the formula above, which gives

*y*= 2

^{3}- 2 x 2

^{3}- 2 + 3

*y*= 8 - 2 x 4 - 2 + 3

*y*= 8 - 8 - 2 + 3

*= 1*

y

y

**That's a lot of work. Isn't there an easier way?**

Of course - that's what my interpolator program is for!