M575 Chapter 7 - LECTURE NOTES, EXERCISE, AND SOLUTION PDF

Preview

Summary

Download M575 Chapter 7 - LECTURE NOTES, EXERCISE, AND SOLUTION PDF

Description

Part 4 INTERPOLATING POLYNOMIAL

MAT 575

Chapter 7

Lagrange Interpolation Method At the end of this chapter, students should be able to: 

Determine the interpolating polynomials by Lagrange method



Estimate the unknown data values



Determine the error involved in the interpolations

7.1 Introduction As mentioned earlier in Chapter 6, interpolation is generally defined as a process of predicting unknown data values by using a polynomial that passes through the given data values. The Newton’s method of divided-difference was discussed in the preceding chapter while only the Lagrange method is described in this chapter.

The setup is similar only that the method is

different. Again, suppose that we are given a table of numerical values of a function, such as the following:

x

x0

x1

…

xn

y

y0

y1

…

yn

The same question remains, Is it possible to find a simple and convenient formula that reproduces the given point exactly?

107

Part 4 INTERPOLATING POLYNOMIAL

MAT 575

Joseph-Louis Lagrange was another great mathematician capable of developing an answer to this question. The Lagrange method was regarded by many as the best choice when one already knows what polynomial degree will be needed. In order to construct a polynomial of degree at most n, we need at least n + 1 points. Another advantage of Lagrange method over the Newton’s method of divided difference is that the estimation of the values of the function need not necessarily be at the top or at the bottom of the table. We shall now describe the Lagrange interpolating polynomials.

7.2 Lagrange Interpolating Polynomials Although, interpolating polynomials can be written in a variety of forms, the most convenient and efficient among these is probably the Newton formula described earlier. Conceptually, however, the Lagrange method has several advantages; such that it may be used to prove the uniqueness of the interpolating polynomials and can be used with either equal or unequal intervals of the independent variable. Therefore it is a method of choice in proofs and theoretical arguments. The Lagrange interpolating polynomial is described in the following theorem without proofs. Theorem 1 If x0 , x1, ..., xn are (n + 1) distinct numbers and f is a function whose values are given at these numbers, then there exists a unique polynomial P of degree at most n with the property that f(xk )  P(x k ) for each k = 0, 1, …, n.

This polynomial is given by

P(x)  f(x0 )L0  f(x1)L1  ...  f(xn )Ln n

 ∑f(xk )Lk (x) k 0

where

L k (x) 

(x - x 0)(x - x 1)...(x - x k -1)(x - x k 1)...(x - x n ) (x k - x 0)(xk - x 1)...(x k - x k -1)(xk - x k 1)...(xk - x n )

n

( x - xi ) i 0 ( xk - xi )

= 

for each k = 0, 1, …, n

i≠ k

108

Part 4 INTERPOLATING POLYNOMIAL

MAT 575

Steps – Lagrange Interpolation  Identify the number of points: n + 1  Find L k (x)for each k = 0, 1, 2,…, n n

( x - xi ) i 0 ( xk - xi )

L k( x )  

i≠k

 Apply the Lagrange Interpolation Formula:

Pk ( x) 

n

∑f(xk )Lk (x) k 0

Example 1 Approximate a function f for which

f ( x0 )  y 0 and f(x1)  y1 . Determine

the interpolating polynomial of degree 1 and write it in the form of Lagrange interpolating polynomial.

Solution



There are two points

(x0 , y0 ) and (x1, y1 ) 

Formula for a straight line

y - y0 m x - x0

y1 - y0 x1 - x0

y -y y - y 0  1 0  x - x0  x1 - x 0

y -y  y  y 0   1 0 x - x 0   x1 - x0  A straight line is also known as polynomial of degree 1. Thus,

y -y  P1(x)  y 0   1 0  ( x  x0 )  x1  x 0  Rearrange the term in (1) yields

 x - x0   x - x1     y1 P1(x)  y 0  x x    1 0  x 0  x1  f ( x 0 )L0  f ( x1)L1

109

Part 4 INTERPOLATING POLYNOMIAL

where  x - x1   L0     x0  x1 

 x - x0   L1     x1  x 0 

and

Example 2 Find Lagrange interpolating polynomial for the given values. x y

2 3

4 27

5 45

Solution



Identify the number of points: n + 1

n+1=3 

Find L k (x)for each k = 0, 1, 2 k=0 2

(x - x i ) i 0 ( x 0 - x i)

