| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
I am curious about the subject of interpolation. I want to know if the
methods intended for visual appeal are good for numerical accuracy.
Let me explain the situation:
The classic text book approach of using the Langrange interpolating
polynomial does not work well with large numbers of sample points as
pointed out by Carl deBoor in his book on B-Splines. Carl explains
that you begin to loose accuracy when the order of your interpolating
polynomial gets too large. Additionally I'm not sure how to extend the
technique into n-dimenions.
So Carl convinces me that BSplines are the way to go and then spends
most of his book trying to explain how to get the proper control points
for good interpolation. When I grow up I am going to understand these
algorithms. In the mean time, I need something simpler.
Well the graphics/CAD people have been busy with a closely related
subject of using Bezier and BSplines for drawing surfaces. The
classical approach seems to be having the user provide the control
points and the 2nd derivatives at the boundary conditions. This is
really a drag since I have absolutely no idea what the second partial
derivatives should be for some surface I want to draw or interpolate.
Moreover, these algorithms do not interpolate the control points, they
just go near them.
Recently (this decade) there have been some improvements. A paper by
Charly Rupp (Parametric Interpolation of Curves for Visual
Presentation) explains the ReGIS algorithm for drawing a Smooth curve
thru some points.
Donald Knuth uses a more sophisticated algorithm in his METAFONT
program that can accept tension parameters for drawing a smooth curve
thru user specified points. The source for METAFONT is available from
a number of sources - including the the ENET and your local book store.
The source program provides references to journal articles.
Barskey and Greenberg ("Determing a Set of B-spline Control Vertices to
Generate an Interpolating Surface") provide an algorithm for
interpolating surfaces with BSplines.
Now let me restate my question in more detail: Assuming that I am
not interested in least-squares best fit algorithms and that I want
functions that interpolate (not just go near) 2D, 3D functions, are
these graphics techniques any good? Is there any relationship between
what looks good and what is good numerically?
One specific application I have in mind is the display of empircal
data: I want the option of drawing a graph such that the line to
passes thru the data points. (This is because the purpose of the
interpolating line is largly cosmetic. Perhaps I'll also provide the
user with a least squares best fit option also). I think these
graphical algorithms would be good for this purpose.
But I am curious about using these graphics algorithms for numerical
interpolation as Carl deBoor discusses in his book. I can locate no
references on the suject of 3d numeric interpolation for randomly
placed sample points - only ones like Barsky's for the purpose of
visual appeal. Several text books I've looked at avoid the topic
entirely (including Numerical Recipies).
Sieg
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 1141.1 | may need more info | ALLVAX::ROTH | If you plant ice you'll harvest wind | Fri Oct 20 1989 07:50 | 40 |
If you need to actually interpolate, rather than merely approximate
you are constrained in how you represent your blending functions.
The problem with Lagrangian interpolation is that polynomials are
not extremely 'flexible', so force-fitting a high order polynomial
to an unfortunate set of data points will of necessity introduce
ripples.
If you can tolerate non-interpolatory functions then there is
a wider choice of options, the Bspline basis is an example.
Bsplines have advantages such as a convex hull property, variation
diminishing, recursive subdivision, easy knot insertion, and so on.
For finite element modeling, interpolation is necessary becase the
basis and shape functions are defined by values at discrete nodes
so Lagrangian interpolation is used.
Note that polynomials form a linear space, and the reason an
algorithm like Barsky's works is that he is effectively representing
a Lagrangian interpolant in the Bspline basis rather than the
perhas more natural (from a data standpoint) Lagrangian basis. His trick
is to organize the computations to be efficient.
There are also transfinite interpolants such as Coons patches, which
blend not a set of points but a set of boundary curves (or surfaces
spatial field modeling.)
A useful book which you may already have is "Curve and Surface Fitting",
by P. Lancaster and K. Salkauskas, Academic. It may provide some
insights to your problems.
It's hard to be more specific without knowing what kind of data you
are dealing with, and whether it is really necessary to interpolate
rather than merely approximate. If the need is to display results
visually, then I don't think interpolation is the answer.
Also, there is a literature on interpolants which have higher order
continuity, but this may not be imporant for your work if you have
no derivatives.
- Jim
| |||||