QR decomposition


1 QR Decomposition

Orthogonal matrixMathworldPlanetmath triangularization (QR decompositionMathworldPlanetmath) reduces a real m×n matrix A with mn 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[R0]

with the n×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 Axb is easy to solve with A=QR and Q an orthogonal matrix (here and henceforth R is the entire m×n augmented matrix from above). The solution

x=(ATA)-1ATb

becomes

x=(RTQTQR)-1RTQTb=(RTR)-1RTQTb=R-1QTb

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

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