Solving Linear Systems Using QR
What You'll Learn
You'll learn how to solve the linear system Ax = b efficiently by using QR decomposition to transform it into a simpler triangular system.
The Core Idea
When you have a square, invertible matrix A, you can decompose it as A = QR where Q is orthogonal and R is upper triangular. This transforms your original problem into something much easier to solve.
Here's how it works:
Starting with Ax = b, substitute the QR decomposition:
QRx = b
Since Q is orthogonal, Q^T Q = I. Multiply both sides by Q^T:
Q^T QRx = Q^T b
This simplifies to:
Rx = Q^T b
Now you have an upper triangular system! Upper triangular systems are trivial to solve using back substitution — you start from the bottom row and work your way up.
Why This Matters
Think of it like converting a tough lock into an easier one. Instead of solving Ax = b directly (which might require Gaussian elimination), you:
- Compute Q^T b (just matrix-vector multiplication)
- Solve Rx = Q^T b by back substitution (fast and stable)
This approach is particularly valuable because:
- It's numerically stable
- It leverages the structure you've already computed (the QR decomposition)
- Back substitution on triangular systems is computationally cheap
The Algorithm
- Decompose A = QR using Gram-Schmidt
- Compute c = Q^T b
- Solve Rx = c by back substitution
Key Takeaway: QR decomposition transforms Ax = b into the triangular system Rx = Q^T b, which you solve efficiently using back substitution, providing a numerically stable alternative to Gaussian elimination.