PDA

View Full Version : Cubic splines: summary of responses



Neil Glossop
07-28-1995, 01:33 AM
Hi Biomech-lers,
Here is the summary of the resonses to my follow up on cubic splines.
Many thanks to all who responded.
Neil
--
N. Glossop, Ph.D.,
Toronto, Canada

neil@isgtec.com
------------------------------------------------------------------


My original posting:

Jesus Dapena wrote in a recent summary about splines,

> I would advise you very strongly to stay away from CUBIC splines.
> Usually (always?) they force the second derivative to be zero at the
> beginning and end of the data set. When that is not the case in the
> activity being analyzed (i.e., almost always), the result is very distorted
> data in the early and late parts of the trial (and even the middle parts can
> get messed up too).

I am not sure how much I agree with this statement, and would ask for a
little feedback from list members. While it is true that cubic splines
force the second derivitives to be zero, cubics and piecewise cubics are
often used to interpolate data. Where I would think that this causes a
particular problem is in taking the *derivitives* in order to calculate
velocity and acceleration.

As you rightly point out,

> The differences between cubic and quintic spline was shown very
> clearly in Kit Vaughan's Ph.D. dissertation (University of Iowa, ca. 1981)
> when he fit cubic and quintic splines to the vertical location data of a
> free-falling ball. The quintic gave a beautiful fit, with acceleration very
> near 9.81 m/s2 throughout the entire airborne period. The cubic forced
> acceleration to be zero at the beginning and end of the data set, the curve
> then overshot the 9.81 m/s2 value in the middle part of the trial; the whole
> curve was distorted, so that acceleration was not near 9.81 m/s2 hardly
> anywhere at all.

This is hardly unexpected when taking derivitives. If you are only
interested in *position* information, I might suggest (although I don't know
for sure), that cubics would be more than adequate. My experience with
higher order fits is that they tend to oscillate excessively. The oscillation
tends to badly interpolate the original data. This may however, just be an
artifact of very high order fits (>10 df say), I can't say for sure since I
have not done any recently.

> I have been using splines for about twenty years now, and my
> experience tells me that quintic spline is excellent, but you don't want to
> touch cubic spline with a ten foot pole!

I guess what I am saying is that I don't think cubics are that bad if you
are sticking to interpolation of position data alone. If you want to take
derivitives, use a higher order interpolation, but watch out for artifacts
on the positional interpolation.

I'd appreciate any additional discussion on this, and will post replys sent
to me.

Cheers,
Neil
--
N. Glossop, Ph.D.,
Toronto, Canada
neil@isgtec.com
------------------------------------------------------------------

From: "Beth Todd"
Organization: College of Engineering

> Jesus Dapena wrote in a recent summary about splines,
>
> > I would advise you very strongly to stay away from CUBIC splines.
> > Usually (always?) they force the second derivative to be zero at the
> > beginning and end of the data set. When that is not the case in the
> > activity being analyzed (i.e., almost always), the result is very distorted
> > data in the early and late parts of the trial (and even the middle parts can
> > get messed up too).
>
> I am not sure how much I agree with this statement, and would ask for a
> little feedback from list members. While it is true that cubic splines
> force the second derivitives to be zero, cubics and piecewise cubics are
> often used to interpolate data. Where I would think that this causes a
> particular problem is in taking the *derivitives* in order to calculate
> velocity and acceleration.
>
When I taught a numerical methods course a couple of years ago, I
taught the students that there were five different possible schemes
for constraining the endpoints. (I'm not a mathematician, so there
may be other methods that I'm not aware of.) These conditions are

1) Clamped cubic spline where the first derivatives are specified at
the endpoints; this will give zero second derivatives.

2) Natural cubic spline; the endpoints are set to zero

3) The second derivatives are extrapolated to the endpoints.

4) The second derivatives are constant near the endpoints.

5) The second derivatives are specified at the endpoints.

Not all of the endpoint contraints give zero second derivatives, and
I was surprised when I read the message that you're commenting on.
My reference is "Numerical Methods for Mathematics, Science, and
Engineering", 2nd Ed., by John H. Mathews, Prentice Hall, 1992.

