STFC Website

part of UK Research & Innovation

Version 1.0.0

12th July 2004

MA44: Over-determined linear system: least-squares solution

To solve an equality-constrained linear least squares problem. Given an over-determined system of \(m\) linear equations in \(n\) unknowns,

\[\sum_ {j=1} ^ n a _{ij} x _j = b _i,\; i=1,2,...m, \; m \ge n \ge 1,\]

it calculates the solution vector \(\mathbf{x}\) which satisfies the first \(m _1\) equations (\(0 \le m _1 \le n\)) and minimizes the sum of squares of residuals \[S(\mathbf{x}) = \sum_ {i=1} ^ m r _i ^2 ,\] where \[r_i = \sum_ {j=1} ^ n a_{ij} x _{j} - b _i, \; i=1,2,...,m.\]

The matrix \(\mathbf{A} = a _{ij}\) must have rank \(n\), that is its columns must be linearly independent. Also the first \(m _1\) rows of \(\mathbf{A}\) must be linearly independent.

There is a re-entry facility which allows further systems having the same left-hand sides to be solved economically.

There is an entry to obtain solution standard deviations and the variance-covariance matrix. These are calculated on the assumption that the first \(m _1\) equations are exact and that the remaining equations have errors which are independent random variables with the same variance.

The automatic printing of results and the calculation of equation residuals are options.

The subroutine can be used to solve the general linear least squares data fitting problem with or without equality side conditions.