next up previous contents index
Next: Standard Eigenvalue and Singular Up: Driver Routines Previous: Linear Equations

Linear Least Squares Problems

   

The linear least squares (LLS) problem  is:
 equation988
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, tex2html_wrap_inline12690 and tex2html_wrap_inline12692. 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 tex2html_wrap_inline12696, 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 tex2html_wrap_inline12704, 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 tex2html_wrap_inline12706 -- 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 tex2html_wrap_inline12722 in the statement of the problem (or by tex2html_wrap_inline12724 if A is complex).

In the general case when we may have tex2html_wrap_inline12728 -- in other words, A may be rank-deficient  -- we seek the minimum norm least squares solution  x that minimizes both tex2html_wrap_inline12704 and tex2html_wrap_inline12736.

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 tex2html_wrap_inline12748.

  table1027
Table 3.3: Driver routines for linear least squares problems


next up previous contents index
Next: Standard Eigenvalue and Singular Up: Driver Routines Previous: Linear Equations

Susan Blackford
Tue May 13 09:21:01 EDT 1997