> As you rightly point out,
>
> > The differences between cubic and quintic spline was shown very
> > clearly in Kit Vaughan's Ph.D. dissertation (University of Iowa, ca. 1981)
> > when he fit cubic and quintic splines to the vertical location data of a
> > free-falling ball. The quintic gave a beautiful fit, with acceleration very
> > near 9.81 m/s2 throughout the entire airborne period. The cubic forced
> > acceleration to be zero at the beginning and end of the data set, the curve
> > then overshot the 9.81 m/s2 value in the middle part of the trial; the whole
> > curve was distorted, so that acceleration was not near 9.81 m/s2 hardly
> > anywhere at all.
>
> This is hardly unexpected when taking derivitives. If you are only
> interested in *position* information, I might suggest (although I don't know
> for sure), that cubics would be more than adequate. My experience with
> higher order fits is that they tend to oscillate excessively. The oscillation
> tends to badly interpolate the original data. This may however, just be an
> artifact of very high order fits (>10 df say), I can't say for sure since I
> have not done any recently.
>
As a rule of thumb, I told the students not to use a polynomial of
order higher than 6 due to the excessive oscillations. I'm not
exactly sure why I chose 6--must have been something that I read in
Mathews' book.

Beth Todd

Dr. Beth A. Todd
Assistant Professor
Engineering Science and Mechanics
Box 870278
University of Alabama
Tuscaloosa, AL 35487-0278
btodd@coe.eng.ua.edu
(205)348-1623
fax: (205)348-7240

------------------------------------------------------------------
From: Dale.Knochenmuss@UC.EDU (Dale Knochenmuss)

I agree that cubic splines can be fine to use as long as some thought is
given to what you are doing and what you want from the data.

For many applications, the most desirable way to fit a curve to data is to
come up with a single equation that provides a reasonable approximation to
the entire data set. When the set is long or complex, this is often not
possible or computationally difficult. Segmental approaches (or splines)
are then an alternative. They attempt to use a series of equations to fit
the complete data set. Each equation fits just a portion of the data, but
when you string them together end-to-end, you have a mathematical
approximation to the entire data set. It becomes important for each
equation to blend smoothly into the next since the physical process being
approximated does not, typically, have discontinuities..

It is generally advisable to accomplish curve fitting with an equation, or
equations, of the lowest possible order. This avoids the erratic behavior
you mentioned that can result from higher order equations. Starting with
the lowest possible order, an equation of order one has obvious limitations
since so many kinds of data are nonlinear. Splines made up of linear
equations also have the disadvantage that slopes don't match at the
boundaries between equations so there will be discontinuities in the fit.

Sets of second order (quadratic) equations can fit many types of data and
can be calculated so that the slopes of adjacent equations match at the
boundary. They cannot, however, guarantee that the curvature (second
derivative) will match, thus causing discontinuities.

Third order equations can be found which will match both slope and curvature
at each boundary, eliminating discontinuities and providing a smooth fit.
Splines made up of third order equations are therefore the lowest order
which provide smooth fits through the first and second derivatives (slope
and curvature). This is why cubic splines are often used for curve fitting.

The problem, then, lies in how the beginning and end of the data set are
handled. Jesus Dapena referred to forcing one or more of the derivatives to
be zero at one or both ends. This makes sense only if the physical process
being modelled is known to meet, or approximate, this condition at the
beginning and/or of the test. The important point, I think, is that this is
not the only option and should not be used if it is not appropriate.

Referring to "Applied Numerical Analysis" by Curtis F. Gerald and Patrick O.
Wheatley, Addison-Wesley Publishing, 4th edition, 1989, four options are
suggested for handling end points:

1) Assume the end cubics are linear (Dapena's case)
2) Assume the end cubics approach parabolas
3) Linearly extrapolate from the nearest known data points
4) Assume fixed (but non-zero) values at the ends

Gerald and Wheatley suggest option 4 as being reasonable if a derivative
estimate is available.

Referring to the example application of fitting curves to vertical location
data of a free-falling object, if an analysis of the system being tested
results in the conclusion that the acceleration is non-zero throughout the
test, then it is obviously not a good idea to apply a curve-fitting routine
which forces zero values at the beginning and end. If you know enough to
make an estimate for the end points, a third-order fit might yield
acceptable results. If the available knowledge of the system isn't
sufficient to make an estimate, then it might be better to go with the
higher order fit. I think you are correct in saying that third order
(cubic) equations are likely to be sufficient if you are only going to be
working with the positional data. This also provides a result with less
computational effort and minimizes the risk of erratic results.

