Brief
QR factorisation writes A = QR, with Q orthogonal (its columns are perpendicular unit vectors) and R upper triangular. It is the stable way to solve least squares. Implement classical and modified Gram-Schmidt (build Q one column at a time by subtracting projections; the modified version subtracts them one at a time, which loses less accuracy). Implement Householder QR with implicit Q (zero out each column below the diagonal with a reflection, and store the reflections instead of Q) and Givens QR (zero out one entry at a time with rotations). Also implement the normal equations (solve A^T A x = A^T b) via Cholesky. Run them on synthetic matrices with kappa from 1e2 to 1e14 (kappa is the condition number: how much the matrix can amplify errors) and on all 11 NIST StRD certified linear-regression problems (reference problems whose answers are certified to many digits), including Filip and Longley. Measure loss of orthogonality and digits of accuracy.
VICTORY CONDITIONS
- Householder within 1 digit of LAPACK on all 11 StRD problems. Measured orthogonality-loss slopes match eps*kappa (MGS) and eps*kappa^2 (CGS) within 10x, where eps is machine epsilon. Documented failure of the normal equations on Filip. (||Q^T Q - I|| vs kappa (how far the computed Q is from orthogonal); log relative error (correct digits) against NIST certified values).
- A public repository with a README that shows your result and how to reproduce it.
Terms in plain words
- QR factorisation
- Writing a matrix as an orthogonal matrix Q times an upper-triangular matrix R, which makes least squares easy and stable.
- Gram-Schmidt (CGS / MGS)
- Building orthogonal vectors by subtracting projections onto earlier ones; classical (CGS) and modified (MGS) differ in order of operations and in how fast orthogonality is lost.
- Householder reflection
- A mirror-like orthogonal transformation that zeros out all entries of a column below the diagonal in one step.
- Normal equations
- Solving least squares through A^T A x = A^T b; simple, but it squares the condition number and so loses twice as many digits.
- NIST StRD
- Statistical Reference Datasets from the US standards institute, with answers certified to high precision for testing software.
Why it rates ★★☆☆☆
Core numerical linear algebra, done rigorously against certified data. It is still a known experiment.