Computing QR: Step-by-Step Algorithm
What You'll Learn
You'll learn the explicit, step-by-step procedure to compute the QR decomposition of any matrix using the Gram-Schmidt process.
The Core Algorithm
The QR decomposition factors a matrix A into A = QR, where Q is an orthogonal matrix (with orthonormal columns) and R is upper triangular. Here's the complete algorithm:
Step 1: Apply Gram-Schmidt to the Columns of A
Let A = [a₁ a₂ ... aₙ] be your matrix with columns a₁, a₂, etc.
- Start with u₁ = a₁
- For each subsequent column k = 2 to n:
- Compute uₖ = aₖ - proj_{u₁}(aₖ) - proj_{u₂}(aₖ) - ... - proj_{uₖ₋₁}(aₖ)
- Each projection is: proj_{uⱼ}(aₖ) = (aₖ · uⱼ / uⱼ · uⱼ)uⱼ
Step 2: Normalize to Get Q
Divide each orthogonal vector by its length:
- qₖ = uₖ / ||uₖ||
- Form Q = [q₁ q₂ ... qₙ]
Step 3: Compute R
The matrix R contains the "ingredients" needed to reconstruct A from Q:
- R is upper triangular: Rᵢⱼ = 0 when i > j
- Diagonal entries: Rₖₖ = ||uₖ|| (the normalizing factors)
- Upper entries: Rᵢⱼ = qᵢ · aⱼ for i < j
Think of it this way: Q holds your orthonormal basis vectors, and R records how much of each original column lies in each basis direction.
Example Pattern for a 3×3 Matrix
After Gram-Schmidt and normalization, compute R entry-by-entry using dot products between Q's columns and A's original columns.
Key Takeaway: The QR algorithm is just Gram-Schmidt (orthogonalize → normalize) plus bookkeeping the transformation coefficients in the upper-triangular matrix R.