3.

2 - Interpolation and Lagrange Polynomials

1. Polynomial Interpolation:
Problem: Given n  1 pairs of data points x i , y i , where y i  fx i , i  0, 1, . . . , n for some function
fx, we want to find a polynomial P k x of lowest possible degree for which
P k x i   y i , i  0, 1, . . . , n (P k x agrees with fx at x 0 , . . . , x n ).
The polynomial P k x is said to interpolate the data x i , y i , i  0, 1, . . . , n and is called an
interpolating polynomial. Graphically, P k x is an approximation to fx and satisfies the conditions:
P k x i   fx i , i  0, 1, . . . , n.
For example,
y
10

-3.0 -2.5 -2.0 -1.5 -1.0 -0.5 0.5 1.0 1.5 2.0 2.5 3.0
x
-5

-10

— y  fx, - - - y  P k x
Obviously, for this example P k x is not a good approximation to fx though P k x satisfies the
conditions:
P k x i   y i for i  0, 1, 2.
How to form P k x?
There are several ways to form P k x. Let us start with a way we know already. Let
P k x  a 0  a 1 x  a 2 x 2 . . . a k x k .
We want to find coefficients a 0 , a 1 , . . . , a k such that the following n  1 equations hold:
P k x i   a 0  a 1 x  a 2 x 2 . . . a k x k  y i for i  0, 1, . . . , n.
Rewrite these n  1 equations in a matrix-vector form:
a0
1 x 0 x 20  x k0 y0
a1
1 x1 x 21  x k1 y1
(*) a2  .
     

1 x n x 2n  x kn yn
ak

a0
a1
The vector a2 is a solution of the system (*) of n  1 linear equations in k  1 unknowns.

ak

1
Consider the case where k  n. Recall in Linear Algebra, we learned that this system has a unique
1 x 0 x 20  x k0
1 x 1 x 21  x k1
solution if the coefficient matrix is nonsingular and the solution vector is of the
    
1 x n x 2n  x kn
form:
a0 −1
1 x 0 x 20  x k0 y0
a1
1 x 1 x 21  x k1 y1
a2 
     

1 x n x 2n  x kn yn
ak
and can be solved by Gaussian-Elimination and Backward-Substution.
Example Let x 0  0, x 1  0. 6, x 2  0. 9, fx  cosx 2 . Find P 2 x  a 0  a 1 x  a 2 x 2 . Sketch both
y  fx and y  P 2 x for x in 0, 1.
a0
Solve a1 from the following system:
a2

1 0 0 a0 1
1 0. 6 0. 36 a1  cos0. 36
1 0. 9 0. 81 a2 cos0. 81
−1
a0 1 0 0 1 1. 0
a1  1 0. 6 0. 36 cos0. 36  0. 369 487 601 .
a2 1 0. 9 0. 81 cos0. 81 −0. 793 877 047
Hence, P 2 x  1  0. 369 487 601x − 0. 793 877 047 x 2 .

y 1.0
0.9

0.8

0.7

0.6

0.0 0.2 0.4 0.6 0.8 1.0

x

— y  fx, - - - y  P 2 x
In MatLab, we can complete this example as follows.
xv[0;0.6;0.9];
A[ones(3,1) xv xv.^2];

2
yvcos(xv.^2);
coeffvinv(A)*yv
coeffv 
1.000000000000000
0.369487600719125
-0.793877046537612
Now we sketch the graphs of y  cosx 2  and y  P 2 x  1  0. 369 487 601x − 0. 793 877 047 x 2 for x
in 0, 1.
xvnew0:0.01:1;
y1cos(xvnew.^2);
y2coeffv(1)coeffv(2)*xvnewcoeffv(3)*xvnew.^2;
plot(xvnew,y1,’r-’,xvnew,y2,’b-.’);
2
red - y=cos(x ), blue -. y=P (x)
2
1.3

1.2

1.1

0.9

0.8

0.7