L 0( x )  

i≠0

x  x1x  x 2  x 0  x 1x 0  x 2 x  4 x  5   2  4 2  5  



L 0 ( x)  



x 2  9 x  20  2  3 





1 2 x  9 x  20 6

k=1

L1 (x ) 

2

(x - x )

 ( x1 - xi i ) i 0 i≠1

x  x 0 x  x 2  x1  x0 x1  x 2  x  2 x  5   4  24  5



110

MAT 575

Part 4 INTERPOLATING POLYNOMIAL

x2  7 x  10 2 1 1 2  x  7 x  10 2

MAT 575

L1 (x ) 





k=2 2

(x - xi) i 0 ( x 2 - x i)

L 2( x)  

i≠2



x  x0 x  x1  x2  x0 x2  x1  x  2x  4  5  2 5  4  

x 2  6x  8 31



1 2 x  6x  8 3





 Apply the Lagrange Interpolation Formula: n

Pk ( x ) 

∑f (xk )Lk (x) k 0

 f(x0 )L 0 (x) f(x1)L1(x) f(x2 )L 2(x)











 1  1   1  3  x2  9 x  20  27  x2  7 x  10  45  x2  6x  8 6 2    3     9 189   1 27    90   10  135  120   x2    15  x  2 2 2 2    

 2x 2  0  5  2 x2  5

Example 3 Find Lagrange interpolating polynomial for the given values. X

1

Y

-1

2 1 3

2.5 3 32

Use the interpolating polynomial to approximate y(2.01).

111

3 4 3



Part 4 INTERPOLATING POLYNOMIAL

Solution

n +1=4 k = 0: n

(x - x i) i 0 ( x 0 - x i )

L0 ( x)  

i≠0

 x  x 1  x  x 2  x  x3        x 0  x 1  x 0  x 2  x 0  x 3   x  2   x  2 .5 x  3       1 2   1  2 .5  1  3   x  2   x  2 .5 x  3        1    1 .5   2 



x



 2 .5  x 2  5 x  6 3 1  x 3  2.5 x 2  5 x 2  12 . 5x  6 x  15  3 1 3 x  7.5 x 2  18 .5 x  15  3 

 





k = 1: n

(x - x i ) i 0 ( x 1 - x i )

L1 ( x)  

i ≠1

 x  x 0  x  x 2  x  x 3        x 1  x 0  x1  x 2  x1  x 3

 x  1  x  2 .5  x 3       2  1  2  2 .5  2 3   x  1  x  2 .5 x  3  L1 ( x)       2  1  2  2 .5 2  3   x 1  x  2 .5   x  3       1   0 .5    1  



  13 x  7 .5

1 x  2.5  x 2  4x  3 0 .5



3

 2 x  6 .5 x

2

112

   

MAT 575

Part 4 INTERPOLATING POLYNOMIAL

MAT 575

k = 2: n

(x - x i ) i 0 ( x 2 - x i)

L 2( x )  

i≠2

 x  x 0  x  x 1  x  x 3        x 2  x 0  x 2  x 1  x 2  x 3   x  1  x  2  x  3       2. 5  1  2 .5  2  2 .5  3   x  1  x  2  x  3       1 .5   0 .5   0 .5  1 x  1 x2  5 x  6  0. 375 8 3 2  x  6 x  11x  6 3









k = 3: n

(x - x i ) ( x i 0 3 - x i)

L 3 (x )  

i ≠3

 x  x 0  x  x 1  x  x 2        x 3  x 0  x 3  x 1  x 3  x 2   x  1  x  2  x  2 .5       3  1  3  2  3  2. 5   x  1  x  2  x  3       2   1  0 .5   x 3  5 .5 x 2  9.5 x  5 Apply the Lagrange Interpolation Formula: n

Pk ( x)  ∑f(xk )Lk (x) k 0

 f(x0 )L0 (x)  f(x1 )L1(x)  f(x2 )L2 (x)  f(x3 )L3 (x)

4   3    1 P3 ( x)  (-1)L0 (x)   L1(x)   L2 (x)   L3 (x) 3   32   3    1  1   - 1  x 3  7.5 x 2  18 .5 x  15    2  x 3  6 .5 x 2  13 x  7 .5 3  3 















 3   8  3 4      x  6x2  11x  6    x3  5 .5 x2  9 .5 x  5  32  3  3 

113



Part 4 INTERPOLATING POLYNOMIAL

