This chapter describes routines for performing least squares fits to experimental data using linear combinations of functions.  The data may be weighted or unweighted, i.e. with known or unknown errors.  For weighted data the functions compute the best fit parameters and their associated covariance matrix.  For unweighted data the covariance matrix is estimated from the scatter of the points, giving a variance-covariance matrix.

The functions are divided into separate versions for simple one- or two-parameter regression and multiple-parameter fits.  The functions are declared in the header file gsl_fit.h.

Overview
========

Least-squares fits are found by minimizing \chi^2 (chi-squared), the weighted sum of squared residuals over n experimental datapoints (x_i, y_i) for the model Y(c,x),

     \chi^2 = \sum_i w_i (y_i - Y(c, x_i))^2

The p parameters of the model are $c = \c_0, c_1, \dots\$ c = {c_0, c_1, ...}.  The weight factors w_i are given by w_i = 1/\sigma_i^2, where \sigma_i is the experimental error on the data-point y_i.  The errors are assumed to be gaussian and uncorrelated. For unweighted data the chi-squared sum is computed without any weight factors.

The fitting routines return the best-fit parameters c and their p \times p covariance matrix.  The covariance matrix measures the statistical errors on the best-fit parameters resulting from the errors on the data, \sigma_i, and is defined as $C_ab = \langle \delta c_a \delta c_b \rangle$ C_{ab} = <\delta c_a \delta c_b> where $\langle \, \rangle$ < > denotes an average over the gaussian error distributions of the underlying datapoints.

The covariance matrix is calculated by error propagation from the data errors \sigma_i.  The change in a fitted parameter \delta c_a caused by a small change in the data \delta y_i is given by

     \delta c_a = \sum_i (dc_a/dy_i) \delta y_i

allowing the covariance matrix to be written in terms of the errors on the data,

     C_{ab} = \sum_{i,j} (dc_a/dy_i) (dc_b/dy_j) <\delta y_i \delta y_j>

For uncorrelated data the fluctuations of the underlying datapoints satisfy $\langle \delta y_i \delta y_j \rangle = \sigma_i^2 \delta_ij$ <\delta y_i \delta y_j> = \sigma_i^2 \delta_{ij}, giving a corresponding parameter covariance matrix of

     C_{ab} = \sum_i (1/w_i) (dc_a/dy_i) (dc_b/dy_i)

When computing the covariance matrix for unweighted data, i.e. data with unknown errors, the weight factors w_i in this sum are replaced by the single estimate w = 1/\sigma^2, where \sigma^2 is the computed variance of the residuals about the best-fit model, \sigma^2 = \sum (y_i - Y(c,x_i))^2 / (n-p). This is referred to as the variance-covariance matrix.

The standard deviations of the best-fit parameters are given by the square root of the corresponding diagonal elements of the covariance matrix, $\sigma_c_a = \sqrtC_aa$ \sigma_{c_a} = \sqrt{C_{aa}}.

Linear regression
=================

The functions described in this section can be used to perform least-squares fits to a straight line model, Y(c,x) = c_0 + c_1 x.

 -- Function: int gsl_fit_linear (const double * X, const size_t XSTRIDE, const double * Y, const size_t YSTRIDE, size_t N, double * C0, double * C1, double * COV00, double * COV01, double * COV11, double * SUMSQ)
     This function computes the best-fit linear regression coefficients (C0,C1) of the model Y = c_0 + c_1 X for the dataset (X, Y), two vectors of length N with strides XSTRIDE and YSTRIDE.  The errors on Y are assumed unknown so the variance-covariance matrix for the parameters (C0, C1) is estimated from the scatter of the points around the best-fit line and returned via the parameters (COV00, COV01, COV11). The sum of squares of the residuals from the best-fit line is returned in SUMSQ.

 -- Function: int gsl_fit_wlinear (const double * X, const size_t XSTRIDE, const double * W, const size_t WSTRIDE, const double * Y, const size_t YSTRIDE, size_t N, double * C0, double * C1, double * COV00, double * COV01, double * COV11, double * CHISQ)
     This function computes the best-fit linear regression coefficients (C0,C1) of the model Y = c_0 + c_1 X for the weighted dataset (X, Y), two vectors of length N with strides XSTRIDE and YSTRIDE.  The vector W, of length N and stride WSTRIDE, specifies the weight of each datapoint. The weight is the reciprocal of the variance for each datapoint in Y.

     The covariance matrix for the parameters (C0, C1) is computed using the weights and returned via the parameters (COV00, COV01, COV11).  The weighted sum of squares of the residuals from the best-fit line, \chi^2, is returned in CHISQ.

 -- Function: int gsl_fit_linear_est (double X, double C0, double C1, double C00, double C01, double C11, double * Y, double * Y_ERR)
     This function uses the best-fit linear regression coefficients C0,C1 and their covariance COV00,COV01,COV11 to compute the fitted function Y and its standard deviation Y_ERR for the model Y = c_0 + c_1 X at the point X.

