| |
Interpolatory Polynomial Examples
Given a set of n+1 points (x0,f0),...,(xn,fn), it can be shown that
there is exactly one polynomial of degree n or less passing through the
points. Here, I will give examples of three algorithms for finding this
polynomial. I advise reading a description of the
three algorithms before reading through this page.
For these examples, I will find the polynomial which interpolates the points
(-2,-8), (1,1), (2,0) and (4,10). Here, n = 3, and x0 = -2, x1 = 1, x2 = 2, x3 = 4,
and f0 = -8, f1 = 1, f2 = 0 and f3 = 10. We should expect the interpolating
polynomial to be a cubic polynomial.
A direct method: If one writes the polynomial as
p(x) = a0+a1x+a2x2+a3x3, then substituting the given points
into p(x) gives the following system of equations:
With a lot of patience, and even more care with the arithmetic, this system
of equations can be solved, giving a0 = 2, a1 = 0, a2 = -3/2 and a3 = 1/2,
so that the desired polynomial is p(x) = 2-(3/2)x2+(1/2)x3.
The Lagrange Interpolating Polynomial (LIP):
Given x0 = -2,x1 = 1,x2 = 2,xn = 4, we can write down Lagrange's li(x), as follows:
|
l0(x) = |
(x-1)(x-2)(x-4)
(-2-1)(-2-2)(-2-4)
|
= - |
1
72
|
(x-1)(x-2)(x-4), |
|
|
l1(x) = |
(x+2)(x-2)(x-4)
(1+2)(1-2)(1-4)
|
= |
1
9
|
(x+2)(x-2)(x-4), |
|
|
l2(x) = |
(x+2)(x-1)(x-4)
(2+2)(2-1)(2-4)
|
= - |
1
8
|
(x+2)(x-1)(x-4), and |
|
|
l3(x) = |
(x+2)(x-1)(x-2)
(4+2)(4-1)(4-2)
|
= |
1
36
|
(x+2)(x-1)(x-2). |
|
Then, using the values f0 = -8,f1 = 1,f2 = 0,f3 = 10, we can write the desired polynomial
as p(x) = -8.l0(x)+1.l1(x)+0.l2(x)+10.l3(x), or
|
p(x) = - |
8
72
|
(x-1)(x-2)(x-4) + |
1
9
|
(x+2)(x-2)(x-4) + |
10
36
|
(x+2)(x-1)(x-2). |
|
Although it looks completely different, this is the same polynomial that
we derived before.
The Divided Difference Method:
Given the same values of the xi and the fi, we can begin to write down the
divided difference table. The values of Di,0 are just the values of fi,
so
|
D0,0 = -8, D1,0 = 1, D2,0 = 0, D3,0 = 10. |
|
Then, we can apply the Divided Difference Table formula to find the Di,1:
|
D0,1 = |
D1,0-D0,0
x1-x0
|
= |
1 + 8
1+2
|
= 3, D1,1 = |
0-1
2-1
|
= -1, D2,1 = |
10-0
4-2
|
= 5. |
|
Again, the formulas can be applied to find the Di,2:
|
D0,2 = |
D1,1-D0,1
x2-x0
|
= |
-1 - 3
2+2
|
= -1, D1,2 = |
D2,1-D1,1
x3-x1
|
= |
5 + 1
4-1
|
= 2. |
|
Lastly, the formula is applied one more time to find D0,3.
|
D0,3 = |
D1,2-D0,2
x3-x0
|
= |
2+1
4+2
|
= 1/2. |
|
Written in full, the DDT would look like this:
-
| -8 | 3 | -1 | 1/2 |
| 1 | -1 | 2 | |
| 0 | 5 | | |
| 10 | | | |
All we need now is the top row (and the values of the xi)f. The desired polynomial is
|
p(x) = -8 + (x+2)[3 + (x-1)[-1 + (x-2)[1/2]]]. |
|
Again, although this looks completely different, it is in fact the same
polynomial that was derived using the other two methods.
File translated from TEX by TTH, version 2.25.
|