MAT 575

13 3 22   1 2 1 4  P3 ( x )  x 3       x 2  2.5     3 2 3  3 3 4 3    3 20  18.5 26 11 38   x      5 5  2 3  3 4 3    3 89 31 3  x3  4 x2  x 12 6 4

3 2.013  42. 012  89 2.01  31 6 12 4 6. 0905 16 . 1604 14. 9075  5. 6667  - 0.3291

P3(2. 01) 

Example 4 Consider the curve y = f(x) = sin x over the interval [0.4, 1.0]. Find the linear approximations using a)

the nodes 0.4 and 0.9

b)

the nodes 0.5 and 0.8

c)

approximate at x = 0.65

Solution

x f(x) a)

0.4 0.3894

0.9 0.7833

Linear approximation using nodes 0.4 and 0.9 P (x )  f 0L 0  f 1L1 ( x  x1) ( x  x0 )  f1  f0 (x 0  x 1 ) ( x1  x 0)  (0.3894 )

( x  0.4) ( x  0.9)  (0.7833 ) (0.9  0.4) (0.4  0.9)

 0.7878 x  0.0742

b)

Linear approximation using nodes 0.5 and 0.8 P (x )  f0 L0  f1L1 ( x  x1) (x  x 0 )  f1  f0 ( x0  x1) ( x1  x 0 )

114

Part 4 INTERPOLATING POLYNOMIAL

P( x)  (0. 4794 )

MAT 575

( x  0. 5 ) ( x  0. 8 )  (0. 7174 ) ( 0. 8  0. 5 ) ( 0. 5  0. 8 )

 1.598( x  0.8)  2. 3913 ( x  0.5)  0. 7933 x  0. 0828

c)

use linear approximation to estimate f(0.65) P (0.65 )  f0 L0  f1L1  f0

( x  x1) ( x  x 0)  f1 ( x0  x1 ) (x 1  x 0 )

(0.65  0 .6) (0.65  0.7)  (0. 6442 )  (0. 5646 ) ( 0. 7  0 . 6 ) (0 .6  0.7)  0. 2823  0. 3221  0. 6044

For (a), P1 (0.65)  0.5864 For (b), P1 (0.65)  0.5984 But Exact Value of sin x  0.6052 Therefore, P1( x ) for (b) is much better approximation because the range in (b) is much closer to the estimated value.

Warm up exercise The data below was obtained at the FTSE London on June 8 2010, where the time t is in the 24 hour clock system. t (time) f(t) Share indices

800

1000

1200

1400

1600

5,077

5,011

5,012

5,043

5,002

Estimate the index at 1145am.

7.3 Error Analysis The error bound for interpolating polynomial of degree  n for the given n  1 nodes is stated in Theorem 2 and 3.

115

Part 4 INTERPOLATING POLYNOMIAL

MAT 575

Theorem 2 If p is the polynomial of degree at most n that interpolates f at the n + 1

x0 , x1, x2 , ..., xn

distinct nodes

belonging to an interval

f (n1)(x) is continuous, then for each x in [a, b] there is a

[a, b] and if

 in (a, b) for

which

f(x)- p(x) 

n

1 f (n 1) (β ) (x - x i ) (n  1)! i 0



Theorem 3 f (n1)(x) is continuous on [a, b] and satisfies

Let f be a function such that

 f (n 1) (x) ≤ M . Let p be the polynomial of degree

 n that interpolates f at

n + 1 equally spaced nodes in [a, b], including the endpoints. Then on [a, b] f(x)- p(x) ≤

1  b - a   4n  1  n 

n 1

M

Steps – Error Analysis  Identify number of data : n + 1  Identify exact function (if given)  Find the n+1th derivatives; f (n1)( x)  Find the maximum bound M : f (n 1) ( x )  M

 Compute the approximated error;

Example 5 Given the following values of sin x, evaluate the error when x = 0.197 using error formula. x

0.15

0.17

0.19

0.20

0.23

sin x

0.149

0.169

0.189

0.199

0.228

116

Part 4 INTERPOLATING POLYNOMIAL

MAT 575

Solution

Total data points : n + 1 = 5

(not equispaced)

f(x) = sin x f’(x) = cos x f’’(x) = -sin x … f5(x) = cos x For 0.15  x  0.23 then f ( x)  p( x ) 

max f 5 ( x)  0.9888

