Numbers in a finite machine
A mathematical real number may need infinitely many digits. A computer format stores only finitely many, so even a short calculation can combine two different sources of discrepancy: the data may change when represented, and each subsequent operation may round its result. To interpret an answer, we need to specify which problem is exact and which operations are approximate.
The examples below use round to nearest, with ties broken by choosing the representable value whose final significand digit is even. This is an idealized rule for the stated format; actual software also has choices about precision, intermediate operations, underflow, overflow and exceptional values. The analysis is not a promise that every programming environment evaluates an expression in the same way.
Representation and a local rounding model
Definition 1.1.1
(Normalized floating-point number)
A normalized base- floating-point number with precision has the form
where the digits and exponent are integers and the exponent lies in the format's allowed range. Zero is represented separately. For fixed the spacing between adjacent significands is .
Spacing changes with magnitude. A finite exponent range also creates overflow and very small numbers for which a system may use subnormal representations. These boundary cases are important, but the simple relative-error model below does not cover them automatically.
Definition 1.1.2
(Unit roundoff and the rounding model)
For rounding to nearest, the unit roundoff is . For an elementary operation whose exact result is defined and lies in the normal range, the rounding model is
It compares the computed operation with the exact operation on its supplied operands. If those operands already approximate other quantities, their errors require separate accounting. When the exact result is zero, the relative expression needs separate interpretation; exact zero is represented as zero in the ordinary model.
Proposition 1.1.3
(Relative error of rounding to nearest)
When a nonzero real number rounds within the normal range, and no overflow or underflow invalidates the estimate,
Proof
(Half a spacing, divided by the magnitude)
Choose with . On this binade the spacing of representable numbers is , and rounding to nearest moves by at most half of it, namely . Since , the relative change is at most .
Worked example 1.1.4
(Rounding and ties)
In base two with , the normalized numbers between 1 and 2 are , , and , and . The number is halfway between and ; ties-to-even rounds it to . The relative error is , within . The next number is exactly representable, so its error is zero. The bound is a worst-case guarantee for a normal rounding, not the error of every number.
Quick check
(In base two with , round to nearest with ties to even. Find the relative rounding error and compare it with .)
Solution · Answer
is halfway between and . The latter has even final digit, so it rounds to . The relative error is .
Forward error, backward error and conditioning
Definition 1.1.5
(Forward and backward error)
Let a problem map data to the exact result , and let an algorithm return . The forward error is ; a relative version divides its magnitude or norm by when the latter is nonzero. A backward error asks how much the input must change so that exactly. Its value depends on which data may be perturbed and how perturbations are measured.
A small backward error says the answer solves a nearby problem; it does not by itself say nearby problems have nearby answers.
Proposition 1.1.6
(Residual bound for a perturbed right-hand side)
Let be nonsingular and fixed, , and suppose only may be perturbed. For a computed with residual , the unique right-hand-side change making exact is , with relative size . In an induced norm, the exact solution satisfies
Proof
(Residual, inverse and the size of the solution)
From we get , and it is the only choice since is invertible. Next, gives , while gives . Dividing the first bound by the second yields the displayed inequality.
Thus a small backward error for this perturbation model may be amplified by a large condition number. If perturbations to are also allowed, the definition and value of backward error change; the residual ratio above is not automatically the minimum for that broader model.
Common mistake
(A small residual is not a small error)
It is tempting to accept because is tiny. The proposition above shows that the relative error in can still be as large as times that residual ratio. Judge the answer by the residual and the conditioning of the problem.
Quick check
(For , and , find the residual, the exact solution and the backward error when only may change, using the infinity norm.)
Solution · Answer
and . The unique permitted change is , giving relative backward error . Yet the relative infinity-norm forward error is one.
Definition 1.1.7
(Relative condition number)
For a differentiable map between finite-dimensional normed spaces at nonzero with , the local relative condition number is , using the induced operator norm.
Conditioning belongs to a problem. It measures the sensitivity of an exact output to small changes in exact input. It describes first-order sensitivity; it depends on the input, norms and permitted perturbations. It is not an error made by an algorithm.
Proposition 1.1.8
(Sensitivity of subtraction to relative input perturbations)
For scalar subtraction , suppose and with . Even if their difference is then computed exactly,
Proof
(Two perturbations, one triangle inequality)
Subtracting gives , whose magnitude is at most . Divide by .
When and nearly agree, the ratio can be large. This is sensitivity of subtraction to relative perturbations in its inputs. It does not mean that the subtraction operation itself necessarily incurs a large relative rounding error on the two stored operands. Cancellation exposes errors already present; identifying their source requires following the whole calculation.
Cancellation and algebraically equivalent formulas
Worked example 1.1.9
(Rounded inputs hide a difference)
Consider decimal rounding to three significant digits. Exact inputs and both round to . Subtracting the stored values exactly gives zero, while the difference of the original inputs is one. The loss occurs when the inputs are rounded; the subsequent subtraction of the stored numbers is exact. Extra digits in the original data cannot be recovered merely by printing more digits in the final answer.
Quick check
(In three-significant-digit decimal arithmetic, and are first rounded separately and then subtracted. Find the computed and exact differences. Does the example show that subtracting the stored operands is inaccurate?)
Solution · Answer
Both inputs round to , so the computed difference is zero and the original difference is one. The subtraction of the two stored values is exact; the input rounding caused the discrepancy.
Common mistake
(Blaming the subtraction for cancellation)
When a result loses all its digits after subtracting nearly equal numbers, the subtraction is usually exact. What went wrong happened earlier, when the operands were rounded or computed with error. The sensitivity bound for subtraction explains why those earlier errors become visible; it does not locate the operation that created them.
A formula can create the same difficulty inside a computation. For , the expressions
are equal in real arithmetic. At large , the first subtracts nearly equal positive numbers; the second avoids that subtraction.
Counterexample mode
Algebraically equal formulas can compute different values
Claim: two expressions that are equal in real arithmetic return the same value in floating point. Under IEEE 754 binary64 round-to-nearest arithmetic, take the exactly representable input and evaluate each elementary operation separately. Then exactly, and : the increment lies halfway between adjacent binary64 numbers there, and ties to even select . The direct expression then gives , although the exact value is positive and approximately . The rationalized expression gives a useful nonzero approximation in this example. This comparison assumes the shown evaluation order and no fused operation or compiler reassociation; it does not prove that the rationalized formula is safe for every , since itself can overflow.
Worked example 1.1.10
(Associativity does not survive rounding)
In binary64, with each operation separately rounded, , whereas . In the second expression, is not representable: the numbers near are spaced apart, and the tie between and resolves to the even significand , so the inner sum rounds back to . The exact real sum is one in both parenthesizations. An algorithm's evaluation order is therefore part of its specification.
Stability is a property of an algorithm
Definition 1.1.11
(Backward stability)
Informally, an algorithm is backward stable for a specified problem and input model if its computed result is the exact answer to a nearby input, with a controlled small perturbation relative to the data. The word "nearby" requires a norm, allowable perturbations and a bound depending on precision and problem size.
A theorem about stability may hold only under conditions on the input and on intermediate range. Stability does not mean that every computed digit is accurate: an ill-conditioned problem can amplify even a small backward error. Conversely, a well-conditioned problem can be solved badly by an unstable algorithm.
Theorem 1.1.12
(Accumulation bound for sequential summation)
Let be computed from representable inputs by setting and then adding in the listed order, , and suppose each nonzero exact operation satisfies the relative rounding model with the same , without overflow or underflow. If , then
Moreover with .
Proof
(Expanding the recursion)
Expand the recursion: each is multiplied by a product of at most factors . For , the absolute difference between such a product and one is at most . The triangle inequality yields the displayed bound. Exact zero intermediate sums contribute zero rounding error and can be treated separately. The same expansion expresses as , which is a componentwise backward-error statement for the summation inputs.
Proof X-ray
Attach every error to an input
Each addition contributes one factor , so unrolling the recursion multiplies and by such factors, by , and by one. This bookkeeping is the real idea: errors are charged to the inputs, not to the partial sums, which gives the backward form for free. The rounding model, with its range assumption, is used once per addition; only makes finite. The forward bound is then the triangle inequality, and because it involves , cancellation in the exact sum is invisible to it.
The displayed inequality is an absolute forward error bound. If the true sum is close to zero compared with , it may permit a large relative error; it does not guarantee accurate digits for a canceling sum.
Quick check
(Under the rounding model for sequential summation, state an absolute error bound for four numbers. Explain why it need not be a small relative error bound.)
Solution · Answer
If and the stated range assumptions hold, the bound is with . The exact sum can be arbitrarily small relative to the sum of magnitudes, so dividing by its magnitude can give a large bound, or be undefined when the sum is zero.
Adding in a balanced tree gives each input far fewer roundings than adding in a line.
A natural next question
Can the order of addition shrink the bound?
Adding in a balanced tree gives each input far fewer roundings than adding in a line.
Yes. If the sum is formed by adding pairs, then pairs of pairs, each passes through only additions instead of up to ; for that is against . The same expansion then gives the bound . Neither order helps when the exact sum is much smaller than .
The neighbors of 1 and their asymmetry
Assumptions. We use a normalized binary format with precision (counting the leading bit), with exponents and available, and round to nearest with ties to even. Range limits are ignored. Nothing here concerns subnormal numbers or overflow.
Proposition 1.1.13
(The neighbors of 1)
In this format the successor of is and the predecessor of is . The gap below is half the gap above it.
Proof
(Spacing in the two adjacent binades)
Numbers in the binade have the form . Changing the last fraction bit changes the value by , so the next number after is .
Numbers in have the form . Their spacing is . The largest such number has every significand bit equal to , which is . So the gap below is , half of the gap above.
Definition 1.1.14
(Gap above 1)
In this note, denotes the gap above 1. It differs from the unit roundoff , which is half of it. Authors use "machine epsilon" for either quantity, so the term needs an explicit definition before it is used.
Common mistake
(Two meanings of machine epsilon)
Using a library constant called "epsilon" as if it were the unit roundoff doubles the error bound in every estimate of this note. Before substituting a value, check whether the source means the gap above 1 () or the bound on relative rounding error ().
Worked example 1.1.15
(Ties at the boundary of a binade)
For binary64, . The neighbors of 1 are and , and .
The midpoint above 1 is . One candidate is , whose significand ends in (even). The other is , whose significand ends in (odd). Ties-to-even chooses . The midpoint below 1 is . Its candidates are (53 ones, odd) and (even), so the result is again . The tie below 1 lies only away from 1, half the distance of the tie above it.
The ties above concern rounding a given exact real number. In arithmetic, the operands are already floating-point numbers, and only the exact result of each operation is rounded. Since is representable, . Evaluating left to right therefore returns , even though is representable.
Quick check
(With , find the neighbors of 1 and , then round the exact midpoints and .)
Solution · Answer
The predecessor is . The successor is , and . The exact number is the midpoint of and . Since is even and is odd, it rounds to . The exact number is the midpoint of (odd significand ) and , so it also rounds to .