Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Invariance — where it appears

A property of a computed answer that does not change when the problem is rewritten in a way the question itself does not depend on. It is checked by running a routine twice on two descriptions of one problem and comparing the results, so it needs no reference answer, and a departure from it is read against the size of the correction being computed rather than against the answer's own norm.

Named by 4 essays across 3 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 polar: U₁P − U₂QR: Q₁P − Q₂0000000000000000000000000000000000000.67-0.35-0.23-0.620.19-0.72-0.770.170.20.290.190.93-0.180.55-0.0290.06-0.460.11-0.17-0.61-0.230.38-0.55-0.380.750.870.661.1-0.36-0.530.42-0.670.180.180.52-0.3the same columns, reordered‖U₁P − U₂‖_F2.8·10⁻¹⁵‖Q₁P − Q₂‖_F3‖Q‖_F, for scale2.4κ of the matrix100distance between the two answers, on one scale0 to 4polar2.8·10⁻¹⁵QR3.048‖Q‖_F = 2.449the column space did not moveand one of the two answers did

A test with no answer in it

A caller with no reference answer can still ask whether a routine answered the right question: reverse the columns, run it again, compare. The polar factor's two answers agree to 10⁻¹⁵ at every conditioning drawn; a QR's differ by 2.353 on matrices whose own norm is 2.449. The test has a floor, and the floor is measurable too.

orthogonality · Polar decomposition the diagonal of the hat matrix, hᵢ = aᵢᵀ(AᵀA)⁻¹aᵢaverage p/m = 0.20010the leave-one-out residual: eᵢ/(1 − hᵢ), and forty refitsbars: closed form · dots: refitted without that pointone number, two fieldsΣ hᵢ, exactly p10largest leverage0.5closed form against refits8.9·10⁻¹³1 − h of the first row0.5y appears in the residualand nowhere in the leverage

Influence is decided before the data

The diagonal of the hat matrix sums to the number of columns and the response appears nowhere in it, so a fit has exactly p units of influence to hand out among m observations. The same row at h = 0.5 is a ten-fold outlier on one design and a boundary case on another, and which of those it is was settled before a single measurement was taken.

leastsquares · Leverage 012345610⁻¹10²10⁵10⁸10¹¹log₁₀ γ, the change of unitscondition numberthe linearisationthe quadraticone problem, two amplifiersκ(quadratic), first6.6κ(quadratic), last6.6κ(linearisation), last10¹²how far the first moved1the problem is as well conditioned as everand the method is not

The number that moves when the problem does

Two quantities are offered as the condition number of one eigenvalue. One is unmoved to eight digits by a change of variable that is exact in both directions, and grows like the square root of the chain's length. The other is inflated by ten orders by that change of variable, and is ten times too large before anything has been done at all.

polynomial · Linearisation backward error

Named alongside it

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

Condition numberGram–SchmidtHouseholderOrthogonalityPolar decompositionQR factorisationBackward errorCholeskyCompanion formConditioningForward errorFrobenius norm

All concepts