FAQ
overflow

Great Answers to
Questions About Everything

QUESTION

I'm looking for some explanation or advice, not help in solving something. Recently I finished my program and my supervisor said "Ok, now it's time for your first paper: write a scientific text about how your program works". If I understand him correctly it means I have to describe the algorithm I used instead of writing in a manner like "for this purpose I use the built-in Interpolation function, and for this purpose I use NDSolve" etc. I know how FindRoot and NDSolve work because there is an explanation in the doc pages about the methods they use, but I did not find detailed information about Interpolation. The only thing I know it fits with polynomial curves.

So my question is: What exactly does the Interpolation function do? How does it work? How does it determinate (partial) derivatives? And why do 3D data points have to be situated in rectangle order to interpolate a surface?

If there is some literature I may read and then reference it would be great too.

{ asked by ddd }

ANSWER

Interpolation function methods

Interpolation supports two methods:

Hermite method

I really can't find any good reference to Hermite method within Mathematica's documentation. Instead, I recommend you to take a look at this Wikipedia article.

The benefits of Hermite interpolation are:

  1. You can compute them locally at the time of evaluation. No global system solving required. So construction time is shorter, and the resulting InterpolatingFunction is smaller.
  2. Multi-level derivatives can be specified at each point.

One problem is that the resulting function is not continuously differentiable ($C^1$ or higher), even if InterpolationOrder->2 or higher is used. See the following example:

enter image description here

Spline method

To be specific, we are using B-spline interpolation with certain knot configuration--depending on the distribution of sample points. I could not find a good web source to describe the method (the Wikipedia article is not great). Although, you can find a step-by-step description of the method in 1D case within Mathematica's documentation (BSplineCurve documentation, Applications -> Interpolation section). Multi-dimension is simply tensor product version.

The benefits:

  1. InterpolationOrder->d always guarantees a smooth function of $C^{d-1}$ class.

    enter image description here

  2. Evaluation/derivative computation is very fast.

  3. You can take BSplineFunction out of the resulting InterpolatingFunction (it's the 4th part), which is compatible with BSplineCurve and BSplineSurface for fast rendering.

The problems (of current implementation in V8):

  1. It is machine precision only--although, it is not hard to implement it manually for arbitrary precision using BSplineBasis.
  2. It does not support derivative specification.
  3. Initially it solves global linear system and store the result. So the resulting function is much larger than Hermite method (this is not implementation problem).
Other functions

Some plot functions such as ListPlot3D have their own methods. Sometimes they call the B-spline method, sometimes they use a method based on distance field (for unorganized points), etc. But probably it is not useful here since they are only supported as a visual measure.

{ answered by Yu-Sung Chang }
Tweet