Linear fitting without a constant term
======================================

The functions described in this section can be used to perform least-squares fits to a straight line model without a constant term, Y = c_1 X.

 -- Function: int gsl_fit_mul (const double * X, const size_t XSTRIDE, const double * Y, const size_t YSTRIDE, size_t N, double * C1, double * COV11, double * SUMSQ)
     This function computes the best-fit linear regression coefficient C1 of the model Y = c_1 X for the datasets (X, Y), two vectors of length N with strides XSTRIDE and YSTRIDE.  The errors on Y are assumed unknown so the variance of the parameter C1 is estimated from the scatter of the points around the best-fit line and returned via the parameter COV11.  The sum of squares of the residuals from the best-fit line is returned in SUMSQ.

 -- Function: int gsl_fit_wmul (const double * X, const size_t XSTRIDE, const double * W, const size_t WSTRIDE, const double * Y, const size_t YSTRIDE, size_t N, double * C1, double * COV11, double * SUMSQ)
     This function computes the best-fit linear regression coefficient C1 of the model Y = c_1 X for the weighted datasets (X, Y), two vectors of length N with strides XSTRIDE and YSTRIDE.  The vector W, of length N and stride WSTRIDE, specifies the weight of each datapoint. The weight is the reciprocal of the variance for each datapoint in Y.

     The variance of the parameter C1 is computed using the weights and returned via the parameter COV11.  The weighted sum of squares of the residuals from the best-fit line, \chi^2, is returned in CHISQ.

 -- Function: int gsl_fit_mul_est (double X, double C1, double C11, double * Y, double * Y_ERR)
     This function uses the best-fit linear regression coefficient C1 and its covariance COV11 to compute the fitted function Y and its standard deviation Y_ERR for the model Y = c_1 X at the point X.

Multi-parameter fitting
=======================

The functions described in this section perform least-squares fits to a general linear model, y = X c where y is a vector of n observations, X is an n by p matrix of predictor variables, and the elements of the vector c are the p unknown best-fit parameters which are to be estimated.  The chi-squared value is given by $\chi^2 = \sum_i w_i (y_i - \sum_j X_ij c_j)^2$ \chi^2 = \sum_i w_i (y_i - \sum_j X_{ij} c_j)^2.

This formulation can be used for fits to any number of functions and/or variables by preparing the n-by-p matrix X appropriately.  For example, to fit to a p-th order polynomial in X, use the following matrix,

     X_{ij} = x_i^j

where the index i runs over the observations and the index j runs from 0 to p-1.

To fit to a set of p sinusoidal functions with fixed frequencies \omega_1, \omega_2, ..., \omega_p, use,

     X_{ij} = sin(\omega_j x_i)

To fit to p independent variables x_1, x_2, ..., x_p, use,

     X_{ij} = x_j(i)

where x_j(i) is the i-th value of the predictor variable x_j.

The functions described in this section are declared in the header file gsl_multifit.h.

The solution of the general linear least-squares system requires an additional working space for intermediate results, such as the singular value decomposition of the matrix X.

 -- Function: gsl_multifit_linear_workspace * gsl_multifit_linear_alloc (size_t N, size_t P)
     This function allocates a workspace for fitting a model to N observations using P parameters.

 -- Function: void gsl_multifit_linear_free (gsl_multifit_linear_workspace * WORK)
     This function frees the memory associated with the workspace W.

 -- Function: int gsl_multifit_linear (const gsl_matrix * X, const gsl_vector * Y, gsl_vector * C, gsl_matrix * COV, double * CHISQ, gsl_multifit_linear_workspace * WORK)
 -- Function: int gsl_multifit_linear_svd (const gsl_matrix * X, const gsl_vector * Y, double TOL, size_t * RANK, gsl_vector * C, gsl_matrix * COV, double * CHISQ, gsl_multifit_linear_workspace * WORK)
     These functions compute the best-fit parameters C of the model y = X c for the observations Y and the matrix of predictor variables X.  The variance-covariance matrix of the model parameters COV is estimated from the scatter of the observations about the best-fit.  The sum of squares of the residuals from the best-fit, \chi^2, is returned in CHISQ.

     The best-fit is found by singular value decomposition of the matrix X using the preallocated workspace provided in WORK. The modified Golub-Reinsch SVD algorithm is used, with column scaling to improve the accuracy of the singular values. Any components which have zero singular value (to machine precision) are discarded from the fit. In the second form of the function the components are discarded if the ratio of singular values s_i/s_0 falls below the user-specified tolerance TOL, and the effective rank is returned in RANK.

 -- Function: int gsl_multifit_wlinear (const gsl_matrix * X, const gsl_vector * W, const gsl_vector * Y, gsl_vector * C, gsl_matrix * COV, double * CHISQ, gsl_multifit_linear_workspace * WORK)
 -- Function: int gsl_multifit_wlinear_svd (const gsl_matrix * X, const gsl_vector * W, const gsl_vector * Y, double TOL, size_t * RANK, gsl_vector * C, gsl_matrix * COV, double * CHISQ, gsl_multifit_linear_workspace * WORK)

     This function computes the best-fit parameters C of the weighted model y = X c for the observations Y with weights W and the matrix of predictor variables X.  The covariance matrix of the model parameters COV is computed with the given weights.  The weighted sum of squares of the residuals from the best-fit, \chi^2, is returned in CHISQ.

     The best-fit is found by singular value decomposition of the matrix X using the preallocated workspace provided in WORK. Any components which have zero singular value (to machine precision) are discarded from the fit.  In the second form of the function the components are discarded if the ratio of singular values s_i/s_0 falls below the user-specified tolerance TOL, and the effective rank is returned in RANK.

 -- Function: int gsl_multifit_linear_est (const gsl_vector * X, const gsl_vector * C, const gsl_matrix * COV, double * Y, double * Y_ERR)
     This function uses the best-fit multilinear regression coefficients C and their covariance matrix COV to compute the fitted function value Y and its standard deviation Y_ERR for the model y = x.c at the point X.

