Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Householder — where it appears

A reflection that maps a vector onto a multiple of a coordinate axis, used to introduce zeros into a matrix a whole column at a time. It is orthogonal to the rounding level whatever the matrix, which is what makes a factorisation built from a sequence of them backward stable.

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

how far is it from A to an orthogonal matrix?smaller is nearer · the polar factor minimises this in every unitarily invariant normpolar factor U1.8554QR, signs fixed2.1265QR as returned3.8226200 drawn at randomκ = 10polar factor1.9QR, signs fixed2.1QR as returned3.8best of 200 random2.7‖A − QR‖ is the same either wayand ‖A − Q‖ is not

The nearest orthogonal matrix

Every field that has to clean up a drifted rotation reaches for QR, and QR does not answer the question. The nearest orthogonal matrix is the orthogonal factor of the polar decomposition — nearer by about a tenth, and, more to the point, the same matrix whatever order the columns were written in. QR's answer changes completely.

orthogonality · polar decomposition 0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴10⁷10¹⁰log₁₀ τ — the weight on the constraintrelative error against the exact answerτ = 1/√uGram–Schmidtnormal equationsHouseholder QRthe ceiling is the method'sHouseholder, τ = 10¹⁴4.8·10⁻¹⁵normal equations14Gram–Schmidt4.9·10¹⁰1/√u6.7·10⁷a constraint is a weight at infinityand the solver decides how far infinity is

A constraint is a weight at infinity

Stack an equality constraint on top of a least-squares problem with a large weight and the answer approaches the constrained one like 1/τ². The limit is takeable to any accuracy — and how far it can be taken is a property of the solver, not of the problem. One of them stops at the square root of the precision, and one of them does not stop.

leastsquares · constrained least squares

Named alongside it

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

QR factorisationCondition numberEquality constrained least squaresExact ground truthGram–SchmidtInvarianceLeast squaresMethod of weightingNormal equationsOrthogonalityPolar decompositionRotation

All concepts