87. QR Decomposition
Every matrix with can be factored as:
where:
- is with orthonormal columns (so )
- is upper triangular
If is full column rank, the decomposition is unique up to signs on the diagonal of .
For square (full rank), is a full orthogonal matrix and is square upper triangular.
87.1. Construction via Gram–Schmidt
The columns of are the result of applying Gram–Schmidt orthogonalization to the columns of :
- are the columns of
- are orthonormalized versions
- records the coefficients of each in terms of
Explicitly, for and for .
Example
Apply Gram–Schmidt to columns:
- Project off :
- that, normalized:
87.2. Why it matters
QR is the workhorse for least-squares problems:
Given overdetermined (more equations than unknowns), the least-squares solution
solves the normal equations . Using :
Then back-substitute on the upper-triangular — much more numerically stable than forming directly.
Other uses:
- Eigenvalue computation via the QR algorithm — iteratively factor and update ; converges to a triangular matrix whose diagonal gives the eigenvalues
- Orthonormalizing a basis numerically (Gram–Schmidt is unstable in floating point; Householder QR is much more reliable)
- Solving square systems as an alternative to LU
87.3. Computation methods
- Classical Gram–Schmidt — conceptually clean but numerically unstable
- Modified Gram–Schmidt — small variation, much more stable
- Householder reflections — uses orthogonal reflections, very stable,
- Givens rotations — useful for sparse / structured matrices
87.4. See also
- Gram–Schmidt Process — the orthogonalization underlying QR
- Orthogonal Matrix
- Triangular Matrix
- LU / Cholesky / SVD