Next: QR Decomposition with Column Pivoting, Previous: LU Decomposition, Up: Linear Algebra [Index]

A general rectangular *M*-by-*N* matrix *A* has a
*QR* decomposition into the product of an orthogonal
*M*-by-*M* square matrix *Q* (where *Q^T Q = I*) and
an *M*-by-*N* right-triangular matrix *R*,

A = Q R

This decomposition can be used to convert the linear system *A x =
b* into the triangular system *R x = Q^T b*, which can be solved by
back-substitution. Another use of the *QR* decomposition is to
compute an orthonormal basis for a set of vectors. The first *N*
columns of *Q* form an orthonormal basis for the range of *A*,
*ran(A)*, when *A* has full column rank.

- Function:
*int***gsl_linalg_QR_decomp***(gsl_matrix **`A`, gsl_vector *`tau`) This function factorizes the

*M*-by-*N*matrix`A`into the*QR*decomposition*A = Q R*. On output the diagonal and upper triangular part of the input matrix contain the matrix*R*. The vector`tau`and the columns of the lower triangular part of the matrix`A`contain the Householder coefficients and Householder vectors which encode the orthogonal matrix`Q`. The vector`tau`must be of length*k=\min(M,N)*. The matrix*Q*is related to these components by,*Q = Q_k ... Q_2 Q_1*where*Q_i = I - \tau_i v_i v_i^T*and*v_i*is the Householder vector*v_i = (0,...,1,A(i+1,i),A(i+2,i),...,A(m,i))*. This is the same storage scheme as used by LAPACK.The algorithm used to perform the decomposition is Householder QR (Golub & Van Loan, Matrix Computations, Algorithm 5.2.1).

- Function:
*int***gsl_linalg_QR_solve***(const gsl_matrix **`QR`, const gsl_vector *`tau`, const gsl_vector *`b`, gsl_vector *`x`) This function solves the square system

*A x = b*using the*QR*decomposition of*A*held in (`QR`,`tau`) which must have been computed previously with`gsl_linalg_QR_decomp`

. The least-squares solution for rectangular systems can be found using`gsl_linalg_QR_lssolve`

.

- Function:
*int***gsl_linalg_QR_svx***(const gsl_matrix **`QR`, const gsl_vector *`tau`, gsl_vector *`x`) This function solves the square system

*A x = b*in-place using the*QR*decomposition of*A*held in (`QR`,`tau`) which must have been computed previously by`gsl_linalg_QR_decomp`

. On input`x`should contain the right-hand side*b*, which is replaced by the solution on output.

- Function:
*int***gsl_linalg_QR_lssolve***(const gsl_matrix **`QR`, const gsl_vector *`tau`, const gsl_vector *`b`, gsl_vector *`x`, gsl_vector *`residual`) This function finds the least squares solution to the overdetermined system

*A x = b*where the matrix`A`has more rows than columns. The least squares solution minimizes the Euclidean norm of the residual,*||Ax - b||*.The routine requires as input the*QR*decomposition of*A*into (`QR`,`tau`) given by`gsl_linalg_QR_decomp`

. The solution is returned in`x`. The residual is computed as a by-product and stored in`residual`.

- Function:
*int***gsl_linalg_QR_QTvec***(const gsl_matrix **`QR`, const gsl_vector *`tau`, gsl_vector *`v`) This function applies the matrix

*Q^T*encoded in the decomposition (`QR`,`tau`) to the vector`v`, storing the result*Q^T v*in`v`. The matrix multiplication is carried out directly using the encoding of the Householder vectors without needing to form the full matrix*Q^T*.

- Function:
*int***gsl_linalg_QR_Qvec***(const gsl_matrix **`QR`, const gsl_vector *`tau`, gsl_vector *`v`) This function applies the matrix

*Q*encoded in the decomposition (`QR`,`tau`) to the vector`v`, storing the result*Q v*in`v`. The matrix multiplication is carried out directly using the encoding of the Householder vectors without needing to form the full matrix*Q*.

- Function:
*int***gsl_linalg_QR_QTmat***(const gsl_matrix **`QR`, const gsl_vector *`tau`, gsl_matrix *`A`) This function applies the matrix

*Q^T*encoded in the decomposition (`QR`,`tau`) to the matrix`A`, storing the result*Q^T A*in`A`. The matrix multiplication is carried out directly using the encoding of the Householder vectors without needing to form the full matrix*Q^T*.

- Function:
*int***gsl_linalg_QR_Rsolve***(const gsl_matrix **`QR`, const gsl_vector *`b`, gsl_vector *`x`) This function solves the triangular system

*R x = b*for`x`. It may be useful if the product*b' = Q^T b*has already been computed using`gsl_linalg_QR_QTvec`

.

- Function:
*int***gsl_linalg_QR_Rsvx***(const gsl_matrix **`QR`, gsl_vector *`x`) This function solves the triangular system

*R x = b*for`x`in-place. On input`x`should contain the right-hand side*b*and is replaced by the solution on output. This function may be useful if the product*b' = Q^T b*has already been computed using`gsl_linalg_QR_QTvec`

.

- Function:
*int***gsl_linalg_QR_unpack***(const gsl_matrix **`QR`, const gsl_vector *`tau`, gsl_matrix *`Q`, gsl_matrix *`R`) This function unpacks the encoded

*QR*decomposition (`QR`,`tau`) into the matrices`Q`and`R`, where`Q`is*M*-by-*M*and`R`is*M*-by-*N*.

- Function:
*int***gsl_linalg_QR_QRsolve***(gsl_matrix **`Q`, gsl_matrix *`R`, const gsl_vector *`b`, gsl_vector *`x`) This function solves the system

*R x = Q^T b*for`x`. It can be used when the*QR*decomposition of a matrix is available in unpacked form as (`Q`,`R`).

- Function:
*int***gsl_linalg_QR_update***(gsl_matrix **`Q`, gsl_matrix *`R`, gsl_vector *`w`, const gsl_vector *`v`) This function performs a rank-1 update

*w v^T*of the*QR*decomposition (`Q`,`R`). The update is given by*Q'R' = Q (R + w v^T)*where the output matrices*Q'*and*R'*are also orthogonal and right triangular. Note that`w`is destroyed by the update.

- Function:
*int***gsl_linalg_R_solve***(const gsl_matrix **`R`, const gsl_vector *`b`, gsl_vector *`x`) This function solves the triangular system

*R x = b*for the*N*-by-*N*matrix`R`.

- Function:
*int***gsl_linalg_R_svx***(const gsl_matrix **`R`, gsl_vector *`x`) This function solves the triangular system

*R x = b*in-place. On input`x`should contain the right-hand side*b*, which is replaced by the solution on output.

Next: QR Decomposition with Column Pivoting, Previous: LU Decomposition, Up: Linear Algebra [Index]