Engineering Analysis ENG 3420 Fall 2009 Dan C Marinescu Office HEC 439 B Office hours Tu Th 11 00 12 00 1 Lecture 23 Attention The last homework HW5 and the last project are due on Tuesday November 24 Last time Linear regression versus sample mean Coefficient of determination Polynomial least squares fit Multiple linear regression General linear squares More on non linear models Interpolation Chapter 15 Today Lagrange interpolating polynomials Splines Cubic splines Searching and sorting Next Time More on Splines Numerical integration chapter 17 Lecture 23 2 Newton interpolating polynomial of degree n 1 In general an n 1 th Newton interpolating polynomial has all the terms of the n 2 th polynomial plus one extra The general formula is fn 1 x b1 b2 x x1 L bn x x1 x x2 L x xn 1 where b1 f x1 b2 f x2 x1 b3 f x3 x2 x1 M bn f xn xn 1 L x2 x1 and the f represent divided differences 3 Divided differences Divided difference are calculated as follows 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 xi x k f xn xn 1 L x2 x1 f xn xn 1 L x2 f xn 1 xn 2 L x1 xn x1 Divided differences are calculated using divided difference of a smaller number of terms 4 5 Lagrange interpolating polynomials Another method that uses shifted value to express an interpolating polynomial is the Lagrange interpolating polynomial The differences between a simply polynomial and Lagrange interpolating polynomials for first and second order polynomials is Order 1st 2nd Simple f1 x a1 a2 x f2 x a1 a2 x a3 x 2 Lagrange f1 x L1 f x1 L2 f x2 f2 x L1 f x1 L2 f x2 L3 f x 3 where the Li are weighting coefficients that are functions of x 6 First order Lagrange interpolating polynomial The first order Lagrange interpolating polynomial may be obtained from a weighted combination of two linear interpolations as shown The resulting formula based on known points x1 and x2 and the values of the dependent function at those points is f1 x L1 f x1 L2 f x2 x x2 x x1 L1 L2 x1 x2 x2 x1 x x2 x x1 f1 x f x1 f x2 x1 x2 x2 x1 7 Lagrange interpolating polynomial for n points In general the Lagrange polynomial interpolation for n points is n fn 1 xi Li x f xi i 1 where Li is given by x xj Li x x xj j 1 i n j i 8 9 Inverse interpolation Interpolation find the value f x for some x between given independent data points Inverse interpolation find the argument x for which f x has a certain value Rather than finding an interpolation of x as a function of f x it may be useful to find an equation for f x as a function of x using interpolation and then solve the corresponding roots problem f x fdesired 0 for x 10 Extrapolation Extrapolation estimating a value of f x that lies outside the range of the known base points x1 x2 xn Extreme care should be exercised when extrapolating 11 Extrapolation Hazards The following shows the results of extrapolating a seventh order population data set 12 Oscillations Higher order polynomials can not only lead to round off errors due to illconditioning but can also introduce oscillations to an interpolation or fit where they should not be The dashed line represents a function the circles represent samples of the function and the solid line represents the results of a polynomial interpolation 13 Splines picewise interpolation Splines an alternative approach to using a single n 1 th order polynomial to interpolate between n points Apply lower order polynomials in a piecewise fashion to subsets of data points The connecting polynomials are called spline functions Splines eliminate oscillations by using small subsets of points for each interval rather than every point Especially useful when there are jumps in the data as is the case in this figure at the right where we use 3rd order polynomial b 5th order polynomial c 7th order polynomial d Linear spline seven 1st order polynomials generated by using pairs of points at a time a 14 Splines cont d Spline function si x coefficients are calculated for each interval of a data set The number of data points fi used for each spline function depends on the order of the spline function The conditions a b c First order splines find straight line equations between each pair of points that Go through the points Second order splines find quadratic equations between each pair of points that Go through the points Match first derivatives at the interior points Third order splines find cubic equations between each pair of points that Go through the points Match first and second derivatives at the interior points Note that the results of cubic spline interpolation are different from the results of an interpolating cubic 15