QR Decomposition

QR decomposition is a fundamental matrix factorization technique that decomposes a matrix into the product of an orthogonal matrix (Q) and an upper triangular matrix (R). This decomposition is widely used in numerical linear algebra, playing a critical role in solving linear systems, least squares problems, and eigenvalue computations. The implementation typically involves functions like `qr()` in MATLAB or similar linear algebra libraries.

### 1. Householder Transformations Householder transformations achieve QR decomposition through a series of reflection operations. The core idea utilizes reflection matrices (Householder matrices) to progressively transform column vectors into upper triangular form. This method offers high computational efficiency and excellent numerical stability, making it suitable for dense matrices. Code implementation involves generating Householder vectors and applying them to zero out subdiagonal elements column by column.

### 2. Givens Rotations Givens rotations employ a sequence of plane rotations to eliminate off-diagonal elements incrementally, eventually yielding the R matrix. Compared to Householder transformations, Givens rotations are particularly advantageous for sparse or banded matrices since rotations can be applied selectively to nonzero elements, reducing computational overhead. Algorithm implementation requires calculating rotation angles and updating only affected matrix entries.

### 3. Classical Gram-Schmidt Orthogonalization Gram-Schmidt orthogonalization provides the most intuitive QR decomposition approach by sequentially orthogonalizing and normalizing matrix column vectors to construct the Q matrix. However, due to error accumulation in floating-point arithmetic, the classical method may suffer from loss of orthogonality, leading to numerical instability. Implementation involves explicit projection and normalization operations for each vector.

### 4. Modified Gram-Schmidt Orthogonalization The modified Gram-Schmidt method improves numerical stability over the classical version by re-orthogonalizing processed vectors to reduce error accumulation. Although computationally more expensive, the modified approach often yields better numerical results. Code implementation requires additional orthogonalization steps but maintains better orthogonality in Q.

### Application Scenarios Comparison Householder: Ideal for large-scale dense matrices with high computational efficiency and stability. Givens: Suitable for sparse or structured matrices offering greater flexibility. Gram-Schmidt (especially modified): Appropriate for small-to-medium matrices or when explicit Q matrix computation is required.

Different QR decomposition implementations present distinct trade-offs, and selecting the appropriate method depends on matrix characteristics and computational requirements of practical problems. Common libraries like LAPACK provide optimized implementations for each approach.