Archived

This topic is now archived and is closed to further replies.

Zipster

Points to Function

Recommended Posts

Zipster    2365
I've been thinking, if we had several points, would it be possible to find a function that is true at all those points? For example, if I hade (3,4), (12,-9), (89, 0), (0,111), and (123,987), how would I go about finding the function that works at all those points? It would be nice if it was polynomial, but has to be differential for the uses I'm thinking of. Is it even possible? It seems so, but also appears it would require intense math. Edited by - Zipster on November 5, 2001 1:09:21 AM

Share this post


Link to post
Share on other sites
Timkin    864
The approach you take depends on whether you wish to do interpolation (i.e., determine function values at given points within the domain of the data) or extrapolation (determine function values for values of the independent variable(s) outside the domain of the data).

If you wish to perform interpolation, use the ''Cubic Splines'' technique, which fits a set of polynomials of degree three to the data. If however you wish to perform extrapolation, then use a regression technique. Be warned though: multivariate regression on non-linear data is by no means a trivial excercise.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
nickm    122
Well, I don''t think this is posssible. For example, consider the prime numbers (numbers that can only be divided by themselves or by one): 1, 2, 5, 7, 11, etc. No one has ever found a function (and not even an algorithm) that can describe (solve) the list of prime numbers.

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
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.

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
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.

Share this post


Link to post
Share on other sites
Zipster    2365
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?

P.S I did mean "diferentiable" I sometimes use "diferential" because it''s short and for some reason I like using the ''tial'' postfix

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
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[i] = x[i] + small_random_number can get rid of the oscillations, but this doesn''t make the higher-order fit robust.

You could possibly use something like a discreet fourier transform or wavelet transform, but it might not be as convenient as polynomials.


Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
Vetinari    133
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

Share this post


Link to post
Share on other sites