QR Decomposition

Orthogonal matrix triangularization (QR decomposition) reduces a real $m \times n$ matrix with $m \ge n$ and full rank to a much simpler form. It guarantees numerical stability by minimizing errors caused by machine roundoffs. A suitably chosen orthogonal matrix will triangularize the given matrix:

$\displaystyle A = Q \begin{bmatrix}R \\ 0 \end{bmatrix}$

with the $n \times n$ right triangular matrix . One only has then to solve the triangular system , where consists of the first rows of .

The least squares problem $Ax \approx b$ is easy to solve with and an orthogonal matrix (here and henceforth is the entire $m \times n$ augmented matrix from above). The solution

$\displaystyle x = (A^TA)^{-1} A^Tb$

becomes

$\displaystyle x = (R^TQ^TQR)^{-1}R^TQ^Tb = (R^TR)^{-1}R^TQ^Tb = R^{-1}Q^Tb$

This is a matrix-vector multiplication , followed by the solution of the triangular system by back-substitution. The QR factorization saves us the formation of and the solution of the normal equations.

Many different methods exist for the QR decomposition, e.g. the Householder transformation, the Givens rotation, or the Gram-Schmidt decomposition.

Bibliography

1: The Data Analysis Briefbook. http://rkb.home.cern.ch/rkb/titleA.html

"QR decomposition" is owned by akrowne.

(view preamble)

Other names:

QR factorization, QR-decomposition, QR-factorization

Keywords:

matrix factorization

Log in to rate this entry.
(view current ratings)

Cross-references: Gram-Schmidt decomposition, Givens rotation, Householder transformation, normal equations, multiplication, solution, entire, least squares problem, rows, right triangular matrix, machine, rank, matrix, real, orthogonal matrix
There are 6 references to this entry.

This is version 4 of QR decomposition, born on 2002-01-04, modified 2006-04-24.
Object id is 1207, canonical name is QRDecomposition.
Accessed 26239 times total.

Classification:

AMS MSC:	15A23 (Linear and multilinear algebra; matrix theory :: Factorization of matrices)
	65F25 (Numerical analysis :: Numerical linear algebra :: Orthogonalization)

Pending Errata and Addenda

None.[ View all 1 ]

Discussion

forum policy

No messages.

Interact