Hermite Interpolation: Week 10: Monday, Apr 2

Bindel, Spring 2012 Intro to Scientic Computing (CS 3220)
Week 10: Monday, Apr 2

Hermite interpolation
For standard polynomial interpolation problems, we seek to satisfy conditions
of the form
p(x
j
) = y
j
,
where y
j
is frequently a sampled function value f(x
j
). If all we know is
function values, this is a reasonable approach. But sometimes we have more
information. Hermite interpolation constructs an interpolant based not only
on equations for the function values, but also for the derivatives.
For example, consider the important special case of nding a cubic poly-
nomial that satises proscribed conditions on the values and derivatives at
the endpoints of the interval [1, 1]. That is, we require
p(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 satises these conditions with respect to several dierent
bases: monomial, Lagrange, or Newton.
For the monomial basis, we have
p(x) = c
0
+ c
1
x + c
2
x
2
+ c
3
x
3
,
which yields the linear system
_
_
1 1 1 1
1 1 1 1
0 1 2 3
0 1 2 3
_
_
_
_
c
0
c
1
c
2
c
3
_
_
=
_
_
f(1)
f(1)
f
(1)
f
(1)
_
_
.
For the Newton basis, we have expressions like
p(x) = f[1]+f[1, 1](x+1)+f[1, 1, 1](x+1)
2
+f[1, 1, 1, 1](x+1)
2
(x1),
where the divided dierences for f are
f[1] = f(1)
f[1] = f(1)
f[1, 1] = f
(1)
f[1, 1] = f
(1)
f[1, 1] = (f(1) f(1)) /2
f[1, 1, 1] = (f[1, 1] f[1, 1]) /2
f[1, 1, 1] = (f[1, 1] f[1, 1]) /2
f[1, 1, 1, 1] = (f[1, 1, 1] f[1, 1, 1]) /2.
We leave the Lagrange basis as a problem to ponder (or look up).
Piecewise polynomial approximations
Polynomials are convenient for interpolation for a few reasons: we know
how to manipulate them symbolically, we can evaluate them quickly, and
there is a theorem of analysis (the Weierstrass approximation theorem) that
says that any continuous function on some interval [a, b] can be uniformly
approximated by polynomials. In practice, though, high-degree polynomial
interpolation does not always provide fantastic function approximation. An
alternative approach that retains the advantages of working with polynomials
is to work with piecewise polynomial functions.
Piecewise linear interpolation
Perhaps the simplest example is piecewise linear interpolation; if function
values f(x
j
) are given at points x
1
< x
2
< x
3
< . . . < x
n
, then we write the
approximating function

f(x) as
f(x) =
f(x
j
)(x x
j
) + f(x
j+1
)(x
j+1
x)
x
j+1
x
j
, x [x
j
, x
j+1
].
Alternately, we can write
f(x) =
n
j=1
j
(x)f(x
j
)
where
j
(x) is a hat function:
j
(x) =
_
_
(x x
j+1
)/(x
j
x
j+1
), x [x
j
, x
j+1
],
(x x
j1
)/(x
j
x
j1
), x [x
j1
, x
j
],
0 otherwise.
This last you may recognize as similar in spirit to using a basis of Lagrange
polynomials for polynomial interpolation.
Using piecewise linear interpolation to approximate a function f yields
O(h
2
) error (where h is the distance between interpolation points), assum-
ing f has two continuous derivatives. This level of accuracy is adequate for
many purposes. Beyond the basic error behavior, though, piecewise linear
interpolation has several virtues when structural properties are important.
For example, the maximum and minimum values of a piecewise linear inter-
polant are equal to the maximum and minimum values of the data. And if
f is positive or monotone (like a probability density or cumulative density
function), then any piecewise linear interpolant inherits these properties.
Piecewise cubic interpolation
If f is reasonably smooth and the data points are widely spaced, it may make
sense to use higher-order polynomials. For example, we might decide to use
a cubic spline

f(x) characterized by the properties:
Interpolation:

f(x
i
) = f(x
i
)
Twice dierentiability:

f
and

f
are continuous at {x
2
, . . . , x
n1
}
The interpolation and dierentiability constraints give us 4n 2 constraints
on the 4n-dimensional space of piecewise polynomial functions that are de-
ned by general cubics on each interval [x
j
, x
j+1
]. In order to uniquely de-
termine the spline, we need some additional constraint; common choices are
Specied values of f
at x
1
and x
n
(clamped conditions)
A natural spline: f
(x
1
) = f
(x
n
) = 0
Not-a-knot conditions: f
is continuous at x
2
and x
n1
Periodicity: f
(x
1
) = f
(x
n
), f
(x
1
) = f
(x
n
)
For the clamped conditions and not-a-knot conditions, one has the error
bound
p f
cf
h
4
where
is the L
norm (max norm) on some interval of interest and h

is the maximum space between interpolation nodes.
In addition to spline conditions, one can choose piecewise cubic polyno-
mials that satisfy Hermite interpolation conditions (sometimes referred to by
the acronym PCHIP or Piecewise Cubic Hermite Interpolating Polynomials).
That is, the function values and derivatives are specied at each nodal point.
If we dont actually have derivative values prescribed at the nodal points,
then we can assign these values to satisfy additional constraints. We gain
this exibility at the cost of some dierentiability; piecewise cubic Hermite
interpolants are in general not twice continuously dierentiable.
As in the case of polynomial interpolation, there are several dierent bases
for the space of piecewise cubic functions. Any choice of locally supported
basis functions (basis functions that are only nonzero on only a xed number
of intervals [x
j
, x
j+1
]) leads to a banded linear system which can be solved
in O(n) time to nd either cubic splines or piecewise Hermite cubic inter-
polants. One common choice of basis is the B-spline basis, which you can
nd described in the book.

Hermite Interpolation: Week 10: Monday, Apr 2

Uploaded by

Copyright:

Available Formats

Hermite Interpolation: Week 10: Monday, Apr 2

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Hermite Interpolation: Week 10: Monday, Apr 2

Uploaded by

Copyright:

Available Formats

Bindel, Spring 2012 Intro to Scientic Computing (CS 3220)

Week 10: Monday, Apr 2

norm (max norm) on some interval of interest and h

You might also like