
Interpolatory Polynomial Examples
Given a set of n+1 points (x_{0},f_{0}),...,(x_{n},f_{n}), 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 x_{0} = 2, x_{1} = 1, x_{2} = 2, x_{3} = 4,
and f_{0} = 8, f_{1} = 1, f_{2} = 0 and f_{3} = 10. We should expect the interpolating
polynomial to be a cubic polynomial.
A direct method: If one writes the polynomial as
p(x) = a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}, then substituting the given points
into p(x) gives the following system of equations:
a_{0}2a_{1}+4a_{2}8a_{3} = 8, 

a_{0}+a_{1}+a_{2}+a_{3} = 1, 

a_{0}+2a_{1}+4a_{2}+8a_{3} = 0, and 

a_{0}+4a_{1}+16a_{2}+64a_{3} = 10. 

With a lot of patience, and even more care with the arithmetic, this system
of equations can be solved, giving a_{0} = 2, a_{1} = 0, a_{2} = 3/2 and a_{3} = 1/2,
so that the desired polynomial is p(x) = 2(3/2)x^{2}+(1/2)x^{3}.
The Lagrange Interpolating Polynomial (LIP):
Given x_{0} = 2,x_{1} = 1,x_{2} = 2,x_{n} = 4, we can write down Lagrange's l_{i}(x), as follows:
l_{0}(x) = 
(x1)(x2)(x4) (21)(22)(24)

=  
1 72

(x1)(x2)(x4), 

l_{1}(x) = 
(x+2)(x2)(x4) (1+2)(12)(14)

= 
1 9

(x+2)(x2)(x4), 

l_{2}(x) = 
(x+2)(x1)(x4) (2+2)(21)(24)

=  
1 8

(x+2)(x1)(x4), and 

l_{3}(x) = 
(x+2)(x1)(x2) (4+2)(41)(42)

= 
1 36

(x+2)(x1)(x2). 

Then, using the values f_{0} = 8,f_{1} = 1,f_{2} = 0,f_{3} = 10, we can write the desired polynomial
as p(x) = 8.l_{0}(x)+1.l_{1}(x)+0.l_{2}(x)+10.l_{3}(x), or
p(x) =  
8 72

(x1)(x2)(x4) + 
1 9

(x+2)(x2)(x4) + 
10 36

(x+2)(x1)(x2). 

Although it looks completely different, this is the same polynomial that
we derived before.
The Divided Difference Method:
Given the same values of the x_{i} and the f_{i}, we can begin to write down the
divided difference table. The values of D_{i,0} are just the values of f_{i},
so
D_{0,0} = 8, D_{1,0} = 1, D_{2,0} = 0, D_{3,0} = 10. 

Then, we can apply the Divided Difference Table formula to find the D_{i,1}:
D_{0,1} = 
D_{1,0}D_{0,0} x_{1}x_{0}

= 
1 + 8 1+2

= 3, D_{1,1} = 
01 21

= 1, D_{2,1} = 
100 42

= 5. 

Again, the formulas can be applied to find the D_{i,2}:
D_{0,2} = 
D_{1,1}D_{0,1} x_{2}x_{0}

= 
1  3 2+2

= 1, D_{1,2} = 
D_{2,1}D_{1,1} x_{3}x_{1}

= 
5 + 1 41

= 2. 

Lastly, the formula is applied one more time to find D_{0,3}.
D_{0,3} = 
D_{1,2}D_{0,2} x_{3}x_{0}

= 
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 x_{i})f. The desired polynomial is
p(x) = 8 + (x+2)[3 + (x1)[1 + (x2)[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 T_{E}X by T_{T}H, version 2.25.
