From: ksbrown@seanet.com (Kevin Brown)
Newsgroups: sci.math,comp.msdos.programming,alt.msdos.programming
Subject: Re: Curve-Fit Algorithms
Date: Fri, 15 May 1998 03:01:17 GMT

On Thu, 14 May 1998 20:55:41 GMT, jbrickley@programmer.net wrote:
> I am looking for either C source, algorithms on paper, or the name
> of algorithms (so that I can look them up) that will do nth order
> polynomial curve-fit's similar to what MS Excel can do.... I would
> like to be able to use curve-fitting algorithms based on a series
> of points in my own programs...

The general method is usually called linear regression, and can
be applied to give the "least-squares" fit to any polynomial
function.  It sounds like you're only interested in polynomials
in one variable, but the general method applies to functions in
any number of variables.  Essentially you just find the coefficients
such that the sum of the squares of the errors is a minimum.

Suppose you have a bunch of data points giving the triples (x,y,v)
and you want to find a polynomial give v as a function of x and y
of the form

            v  =  A + Bx + Cy + Dx^2 + Ey^2

Consider your first data point, [x,y,v]_1, where "v" is your dependent
variable.  For any given choice of coefficients A,B,..,E the square of
the "error" for the first data point is

  [ A + Bx + Cy + Dx^2 + Ey^2  - v ]^2

         =  A^2 + 2ABx    + 2ACy    + 2ADx^2  + 2AEy^2    - 2Av
                + B^2 x^2 + 2BCxy   + 2BDx^3  + 2BExy^2   - 2Bxv
                          + C^2 y^2 + 2CDyx^2 + 2CEy^3    - 2Cyv
                                    + D^2 x^4 + 2DE(xy)^2 - 2Dvx^2
                                              + E^2 y^4   - 2Evy^2
                                                          + v^2

The squared error for each of the N data points is of this form, so
you can add them all together to give the total sum-of-sqaures of
all the errors. Clearly this yields an expression identical to the
one above, except that "x" is replaced by the sum of x_i  (i=1 to N),
and "yx^2" is replaced by the sum of  (y_i)(x_i)^2  (i=1 to N),  and
so on.  For convenience, let [*] denote the sum of the bracketed
expression over all N data points.

Now we can take the partial derivatives of this total sum of squares
with respect to each coefficient A,B...E in turn, and set each of
these partials to zero to give the minimum sum of squares.  This
results in the following set of simultaneous equations

  2AN     + 2B[x]    + 2C[y]    + 2D[x^2]    + 2E[y^2]    =  2[v]
  2A[x]   + 2B[x^2]  + 2C[xy]   + 2D[x^3]    + 2E[xy^2]   =  2[xv]
  2A[y]   + 2B[xy]   + 2C[y^2]  + 2D[yx^2]   + 2E[y^3]    =  2[yv]
  2A[x^2] + 2B[x^3]  + 2C[yx^2] + 2D[x^4]    + 2E[(xy)^2] =  2[vx^2]
  2A[y^2] + 2B[xy^2] + 2C[y^3]  + 2D[(xy)^2] + 2E[y^4]    =  2[vy^2]

Dividing all terms by 2 and putting these equations into matrix form
gives the 5x5 system of equations
  _                                          _   _   _     _       _
 |                                            | |     |   |         |
 |   N     [x]     [y]     [x^2]     [y^2]    | |  A  |   |  [v]    |
 |  [x]    [x^2]   [xy]    [x^3]     [xy^2]   | |  B  |   |  [xv]   |
 |  [y]    [xy]    [y^2]   [yx^2]    [y^3]    |.|  C  | = |  [yv]   |
 |  [x^2]  [x^3]   [yx^2]  [x^4]     [(xy)^2] | |  D  |   |  [vx^2] |
 |  [y^2]  [xy^2]  [y^3]   [(xy)^2]  [y^4]    | |  E  |   |  [vy^2] |
 |_                                          _| |_   _|   |_       _|

Solve this system in any of the usual ways (e.g., Gaussian
elimination, or multiply the right-hand column vector by the
inverse of the 5x5 matrix) to give the best fit coefficients A,
B, C, D, and E.  Thus, all you need to do is compute all the
sums [*] from your N data points, then perform one matrix
inversion and one matrix multiplication, and you have your
least squares fit.
  ________________________________________________________________
 |  MathPages  /*\      http://www.seanet.com/~ksbrown/           |
 |            /   \                                               |
 |___________/Keep a metaphor in your heart ______________________| 
              and a simile on your face.