Phase 5 - Lesson 5.3
QR Factorization and Least Squares
Orthonormal bases from Gram-Schmidt, why the modified version keeps its orthogonality, and the stable route to regression.
Builds on: 5.1 warned that normal equations square the condition number; QR is the cure.
Leads to: QR drives the eigenvalue algorithm in 5.5 and least-squares regression in Phase 11.
Leads to: QR drives the eigenvalue algorithm in 5.5 and least-squares regression in Phase 11.
Learning Objectives
Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.
- Derive the reduced QR factorization from Gram-Schmidt orthogonalization.
- Explain why classical Gram-Schmidt loses orthogonality and how modified GS fixes it.
- Solve least squares via \(R x = Q^\top b\) and justify its stability over normal equations.
- Implement classical and modified Gram-Schmidt and measure the orthogonality error.
- Interpret Householder QR as the backward-stable production method.
Key Vocabulary
- QR factorization
- Writing \(A=QR\) with \(Q\) orthonormal columns and \(R\) upper-triangular.
- Gram-Schmidt
- Sequentially subtracting projections onto prior vectors to orthonormalize a basis.
- Loss of orthogonality
- Rounding makes classical GS columns drift from orthogonal; measured by \(\lVert Q^\top Q-I\rVert\).
- Least squares
- Minimizing \(\lVert Ax-b\rVert_2\) over \(x\); solved by \(Rx=Q^\top b\).
- Householder reflector
- An orthogonal matrix \(H=I-2vv^\top/v^\top v\) that zeros a column below the diagonal, giving stable QR.
- Normal equations
- The system \(A^\top A x = A^\top b\); correct but conditioned like \(\kappa(A)^2\).
Intuition & Motivation
Intuition
Least squares asks: project \(b\) onto the column space of \(A\). If we had an orthonormal basis \(Q\) for that space the projection would be trivial - just \(QQ^\top b\). QR builds exactly that basis, and the triangular \(R\) records how the original columns relate to it. The subtlety is arithmetic: classical Gram-Schmidt subtracts all projections at once and lets rounding accumulate, so the columns quietly lose orthogonality. Modified Gram-Schmidt subtracts them one at a time against the freshly updated vector, and stays orthogonal to working precision.
Reduced QR from Gram-Schmidt
Given columns \(a_1,\dots,a_n\), set \(q_1=a_1/\lVert a_1\rVert\) and, for each new column, subtract its projection onto the span of the previous \(q\)’s, then normalize:
\[q_k = \frac{a_k-\sum_{j\lt k}(q_j^\top a_k)q_j}{\big\lVert a_k-\sum_{j\lt k}(q_j^\top a_k)q_j\big\rVert},\qquad A=QR,\ \ R_{jk}=q_j^\top a_k.\] (5.4)
Theorem - Least squares via QR
If \(A=QR\) (reduced, \(Q^\top Q=I\)) has full column rank, the least-squares minimizer of \(\lVert Ax-b\rVert_2\) solves the triangular system \(Rx=Q^\top b\), with conditioning \(\kappa(A)\) - not \(\kappa(A)^2\).
Proof
Since \(Q\) has orthonormal columns, \(\lVert Ax-b\rVert^2=\lVert QRx-b\rVert^2\). Split \(b\) into \(QQ^\top b\) (in the column space) plus an orthogonal remainder; the cross term vanishes, leaving \(\lVert Rx-Q^\top b\rVert^2 + \text{const}\), minimized at \(Rx=Q^\top b\). ∎
Worked Example - Why modified Gram-Schmidt survives rounding
1
Take nearly parallel columns, e.g. the Läuchli matrix with a tiny \(\varepsilon\) so all columns share a dominant direction.
2
Classical GS forms every \(q_j^\top a_k\) against the original \(a_k\); the cancellation leaves rounding noise, and \(q_2,q_3\) end up non-orthogonal.
3
Modified GS updates \(a_k\) immediately after subtracting each projection, so later inner products use the already-orthogonalized vector.
4
Measured by \(\lVert Q^\top Q-I\rVert\), classical GS can be \(O(\kappa\epsilon_{\text{mach}})\) off while MGS stays near \(\epsilon_{\text{mach}}\).
Interactive: classical vs modified Gram-Schmidt
Build both and print the orthogonality error \(\lVert Q^\top Q-I\rVert_\infty\) on an ill-conditioned matrix. The gap is the whole point.
Common Mistakes to Avoid
- Using classical Gram-Schmidt in finite precision and trusting the resulting \(Q\) as orthonormal.
- Solving least squares via \(A^\top A\) when \(A\) is ill-conditioned - QR keeps \(\kappa(A)\), not \(\kappa(A)^2\).
- Forgetting that reduced QR needs full column rank; a rank-deficient \(A\) needs SVD/pivoted QR.
- Confusing the reduced ( \(m\times n\) ) and full ( \(m\times m\) ) \(Q\).
Quant Practitioner Tips
- For production QR use Householder or Givens; both are unconditionally backward stable.
- Reuse \(Q^\top b\) for warm-starting when only \(b\) changes.
- MGS suffices when you also need the columns of \(Q\) explicitly (e.g. Arnoldi/GMRES).
- Report \(\lVert Q^\top Q-I\rVert\) as a sanity check when hand-coding orthogonalization.
Knowledge Check
Q1 Medium
Least squares via \(Rx=Q^\top b\) is preferred over the normal equations mainly because:
Q2 Medium
The single algorithmic difference between classical and modified Gram-Schmidt is:
Q3 Easy
For a full-rank \(A=QR\) (reduced), the least-squares residual \(b-Ax^\star\) is:
Practical Exercise
Given \(A=QR\) (reduced), show that the least-squares solution satisfies \(Rx=Q^\top b\) and that the minimized residual norm is \(\lVert(I-QQ^\top)b\rVert\).
▶ Show full solution
Write \(\lVert Ax-b\rVert^2=\lVert QRx-b\rVert^2\). Insert \(b=QQ^\top b+(I-QQ^\top)b\), where the second term is orthogonal to \(\mathrm{range}(Q)\).
Then \(\lVert QRx-QQ^\top b\rVert^2+\lVert(I-QQ^\top)b\rVert^2\). Only the first term depends on \(x\) and is minimized (to zero) by \(Rx=Q^\top b\); the leftover is the residual norm \(\lVert(I-QQ^\top)b\rVert\).
After the reveal, answer for yourself: What happens to this argument if \(A\) loses column rank?
Lesson Summary
QR builds an orthonormal basis for \(\mathrm{range}(A)\) and reduces least squares to the triangular solve \(Rx=Q^\top b\), keeping conditioning at \(\kappa(A)\). Classical Gram-Schmidt loses orthogonality under rounding; modified GS - and, in production, Householder QR - stays orthonormal to working precision.
Retrieval Practice
Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.
▶ Show retrieval prompts & answers
Q: Why does QR beat the normal equations for least squares?
A: QR preserves the condition number \(\kappa(A)\), whereas \(A^\top A\) squares it to \(\kappa(A)^2\), doubling digits lost.
A: QR preserves the condition number \(\kappa(A)\), whereas \(A^\top A\) squares it to \(\kappa(A)^2\), doubling digits lost.
Q: What is the one change from classical to modified Gram-Schmidt?
A: MGS subtracts each projection against the running (already partly orthogonalized) vector instead of the original column, avoiding accumulated rounding.
A: MGS subtracts each projection against the running (already partly orthogonalized) vector instead of the original column, avoiding accumulated rounding.
Completion Checklist
- I can explain the core ideas in my own words
- I worked the derivations/examples by hand
- I completed the interactive workbench(es)
- I passed the knowledge check
Confidence / mastery rating
Personal notes
Source References
This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.
- Numerical Linear Algebra (Trefethen & Bau, SIAM, 1997) foundational - Lec 7–11,18 - Lectures 7–11, 18–19: Gram-Schmidt, Householder QR, least squares.
- Linear Algebra Done Right (Sheldon Axler, 4th ed., 2024) current - Ch. 6 - Orthonormal bases and orthogonal projections behind least squares.