Javascript required
Skip to content Skip to sidebar Skip to footer
Home / Find the Least-squares Solution of the Linear System

Find the Least-squares Solution of the Linear System

next up previous contents index
Next: Generalized Linear Least Squares Up: Driver Routines Previous: Linear Equations Contents Index


Linear Least Squares (LLS) Problems

The linear least squares problem is:

\begin{displaymath} \mathop{\mbox{minimize }}_{x} \Vert b - A x {\Vert}_2 \end{displaymath} (2.1)

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 $m \ge n$ and $\mbox{rank}(A) = n$, and in this case the solution to problem (2.1) is unique, and the problem is also referred to as finding a least squares solution to an overdetermined system of linear equations.

When m < n and $\mbox{rank}(A) = m$, there are an infinite number of solutions x which exactly satisfy b-Ax=0. In this case it is often useful to find the unique solution x which minimizes |x|2, and the problem is referred to as finding a minimum norm solution to an underdetermined system of linear equations.

The driver routine xGELS solves problem (2.1) on the assumption that $\mbox{rank}(A) = \min(m,n)$ -- 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. xGELS uses a QR or LQ factorization of A, and also allows A to be replaced by A T in the statement of the problem (or by A H if A is complex).

In the general case when we may have $\mbox{rank}(A) < \min(m,n)$ -- in other words, A may be rank-deficient -- we seek the minimum norm least squares solution x which minimizes both |x|2 and $\Vert b - Ax{\Vert}_2$.

The driver routines xGELSX, xGELSY, xGELSS, and xGELSD, solve this general formulation of problem 2.1, allowing for the possibility that A is rank-deficient; xGELSX and xGELSY use a complete orthogonal factorization of A, while xGELSS uses the singular value decomposition of A, and xGELSD uses the singular value decomposition of A with an algorithm based on divide and conquer.

The subroutine xGELSY is a faster version of xGELSX, but requires more workspace since it calls blocked algorithms to perform the complete orthogonal factorization. xGELSX has been retained for compatibility with Release 2.0 of LAPACK, but we omit references to this routine in the remainder of this users' guide.

The subroutine xGELSD is significantly faster than its older counterpart xGELSS, especially for large problems, but may require somewhat more workspace depending on the matrix dimensions.

The LLS driver routines are listed in Table 2.3.

All four 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 problem 2.1 is solved for each right hand side vector independently; this is not the same as finding a matrix X which minimizes $\Vert B - A X \Vert _2$.

Table 2.3: Driver routines for linear least squares problems
Operation Single precision Double precision
real complex real complex
solve LLS using QR or LQ factorization SGELS CGELS DGELS ZGELS
solve LLS using complete orthogonal factorization SGELSY CGELSY DGELSY ZGELSY
solve LLS using SVD SGELSS CGELSS DGELSS ZGELSS
solve LLS using divide-and-conquer SVD SGELSD CGELSD DGELSD ZGELSD

next up previous contents index
Next: Generalized Linear Least Squares Up: Driver Routines Previous: Linear Equations Contents Index
Susan Blackford
1999-10-01

Find the Least-squares Solution of the Linear System

Source: https://www.netlib.org/lapack/lug/node27.html