It sounds like Zipster wants a function that does interpolate the points. Not sure what he means specifically by saying the function must be "differential." Perhaps he means "differentiable?" Polynomials are that. So are splines.

Timkin''s reply is the most useful starting point here. Cubic splines are piecewise polynomials that can interpolate the points. Keep in mind that if your points are arbitrary, forming a curve that wraps around itself, you''ll need to create a parametric representation, where:

x = fx(u)
y = fy(u)

Here, u is the parameter that varies from, say, 0 to 1. fx(u) and fy(u) are interpolating cubic spline functions that, for some values of u, result in the exact points you started with. These functions are piecewise polynomials in the parameter u. In the example given by Zipster, then

x = fx(u = 0) = 3
y = fy(u = 0) = 4 ----> point (3,4)

And,

x = fx(u = 1) = 123
y = fy(u = 1) = 987 ----> point (123,987)

I don''t doubt that there is no closed form function that interpolates all prime numbers. But that is irrelevant since Zipster doesn''t need to interpolate a infinite number of points. With splines, he''ll be creating a piecewise function such that each piece interpolates at most a few points. It''ll work even if the values of those points are prime numbers.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

I forgot to describe the other meaning of "interpolation." Timkin''s correct in saying that it means "determine function values at given points within the domain of the data," but the root word "interpolate" and "interpolating" have a different meaning in the mathematics of splines or fitting functions to a set of points.

In splines and function fitting, a function is said to "interpolate" a set of points if the curve defined by the function passes exactly through each of the points. Splines that interpolate a set of points are called "interpolating splines". Notice that this does occur within the domain of the data.

A function that does not interpolate a set of points, but only approximates the points, tends to be smoother than an interpolating function. Such noninterpolating functions or splines are sometimes called "smoothing splines." Since smoothing splines are generally lower order than interpolating splines, the process of calculating the smoothing spline is called "fitting a curve" since you''re really taking a function that isn''t capable of interpolating, and finding coefficients that make it "fit" as best it can. Linear regression is an example of "fitting" since it generates a line that can''t possibly interpolate an arbitrary set of scattered points (unless the points happen to lie exactly on a perfect line).

Notice that smoothing splines also can be evaluated within the domain of the data, but they do not (usually) interpolate the data.

I know I''m just nitpicking here, .

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

quote:Original post by Zipster
I was guessing it would have to be a piecewise function... any chance of being able to find a single function that interpolates all the data points? Since we can''t generate a line that interpolates non-linear sets of points, does the same thing apply to higher order equations?

For a finite number of points, you could possibly find a higher-order function that interpolates the points. BUT, when it comes to evaluating that higher-order equation on a computer that uses floating point math, you may find the function unstable. I''m reaching back to around 1996 or so here, when I took a graduate level class in numerical mathematics that studied splines an curve fitting in detail. So I can''t easily quote specific details. But as I recall, the stability of a high order polynomial fit becomes unstable rapidly as the order increases. For example, suppose you have a set of points (x,y) such that x = x[i-1] + delta_x for all i = 1 to N-1, and N is the number of points. That is, the points are uniformly distributed in x and the function is single-valued. If you try to fit a polynomial of order N, then as N becomes even moderately large (maybe as low as N = 5 in some cases), the polynomial will exhibit large, unrealistic oscillations. Just tweaking the points so that x = x + small_random_number can get rid of the oscillations, but this doesn''t make the higher-order fit robust.<br><br>You could possibly use something like a discreet fourier transform or wavelet transform, but it might not be as convenient as polynomials. </i> <br><br>Graham Rhodes<br>Senior Scientist<br>Applied Research Associates, Inc.

quote:Original post by Zipster
any chance of being able to find a single function that interpolates all the data points?

Yes, the solution I know is simple but requires inverting an NxN (or mabye it''s (N+1)x(N+1)) matrix where N is the number of data points. If you are prepared to do that (I don''t know how off hand), I''ll try to refresh my memory and get more specific. All it really is is another form of spline, you may want to look up natural splines.

This would also be a polynomial of order N (or mabye N+1), and you should be aware of what grhodes_at_work said. It will also be parametric (x(t) and y(t)) not f(x,y).


Mike