← All Base Form Math projects
BM-06NOT STARTEDBASE FORM · LINEAR ALGEBRAMATHPYTHON

Fit-explosion detector

A curve fitter that warns you before it lies: watch normal equations fall apart on a degree-15 polynomial, then rescue the fit with QR.

EST.5 h
REWARD+100 XP
AFTERoriginal

ML-ARENA BENCHMARKS

YOUR NUMBER VS THE INDUSTRY'S
METRICINDUSTRYMINE
condition numbers and fit error
GOAL · cond within 1%; QR error ≤ polyfit error
numpy.linalg.cond and numpy.polyfit—
no results yet
YOUR RESULTS

Your recorded results appear here.

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, ε≈2.2×10−16\varepsilon \approx 2.2 \times 10^{-16}. Usually that is harmless. But some problems amplify it. The condition number κ(A)\kappa(A) measures how much: a relative error δ\delta in the input can become an error of about κ(A) δ\kappa(A)\,\delta in the answer. So you lose roughly log⁡10κ(A)\log_{10}\kappa(A) digits, and when κ(A)\kappa(A) passes 1/ε1/\varepsilon the answer can be pure noise.

Polynomial fits are a classic trap. On [0,1][0, 1] the columns x12x^{12}, x13x^{13}, x14x^{14} look almost the same, so XX is badly conditioned. The normal equations make it worse, because forming X⊤XX^\top X squares the condition number:

κ2(X⊤X)=κ2(X)2\kappa_2(X^\top X) = \kappa_2(X)^2

QR works on XX 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.)

EXPECTEDFig. 1
1 1e6 1e12 1e18 1e24 1 5 10 15 polynomial degree 1/ε ≈ 4.5e15: results can be pure noise cond(X) cond(XᵀX) = cond(X)²
Condition numbers for 100 points on [0, 1]. Squaring pushes XᵀX past 1/ε between degree 10 and 11; X itself stays below it up to degree 15. Why it's here: Your plot in victory 2 should look like this. If your normal equations fail much earlier or later, check your x scaling.
HINT · OBJECTIVE 2
Stuck? Hints stay hidden until you ask.
HINT · OBJECTIVE 4
Stuck? Hints stay hidden until you ask.

DATA · generated data

Objectives

0 / 5 CLEARED

Read-only. Log in to update progress.

VICTORY CONDITIONS

  1. 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 %>"`.
  2. A plot of condition number against degree for X and XᵀX on a log scale, with the line at 1/ε marked.
  3. The detector fires on the degrees where the normal equations actually fail, and stays quiet on the low degrees where they work.

Side quests

Repeat everything in float32. Find the degree where even QR gives up, and compare it with 1/ε ≈ 8.4e6 for float32.
Replace the powers of x with Chebyshev polynomials on [−1, 1] and watch the condition number collapse.

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.