Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Inverse iteration — where it appears

A way to find the eigenvector belonging to the eigenvalue nearest a chosen shift, by solving with the shifted matrix repeatedly. Each solve multiplies that eigenvector's share of the iterate by a factor that grows as the shift approaches its eigenvalue, so a factorisation computed once serves every step.

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

0246810⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹log₁₀ γ, the change of unitsrelative errorforward errorη, the quadraticη, the linearisationagainst a closed formη(linearisation), worst7.6·10⁻¹³η(quadratic), worst1.2·10⁻⁴forward error, worst0.0013coefficient spread4.2·10¹⁵the solver is right at every stopabout a problem nobody asked

A backward-stable answer to a problem nobody asked

One quadratic eigenvalue problem, in nine systems of units, with a change of variable that is exact in both directions. The residual the solver prints stays at the rounding level at every stop. The answer loses eleven orders of magnitude, and the two facts are consistent.

polynomial · Linearisation backward error fractions of the curvaturebounded rule's direction, every ε0.14nearest zero at ε = 10⁻⁸, ÷ λ10⁻¹⁶10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹coupling ε|quotient| ÷ |smallest eigenvalue|Bunch–Kaufman's directionthe bounded rule'seigenvalue nearest zeroinverse iteration goes where the eigenvalue nearest zero isa solve amplifies the smallest, not the most negative

A curvature direction the factors cannot refine

A direction of negative curvature read from Bunch–Kaufman's factors held 7·10⁻¹⁶ of the curvature that was there, and the bounded rule's held 14 per cent. The prediction was that a few steps of inverse iteration with the same factors would recover it from either. One step leaves both under a thousandth, and two put both on positive curvature, at the eigenvalue nearest zero — because a solve amplifies the smallest eigenvalue in magnitude, not the most negative. What recovers the curvature is the matrix, not its factors: Lanczos from either direction reaches ninety-nine per cent in six to nine products at every coupling, and power iteration from Bunch–Kaufman's direction has not reached a tenth after sixty.

elimination · Cholesky

Named alongside it

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

Backward errorBunch–KaufmanCondition numberExact ground truthForward errorLanczos algorithmLDLᵀ factorisationLinearisationMatrix polynomialNegative curvatureQuadratic eigenvalue problemRayleigh quotient

All concepts