Qr DecompositionEdit
QR decomposition is a foundational factorization in numerical linear algebra that expresses a matrix A as A = Q R, where Q is orthogonal (Q^T Q = I) and R is upper triangular. This split is powerful because multiplying by an orthogonal matrix preserves norms and angles, which makes QR decomposition a stable and practical tool for solving linear systems and for computing least-squares fits. In real-world computation, it helps avoid the squaring of errors that comes with forming A^T A, and it aligns well with modern hardware and software libraries. For context, see linear algebra and least squares.
Historically, QR decomposition grew out of Gram-Schmidt orthogonalization, which builds an orthonormal basis step by step. In finite-precision arithmetic, classical Gram-Schmidt can accumulate rounding errors, so more stable variants were developed, notably Householder reflections and Givens rotations. These approaches prioritize backward stability and robustness, qualities that are prized in engineering applications and critical software. For readers who want the lineage, see Gram-Schmidt process, Householder transformation, and Givens rotation. In practical software, routines implementing QR factorization are common in numerical libraries like LAPACK.
QR decomposition is central to many computational tasks. To solve A x ≈ b in a least-squares sense, one computes x from Q^T b and R, exploiting the triangular structure of R. It also plays a key role in the QR algorithm for eigenvalue computations, where repeated QR factorizations reveal the spectrum of a matrix. In applied settings, QR decomposition is used in linear regression, signal processing, control theory, and computer graphics, among other fields. The economy or thin QR factorization is often employed for large problems to reduce memory usage while preserving the essential algebraic properties.
Algorithms
- Classical Gram-Schmidt: builds Q by orthogonalizing column vectors of A, then forms R as the projection coefficients. This method is simple but numerically unstable for ill-conditioned A.
- Modified Gram-Schmidt: a reorganization that improves numerical behavior by re-orthogonalizing in a more careful order; more stable than the classical variant but still sensitive to conditioning.
- Householder QR: uses reflections to annihilate subdiagonal elements, producing a robust and widely used implementation in software such as LAPACK; typically the standard choice for general dense matrices.
- Givens rotations: apply plane rotations to zero out individual elements, offering great stability and particular advantages for sparse matrices where zeroing occurs in a structured way.
- Pivoting: column pivoting or row pivoting can be incorporated to enhance stability in some applications, yielding a factorization A P = Q R that is more reliable when columns vary greatly in scale.
- Economic (thin) QR: for m × n matrices with m ≥ n, computes Q with orthonormal columns and R ∈ R^{n×n}, reducing memory usage while retaining the essential factors.
Numerical considerations and performance vary by method. Householder-based QR generally provides strong backward stability and good performance on modern hardware, while Givens rotations can be advantageous for sparse matrices or when selectively zeroing elements is important. The choice of method often reflects a balance between numerical stability, memory footprint, and the characteristics of the target matrix.
Properties and implications
- Orthogonality of Q (Q^T Q = I) ensures that QR factorization does not magnify the data’s norm, contributing to numerical stability in downstream computations.
- R is upper triangular, so solving R x = y is straightforward via back substitution.
- For ill-conditioned A, QR factorization remains more stable than naive elimination methods that form A^T A, which can amplify rounding errors.
- The factorization is intimately connected to other matrix decompositions and linear-algebra workflows, including eigenvalues computations via the QR algorithm and regression analyses in linear regression.
Applications and practical considerations
- In engineering and data analysis, QR decomposition provides a dependable path to least-squares solutions, especially when data are large or noisy.
- In software practice, robust QR implementations underlie many linear-algebra toolkits and numerical libraries, making QR a mainstream workhorse in scientific computing.
- For sparse or structured matrices, tailored variants using Givens rotations or sparse Householder reflections can offer both speed and memory efficiency.