Looking for online description: 3rd order polynomial curve fit

[peemo]

I'm no stats man but I need a rather detailed explanantion or example of how to contruct a 3rd order polynomial least-squares fit to a set of x-y data. From the searching I have done it seemss there are several methods. Anyone know a reference? Anyone know what method Excel uses?

Thanks.

 

[dennilfloss]

Three sites that might be helpful:

complete guide to curve fitting

Non-linear least-square curve fitter

least-square fitting of data.

Hope these help. One is just an applet for curve fitting.

Step By Step (Erik & The Vikings)

 

[peemo]

Whoa, thanks a lot dennilfloss! I start going through them right away.

 

[br0wn]

hey, I did a paper on this topic (curve and surface interpolation and approximation).

We did a degree 3 B-Spline to fit x-y-z data points.
The hard part is to find the parameterization (we used several techniques, such
as chord-length, uniform, centripetal, and universal).

After that it is easy, basically solving a linear equation.

Let me know if you need more help

 

[peemo]

I need a good algorithm for choosing & optimizing coefficients. I am reading about the Levenberg-Marquardt method but the description I have is somewhat confusing.

Here's another interesting little abstract. Too bad I can't download the paper:

A Sharp Lagrange Multiplier Rule for Nonsmooth Mathematical Programming Problems Involving Equality Constraints
X. Wang, V. Jeyakumar

Abstract. It is shown that a Lagrange multiplier rule that uses approximate Jacobians holds for mathematical programming problems involving Lipschitzian functions, finitely many equality constraints, and convex set constraints. It is sharper than the corresponding Lagrange multiplier rules for the convex-valued subdifferentials such as those of Clarke [Optimization and Nonsmooth Analysis, 2nd ed., SIAM, 1990] and Michel and Penot [Differential Integral Equations, 5 (1992), pp. 433--454]. The Lagrange multiplier result is obtained by means of a controllability criterion and the theory of fans developed by A. D. Ioffe [Math. Oper. Res., 9 (1984), pp. 159--189, Math. Programming, 58 (1993), pp. 137--145]. As an application, necessary optimality conditions are derived for a class of constrained minimax problems. An example is discussed to illustrate the nature of the multiplier rule.

Key words. generalized Jacobians, nonsmooth analysis, sharp Lagrange mutipliers, equality constraints, minimax problems

Uh, yeah, right.

 

[br0wn]

ok first, tell me what is your project about
and what level of competence or background you have in this field.

I can just spit out the jargons, but no use if you don't
know what I am talking about

Are you a college student ? grad student ? researcher ?

Do you familiar with parametric curve (Bezier, Bspline,
Nurbs) ?

I have tons of papers about this topic, fitting a curve
into a set of data, since I did a research on this topic.

I can give you some of the reference papers.

One note is you can fit UNLIMITED curves into a set of data,
that's why there are so many different algorithms/techniques
proposed by many ppls.

 

[peemo]

Thanks brOwn,

I'm helping to develop a website focussed on financial data. I work with Excel, MathCad & S-Plus. I am familiar with regression analysis. I work with time series and cross sectional data. I have read a bit about Bezier curves and cubic splines (not B-splines) but that's it. I'm looking to fit "smooth" trendline curves to different time series so that their relative behaviour may be visualized. I'm therefore looking for a fit that approximates the general shape of the data. I have rejected higher than 5th order polynomial fits for the data I'm looking at now for this reason.

I'm trying to minimize the sum of the squared differences of actual y vs predicted y for the fitted function: y = a + bx + cx^2 + dx^3. I need a relatively simple algorithm that chooses initial a, b, c, d values and adjusts these to minimize prediction error.

Thanks again.

 

[br0wn]

hmm....your description seems to be too broad. Can you give more detail info ?



<<
I'm helping to develop a website focussed on financial data. I work with Excel, MathCad &amp; S-Plus. I am familiar with regression analysis. I work with time series and cross sectional data. I have read a bit about Bezier curves and cubic splines (not B-splines) but that's it. I'm looking to fit &quot;smooth&quot; trendline curves to different time series so that their relative behaviour may be visualized. I'm therefore looking for a fit that approximates the general shape of the data. I have rejected higher than 5th order polynomial fits for the data I'm looking at now for this reason.
>>



Ok...First question : are you looking for interpolation or approximation techniques ?
Interpolation --> the curve will pass through all the data points.
Approximation --> the curve will not pass through all the data points, but approximates or follow the shape
of the data points' trail.



<<
I'm trying to minimize the sum of the squared differences of actual y vs predicted y for the fitted function: y = a + bx + cx^2 + dx^3. I need a relatively simple algorithm that chooses initial a, b, c, d values and adjusts these to minimize prediction error
>>



Second question : are you looking for iterative algorithm ? or one that give you 1-shot answer ?

Third question : are you looking for the algorithm and will write a program ? or you just want
to get a curve fitting to a set of datas, if so just use excel then ?


What you are looking for is basically the traditional method of curve fitting, this is discussed and beaten to death
by mathematician. You shouldn't have a problem to find a math book describing the procedure.
This is what excel uses: least-square method if I am not mistaken.

Current research and trend in Computer Science is doing interpolation and approximation using parametric curve (splines).

 

[peemo]

Hi brOwn,

I'm looking for approximation. I expect to use an iterative solution which we will programme; I am not looking for a package. I know Excel can produce trendlines but that doesn't help build a dynamic web-based tool.

Yes, Excel uses a least-squares method but how does it choose starting coefficients and what rules does it use for adjusting these to minimize the sum of the squared differences?

I'll do some reading on splines.

Thanks for your help.

 

[br0wn]

hmm...I'm not sure if using parametric curve is a good idea for you.
No offense, but it might be way over your head, especially if you are
a beginner to the parametric curve
(my suggestion is to find the least-square method which used
by excel from a math book, you should be able to find it in
library, I can't recall any books on top of my head, but
there are many books in this topic).

But if you are still challenged to use parametric curve,
a good place to start is
The NURBS Book, by Les Piegl and Wayne Tiller
(get this book from library).
The book has algorithm and described all of the techniques very well
(this is the bible for parametric curve btw).

Even approximation techniques (using splines) have several branches,
such as global approximation, local approximation, approximation with
tolerance, and each of these are still divided into several techniques
such as global approximation with weighted-average, global approximation
with least squares curve fitting, global approximation within specified
accuracy, ...
This is a huge field by itself and still expanding.

 

[cavingjan]

Most programs written in the 90s will use several methods for determining best fit curve. They'll just calculate them and choose which model fits the data the best. I took a 400 level Numerical Methods class in college that was both the hard math behind this and how to program for it. Long and short of the class was this: don't bother writing the code for it when you can find it already written. That was the essence of the final. It was a take-home, written exam that didn't even require the use of the computer other than wordprocessing. So glad I spent a semester learning this.

 

[peemo]

Thanks All,

Guess I'll keep pick up a couple of books on parametric curves and look online for free source code using a simple least squares method. I found that Polyfit written in Java does most of what I want for the moment.

Quite a fascinating field of study.

 

[br0wn]

hey, i was at the library this afternoon.

I found all linear algebra books discuss
this topic (least squares method).

Also check numerical recipes book (it has program
in there).

cavingjan has the right idea, you don't
want to write this program by yourself, just
find the package (such as linpack, one
from numerical recipes, ....)

 

[cavingjan]

You mean I'm right for once? Woohoo!!!! Thanks br0wn. I'll look which Numerical Methods book I have when I get home from work. (If I ever get home from work today.)