Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Levinson recursion — where it appears

The recursion that solves a symmetric positive definite Toeplitz system in O(n²) operations by extending the solution of each leading submatrix to the next. Each step uses one reflection coefficient and the residual variance of the order-k prediction problem, so it forms no factorisation and touches no entry off the first row.

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

the smallest perturbation of any kind — 1.89·10⁻¹⁷the smallest Toeplitz one — 2.65·10⁻¹³both exact for the same x̂smallest of any kind1.9·10⁻¹⁷smallest Toeplitz one2.7·10⁻¹³the price of the constraint1.4·10⁴diagonal defect, unconstrained0.97an exact answer to a nearby problemof a kind nobody posed

A nearby problem of the wrong kind

A good algorithm returns the exact answer to a nearby problem. A hundred and eighteen essays have measured the distance and not one has asked what the nearby problem looks like. On a Toeplitz system it is a rank-one matrix that is constant along none of its diagonals — and the smallest one that is Toeplitz is two and a half million times larger.

structure · Structured backward error 10⁻³10⁻²10⁻¹110⁻¹⁹10⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹1 − ρbackward errorLevinson, Toeplitzelimination, ToeplitzLevinson, any kindelimination, any kindat ρ = 0.999Levinson, any perturbation2.9·10⁻¹⁷Levinson, Toeplitz only6·10⁻¹²the ratio between them2·10⁵diagonal defect of the first0.97the number that is reportedand the number that is asked about

The number that cannot rank them

Levinson and Gaussian elimination are indistinguishable on the backward error a library reports — every one of ninety-six measurements between 1.16·10⁻¹⁷ and 5.73·10⁻¹⁷. The structured backward error separates them by up to a hundredfold, in whichever direction the point happens to give. Only the forward error ranks them, and only because this family's exact answer is known.

structure · Structured backward error

Named alongside it

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

Backward errorBackward stabilityCondition numberExact inverseStructured perturbationToeplitz matrixFast algorithmForward errorGaussian eliminationLow-rank updateStructured backward error

All concepts