Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Least squares by QR — where it appears

Solving an overdetermined least-squares problem by factoring the matrix as QR and back-substituting with R against Qᵀb. It avoids forming the normal equations, whose condition number is the square of the matrix's, and is backward stable.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹ε in Läuchli's matrix (smaller ε, larger κ)relative error in the coefficientsAᵀA exactly singularnormal equationsQRκ from 1.7·10⁸ to 17the cliff is at √u = 2.4·10⁻⁴

The road that squares the problem

The normal equations are the first method every course teaches and the method no library uses. Forming AᵀA squares the condition number, and below ε = √u it does not degrade — it produces a matrix that is exactly singular, from data that was perfectly usable.

leastsquares · Normal equations how lopsided the valley isσ = 0.1: 6 too few ÷ 40 too many17σ = 10⁻³: 6 too few ÷ 40 too many231σ = 10⁻⁶: 6 too few ÷ 40 too many8184-50510152025303540110¹10²10³10⁴degree minus the best degreeerror ÷ best degree's errorσ = 0.1σ = 10⁻³σ = 10⁻⁶left of the line: too few degrees; right: too manya missing degree costs orders, an extra one a few per cent

The degree that is safe to overshoot

The rules that choose a Tikhonov parameter miss by factors of millions on one draw in twenty. Transplanted to the degree of a polynomial fit, in a basis orthonormal on the data, the same rules never cost more than 2.7 times the best degree's error in three hundred draws. The reason is the shape of the valley they search: six degrees too few costs from 44 to 16,000 times the best error, forty degrees too many costs about twice it. The one rule with a tail, the discrepancy principle, has its threshold half a standard deviation above the residual it is waiting for.

leastsquares · Fitting

Named alongside it

The objects these essays reach for when they reach for this one.

Bias varianceCholeskyCondition squaringCross-validationDiscrepancy principleError accumulationGeneralised cross-validationGram matrixHilbert matrixLäuchli's matrixLeast-squaresLeverage

All concepts