0.6

0.5
0 0.2 0.4 0.6 0.8 1

If we want to add a pair of data 0. 3, cos0. 09, then we can go over the following steps.
xv[0;0.3;0.6;0.9];
A[ones(4,1) xv xv.^2 xv.^3];
yvcos(xv.^2);
coeffvinv(A)*yv
coeffv 
1.000000000000000
-0.064958529434456
0.412917759444563
-0.804529870654783
Hence, P 3 x  1 − 0. 064958529434456x  0. 412917759444563x 2 − 0. 804529870654783x 3 . Now we
sketch the graphs of y  cosx 2  and y  P 3 x as follows. Remember that xvnew and y1 are still there.
We need to recompute y2.
y2coeffv(1)coeffv(2)*xvnewcoeffv(3)*xvnew.^2coeffv(4)*xvnew.^3;
plot(xvnew,y1,’r-’,xvnew,y2,’b-.’);
 title(’red - ycos(x^2), blue -. yP_3(x) ’)

3
 2
red - y=cos(x ), blue -. y=P (x)
3
1

0.95

0.9

0.85

0.8

0.75

0.7

0.65

0.6

0.55

0.5
0 0.2 0.4 0.6 0.8 1

Clearly, P 3 x fits y  cosx 2  much better than P 2 x does.

Note that the system (*) of linear equations are getting more difficult to solve when n is large. Can
P k x be formed with less computation?
2. Lagrange Interpolating Polynomials:
a. Lagrange Polynomials:
For k  0, 1, . . . , n, define
n
x − x i  x − x 0 . . . x − x k−1 x − x k1 . . . x − x n 
L n,k x   x k − x i 

x k − x 0 . . . x k − x k−1 x k − x k1 . . . x k − x n 
.
i0, i≠k

L n,k x are called Lagrange polynomials. For example, let x i  i, i  0, 1, 2, 3. Then
x 0  0, x 1  1, x 2  2 and x 3  3, and
x − 0x − 2x − 3
L 3,1 x   1 xx − 2x − 3
1 − 01 − 21 − 3 2
xx − 1x − 3
L 3,2 x   − 1 xx − 1x − 3
2 − 02 − 12 − 3 2
Observe that Lagrange Polynomials have the following properties:
i. L n,k x k   1
x k − x 0 . . . x k − x k−1 x k − x k1 . . . x k − x n 
L n,k x k   1
x k − x 0 . . . x k − x k−1 x k − x k1 . . . x k − x n 
ii. L n,k x i   0 for i ≠ k.
x i − x 0 . . . x i − x i . . . x i − x k−1 x i − x k1 . . . x i − x n 
L n,k x i   0
x k − x 0 . . . x k − x i . . . x k − x k−1 x k − x k1 . . . x k − x n 
For example,
22 − 12 − 3 11 − 11 − 3
L 3,2 2   1 and L 3,2 1   0.
2 − 02 − 12 − 3 2 − 02 − 12 − 3

b. Lagrange Interpolating Polynomials:

The polynomial
4
 n
P n x  ∑ y k L n,k x  y 0 L n,0 x  y 1 L n,1 x . . . y n L n,n x
k0

is called the nth Lagrange interpolating polynomial. Observe that for i  0, 1, . . . , n

n
P n x i   ∑ y k L n,k x i   y i L n,i x i   y i .
k0

P n x is an nth polynomial that agrees with fx at x 0 , x 1 , . . . , x n .

Theorem Suppose that x 0 , . . . , x n are distinct numbers in the interval a, b and f n1 is continuous
in a, b . For each x in a, b , there exists a number cx in a, b such that
f n1 cx
fx  P n x  x − x 0 x − x 1 . . . x − x n .
n  1!
t − x 
Proof For x ≠ x i and x in a, b , define ht  ft − P n t − fx − P n x  k0 x − xkk .
n

Clearly, hx i   0, i  0, 1, . . . , n. Observe that hx  0. Since x ≠ x i ,

