Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Interval arithmetic — where it appears

Arithmetic on ranges, with each operation rounded outward, so that the computed interval certainly contains the exact result.

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

10²10³10⁴10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴terms summedrelative error+∞, −∞ 1.01zero 1.00stochastic 0.50nearest 0.47√n against n, fittednearest, fitted exponent0.47stochastic, fitted exponent0.5toward +∞, fitted exponent1twelve seeds averaged at each sizethe slope is the bias, not the precision

The direction the error leans

The size of one rounding error is set by the precision. How ten thousand of them combine is set by something else entirely — the rounding mode — and the fitted exponents are 0.47 for round-to-nearest and 1.01 for round-toward-infinity, on identical data at identical precision.

arithmetic · rounding 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 grey: proved empty · filled: proved to contain exactly one roota covered squareboxes proved empty42boxes proved unique2undecided0operator evaluations87every rectangle carries a proofand the two dots are where the roots are

Where the box is cut

A branch-and-bound with an interval operator settles a whole square — two roots proved unique, forty-two regions proved empty, nothing left undecided, in 87 evaluations. Move the roots so one lands on the first bisection and it proves nothing at all, at any depth. Cutting at 0.485 instead of 0.5 finds both, in a quarter of the work.

arithmetic · interval

Named alongside it

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

Directed roundingUnit roundoffExistence and uniquenessKrawczyk operatorVerified computingBisectionBranch and boundCancellationCondition numberError accumulationExact ground truthHilbert matrix

All concepts