Examples
========

The following program computes a least squares straight-line fit to a simple dataset, and outputs the best-fit line and its associated one standard-deviation error bars.

          [file fitting.c not included]

The following commands extract the data from the output of the program and display it using the GNU plotutils graph utility,

     $ ./demo > tmp
     $ more tmp
     # best fit: Y = -106.6 + 0.06 X
     # covariance matrix:
     # [ 39602, -19.9
     #   -19.9, 0.01]
     # chisq = 0.8

     $ for n in data fit hi lo ;
        do
          grep "^$n" tmp | cut -d: -f2 > $n ;
        done
     $ graph -T X -X x -Y y -y 0 20 -m 0 -S 2 -Ie data
          -S 0 -I a -m 1 fit -m 2 hi -m 2 lo

The next program performs a quadratic fit y = c_0 + c_1 x + c_2 x^2 to a weighted dataset using the generalised linear fitting function gsl_multifit_wlinear.  The model matrix X for a quadratic fit is given by,

     X = [ 1   , x_0  , x_0^2 ;
           1   , x_1  , x_1^2 ;
           1   , x_2  , x_2^2 ;
           ... , ...  , ...   ]

where the column of ones corresponds to the constant term c_0. The two remaining columns corresponds to the terms c_1 x and c_2 x^2.

The program reads N lines of data in the format (X, Y, ERR) where ERR is the error (standard deviation) in the value Y.

          [file fitting2.c not included]

A suitable set of data for fitting can be generated using the following program.  It outputs a set of points with gaussian errors from the curve y = e^x in the region 0 < x < 2.

          [file fitting3.c not included]

The data can be prepared by running the resulting executable program,

     $ ./generate > exp.dat
     $ more exp.dat
     0.1 0.97935 0.110517
     0.2 1.3359 0.12214
     0.3 1.52573 0.134986
     0.4 1.60318 0.149182
     0.5 1.81731 0.164872
     0.6 1.92475 0.182212
     ....

To fit the data use the previous program, with the number of data points given as the first argument.  In this case there are 19 data points.

     $ ./fit 19 < exp.dat
     0.1 0.97935 +/- 0.110517
     0.2 1.3359 +/- 0.12214
     ...
     # best fit: Y = 1.02318 + 0.956201 X + 0.876796 X^2
     # covariance matrix:
     [ +1.25612e-02, -3.64387e-02, +1.94389e-02
       -3.64387e-02, +1.42339e-01, -8.48761e-02
       +1.94389e-02, -8.48761e-02, +5.60243e-02 ]
     # chisq = 23.0987

The parameters of the quadratic fit match the coefficients of the expansion of e^x, taking into account the errors on the parameters and the O(x^3) difference between the exponential and quadratic functions for the larger values of x.  The errors on the parameters are given by the square-root of the corresponding diagonal elements of the covariance matrix.  The chi-squared per degree of freedom is 1.4, indicating a reasonable fit to the data.

References and Further Reading
==============================

A summary of formulas and techniques for least squares fitting can be found in the ``Statistics'' chapter of the Annual Review of Particle Physics prepared by the Particle Data Group,

  Review of Particle Properties, R.M. Barnett et al., Physical Review D54, 1 (1996) http://pdg.lbl.gov/

The Review of Particle Physics is available online at the website given above.

The tests used to prepare these routines are based on the NIST Statistical Reference Datasets. The datasets and their documentation are available from NIST at the following website,

http://www.nist.gov/itl/div898/strd/index.html.