What Is QR Decomposition?
QR decomposition (also called QR factorization) expresses a matrix A as the product of an orthogonal matrix Q and an upper triangular matrix R: A = QR. This factorization is fundamental in numerical linear algebra and has many important applications.
The Gram-Schmidt Process
The classical Gram-Schmidt process converts a set of linearly independent vectors into an orthonormal set. Given the columns of A as vectors a1, a2, ..., the process constructs orthogonal vectors u1, u2, ... and then normalizes them to get the columns of Q.
Matrix Q (Orthogonal)
Columns are orthonormal: Q^T Q = I. Preserves vector lengths and angles.
Matrix R (Upper Triangular)
All entries below the diagonal are zero. Diagonal entries are the norms.
Verification
Multiply Q and R to recover the original matrix A.
Applications of QR Decomposition
- Solving Linear Systems: QR decomposition provides a numerically stable way to solve Ax = b.
- Eigenvalue Computation: The QR algorithm iteratively applies QR decomposition to find eigenvalues.
- Least Squares: QR decomposition gives a stable method for linear least-squares problems.
- Principal Component Analysis: Used in computing PCA for dimensionality reduction.
Gram-Schmidt vs Householder
While the classical Gram-Schmidt process is intuitive, it can suffer from numerical instability. The modified Gram-Schmidt process and Householder reflections are more numerically stable alternatives used in practice. This calculator uses the classical Gram-Schmidt process for educational purposes.
Properties
- Every real matrix with linearly independent columns has a QR decomposition.
- Q is orthogonal: its inverse equals its transpose.
- The diagonal entries of R are the norms of the orthogonalized vectors.
- If A is square and invertible, the QR decomposition is unique (with positive diagonal entries in R).