QR decomposition
1 QR Decomposition
Orthogonal matrix triangularization (QR decomposition) reduces a real matrix with 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:
with the right triangular matrix . One only has then to solve the triangular system , where consists of the first rows of .
The least squares problem is easy to solve with and an orthogonal matrix (here and henceforth is the entire augmented matrix from above). The solution
becomes
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.
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 |