I had an idea for curve fitting, but haven''t managed to get it to work yet. I''m posting here to ask whether something like what I''m about to propose has some hidden pitfall I''m not considering, and to see if I''m just re-inventing an existing wheel. Fitting a high-order polynomial to a set of points can be a pain. But fitting a line to a set of two points (or better yet: a horizontal line to a constant)is trivial. So what happens if we repeatedly "differentiate" a set of points through finite differences until one remains, then set up the simple equation y=remaining_value and then integrate our way back up to an n-1 (for n points) degree polynomial? Any thoughts on the subject?

There are a few techinques that I am aware of to find a polynomial n-degree that passes through n points. The biggest problem is that curves above the third degree tend to have unwanted features. That''s why splines are so popular; they provide a greater degree of local control.

One interesting way to find a polynomial that passes through n points is to use the following recursive method:

Given a polynomial that passes through n-1 points, you can easily find a polynomial that passes through theses n-1 points and an additional nth point is to find a function that has y = 0 at every x_i, for i between 1 and n-1, and that passes through the nth point. Add this polynomial to the preceding polynomial, and you won''t affect the first n-1 points.

I think that it could also be done with matrices. After all, you are simply looking for n coefficients.

Cédric

Thanks for the response, Cedric.

I really like the idea of adding many polynomials - probably because it takes a line of thinking, that I didn''t manage to continue, to its completion.

I do get the feeling that this method would produce the same huge extrema between data points from which other n-point polynomial curve fitting techniques suffe. (One of the "unwanted features" you mentioned?)

That''s part of the reason why I like the thought of fitting nth derivatives and then integrating. It seems that it wouldn''t have the same problems. Of course, I''m just going by vague intuition since I haven''t actually managed to get anywhere with the idea. I have a feeling my problem is that I''m not entirely sure what to do with the x values. But maybe I can give a better explanation for other readers:

Let'' say I start with the following 7 y values and differentiate by finite differences. For simplicity, I''ll say they''re evenly spaced 1 apart horizontally, starting at x=0.

Starting   First        Second       ThirdValues     Derivative   Derivative   Derivative    (and so on...)--------   ----------   ----------   ----------      3                -4     -1                     8                 4                     -6      3                     2                     0                 6                     -6               7      9                    -4                     7          -20                 2                      1             -13      7                    -3                    -6                -1                     -5      6                    -8                -9     -3 

(Let''s hope I did the arithmatic right. Even if not, you get the point.)

Then I start with:
y = -20x + 7
And then I repeatedly integrate:
y = -10x² + 7x + 0
y = (-10/3)x³ + (7/2)x² + 0x -6
(and so on...)

Now here''s the problem. My first equation there is wrong. It''s supposed to interpolate between 7 and 13 over a certain interval; here the change takes place over an interval of one. In short, I''m not taking x values into account. But I don''t know what the x values should be! Should they be 0 and 6, or should I set the x value of each "child" halfway between the x values of its two "parents?" And if I do, how can I take that into consideration?

Those are the problems with my idea.

So, so far the best idea has been cedric''s, of recursively adding smaller polynomials (because that''s the one that works).

(As for matrices, Cedric, I have no idea.)

Now, I''d like to know what needs to be done to make my method work. Or, if it never will work, I''d like to know why.

Of course, I''m also interested in completely different techniques, like Cedric''s.

Any (more) thoughts?

The standard way to find the polynom is to create a linear equation system from the data points and solve it with gaussian elimination.

By the way, I don''t think your approach is feasible. You need the real derivatives, not your finite differentials.

   A = { +3, -1, +3, +9, +7, +6, -3}  dA = { -4, +4, +6, -2, -1, -9}d^2A = { +8, +2, -8, +1, -8}d^3A = { -6,-10, +9, -9}d^4A = { -4,+19,-18}d^5A = {+23,-37}d^6A = {-60} 

There is an easy to remember relationship:
A_n = (1 + d)^n A_0
It doesn''t mean anything, but you can expand it using Newton''s binomial formula to get
A_n = Comb(n,0)*A_0 + Comb(n,1)*dA_0 + Comb(n,2)*d^2A_0 + ...
That''s a good way to find an interpolating polynomial.

I just found this:
http://www.geocities.com/RainForest/Vines/2977/gauss/formulae/interpolation.html

Your first method is exactly what I had come up with the first time I tried to solve that problem. The polynomial sum is my friend''s idea. It works better, because with the finite derivation, you can only use points that are 1 unit apart in x, AFAIK.

I''m late for school, but I can tell you that it does work. If I remember correctly, you have to use your last derivative -20, and divide it by n! (the "level" of the derivative). That''s the coefficient of the term of degree n in your final polynomial. Now, substract that first term from every value that you have, and repeat the process. The final derivative should be 0, so you take the one before it, and repeat the process.

This should give the same result as the method that adds polynomials.

BTW, there is something missing in my OP, so it wouldn''t work as it is. You can probably figure it out.

Gotta go!

Cédric