Interpolation Chapter 18 - Universiti Teknologi Malaysia

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.

Recently Viewed Presentations

• Want to find out more? Visit our website macmillan.org.uk Macmillan Support Line 0808 808 00 00 Monday-Friday, 9am-8pm * This presentation is designed to be used in assemblies or classrooms to help young people understand a bit more about Macmillan...
• GAME THEORY Game Theory and Economics Game theory is the study of how people behave in strategic situations. Strategic decisions are those in which each person, in deciding what actions to take, must consider how others might respond to that...
• The studio at the Holzstrasse 11/11a is located in a quiet neighbourhood called Rotmonten. It is close to the Executive Campus HSG. The University of St.Gallen can be reached by foot in five minutes. A 10- minute bus ride brings...
• Please follow the directions to establish your MIAP account. It is strongly recommended that all users register their CAC to their STARS User id. Please see section 2.4/page 4 of the STARS MIAP Supplemental Guide. New STARS User Login Procedures...
• Investments "101"8-4 Investment Styles. Comparison of Active versus Passive Investment Styles. Active Style. Passive Style; Beat. the market by buying low and selling high "Make" the market by buying and holding. Selection and timing of.
• Magnetospheric solitary structure maintained by 3000 km/s ions as a cause of westward moving auroral bulge at 19 MLT M. Yamauchi1, I. Dandouras2, P.W. Daly3, H. Frey4, G. Stenberg5, P.-
• In the text box toward the bottom of the page called 'Private Metadata Fields ' enter all these fields: Note , Scope, Robots honored, Max crawl seconds, Capture frequency, Seed type, Site ID . NB: Enter each field name on...
• Studio multicentrico open label di fase I/II. Il disegno della . fase I. è il classico 3+3 con coorti di dose-escalation. La fase II è una valutazione a bracci paralleli 1:1, open label, per valutare l'efficacia di Nab-FOLFIRI e/o Nab-FOLFOX...