Brief
In BM-05 the normal equations and QR gave the same answer. This project finds where they stop agreeing, and builds a fitter that notices before it hands you garbage.
Computers store numbers with about 16 significant digits in float64. Every operation rounds to the nearest storable value, an error of about machine epsilon, . Usually that is harmless. But some problems amplify it. The condition number measures how much: a relative error in the input can become an error of about in the answer. So you lose roughly digits, and when passes the answer can be pure noise.
Polynomial fits are a classic trap. On the columns , , look almost the same, so is badly conditioned. The normal equations make it worse, because forming squares the condition number:
QR works on directly and never squares it. That is why every serious least-squares routine, including numpy.polyfit, avoids the normal equations. (The subscript 2 means the 2-norm version that NumPy reports by default. You compute the 1-norm version, which is easier by hand and tells the same story.)
DATA · generated data
Objectives
Read-only. Log in to update progress.
VICTORY CONDITIONS
- Your condition numbers match numpy.linalg.cond within 1% wherever cond is below 1e13, and your QR residual is no larger than numpy.polyfit at every degree from 1 to 15 (1e-9 relative slack for rounding). Record the worst cond mismatch with `python tools/mlarena.py record BM-06 "<worst cond error %>"`.
- A plot of condition number against degree for X and XᵀX on a log scale, with the line at 1/ε marked.
- The detector fires on the degrees where the normal equations actually fail, and stays quiet on the low degrees where they work.
Side quests
Terms in plain words
- Condition number
- How much a matrix can blow up small errors in its input. A condition number of 1e8 can turn a rounding error in the 16th digit into an error in the 8th.
- Machine epsilon
- The gap between 1 and the next number a float can store. About 2.2e-16 for float64 and 1.2e-7 for float32.
- Numerical stability
- A method is stable if rounding errors stay about as small as the problem's condition number allows, instead of growing on top of it.
- Householder reflection
- A mirror matrix that zeroes everything below one entry of a column. A few of them in a row turn X into R, with less rounding error than Gram-Schmidt.
- Float precision
- float64 keeps about 16 significant digits, float32 about 7, float16 and bfloat16 even fewer. Fewer digits means ill-conditioned problems fail sooner.