Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Sensitivity — where it appears

How much an answer moves when the data moves. It belongs to the problem rather than to any algorithm, which is what separates a wrong answer's two possible authors and is the whole of what a condition number measures.

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

110¹10²10³10⁴10⁵10⁶10⁷00.250.50.751amplification of the input perturbationfraction of directions at or belowκ = 10·10⁵worst found 7.6·10⁵6×6, 200 directionsmedian reaches 0.29 of κ

The condition number is an amplifier

κ is usually introduced as a definition and then quoted. It is a measurement: perturb the input by a known amount, look at how much the output moves, and the largest ratio you can find is the number.

error · Conditioning 110¹10²10³110¹10²10³off-diagonal entry ccondition number of the eigenvalue√(1 + c²)decoupled: 1measuredthree routes, one number‖A − ZTZᵀ‖/‖A‖1.7·10⁻¹⁵closed form100computed 1/|yᵀx|100worst measured movement46four eigenvalues, two conditioning numbersthe symmetric case has one, and it is 1

A condition number for one eigenvalue

In the symmetric case every eigenvalue has condition number exactly one. In this four-by-four matrix two of them have condition number 100.005 and the other two have exactly 1, and the number belongs to the eigenvalue rather than to the matrix.

spectra · Eigen conditioning 110¹10²01020304050noise ÷ thicknesstrials mirrored, %a coin: 50%t = 10⁻²t = 10⁻³t = 10⁻⁴per cent mirroredσ/t = 3, mean of three7.7σ/t = 10, mean of three34σ/t = 100, mean of three4720 points, 400 trials a stop, one seed per thicknessthe ratio decides, not the thinness

A rotation that comes back mirrored

Align twenty noisy points and the nearest orthogonal matrix to the answer is a reflection in 7.7 per cent of trials at noise three times the set's thickness and a third of them at ten — at thicknesses of 10⁻², 10⁻³ and 10⁻⁴ alike. The determinant fix is never a small correction. It moves the answer by exactly 2, it costs exactly 4σ₃ of residual, and it leaves the rotation's error at half the noise however thin the set becomes.

orthogonality · Polar decomposition 0123401020304050z, the effective noise ratiotrials mirrored, %1 thin: 1 × 1 model2 thin: 2 × 2 model3 thin: 3 × 3 modelper cent mirrored at z = 0.7, 600 trialsn = 3, 1 thin, 20 points9.7n = 5, 1 thin, 20 points13n = 10, 1 thin, 40 points12n = 5, 2 thin, 20 points23n = 10, 2 thin, 40 points24n = 8, 3 thin, 40 points32points: measured in n dimensionslines: a k × k determinant, no n in it

A mirror decided in the thin directions

In n dimensions the nearest orthogonal matrix to a noisy alignment is still sometimes a reflection, and the rate at which it is does not depend on n. Three, five and ten dimensions with one thin direction mirror alike; two thin directions mirror like each other in five dimensions and in ten. The rate is the chance that a k × k matrix built from the k thin directions has a negative determinant — 21.7 per cent at a noise ratio of 0.7 for k = 2, measured at 23.0 — and it is well above k independent coin flips. With two or more thin directions the determinant correction still fires, and it no longer rescues the rotation: the answer is eleven noise-widths off whether or not it was mirrored.

orthogonality · Polar decomposition same κ(B), two right-hand sides‖λ‖ ÷ κ(B), asking0.0081‖λ‖ at κ(B) = 10⁶·⁷, consistent0.00410¹10³10⁵10⁷10⁹10¹¹10¹³10⁻³10⁻¹10¹10³10⁵10⁷10⁹10¹¹κ(B), the conditioning of the constraint block‖λ‖, the multipliers' sizethird constraint asksasks nothing∝ κ(B)the same B at every point, two values of d₃the multipliers read the right-hand side

A multiplier is a force

A third constraint nearly parallel to the first made the multipliers of a constrained fit rise in exact proportion to κ(B), which looked like the conditioning measured a second, dearer way. It was not. Give the third constraint a datum that asks for nothing new and, at the same κ(B) = 4.6·10¹², the multipliers are eighteen thousand times smaller; give it a strain δ and they are 0.0133 δ/ε², a force on a lever of length ε. What they measure is what the constraint asks. What they do not measure is the error of the best route, which sits at the same level whether the constraint asks for nothing or for a displacement of 3·10⁹.

leastsquares · Constrained least squares a generic tall matrixHouseholder: aimed over median8b appended: aimed over median11column MGS: aimed over median1110⁻⁴10⁻³10⁻²10⁻¹1error ÷ κ²uρthe boundHouseholderb appendedcolumn MGSdots: random directions · bar: aimed · ring: the fixed directionaiming closes a factor of seven

The worst residual belongs to the route

Every stable least-squares route's error rises with the residual at about a fiftieth of the bound κ²uρ, and the question left open was whether a residual aimed at the weak directions closes the gap. It can be aimed exactly: the map from residual to error is, on these problems, one direction and rounding. Aimed, Householder's constant rises from a median of 0.014 to 0.11 — √(m − n) = 6.9 times a typical direction, at 32, 64 and 128 rows to three figures — and stops a factor of nine short of the bound. The direction is each route's own: aimed at one, another route draws a fifth of its worst. And aimed at the appended block, the one-per-cent rule that made it worth its extra block falls to half a per cent, with the block twelve times behind Householder on the same data.

orthogonality · Gram–Schmidt

Named alongside it

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

Condition numberOrthogonalityDeterminantExact ground truthPerturbationPolar decompositionRotationSingular value decompositionSingular valuesBackward errorCondition squaringDeparture from normality

All concepts