Engineering Analysis ENG 3420 Fall 2009Lecture 23Newton interpolating polynomial of degree n-1Divided differencesLagrange interpolating polynomialsFirst-order Lagrange interpolating polynomialLagrange interpolating polynomial for n pointsInverse interpolationExtrapolationExtrapolation HazardsOscillationsSplines –picewise interpolationSplines (cont’d)1Engineering Analysis ENG 3420 Fall 2009Dan C. MarinescuOffice: HEC 439 BOffice hours: Tu-Th 11:00-12:00222Lecture 23Lecture 23 Attention: The last homework HW5 and the last project are due onTuesday 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)3Newton interpolating polynomial of degree n-1 In general, an (n-1)thNewton interpolating polynomial has all the terms of the (n-2)thpolynomial plus one extra. The general formula is: where  and the f[…] represent divided differences. fn−1x()= b1+ b2x−x1()+L+bnx−x1()x − x2()L x−xn−1() b1=fx1()b2= fx2, x1[]b3= fx3, x2, x1[]Mbn= fxn, xn−1,L, x2, x1[]4Divided differences Divided difference are calculated as follows: Divided differences are calculated using divided difference of asmaller number of terms: fxi, xj[]=fxi()− fxj()xi− xjfxi, xj, xk[]=fxi, xj[]− fxj, xk[]xi− xkfxn, xn−1,L, x2, x1[]=fxn, xn−1,L, x2[]− fxn−1, xn−2,L, x1[]xn− x156Lagrange 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:where the Liare weighting coefficients that are functions of x.OrderSimple Lagrange1st f1(x) = a1+ a2xf1(x) = L1fx1()+ L2fx2()2nd f2(x) = a1+ a2x + a3x2f2(x) = L1fx1()+ L2fx2()+ L3fx3()7First-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 x1and x2and the values of the dependent function at those points is:f1(x) = L1fx1()+ L2fx2()L1=x − x2x1− x2, L2=x − x1x2− x1f1(x) =x − x2x1− x2fx1()+x − x1x2− x1fx2()8Lagrange interpolating polynomial for n points In general, the Lagrange polynomial interpolation for n points is: where Liis given by:fn−1xi()= Lix()fxi()i=1n∑Lix()=x−xjxi− xjj=1j≠in∏910Inverse 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.11Extrapolation Extrapolation Î estimating a value of f(x) that lies outside the range of the known base pointsx1, x2, …, xn. Extreme care should be exercised when extrapolating!12Extrapolation Hazards The following shows the results of extrapolating a seventh-order population data set:13Oscillations Higher-order polynomials can not only lead to round-off errors due to ill-conditioning, 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:14Splines –picewise interpolation SplinesÆ an alternative approach to using a single (n-1)thorder 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 dataas is the case in this figure at the right where we use:a) 3rdorder polynomialb) 5thorder polynomialc) 7thorder polynomiald) Linear spline seven 1st order polynomials generated by using pairs of points at a time15Splines (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) First-order splines Æ find straight-line equations between each pair of points that• Go through the pointsb) Second-order splines Æfind quadratic equations between each pair of points that• Go through the points• Match first derivatives at the interior pointsc) Third-order splinesÆ find cubic equations between each pair of points that• Go through the points• Match first and second derivatives at the interior pointsNote that the results of cubic splineinterpolation are different from the results of an interpolating