Fastest way to fit a parabola to set of points?

Question

Given a set of points, what's the fastest way to fit a parabola to them? Is it doing the least squares calculation or is there an iterative way?

Thanks

Edit: I think gradient descent is the way to go. The least squares calculation would have been a little bit more taxing (having to do qr decomposition or something to keep things stable).

Answer 1

If the points have no error associated, you may interpolate by three points. Otherwise least squares or any equivalent formulation is the way to go.

Answer 2

I recently needed to find a parabola that passes through 3 points.

suppose you have (x1,y1), (x2,y2) and (x3,y3) and you want the parabola

y-y0 = a*(x-x0)^2

to pass through them: find y0, x0, and a.

You can do some algebra and get this solution (providing the points aren't all on a line) :

let c = (y1-y2) / (y2-y3)
x0    = ( -x1^2 + x2^2 + c*( x2^2 - x3^2 ) )  /  (2.0*( -x1+x2 + c*x2 - c*x3 ))
a     = (y1-y2)  /  ( (x1-x0)^2 - (x2-x0)^2 )
y0    = y1 - a*(x1-x0)^2

Note in the equation for c if y2==y3 then you've got a problem. So in my algorithm I check for this and swap say x1, y1 with x2, y2 and then proceed.

hope that helps!

Paul Probert

Answer 3

A calculated solution is almost always faster than an iterative solution. The "exception" would be for low iteration counts and complex calculations.

I would use the least squares method. I've only every coded it for linear regression fits but it can be used for parabolas (I had reason to look it up recently - sources included an old edition of "Numerical Recipes" Press et al; and "Engineering Mathematics" Kreyzig).

Answer 4

ALGORITHM FOR PARABOLA

1. Read no. of data points n and order of polynomial Mp .
2. Read data values .
3. If n< Mp [ Regression is not possible ] stop else continue ;
4. Set M=Mp + 1 ;
5. Compute co-efficient of C-matrix .
6. Compute co-efficient of B-matrix .
7. Solve for the co-efficients a1,a2,. . . . . . . an .
8. Write the co-efficient .
9. Estimate the function value at the glren of independents variables .