Regards,

Dale
----------
Dale R. Knochenmuss
University of Cincinnati
Noyes-Giannestras Biomechanics Laboratories
Dale.Knochenmuss@UC.Edu

------------------------------------------------------------------

From: "Ton van den Bogert"

Neil,

I agree with your comments on cubic vs. quintic splines; I had
almost sent a similar reply to Jesus Dapena's posting.

In my experience, cubic splines are fine for 1st derivatives
unless you have a large amount of smoothing which makes the
boundary effects (cubic spline is straight line at the endpoints)
extend too far.

The oscillation problems with quintic splines that you mention
only occur, as far as I have seen, when there are gaps in the
data. As you say, interpolation can become very wild. For
typical, regularly spaced data, the quintic spline gives
essentially the same result as the cubic spline. Except the
quintic spline is better at the endpoints, especially the 2nd
derivative.

Still, I tend to use cubic splines whenever I don't need a 2nd
derivative. I guess that decision is based on saving computer
time.

-- Ton van den Bogert
Human Performance Laboratory
University of Calgary

------------------------------------------------------------------

From: Victor Ng-Thow-Hing

There are various formulations for basis functions of cubic splines that
do different things. Catmull-Rom and Hermite both have the ability to
interpolate points. Several spline segments are often used to fit data
points. The most popular formulations like Bezier and B-spline can have
some built in constraints for C1 and c2 continuity, but these can be
circumvented by using tricks like multiple knots for B-splines.

For higher degree splines, there is always the danger of greater instability
with the curve shape (eg., unwanted oscillations), especially when fitting
data. NURBS (non-rational uniform B-splines) also get around many problems
and can represent a wide variety of shapes, such as cusps, and perfect
circles.

In conclusion, I think cubic splines are very stable and useful.

Vic.

------------------------------------------------------------------

From: dapena@valeri.hper.indiana.edu

Neil:

It is possible that cubic spline data may be OK if you are only
interested in location data, and not interested in getting derivatives. But
getting merely ***location*** data seems to be a rather unusual final
objective. And you will have to beware if you later on get derivatives from
the cubic-spline smoothed data at any later point in the process, by
whatever method.

I have not used cubic spline for a very long time now, but my rough
recollection is that the cubic did not oscillate any less than the quintic.
(I am just writing from memory, an untrustworthy thing!) So I don't think
the cubic provides any advantage.

Jesus Dapena

------------------------------------------------------------------

From: Glen Niebur

Neil Glossop wrote:

>Jesus Dapena wrote in a recent summary about splines,

>> I would advise you very strongly to stay away from CUBIC splines.
>> Usually (always?) they force the second derivative to be zero at the
>> beginning and end of the data set. When that is not the case in the
>> activity being analyzed (i.e., almost always), the result is very distorted
>> data in the early and late parts of the trial (and even the middle parts can
>> get messed up too).

>I am not sure how much I agree with this statement, and would ask for a
>little feedback from list members. While it is true that cubic splines
>force the second derivitives to be zero, cubics and piecewise cubics are
>often used to interpolate data.


Cubic splines need not force a zero second derivative at the end points of the
curve. This is only the case for "Natural" end conditions. Other end
conditions are possible, such as clamped end conditions where we can
apply a known first derivative.

A more useful end condition is the "Quadratic" end condition which sets
the second derivative at the final point equal to the second derivative
and the next to last point at the 2nd derivative at the first point
equal to the second derivative at the second point. For "reasonably"
high sampling rates, this should be a good approximation.

Another good choice is the "not a knot" end condition. This end condition
will cause the first two segments and the last two segments to interpolate
a single cubic curve.

Finally, for cyclic events, you can specify that the second derivatives
are equal at the first and last points.

In summary, it isn't necessarily cubic splines which are bad, it is the
common "natural" end condition implementation that isn't particularly
appropriate to many problems.

A good reference for spline interpolation is:

Farin, Gerald, 1988, "Curves and Surfaces for Computer Aided Geometric
Design," Academic Press

Glen

Glen Niebur |
Mayo Clinic | This space intentionally left blank.
Biomechanics Lab |
gln@hercules.mayo.edu |