Excel Polynomial Curve-Fitting Algorithm

Question

What is the algorithm that Excel uses to calculate a 2nd-order polynomial regression (curve fitting)? Is there sample code or pseudo-code available?

Solution 1

I found a solution that returns the same formula that Excel gives:

1. Put together an augmented matrix of values used in a Least-Squares Parabola. See the sum equations in http://www.efunda.com/math/leastsquares/lstsqr2dcurve.cfm

2. Use Gaussian elimination to solve the matrix. Here is C# code that will do that http://www.codeproject.com/Tips/388179/Linear-Equation-Solver-Gaussian-Elimination-Csharp

3. After running that, the left-over values in the matrix (M) will equal the coefficients given in Excel.

Maybe I can find the R^2 somehow, but I don't need it for my purposes.

Solution 2

The polynomial trendlines in charts use least squares based on a QR decomposition method like the LINEST worksheet function ( http://support.microsoft.com/kb/828533 ). A second order or quadratic trend for given (x,y) data could be calculated using =LINEST(y,x^{1,2}).

You can call worksheet formulas from C# using the Worksheet.Evaluate method.

Comments

[user1214135]

Do you know of an algorithm for least squares fitting? I'd like to throw together some code in C#.

[duffymo]

I interpreted 2nd order to mean y = c0 + c1*x + c2*x^2. Your idea of second order is fitting a surface, not a curve.

[user1214135]

I know about the linest worksheet function. What I wanted to know was the algorithm that linest uses (or the chart with a 2nd order polynomial trendline). I figured it out and answered my own question below, stackoverflow.com/questions/11672385/…

[lori_m]

If you're only doing a quadratic trendline your links should suffice but the trendline (LINEST) algorithm actually implements QR decomposition for greater accuracy - it doesn't solve the "Normal Equations" directly as stated in the kb article.