ht  0 at t  x 0 , x 1 , . . . , x n , x.
Since ht has n  2 distinct zeros in a, b , by Rolle’s Theorem, we know there exists a
constant c in a, b such that h n1 c  0.
n  1!
h n1 t  f n1 t − 0 − fx − P n x
x − x 0 x − x 1 x − x n 
n  1!
h n1 c  f n1 c − 0 − fx − P n x 0
x − x 0 x − x 1 . . . x − x n 
f n1 c
R n x  fx − P n x  x − x 0 x − x 1 x − x n .
n  1!

Recall in Calculus II, we studied nth degree Taylor polynomial at x  c :

′′
f ′ c f c f n c
P Taylor x  fc  x − c  x − c 2    x − c n
1! 2! n!
and its error
f n1 
R Taylor x  x − c n1 where  is between x and c.
n  1!
Note that the differences between a kth degree Taylor polynomial and a kth degree interpolating
polynomial are:
a. P Taylor x  fx at only x  x 0 and P interpolating x  fx, at x  x 0 , x 1 , . . . , x n .
′ ′′
b. P Taylor requires knowledge of f , f , . . . but P interpolating requires fx 0 , fx 1 , . . . , fx n . Recall in
Calculus II, we studied nth degree Taylor polynomial at x  c :
′′
f ′ c f c f n c
P Taylor x  fc  x − c  x − c 2    x − c n
1! 2! n!
and its error
f n1 
R Taylor x  x − c n1 where  is between x and c.
n  1!
Note that the differences between a kth degree Taylor polynomial and a kth degree interpolating
5
polynomial are:
a. P Taylor x  fx at only x  x 0 and P interpolating x  fx, at x  x 0 , x 1 , . . . , x n .
′ ′′
b. P Taylor requires knowledge of f , f , . . . but P interpolating requires fx 0 , fx 1 , . . . , fx n .

Example Let x 0  0, x 1  0. 6, x 2  0. 9, fx  cosx 2 .

(1) Find the Lagrange interpolating polynomial P 2 x and R 2 x.
(2) Use P 2 x to approximate f0. 45 and estimate the approximation error.
1 1
(3) Approximate  cosx 2 dx by  P 2 xdx.
0 0
(1)
x − 0. 6x − 0. 9 xx − 0. 9 xx − 0. 6
P 2 x  f0  f0. 6  f0. 9
−0. 6−0. 9 0. 6−0. 3 0. 90. 3
cos0. 36 cos0. 81
P 2 x  1 x − 0. 6x − 0. 9 − xx − 0. 9  xx − 0. 6
0. 54 0. 18 0. 27

y 1.0

0.9

0.8

0.7

0.6

0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
x

— y  cosx 2 , - - - y  P 2 x
′ ′′
f x  −2x sinx 2 , f x  −2sinx 2   2x 2 cosx 2 ,
′′′
f x  −22x cosx 2   4x cosx 2  − 4x 3 sinx 2   −43x cosx 2  − 2x 3 sinx 2 
− 43c cosc 2  − 2c 3 sinc 2 
R 2 x  xx − 0. 6x − 0. 9
6
where c is in 0, 1 .
(2)
f0. 45 ≈ P 2 0. 45

 1 −0. 15−0. 45 − cos0. 36 0. 45−0. 45  cos0. 81 0. 45−0. 15
0. 54 0. 18 0. 27
 1. 005 509
True error  cos 0. 45 2 − P 2 0. 45  0. 979 566 8 − 1. 005 509  0. 025 942 2
Find the approximation error:
′′′
f x ≤ max − 43x cosx 2  − 2x 3 sinx 2  ≤ 43  2  20
x in 0,1

6
 ′′′ ′′′
or check out the graph of f x to have a better estimate of an upper bound of f x :

