c@225: /* -*- c-basic-offset: 4 indent-tabs-mode: nil -*-  vi:set ts=8 sts=4 sw=4: */
c@225: //---------------------------------------------------------------------------
c@225: 
c@225: #ifndef PolyfitHPP
c@225: #define PolyfitHPP
c@225: //---------------------------------------------------------------------------
c@225: // Least-squares curve fitting class for arbitrary data types
c@225: /*
c@225: 
c@225: { ******************************************
c@225:   ****   Scientific Subroutine Library  ****
c@225:   ****         for C++ Builder          ****
c@225:   ******************************************
c@225: 
c@225:   The following programs were written by Allen Miller and appear in the
c@225:   book entitled "Pascal Programs For Scientists And Engineers" which is
c@225:   published by Sybex, 1981.
c@225:   They were originally typed and submitted to MTPUG in Oct. 1982
c@225:     Juergen Loewner
c@225:     Hoher Heckenweg 3
c@225:     D-4400 Muenster
c@225:   They have had minor corrections and adaptations for Turbo Pascal by
c@225:     Jeff Weiss
c@225:     1572 Peacock Ave.
c@225:     Sunnyvale, CA 94087.
c@225: 
c@225: 
c@225: 2000 Oct 28  Updated for Delphi 4, open array parameters.
c@225:              This allows the routine to be generalised so that it is no longer
c@225:              hard-coded to make a specific order of best fit or work with a
c@225:              specific number of points.
c@225: 2001 Jan 07  Update Web site address
c@225: 
c@225: Copyright © David J Taylor, Edinburgh and others listed above
c@225: Web site:  www.satsignal.net
c@225: E-mail:    davidtaylor@writeme.com
c@225: }*/
c@225: 
c@225:  ///////////////////////////////////////////////////////////////////////////////
c@225:  // Modified by CLandone for VC6 Aug 2004
c@225:  ///////////////////////////////////////////////////////////////////////////////
c@225: 
c@225: 
c@225: using std::vector;
c@225: 
c@225: 
c@225: class TPolyFit
c@225: {
c@225:     typedef vector<vector<double> > Matrix;
c@225: public:
c@225: 
c@225:     static double PolyFit2 (const vector<double> &x,  // does the work
c@225: 			    const vector<double> &y,
c@225: 			    vector<double> &coef);
c@225: 
c@225:                    
c@225: private:
c@225:     TPolyFit &operator = (const TPolyFit &);   // disable assignment
c@225:     TPolyFit();                                // and instantiation
c@225:     TPolyFit(const TPolyFit&);                 // and copying
c@225: 
c@225:   
c@225:     static void Square (const Matrix &x,              // Matrix multiplication routine
c@225: 			const vector<double> &y,
c@225: 			Matrix &a,                    // A = transpose X times X
c@225: 			vector<double> &g,         // G = Y times X
c@225: 			const int nrow, const int ncol);
c@225:     // Forms square coefficient matrix
c@225: 
c@225:     static bool GaussJordan (Matrix &b,                  // square matrix of coefficients
c@225: 			     const vector<double> &y, // constant vector
c@225: 			     vector<double> &coef);   // solution vector
c@225:     // returns false if matrix singular
c@225: 
c@225:     static bool GaussJordan2(Matrix &b,
c@225: 			     const vector<double> &y,
c@225: 			     Matrix &w,
c@225: 			     vector<vector<int> > &index);
c@225: };
c@225: 
c@225: // some utility functions
c@225: 
c@225: namespace NSUtility
c@225: {
c@225:     inline void swap(double &a, double &b) {double t = a; a = b; b = t;}
c@225:     void zeroise(vector<double> &array, int n);
c@225:     void zeroise(vector<int> &array, int n);
c@225:     void zeroise(vector<vector<double> > &matrix, int m, int n);
c@225:     void zeroise(vector<vector<int> > &matrix, int m, int n);
c@225:     inline double sqr(const double &x) {return x * x;}
c@225: };
c@225: 
c@225: //---------------------------------------------------------------------------
c@225: // Implementation
c@225: //---------------------------------------------------------------------------
c@225: using namespace NSUtility;
c@225: //------------------------------------------------------------------------------------------
c@225: 
c@225: 
c@225: // main PolyFit routine
c@225: 
c@225: double TPolyFit::PolyFit2 (const vector<double> &x,
c@225: 			   const vector<double> &y,
c@225: 			   vector<double> &coefs)
c@225: // nterms = coefs.size()
c@225: // npoints = x.size()
c@225: {
c@225:     int i, j;
c@225:     double xi, yi, yc, srs, sum_y, sum_y2;
c@225:     Matrix xmatr;        // Data matrix
c@225:     Matrix a;
c@225:     vector<double> g;      // Constant vector
c@225:     const int npoints(x.size());
c@225:     const int nterms(coefs.size());
c@225:     double correl_coef;
c@225:     zeroise(g, nterms);
c@225:     zeroise(a, nterms, nterms);
c@225:     zeroise(xmatr, npoints, nterms);
c@225:     if(nterms < 1)
c@225: 	throw "PolyFit called with less than one term";
c@225:     if(npoints < 2)
c@225: 	throw "PolyFit called with less than two points";
c@225:     if(npoints != y.size())
c@225: 	throw "PolyFit called with x and y of unequal size";
c@225:     for(i = 0; i < npoints; ++i)
c@225:     {
c@225: 	//      { setup x matrix }
c@225: 	xi = x[i];
c@225: 	xmatr[i][0] = 1.0;	   //     { first column }
c@225: 	for(j = 1; j < nterms; ++j)
c@225: 	    xmatr[i][j] = xmatr [i][j - 1] * xi;
c@225:     }
c@225:     Square (xmatr, y, a, g, npoints, nterms);
c@225:     if(!GaussJordan (a, g, coefs))
c@225: 	return -1;
c@225:     sum_y = 0.0;
c@225:     sum_y2 = 0.0;
c@225:     srs = 0.0;
c@225:     for(i = 0; i < npoints; ++i)
c@225:     {
c@225: 	yi = y[i];
c@225: 	yc = 0.0;
c@225: 	for(j = 0; j < nterms; ++j)
c@225: 	    yc += coefs [j] * xmatr [i][j];
c@225: 	srs += sqr (yc - yi);
c@225: 	sum_y += yi;
c@225: 	sum_y2 += yi * yi;
c@225:     }
c@225: 
c@225:     // If all Y values are the same, avoid dividing by zero
c@225:     correl_coef = sum_y2 - sqr (sum_y) / npoints;
c@225:     // Either return 0 or the correct value of correlation coefficient
c@225:     if (correl_coef != 0)
c@225: 	correl_coef = srs / correl_coef;
c@225:     if (correl_coef >= 1)
c@225: 	correl_coef = 0.0;
c@225:     else
c@225: 	correl_coef = sqrt (1.0 - correl_coef);
c@225:     return correl_coef;
c@225: }
c@225: 
c@225: 
c@225: //------------------------------------------------------------------------
c@225: 
c@225: // Matrix multiplication routine
c@225: // A = transpose X times X
c@225: // G = Y times X
c@225: 
c@225: // Form square coefficient matrix
c@225: 
c@225: void TPolyFit::Square (const Matrix &x,
c@225: 		       const vector<double> &y,
c@225: 		       Matrix &a,
c@225: 		       vector<double> &g,
c@225: 		       const int nrow,
c@225: 		       const int ncol)
c@225: {
c@225:     int i, k, l;
c@225:     for(k = 0; k < ncol; ++k)
c@225:     {
c@225: 	for(l = 0; l < k + 1; ++l)
c@225: 	{
c@225: 	    a [k][l] = 0.0;
c@225: 	    for(i = 0; i < nrow; ++i)
c@225: 	    {
c@225: 		a[k][l] += x[i][l] * x [i][k];
c@225: 		if(k != l)
c@225: 		    a[l][k] = a[k][l];
c@225: 	    }
c@225: 	}
c@225: 	g[k] = 0.0;
c@225: 	for(i = 0; i < nrow; ++i)
c@225: 	    g[k] += y[i] * x[i][k];
c@225:     }
c@225: }
c@225: //---------------------------------------------------------------------------------
c@225: 
c@225: 
c@225: bool TPolyFit::GaussJordan (Matrix &b,
c@225: 			    const vector<double> &y,
c@225: 			    vector<double> &coef)
c@225: //b square matrix of coefficients
c@225: //y constant vector
c@225: //coef solution vector
c@225: //ncol order of matrix got from b.size()
c@225: 
c@225: 
c@225: {
c@225: /*
c@225:   { Gauss Jordan matrix inversion and solution }
c@225: 
c@225:   { B (n, n) coefficient matrix becomes inverse }
c@225:   { Y (n) original constant vector }
c@225:   { W (n, m) constant vector(s) become solution vector }
c@225:   { DETERM is the determinant }
c@225:   { ERROR = 1 if singular }
c@225:   { INDEX (n, 3) }
c@225:   { NV is number of constant vectors }
c@225: */
c@225: 
c@225:     int ncol(b.size());
c@225:     int irow, icol;
c@225:     vector<vector<int> >index;
c@225:     Matrix w;
c@225: 
c@225:     zeroise(w, ncol, ncol);
c@225:     zeroise(index, ncol, 3);
c@225: 
c@225:     if(!GaussJordan2(b, y, w, index))
c@225: 	return false;
c@225: 
c@225:     // Interchange columns
c@225:     int m;
c@225:     for (int i = 0; i <  ncol; ++i)
c@225:     {
c@225: 	m = ncol - i - 1;
c@225: 	if(index [m][0] != index [m][1])
c@225: 	{
c@225: 	    irow = index [m][0];
c@225: 	    icol = index [m][1];
c@225: 	    for(int k = 0; k < ncol; ++k)
c@225: 		swap (b[k][irow], b[k][icol]);
c@225: 	}
c@225:     }
c@225: 
c@225:     for(int k = 0; k < ncol; ++k)
c@225:     {
c@225: 	if(index [k][2] != 0)
c@225: 	{
c@225: 	    throw "Error in GaussJordan: matrix is singular";
c@225: 	}
c@225:     }
c@225: 
c@225:     for( int i = 0; i < ncol; ++i)
c@225: 	coef[i] = w[i][0];
c@225:  
c@225:  
c@225:     return true;
c@225: }   // end;	{ procedure GaussJordan }
c@225: //----------------------------------------------------------------------------------------------
c@225: 
c@225: 
c@225: bool TPolyFit::GaussJordan2(Matrix &b,
c@225: 			    const vector<double> &y,
c@225: 			    Matrix &w,
c@225: 			    vector<vector<int> > &index)
c@225: {
c@225:     //GaussJordan2;         // first half of GaussJordan
c@225:     // actual start of gaussj
c@225:  
c@225:     double big, t;
c@225:     double pivot;
c@225:     double determ;
c@225:     int irow, icol;
c@225:     int ncol(b.size());
c@225:     int nv = 1;                  // single constant vector
c@225:     for(int i = 0; i < ncol; ++i)
c@225:     {
c@225: 	w[i][0] = y[i];      // copy constant vector
c@225: 	index[i][2] = -1;
c@225:     }
c@225:     determ = 1.0;
c@225:     for(int i = 0; i < ncol; ++i)
c@225:     {
c@225: 	// Search for largest element
c@225: 	big = 0.0;
c@225: 	for(int j = 0; j < ncol; ++j)
c@225: 	{
c@225: 	    if(index[j][2] != 0)
c@225: 	    {
c@225: 		for(int k = 0; k < ncol; ++k)
c@225: 		{
c@225: 		    if(index[k][2] > 0)
c@225: 			throw "Error in GaussJordan2: matrix is singular";
c@225: 
c@225: 		    if(index[k][2] < 0 && fabs(b[j][k]) > big)
c@225: 		    {
c@225: 			irow = j;
c@225: 			icol = k;
c@225: 			big = fabs(b[j][k]);
c@225: 		    }
c@225: 		} //   { k-loop }
c@225: 	    }
c@225: 	}  // { j-loop }
c@225: 	index [icol][2] = index [icol][2] + 1;
c@225: 	index [i][0] = irow;
c@225: 	index [i][1] = icol;
c@225: 
c@225: 	// Interchange rows to put pivot on diagonal
c@225: 	// GJ3
c@225: 	if(irow != icol)
c@225: 	{
c@225: 	    determ = -determ;
c@225: 	    for(int m = 0; m < ncol; ++m)
c@225: 		swap (b [irow][m], b[icol][m]);
c@225: 	    if (nv > 0)
c@225: 		for (int m = 0; m < nv; ++m)
c@225: 		    swap (w[irow][m], w[icol][m]);
c@225: 	} // end GJ3
c@225: 
c@225: 	// divide pivot row by pivot column
c@225: 	pivot = b[icol][icol];
c@225: 	determ *= pivot;
c@225: 	b[icol][icol] = 1.0;
c@225: 
c@225: 	for(int m = 0; m < ncol; ++m)
c@225: 	    b[icol][m] /= pivot;
c@225: 	if(nv > 0)
c@225: 	    for(int m = 0; m < nv; ++m)
c@225: 		w[icol][m] /= pivot;
c@225: 
c@225: 	// Reduce nonpivot rows
c@225: 	for(int n = 0; n < ncol; ++n)
c@225: 	{
c@225: 	    if(n != icol)
c@225: 	    {
c@225: 		t = b[n][icol];
c@225: 		b[n][icol] = 0.0;
c@225: 		for(int m = 0; m < ncol; ++m)
c@225: 		    b[n][m] -= b[icol][m] * t;
c@225: 		if(nv > 0)
c@225: 		    for(int m = 0; m < nv; ++m)
c@225: 			w[n][m] -= w[icol][m] * t;
c@225: 	    }
c@225: 	}
c@225:     } // { i-loop }
c@225:     return true;
c@225: }
c@225: //----------------------------------------------------------------------------------------------
c@225: 
c@225: //------------------------------------------------------------------------------------
c@225: 
c@225: // Utility functions
c@225: //--------------------------------------------------------------------------
c@225: 
c@225: // fills a vector with zeros.
c@225: void NSUtility::zeroise(vector<double> &array, int n)
c@225: {
c@225:     array.clear();
c@225:     for(int j = 0; j < n; ++j)
c@225: 	array.push_back(0);
c@225: }
c@225: //--------------------------------------------------------------------------
c@225: 
c@225: // fills a vector with zeros.
c@225: void NSUtility::zeroise(vector<int> &array, int n)
c@225: {
c@225:     array.clear();
c@225:     for(int j = 0; j < n; ++j)
c@225: 	array.push_back(0);
c@225: }
c@225: //--------------------------------------------------------------------------
c@225: 
c@225: // fills a (m by n) matrix with zeros.
c@225: void NSUtility::zeroise(vector<vector<double> > &matrix, int m, int n)
c@225: {
c@225:     vector<double> zero;
c@225:     zeroise(zero, n);
c@225:     matrix.clear();
c@225:     for(int j = 0; j < m; ++j)
c@225: 	matrix.push_back(zero);
c@225: }
c@225: //--------------------------------------------------------------------------
c@225: 
c@225: // fills a (m by n) matrix with zeros.
c@225: void NSUtility::zeroise(vector<vector<int> > &matrix, int m, int n)
c@225: {
c@225:     vector<int> zero;
c@225:     zeroise(zero, n);
c@225:     matrix.clear();
c@225:     for(int j = 0; j < m; ++j)
c@225: 	matrix.push_back(zero);
c@225: }
c@225: //--------------------------------------------------------------------------
c@225: 
c@225: 
c@225: #endif
c@225: