Computational Advantages of QR Decomposition
You'll learn why QR decomposition is often preferred over normal equations for solving least squares problems in real-world computing.
The Core Idea
When solving least squares problems like Ax = b, you have two main approaches:
- Normal Equations: Solve A^T Ax = A^T b directly
- QR Decomposition: Factor A = QR and solve Rx = Q^T b
While both give the same mathematical answer in theory, they behave very differently on actual computers where precision is limited.
Why QR Wins in Practice
Numerical Stability
The normal equations require computing A^T A, which squares the condition number of your matrix. Think of it like photocopying a photocopy—errors get magnified. If A has small singular values (near-zero directions), A^T A makes them microscopic, causing catastrophic rounding errors.
QR decomposition avoids this squaring entirely. The orthogonal matrix Q preserves lengths and angles perfectly, keeping the problem well-conditioned. It's like working with the original document instead of a degraded copy.
Condition Number Impact
- Normal equations: condition number of A^T A ≈ κ(A)²
- QR method: condition number stays ≈ κ(A)
When κ(A) = 1000, normal equations work with κ ≈ 1,000,000—potentially losing 6 more decimal digits of accuracy!
Efficiency Considerations
While computing QR requires more operations than forming A^T A for very small matrices, the stability gains almost always justify the cost. For tall, skinny matrices (many rows, few columns)—common in data fitting—QR is particularly efficient.
Key Takeaway: QR decomposition provides superior numerical stability by avoiding the condition number squaring inherent in normal equations, making it the preferred method for least squares problems in practical applications where precision matters.