y6
′′′
5 f x ≤ 6. 5, for x in 0, 1
4
R 2 0. 45 ≤ 6. 5 0. 45−0. 15−0. 45
3 6
2  0. 03290
1

0
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
x

y  |−43x cosx 2  − 2x 3 sinx 2 |

(3)
1 1
 0 P 2 xdx   0 1 x − 0. 6x − 0. 9 − cos0. 36 xx − 0. 9  cos0. 81 xx − 0. 6 dx
0. 54 0. 18 0. 27
1 cos0. 36 1 2
 1  x − 0. 6 2 − 0. 3x − 0. 6 dx −  0 x − 0. 9xdx
0. 54 0 0. 18
cos0. 81 1 2

0. 27
 0 x − 0. 6xdx
cos0. 36 cos0. 81
 1 0. 123 333 333  − −0. 116 666 667   3. 333 333 33  10 −2 
0. 54 0. 18 0. 27
 0. 920 118 119

3. Neville’s Iterated Interpolation:

If we need to add more points x n1 , . . . from P n x to construct an interpolation polynomial with
larger degree, can we construct an interpolation polynomial iteratively? The answer is yes. The method
is called the Neville Method.
Let m 1 , m 2 , . . . , m k be k distinct integers where 0 ≤ m i ≤ n for each i. Let P m 1 ,m 2 ...,m k x be the
Lagrange polynomial that agrees with f at the k points: x m 1 , x m 2 , . . . , x m k . For example,
x − x 2 x − x 4  x − x 1 x − x 4  x − x 1 x − x 2 
P 1,2,4 x  fx 1   fx 2   fx 4 
x 1 − x 2 x 1 − x 4  x 2 − x 1 x 2 − x 4  x 4 − x 1 x 4 − x 2 
is the Lagrange polynomial that agrees with fx at 3 points: x 1 , x 2 , x 4 :
P 1,2,4 x 1   fx 1 , P 1,2,4 x 2   fx 2 , P 1,2,4 x 3   fx 3 .

Theorem Let f be defined at x 0 , x 1 , . . . , x k , and x j and x k be two distinct numbers. Then

x − x j P 0,1,...,j−1,j1,...,k x − x − x i P 0,1,...,i−1,i1,...,k x
P 0,1,....,k x  xi − xj .

Proof We know that both polynomials P 0,1,...,j−1,j1,...,k x and P 0,1,...,i−1,i1,...,k x are degree k − 1. So,
the degree of P 0,1,....,k x is k. Check if P 0,1,....,k x l   fx l  for l  0, 1, . . . , k : since
P 0,1,...,j−1,j1,...,k x l   fx l  if l ≠ j and P 0,1,...,i−1,i1,...,k x l   fx l  if l ≠ i
For l  0, 1, . . . , k, but l ≠ i and l ≠ j,

7
 x l − x j P 0,1,...,j−1,j1,...,k x l  − x l − x i P 0,1,...,i−1,i1,...,k x l 
P 0,1,....,k x l   xi − xj
x l − x j fx l  − x l − x i fx l  x i − x j 
  fx l   fx l 
x i − x j  x i − x j 
For l  i :
x i − x j P 0,1,...,j−1,j1,...,k x i  − x i − x i P 0,1,...,i−1,i1,...,k x i 
P 0,1,....,k x i   xi − xj
 P 0,1,...,j−1,j1,...,k x i   fx i 
For l  j :
x j − x j P 0,1,...,j−1,j1,...,k x j  − x j − x i P 0,1,...,i−1,i1,...,k x j 
P 0,1,....,k x i   xi − xj
 P 0,1,...,i−1,i1,...,k x j   fx j 
So, P 0,1,....,k x the kth degree interpolating polynomial.

Example Consider x 0 , x 1 , . . . , x n . Then we can form

