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?
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?
And now in English?
The polynomial curve is of the form
y = y1L1 + y2L2 + ... + ynLn
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
The polynomial curve is of the form
y = y1L1 + y2L2 + ... + ynLn
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
(x - xj)
(xi - xj)
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 9
Hence n = 4 (as we have 4 (x,y) coordinate pairs), and we have
x1 = -1
x2 = 0
x3 = 1
x4 = 3
y1 = 1
y2 = 3
y3 = 1
y4 = 9
Therefore we know the Lagrange polynomial is of the form
y = 1 x L1 + 3 x L2 + 1 x L3 + 9 x L4
or, equivalently,
y = L1 + 3L2 + L3 + 9L4
To calculate L1, we need to calculate
(x - xj)
(-1 - xj)
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 - xj)
(0 - xj)
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 - xj)
(1 - xj)
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 + 9L4
which gives us
(x - xj)
(xi - xj)
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 9
Hence n = 4 (as we have 4 (x,y) coordinate pairs), and we have
x1 = -1
x2 = 0
x3 = 1
x4 = 3
y1 = 1
y2 = 3
y3 = 1
y4 = 9
Therefore we know the Lagrange polynomial is of the form
y = 1 x L1 + 3 x L2 + 1 x L3 + 9 x L4
or, equivalently,
y = L1 + 3L2 + L3 + 9L4
To calculate L1, we need to calculate
(x - xj)
(-1 - xj)
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 - xj)
(0 - xj)
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 - xj)
(1 - xj)
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 + 9L4
which 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
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 = 23 - 2 x 23 - 2 + 3
y = 8 - 2 x 4 - 2 + 3
y = 8 - 8 - 2 + 3
y = 1
That's a lot of work. Isn't there an easier way?
Of course - that's what my interpolator program is for!
y = 8 - 8 - 2 + 3
y = 1
That's a lot of work. Isn't there an easier way?
Of course - that's what my interpolator program is for!