1 max f n 1( x ).(x  x 0 )( x  x1 )( x  x 2 )(x  x 3 )( x  x 4 ) (n  1)!

1 (0. 9888 )(0.197  0.15 )(0.197  0.17 )(0.197  0.19 )  5! (0.197  0.20 )(0.197  0.23 )  7. 2464 x 1012

Example 6 Assess the error if sin x is replaced by interpolation polynomial having ten equally spaced nodes in [0, 1.6875].

Solution

Given equispaced data where , n + 1 = 10 f(x) = sin x f’(x) = cos x f’’(x) = -sin x … 10

f (x) = -sin x For 0  x  1.6875 then max f 10 ( x )  1 n 1

f ( x )  P( x ) 

1 b  a    4(n  1)  n 

117

 . max f n 1( x )

Part 4 INTERPOLATING POLYNOMIAL

MAT 575

10

f ( x)  P( x) 

1 1. 6875  0   (1)  4(10 )  9 

 1. 3426 x 10 9

Warm up exercise Given the following values of ln x, evaluate the error when x = 2.137. x

2.0

2.2

2.35

2.6

2.8

ln x

0.6932

0.7885

0.8544

0.9555

1.0296

Exercise 7 1.

If y(1) = - 2, y(3) = 16, y(- 2) = 1 and y(- 3) = - 14, find the value of y(2) without deriving the four-point Lagrange polynomial.

2.

Write down the error term for cubic Lagrange interpolation to f(x) , where interpolation is to be exact at the nodes x 0  1, x 1  0, x 2  3, x 3  4 and f(x) given as below: a)

3.

f ( x )  4x 3  3x  2

Approximate

b) f ( x)  x 5  5 x 4

2.15 using Lagrange interpolation formula and find the error

incurred given the following data:

4.

x

2.0

2.1

2.2

2.3

2.4

x

1.414214

1.449138

1.483240

1.516575

1.549193

Let the function f(x) = ln x be approximated by an interpolation polynomial of degree 9 with ten equally spaced points in the interval [1,2]. What is the maximum bound for the error?

118

Part 4 INTERPOLATING POLYNOMIAL

5.

MAT 575

An electronics lab experiment was designed to compare the measured voltagecurrent relationship for a light emitting diode with calculated values based on the known nonlinear resistance characteristic of the diode. Results are given in the table below. (Source: Monaghan, Computers in Education, Jan-Mar 1998)

a) Plot the measured and calculated current vs. voltage data points on separate graphs. b) Find second, third and fourth order Lagrange interpolating polynomials for each set based on the following data points. MEASURED: ORDER

DATA POINTS

2

(1.421,0.095),(1.512, 0.808),(1.596,6.720)

3

(1.421,0.095),(1.487, 0.461), (1.535,1.390), (1.596,6.720)

4

(1.421,0.095),(1.446, 0.281),(1.512, 0.808), 1.556, 2.350), (1.596,6.720)

CALCULATED: ORDER DATA POINTS 2

(1.420,0.118), (1.500, 0.741), (1.580,4.664)

3

(1.420,0.118), (1.480, 0.468), (1.520,1.173), (1.580,4.664)

4

(1.420,0.118), (1.460, 0.295), (1.500, 0.741),(1.540,1.859), (1.580,4.664)

c) Plot the polynomials on the same graphs with the data points. Comment on the results.

119

Part 4 INTERPOLATING POLYNOMIAL

MAT 575

d) Denote i  f (v i ) as the function relating the actual measured current and voltage. Calculate the average error for each interpolating polynomial

fn (v i ) i.e. 9

Eave 

1 f (v i )  fn (v i ) , 9  i 1



n = 2, 3, 4

e) Repeat Part d) with i  f (v i ) as the function relating the actual calculated current and voltage.

6.

Approximate a function f for which f(x0 )  y0 , f(x1 )  y1 and f(x2 )  y 2 . Determine the interpolating polynomial of degree 2.

120

Part 4 INTERPOLATING POLYNOMIAL

 x - x0  x - x 1  x - x 2    y 1  P2(x)  y 0   x1  x0  x 0  x1  x0  x2   x - x0  x - x 1     y 2    x 2  x0  x 2  x1 

http://www.math.dartmouth.edu/~calcsite/video1.html#406 Source: 1999 Addison Wesley Longman, Inc. http://www.mathcs.emory.edu/ccs/ccs215/integral/node3.html

121

 x - x 2     x1  x 2 

MAT 575...