x − x 2  x − x 1  x − x 4  x − x 4 
P 1,2 x  fx 1   fx 2  and P 2,4 x  fx 2   fx 4 
x 1 − x 2  x 2 − x 1  x 1 − x 4  x 2 − x 4 
using x 1 , x 2 and x 4 . Then we can combine P 1,2 x and P 2,4 x to form P 1,2,4 x:
x − x 4 P 1,2 x − x − x 1 P 2,4 x
P 1,2,4 x 
x 1 − x 4 
which is the Lagrange polynomial that agrees with fx at 3 points: x 1 , x 2 , x 4 .
Now given 0, 1 , 1, e −1 , 2, e −4 , and 3, e −9 , find P 0,1,2,3 x using P 0,1,2 x and
P 1,2,3 x.

x − 1x − 2 x − 0x − 2 x − 0x − 1

P 0,1,2 x   e −1  e −4
0 − 10 − 2 1 − 01 − 2 2 − 02 − 1
−4
 1 x − 1x − 2 − e −1 xx − 2  e xx − 1
2 2
x − 2x − 3 x − 1x − 3 x − 1x − 2
P 1,2,3 x  e −1  e −4  e −9
1 − 21 − 3 2 − 12 − 3 3 − 13 − 2
−9
 1 e −1 x − 2x − 3 − e −4 x − 1x − 3  e x − 1x − 2
2 2
x − 0P 1,2,3 x − x − 3P 0,1,2 x
P 0,1,2,3 x   1 xP 1,2,3 x − x − 3P 0,1,2 x
3 − 0 2

Algorithm Neville’s Iterated Interpolation: Steps of Computing P 0,1,2,...,k x̄  for a given x̄ : (neville.m)
Given x i , fx i  for i  0, 1, . . . , k and , let P i  fx i 

8
 xi P i x̄  P i,i1 x̄  P i,i1,i2 x̄  P i,i1,i2,i3 x̄  P i,i1,i2,i3,i4 x̄ 
x0 P0
x1 P1 P 0,1 x̄ 
x2 P2 P 1,2 x̄  P 0,1,2 x̄ 
x3 P3 P 2,3 x̄  P 1,2,3 x̄  P 0,1,2,3 x̄ 
x4 P4 P 3,4 x̄  P 2,3,4 x̄  P 1,2,3,4 x̄  P 0,1,2,3,4 x̄ 
     

The algorithm stops and fx̄  ≈ P 0,1,2,...,k x̄  whenever

P 0,1,2,...,k x̄  − P 0,1,2,...,k−1 x̄   .

An alternative way:
xi P i x̄  P i,i1 x̄  P i,i1,i2 x̄  P i,i1,i2,i3 x̄  P i,i1,i2,i3,i4 x̄ 
x0 P0
x1 P1 P 0,1 x̄ 
x2 P2 P 0,2 x̄  P 0,1,2 x̄ 
x3 P3 P 0,3 x̄  P 0,2,3 x̄  P 0,1,2,3 x̄ 
x4 P4 P 0,4 x̄  P 0,3,4 x̄  P 0,2,3,4 x̄  P 0,1,2,3,4 x̄ 
     

Example Suppose that x j  j for j  0, 1, 2, 3 and it is known that

P 0,1 x  x  1, P 1,2 x  3x − 1, and P 1,2,3 1. 5  4.
Find P 2,3 1. 5, P 0,1,2 x and P 0,1,2,3, 1. 5.

x − x 2 P 0,1 x − x − x 0 P 1,2 x x − 2x  1 − x3x − 1

P 0,1,2 x  x0 − x2   x2  1
−2
xi P i x̄  P i,i1 x̄  P i,i1,i2 x̄  P i,i1,i2,i3 x̄ 
0 P0
1 P1 P 0,1 1. 5  2. 5
2 P2 P 1,2 1. 5  3. 5 P 0,1,2 1. 5  3. 25
3 P3 P 2,3 1. 5 P 1,2,3 1. 5  4 P 0,1,2,3 1. 5  5. 4375
x − x 1 P 2,3 x − x − x 3 P 1,2 x x − 1P 2,3 x − x − 33x − 1
P 1,2,3 x  x3 − x1  4
3−1
8  1. 5 − 33. 5
P 2,3 1. 5   5. 5
1. 5 − 1
1. 5 − 2P 0,1 1. 5 − 1. 5 − 0P 1,2 1. 5 −0. 52. 5 − 1. 53. 5
P 0,1,2 1. 5    3. 25
0 − 2 −2

