The linear least squares (LLS) problem is:
where A is an m-by-n matrix, b is a given m element vector and x is the n element solution vector.
In the most usual case, and . In this case the solution to problem (3.1) is unique. The problem is also referred to as finding a least squares solution to an overdetermined system of linear equations.
When m < n and , there are an infinite number of solutions x that exactly satisfy b-Ax=0. In this case it is often useful to find the unique solution x that minimizes , and the problem is referred to as finding a minimum norm solution to an underdetermined system of linear equations.
The driver routine PxGELS solves problem (3.1) on the assumption that -- in other words, A has full rank -- finding a least squares solution of an overdetermined system when m > n, and a minimum norm solution of an underdetermined system when m < n. PxGELS uses a QR or LQ factorization of A and also allows A to be replaced by in the statement of the problem (or by if A is complex).
In the general case when we may have -- in other words, A may be rank-deficient -- we seek the minimum norm least squares solution x that minimizes both and .
The LLS driver routines are listed in table 3.3.
All routines allow several right-hand-side vectors b and corresponding solutions x to be handled in a single call, storing these vectors as columns of matrices B and X, respectively. Note, however, that equation 3.1 is solved for each right-hand-side vector independently; this is not the same as finding a matrix X that minimizes .
Table 3.3: Driver routines for linear least squares problems