Chapter 18 1 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Interpolation Chapter 18 Estimation of intermediate values between precise data points. The most common method is: f ( x) a0 a1 x a2 x 2 an x n Although there is one and only one nth-order polynomial that fits n+1 points, there are a variety of mathematical formats in which this polynomial can be expressed: The Newton polynomial
The Lagrange polynomial 2 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Figure 18.1 3 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Newtons Divided-Difference Interpolating Polynomials Linear Interpolation/ Is the simplest form of interpolation, connecting two data points with a straight line.
f1 ( x) f ( x0 ) f ( x1 ) f ( x0 ) x x0 x x0 Slope and a finite divided difference approximation to 1st derivative f ( x1 ) f ( x0 ) f1 ( x) f ( x0 ) ( x x0 ) Linear-interpolation x x0
formula f1(x) designates that this is a first-order interpolating polynomial. 4 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Figure 18.2 5 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Quadratic Interpolation/ If three data points are available, the estimate is improved by introducing some curvature into the line
connecting the points. f 2 ( x) b0 b1 ( x x0 ) b2 ( x x0 )( x x1 ) A simple procedure can be used to determine the values of the coefficients. x x0 b0 f ( x0 ) x x1 f ( x1 ) f ( x0 ) b1 x x0
x x2 f ( x2 ) f ( x1 ) f ( x1 ) f ( x0 ) x2 x1 x1 x0 b2 x2 x0 6 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. General Form of Newtons Interpolating Polynomials/ f n ( x) f ( x0 ) ( x x0 ) f [ x1 , x0 ] ( x x0 )( x x1 ) f [ x2 , x1 , x0 ] ( x x0 )( x x1 ) ( x xn 1 ) f [ xn , xn 1 , , x0 ] b0 f ( x0 )
b1 f [ x1 , x0 ] b2 f [ x2 , x1 , x0 ] bn f [ xn , xn 1 , , x1 , x0 ] f [ xi , x j ] f ( xi ) f ( x j ) f [ xi , x j , xk ] xi x j f [ xi , x j ] f [ x j , xk ] Bracketed function evaluations are finite
divided differences xi xk f [ xn , xn 1 , , x1 , x0 ] f [ xn , xn 1 , , x1 ] f [ xn 1 , xn 2 , , x0 ] xn x0 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 7 Errors of Newtons Interpolating Polynomials/
Structure of interpolating polynomials is similar to the Taylor series expansion in the sense that finite divided differences are added sequentially to capture the higher order derivatives. For an nth-order interpolating polynomial, an analogous relationship for the error is: f ( n 1) ( ) Rn ( x x0 )( x x1 ) ( x xn ) (n 1)! Is somewhere containing the unknown and he data
For non differentiable functions, if an additional point f(xn+1) is available, an alternative formula can be used that does not require prior knowledge of the function: Rn f [ xn 1 , xn , xn 1 , , x0 ]( x x0 )( x x1 ) ( x xn ) 8 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Lagrange Interpolating Polynomials The Lagrange interpolating polynomial is simply a reformulation of the Newtons polynomial that avoids the computation of divided differences: n f n ( x) Li ( x) f ( xi )
i 0 n Li ( x) j 0 j i x xj xi x j 9 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. x x0 x x1
f1 ( x ) f ( x0 ) f ( x1 ) x0 x1 x1 x0 x x0 x x2 x x1 x x2 f 2 ( x) f ( x0 ) x0 x1 x0 x 2 x1 x0 x1 x 2
x x0 x x1 f ( x2 ) x2 x0 x2 x1 f ( x1 ) As with Newtons method, the Lagrange version has an estimated error of: n Rn f [ x, xn , xn 1 , , x0 ]( x xi ) i 0 10
Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Figure 18.10 11 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Coefficients of an Interpolating Polynomial Although both the Newton and Lagrange polynomials are well suited for determining intermediate values between points, they do not provide a polynomial in conventional form: 2
f ( x) a0 a1 x a2 x a x x n Since n+1 data points are required to determine n+1 coefficients, simultaneous linear systems of equations can be used to calculate as. 12 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 2 2 0 n n 0
f ( x0 ) a0 a1 x0 a x a x 2 2 1 n n 1 f ( x1 ) a0 a1 x1 a x a x 2 2 n n n n
f ( xn ) a0 a1 xn a x a x Where xs are the knowns and as are the unknowns. 13 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Figure 18.13 14 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Spline Interpolation There are cases where polynomials can lead to
erroneous results because of round off error and overshoot. Alternative approach is to apply lower-order polynomials to subsets of data points. Such connecting polynomials are called spline functions. 15 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Figure 18.14 16 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Figure 18.15
17 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Figure 18.16 18 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Figure 18.17 19 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