9
 1. 5 − 3P 0,1,2 1. 5 − 1. 5 − 0P 1,2,3 1. 5 −1. 53. 25 − 1. 54
P 0,1,2,3 1. 5    5. 437 5
0 − 3 −2

Example Neville’s method is used to approximate f0. 4 as follows. Complete the table.
xi P i x̄  P i,i1 x̄  P i,i1,i2 x̄  P i,i1,i2,i3 x̄ 
0 1
0. 25 2 P 0,1 0. 4  2. 6
0. 5 P2 P 1,2 0. 4 P 0,1,2 0. 4
0. 75 8 P 2,3 0. 4  2. 4 P 1,2,3 0. 4  2. 96 P 0,1,2,3 0. 4  3. 016

0. 4 − 0. 75P 2 − 0. 4 − 0. 5P 3 2. 4−0. 25 − 0. 18

P 2,3 0. 4   2. 4, P 2  4
0. 5 − 0. 75 −0. 35
0. 4 − 0. 5P 1 − 0. 4 − 0. 25P 2 0. 4 − 0. 52 − 0. 4 − 0. 254
P 1,2 0. 4    3. 2
0. 25 − 0. 5 0. 25 − 0. 5
0. 4 − 0. 5P 0,1 0. 4 − 0. 4 − 0P 1,2 0. 4 0. 4 − 0. 52. 6 − 0. 4 − 03. 2
P 0,1,2 0. 4    3. 08
0 − 0. 5 0 − 0. 5
Check:
0. 4 − 0. 753. 08 − 0. 4 − 02. 96
P 0,1,2,3 0. 4   3. 016
0 − 0. 75

Example Let fx  sinln x, x 0  2. 0, x 1  2. 4, x 2  2. 6.

(1) Estimate the approximation error R 2 x of an interpolating polynomial
P 2 x over 2. 0, 2. 6 .
(2) Approximate f2. 2 and f2. 5, and estimate their errors.
(1)
′′′
f c
R 2 x  x − 2x − 2. 4x − 2. 6 , where c is in 2, 2. 6
3!

′ cosln x ′′ − sinln x 1x x − cosln x − sinln x − cosln x

f x  x , f x  2

x x2
′′′ − cosln x 1x   sinln x 1x x 2  2xsinln x  cosln x
f x 
x4
− cosln x  sinln x  2sinln x  cosln x 3 sinln x  cosln x
 3

x x3

10
 y 0.32 y
0.015
0.30

0.28
0.010
0.26

0.24
0.005
0.22

0.20

0.18 0.000
2.0 2.1 2.2 2.3 2.4 2.5 2.6
2.0 2.1 2.2 2.3 2.4 2.5 2.6 x
′′′
f x y  |x − 2x − 2. 4x − 2. 6|
′′′ ′′′ 3 sinln 2  cosln 2
f x ≤ f 2   0. 336
23
′′′
f c
R 2 x  x − 2x − 2. 4x − 2. 6 ≤ 0. 336 0. 02  0. 001 12
3! 6
(2)  xv[2;2.4;2.6];
 yvsin(log(xv));
 [yout,yall]neville(xv,yv,2.1,2)
yout  0.67510095866951
yall 
0.63896127631363 0.67118192650420 0.67510095866951
0.76784387707588 0.69469611949605 0
0.81660904879577 0 0
 [yout,yall]neville(xv,yv,2.5,2)
