QR decomposition

1 QR Decomposition

Orthogonal matrix  triangularization (QR decomposition  ) reduces a real $m\times n$ matrix $A$ with $m\geq 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 $Q$ will triangularize the given matrix:

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

with the $n\times n$ right triangular matrix $R$. One only has then to solve the triangular system $Rx=Pb$, where $P$ consists of the first $n$ rows of $Q$.

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

 $x=(A^{T}A)^{-1}A^{T}b$

becomes

 $x=(R^{T}Q^{T}QR)^{-1}R^{T}Q^{T}b=(R^{T}R)^{-1}R^{T}Q^{T}b=R^{-1}Q^{T}b$

This is a matrix-vector multiplication $Q^{T}b$, followed by the solution of the triangular system $Rx=Q^{T}b$ by back-substitution. The QR factorization saves us the formation of $A^{T}A$ 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.

References

• 1 The Data Analysis Briefbook. http://rkb.home.cern.ch/rkb/titleA.htmlhttp://rkb.home.cern.ch/rkb/titleA.html
 Title QR decomposition Canonical name QRDecomposition Date of creation 2013-03-22 12:06:04 Last modified on 2013-03-22 12:06:04 Owner akrowne (2) Last modified by akrowne (2) Numerical id 8 Author akrowne (2) Entry type Definition Classification msc 65F25 Classification msc 15A23 Synonym QR factorization Synonym QR-decomposition Synonym QR-factorization Related topic LUDecomposition Related topic GramSchmidtOrthogonalization