2 19 2012 Computational Methods CMSC AMSC MAPL 460 Polynomial Interpolation Ramani Duraiswami Dept of Computer Science Examples of polynomial interpolation Go to MATLAB demo Vandermonde Polynomial interpolation for small set For larger set See that even for six points we have a problem In between the data points especially in first and last subintervals function shows excessive variation overshoots changes in the data values As a result full degree polynomial interpolation is hardly ever used for data and curve fitting However we saw polynomial interpolation works well when degree is low 1 2 19 2012 Piecewise linear interpolation Simple idea Connect straight lines between data points Any intermediate value read off from straight line The local variable s is s x xk The first divided difference is k yk 1 yk xk 1 xk With these quantities in hand the interpolant is L x yk x xk yk 1 yk xk 1 xk yk s k Linear function that passes through xk yk and xk 1 yk 1 Piecewise linear interpolation Same format as all other interpolants Function diff finds difference of elements in a vector Find appropriate sub interval Evaluate Jargon x is called a knot for the linear spline interpolant function v piecelin x y u PIECELIN Piecewise linear interpolation v piecelin x y u finds piecewise linear L x with L x j y j and returns v k L u k First divided difference delta diff y diff x Find subinterval indices k so that x k u x k 1 n length x k ones size u for j 2 n 1 k x j u j end Evaluate interpolant s u x k v y k s delta k 2 2 19 2012 So we can reduce error by choosing small intervals where 2nd derivative is higher If we can choose where to sample data Do more where the action is more Piecewise Cubic interpolation While we expect function not to vary we expect it to also be smooth So we could consider piecewise interpolants of higher degree How many pieces of information do we need to fit a cubic between two points y a bx cx2 dx3 4 coefficients Need 4 pieces of information 2 values at end points Need 2 more pieces of information Derivatives 3 2 19 2012 However for Hermite the derivative needs to be specified Cubic splines the derivative is not specified but enforced Cubic splines 4 2 19 2012 Imposing the continuity conditions Using function continuity 5 2 19 2012 First Derivative continuity Second derivative continuity 6 2 19 2012 Solving for m n 2 equations in n unknowns Need to add two conditions Usually at end points 7 2 19 2012 Solving a cubic spline system Assume natural splines This is a tridiagonal system Can be solved in O n operations How Do LU and solve With tridiagonal structure requires O 7n operations Efficient polynomial evaluation Given a polynomial in power form how many operations does it take to evaluate it ap xp a1 x a0 Horner s Rule Horner s rule Horner 1819 recursively evaluates the polynomial ap xp a1 x a0 as ap x ap 1 x x a0 costs p multiplications and p additions no extra storage Reduces complexity from O p2 to O p 8 2 19 2012 Interpolation wrap up Interpolation Given a function at N points find its value at other point s Polynomial interpolation Monomial Newton and Lagrange forms Piecewise polynomial interpolation Linear Hermite cubic and Cubic Splines Polynomial interpolation is good at low orders However higher order polynomials overfit the data and do not predict the curve well in between interpolation points Cubic Splines are quite good in smoothly interpolating data 9