yout 0.79353280699093
yall 
0.63896127631363 0.80006452726644 0.79353280699093
0.76784387707588 0.79222646293583 0
0.81660904879577 0 0
true error: |sinlog2. 1 − 0. 67510095866951|  6. 163 548 3  10 −4
true error: |sinlog2. 5 − 0. 79353280699093|  1. 838 044 02  10 −4
′′′ ′′′
f c f c
R 2 2. 1  2. 1 − 22. 1 − 2. 42. 1 − 2. 6  |2. 1 − 22. 1 − 2. 42. 1 − 2. 6|
3! 6

≤ 0. 336 0. 015  0. 00084

6
′′′ ′′′
f c f c
R 2 2. 5  2. 5 − 22. 5 − 2. 42. 5 − 2. 6  |2. 5 − 22. 5 − 2. 42. 5 − 2. 6|
3! 6

≤ 0. 336 0. 005  0. 000 28

6

11
 Exercises:
1. Given x i , y i   0, −1,  12 , 1, 1, 2 where y i  fx i  for some fx, construct the polynomial
P 2 x that agrees with fx at x 0 , x 1 and x 2 in the following two ways.
(1) P 2 x  a 0  a 1 x  a 2 x 2 a standard form.
(2) P 2 x is a Lagrange interpolating polynomial.

2. Let x 0  −1, x 1  0, x 2  1, and fx  e x .

(1) Find algebraically (keep e in P 2 x) the Lagrange interpolating polynomial P 2 x and its
approximation error R 2 x.
(2) Use P 2 x to approximate f 12  and f − 13 .
(3) Compute the true approximation errors f 12  − P 2  12  and f − 13 − P 2 − 13 .
(4) Estimate the approximation errors using R 2  12  and R 2 − 13 .
1 1 1 1
(5) Approximate  e x dx by  P 2 xdx and find the true approximation error  e x dx −  P 2 xdx .
−1 −1 −1 0

3. Let x 0  0, x 1  0. 6, x 2  0. 9, and fx  1  x .

(1) Find the Lagrange interpolating polynomial P 2 x and its approximation error R 2 x.
(2) Use P 2 x to approximate f0. 45 and |R 2 0. 45| to estimate the approximation error.

4. Use Neville’s method to approximate f0. 5, giving the following table. Determine P 2  f0. 7.
i xi Pi P i,i1 P i,i1,i2
0 0 0
1 0. 4 2. 8 3. 5
27
2 0. 7 7

5. Suppose we know that f0  1, f0. 25  1. 64872, f0. 5  2. 71828, f0. 75  4. 48169. Use given
data to approximate f0. 43 by a Lagrange interpolating polynomial using Neville’s method (MatLab
program neville.m).

6. A census of the population of the US is taken every 10 years. The population, in thousands, from 1940
to 2000 is given below.
year 1940 1950 1960 1970 1980 1990 2000
t 0 10 20 30 40 50 60
population 132165 151326 179323 203302 226542 249633 251432
Use Neville’s method (MatLab program neville.m) to estimate the populations in 1975 and 2005 and
predict the population in 2010.

7. Let fx  2 x . Approximate f0. 5  2 by P0. 5 where Px is a Lagrangian interpolating

polynomial. Suppose that Neville’s Method is used to generate P0. 5 iteratively as follows.

12
 P 0 0. 5 P 0,1 0. 5 P 0,1,2 0. 5 P 0,1,2,3 0. 5 P 0,1,2,3,4 0. 5 P 0,1,2,3,4,5 0. 5 P 0,1,2,3,4,5,6 0. 5
1. 00000000 1. 35886731 1. 41038161 1. 41407897 1. 41421166 1. 41421356 1. 41421357
Let the stopping criterion be set as | P 01k 0. 5 − P 01k−1 0. 5 | .
a. Determine the degree (k) of the polynomial used to approximate 2 with   0. 0001.
b. If P 0,1,2,3,4,5,6 0. 5 is chosen from above sequence to approximate 2 , what is ?

13