QR Decomposition

Visualize the decomposition of a matrix into orthogonal and upper triangular components.

Concept Overview

QR Decomposition (or QR factorization) is a linear algebra method that decomposes a matrix A into a product A = QR of an orthogonal matrix Q and an upper triangular matrix R. It is a fundamental algorithm for computing eigenvalues, solving linear least squares problems, and solving systems of linear equations.

Mathematical Definition

Any real m × n matrix A with full column rank (m ≥ n) may be decomposed as:

A = Q × R

Where (full QR):

A is an m × n matrix with m ≥ n and linearly independent columns.
Q is an m × m orthogonal matrix (Q^T × Q = I). Its first n columns form an orthonormal basis for the column space of A.
R is an m × n upper triangular matrix (only the top n × n block is non-zero). If A has full column rank, the diagonal entries of the top block are strictly positive.

Key Concepts

Gram-Schmidt Process: The classical way to compute the QR decomposition is by applying the Gram-Schmidt process to the columns of A. The resulting orthonormal vectors form the columns of Q, and the projection coefficients form the upper triangular matrix R.
Householder Reflections & Givens Rotations: While Gram-Schmidt is intuitive, in practice, QR decomposition is often computed using Householder reflections or Givens rotations for better numerical stability. These methods construct Q as a sequence of orthogonal transformations.
Solving Systems: To solve Ax = b, we can write QRx = b, which implies Rx = Q^Tb. Since R is upper triangular, this can be solved efficiently using back substitution.

Historical Context

The development of QR decomposition is closely tied to the QR algorithm for calculating eigenvalues, proposed independently by John G. F. Francis and Vera N. Kublanovskaya in 1961. This algorithm iteratively computes the QR decomposition of a matrix and multiplies the factors in reverse order, remarkably converging to a triangular form that reveals the eigenvalues. It is considered one of the top 10 algorithms of the 20th century.

Real-world Applications

Linear Least Squares: QR decomposition is the standard, numerically stable way to solve overdetermined systems of equations (curve fitting, data regression) without computing the condition-worsening normal equations (A^TA).
Eigenvalue Computation: The QR algorithm is the foundation of most modern software for finding eigenvalues and eigenvectors of matrices.
Signal Processing: Used in adaptive filtering and beamforming, where systems of equations must be solved rapidly as new data arrives.

Related Concepts

Gram-Schmidt Process: The fundamental algorithm that orthogonalizes a set of vectors, directly yielding the Q and R matrices.
LU Decomposition: Another factorization method, often faster but less numerically stable than QR for certain problems.
Least Squares Approximation: Finding the best fit for an overdetermined system, commonly solved using QR.

QR Decomposition