# Least Squares and Eigenvalue Problem Routines

This section includes descriptions of LAPACK computational routines and driver routines for solving linear least squares problems, eigenvalue and singular value problems, and performing a number of related computational tasks. For a full reference on LAPACK routines and related information see [LUG].

**Least Squares Problems.** A typical *least squares problem* is as follows: given a matrix `A` and a vector `b`, find the vector `x` that minimizes the sum of squares `Σ`

or, equivalently, find the vector _{i}((`Ax`)_{i} - `b`_{i})^{2}`x` that minimizes the 2-norm `||`

.`Ax` - `b`||_{2}

In the most usual case, `A` is an `m`-by-`n` matrix with `m` ≥ `n` and `rank(`

. This problem is also referred to as finding the `A`) = `n`*least squares solution* to an *overdetermined* system of linear equations (here we have more equations than unknowns). To solve this problem, you can use the `QR` factorization of the matrix A (see QR Factorization).

If

and `m` < `n``rank(`

, there exist an infinite number of solutions `A`) = `m``x` which exactly satisfy

, and thus minimize the norm `Ax` = `b``||`

. In this case it is often useful to find the unique solution that minimizes `Ax` - `b`||_{2}`||`

. This problem is referred to as finding the `x`||_{2}*minimum-norm solution* to an *underdetermined* system of linear equations (here we have more unknowns than equations). To solve this problem, you can use the `LQ` factorization of the matrix `A` (see LQ Factorization).

In the general case you may have a *rank-deficient least squares problem*, with `rank(`

: find the `A`)< min(`m`, `n`)*minimum-norm least squares solution* that minimizes both `||`

and `x`||_{2}`||`

. In this case (or when the rank of A is in doubt) you can use the `Ax` - `b`||^{2}`QR` factorization with pivoting or *singular value decomposition* (see Singular Value Decomposition).

**Eigenvalue Problems.** The eigenvalue problems (from German `eigen` "own") are stated as follows: given a matrix `A`, find the *eigenvalues* λ and the corresponding *eigenvectors* `z` that satisfy the equation

(right eigenvectors `Az` = λ`z``z`)

or the equation

(left eigenvectors `z`^{H}`A` = λ`z`^{H}`z`).

If `A` is a real symmetric or complex Hermitian matrix, the above two equations are equivalent, and the problem is called a *symmetric* eigenvalue problem. Routines for solving this type of problems are described in the topic Symmetric Eigenvalue Problems.

Routines for solving eigenvalue problems with nonsymmetric or non-Hermitian matrices are described in the topic Nonsymmetric Eigenvalue Problems.

The library also includes routines that handle *generalized symmetric-definite eigenvalue problems*: find the eigenvalues λ and the corresponding eigenvectors `x` that satisfy one of the following equations:

, `Az` = λ`Bz`

, or `ABz` = λz

,`BAz` = λz

where `A` is symmetric or Hermitian, and `B` is symmetric positive-definite or Hermitian positive-definite. Routines for reducing these problems to standard symmetric eigenvalue problems are described in the topic Generalized Symmetric-Definite Eigenvalue Problems.

To solve a particular problem, you usually call several computational routines. Sometimes you need to combine the routines of this chapter with other LAPACK routines described in "LAPACK Routines: Linear Equations" as well as with BLAS routines described in "BLAS and Sparse BLAS Routines".

For example, to solve a set of least squares problems minimizing `||`

for all columns `Ax` - `b`||^{2}`b` of a given matrix `B` (where `A` and `B` are real matrices), you can call ?geqrf to form the factorization

, then call ?ormqr to compute `A` = `QR`

and finally call the BLAS routine ?trsm to solve for `C` = `Q`^{H}`B``X` the system of equations

.`RX` = `C`

Another way is to call an appropriate driver routine that performs several tasks in one call. For example, to solve the least squares problem the driver routine ?gels can be used.

**Parent topic:**LAPACK Routines