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