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.

Named by 2 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

Named alongside it

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

Directed roundingInterval arithmeticUnit roundoffCancellationCondition numberExistence and uniquenessHilbert matrixJacobianKrawczyk operatorNewton iterationWrapping effect

All concepts