Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Verified computing — where it appears

Computing a statement that is true of the real problem rather than an estimate of it, with a refusal as the only failure mode. It costs an interval arithmetic and a fixed-point argument, and what it returns is a statement about the real problem rather than a number about a computation.

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

10⁻⁹10⁻⁶10⁻³110³10⁶13212937κ · usignificand bitsκu = 1a bound was provedthe method refusedit never returns a wrong boundlargest κu with a proof0.45smallest κu without one0.89cases refused, of the grid13a refusal is not a wide bound — it is no bound at alland it is the only failure mode here

A bound that is proved

Every error statement on this site so far is a measurement of one run. Interval arithmetic makes a different kind of claim — the answer lies in this set, for this input, with no probability attached — and its failure mode is that it returns nothing at all. On a Hilbert system it proves a bound 23 times the error it bounds, and one size later it refuses.

arithmetic · Interval 11.522.511.52xyexactly one roota verdict, not a bound‖I − C F′(X)‖0.28width of X0.8width of K(X)0.23strictly inside is a proofand overlapping is nothing at all

Proving the answer is in the box

Every other method here computes a number and estimates how wrong it is. This one returns a verdict: there is exactly one solution in this box, or there is none, or — the honest third outcome — nothing can be said. Two of the three are proofs about infinitely many points from finitely many operations.

arithmetic · Interval 036912151810¹10²10³rotationswidththe enclosurethe seta rotation is an isometrymeasured growth a step1.4√2, from the geometry1.4enclosure ÷ set after 201024no rounding error is responsible for any of thisa higher precision does not touch it

Nine steps of pessimism

A proved bound is 8 to 26 times the error it bounds, at every precision from 16 to 40 significand bits. A carried interval is (√2)ᵐ times too wide after m re-enclosures. The two cross between eight and nine, so the method everybody warns against is the tighter of the two for a short computation.

arithmetic · Interval

Named alongside it

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

Directed roundingInterval arithmeticUnit roundoffCondition numberHilbert matrixWrapping effectCancellationExistence and uniquenessForward errorJacobianKrawczyk operatorNewton iteration

All concepts