Hermite interpolation - Cornell University

1 Bindel, Spring 2012 Intro to Scientific Computing (CS 3220)Week 10: Monday, Apr 2 Hermite interpolationFor standard polynomial interpolation problems, we seek to satisfy conditionsof the formp(xj) =yj,whereyjis frequently a sampled function valuef(xj). If all we know isfunction values, this is a reasonable approach. But sometimes we have constructs an interpolant based not onlyon equations for the function values, but also for the example, consider the important special case of finding a cubic poly-nomial that satisfies proscribed conditions on the values and derivatives atthe endpoints of the interval [ 1,1]. That is, we requirep(1) =f(1)p( 1) =f( 1)p (1) =f (1)p ( 1) =f ( 1).As with polynomial interpolation based just on function values, we can ex-press the cubic that satisfies these conditions with respect to several differentbases: monomial, Lagrange, or the monomial basis, we havep(x) =c0+c1x+c2x2+c3x3,which yields the linear system 11111 11 1012301 23 c0c1c2c3 = f(1)f( 1)f (1)f ( 1).

2 For the Newton basis, we have expressions likep(x) =f[ 1]+f[ 1, 1](x+1)+f[1, 1, 1](x+1)2+f[1,1, 1, 1](x+1)2(x 1),Bindel, Spring 2012 Intro to Scientific Computing (CS 3220)where the divided differences forfaref[1] =f(1)f[ 1] =f( 1)f[1,1] =f (1)f[ 1, 1] =f ( 1)f[1, 1] = (f(1) f( 1))/2f[1, 1, 1] = (f[1, 1] f[ 1, 1])/2f[1,1, 1] = (f[1,1] f[1, 1])/2f[1,1, 1, 1] = (f[1,1, 1] f[1, 1, 1]) leave the Lagrange basis as a problem to ponder (or look up).Piecewise polynomial approximationsPolynomials are convenient for interpolation for a few reasons: we knowhow to manipulate them symbolically, we can evaluate them quickly, andthere is a theorem of analysis (the Weierstrass approximation theorem) thatsays that any continuous function on some interval [a,b] can be uniformlyapproximated by polynomials . In practice, though, high-degree polynomialinterpolation does not always provide fantastic function approximation. Analternative approach that retains the advantages of working with polynomialsis to work withpiecewisepolynomial linear interpolationPerhaps the simplest example is piecewise linear interpolation ; if functionvaluesf(xj) are given at pointsx1< x2< x3<.

3 < xn, then we write theapproximating function f(x) as f(x) =f(xj)(x xj) +f(xj+1)(xj+1 x)xj+1 xj, x [xj,xj+1].Alternately, we can write f(x) =n j=1 j(x)f(xj)Bindel, Spring 2012 Intro to Scientific Computing (CS 3220)where j(x) is a hat function : j(x) = (x xj+1)/(xj xj+1), x [xj,xj+1],(x xj 1)/(xj xj 1), x [xj 1,xj], last you may recognize as similar in spirit to using a basis of Lagrangepolynomials for polynomial piecewise linear interpolation to approximate a functionfyieldsO(h2) error (wherehis the distance between interpolation points), assum-ingfhas two continuous derivatives. This level of accuracy is adequate formany purposes. Beyond the basic error behavior, though, piecewise linearinterpolation has several virtues whenstructuralproperties are example, the maximum and minimum values of a piecewise linear inter-polant are equal to the maximum and minimum values of the data. And iffis positive or monotone (like a probability density or cumulative densityfunction), then any piecewise linear interpolant inherits these cubic interpolationIffis reasonably smooth and the data points are widely spaced, it may makesense to use higher-order polynomials .

4 For example, we might decide to useacubic spline f(x) characterized by the properties: interpolation : f(xi) =f(xi) Twice differentiability: f and f are continuous at{x2,..,xn 1}The interpolation and differentiability constraints give us 4n 2 constraintson the 4n-dimensional space of piecewise polynomial functions that are de-fined by general cubics on each interval [xj,xj+1]. In order to uniquely de-termine the spline, we need some additional constraint; common choices are Specified values off atx1andxn(clamped conditions) A natural spline:f (x1) =f (xn) = 0 Not-a-knot conditions:f is continuous atx2andxn 1 Periodicity:f (x1) =f (xn),f (x1) =f (xn)Bindel, Spring 2012 Intro to Scientific Computing (CS 3220)For the clamped conditions and not-a-knot conditions, one has the errorbound p f c f h4where is theL norm (max norm) on some interval of interest andhis the maximum space between interpolation addition to spline conditions, one can choose piecewise cubic polyno-mials that satisfy Hermite interpolation conditions (sometimes referred to bythe acronym PCHIP or Piecewise Cubic Hermite Interpolating polynomials ).

5 That is, the function values and derivatives are specified at each nodal we don t actually have derivative values prescribed at the nodal points,then we can assign these values to satisfy additional constraints. We gainthis flexibility at the cost of some differentiability; piecewise cubic Hermiteinterpolants are in general not twice continuously in the case of polynomial interpolation , there are several different basesfor the space of piecewise cubic functions. Any choice of locally supportedbasis functions (basis functions that are only nonzero on only a fixed numberof intervals [xj,xj+1]) leads to a banded linear system which can be solvedinO(n) time to find either cubic splines or piecewise Hermite cubic inter-polants. One common choice of basis is the B-spline basis, which you canfind described in the book.