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 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 However for Hermite the derivative needs to be specified Cubic splines the derivative is not specified but enforced Cubic splines Imposing the continuity conditions Using function continuity First Derivative continuity Second derivative continuity Solving for m n 2 equations in n unknowns Need to add two conditions Usually at end points 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 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