Motivation
A numerical answer is produced from finite data by finitely many operations. It is therefore not enough to derive an exact formula: we must also ask how the input was represented and what happens when operations are rounded. Two different questions are easily confused. Does the mathematical problem amplify a small change in its data? Does the chosen algorithm introduce a larger change than necessary? The first is conditioning; the second is stability.
Representation and error
Definition 1.1.1
(Normalized floating-point numbers)
In a normalized base- system with significant digits, a nonzero floating-point number has the form
The exponent is restricted to a finite range. Real machines also have zero, and may have subnormal numbers, infinities and special values. The simplified model above is useful, but it is not a complete specification of any particular machine. Adjacent representable numbers get farther apart as their magnitude increases.
Worked example 1.1.2
(Rounding)
With three decimal digits and rounding to nearest, becomes and becomes . The absolute errors, and , differ by a factor of a thousand, while the relative errors are both about , below the unit roundoff defined next.
Definition 1.1.3
(Absolute error, relative error, and unit roundoff)
For an exact value and approximation , the absolute error is ; for , the relative error is . Absolute error is meaningful near zero, where relative error is undefined or can be misleading. Under rounding to nearest, away from overflow and underflow, the standard model is
where is the unit roundoff.
This bound concerns one rounding operation. It does not say that an entire multi-step calculation has relative error at most . Underflow requires separate attention because the relative model need not hold there.
Sensitivity belongs to the problem
Definition 1.1.4
(Relative condition number)
Let be differentiable at and suppose . For a small perturbation , the first-order relative change is
The factor is the local relative condition number.
It depends on the problem, the input, and the chosen measure of perturbation. It is a first-order statement, not a uniform guarantee for arbitrarily large perturbations. At a zero of the displayed relative output measure is unavailable; an absolute error measure may be appropriate instead.
Concept lensGeometric
A condition number is a slope on logarithmic axes
Write and . Wherever is differentiable and nonzero, the chain rule gives , so . To first order a relative change is a difference of logarithms, which is why relative error and this slope belong together. For the log–log graph is a line of slope ; for the slope is unbounded near , where .
Worked example 1.1.5
(Condition numbers)
For with , : a small relative input change produces approximately half as large a relative output change. In contrast, for , , which grows without bound as approaches . If the input has already been rounded, no rearrangement of the subtraction can recover the lost information.
Cancellation and a stable formula
Consider for small positive . The two terms are close, so their subtraction can discard significant digits already affected by rounding. Rationalizing gives the mathematically equal formula
In exact arithmetic the two formulas agree. In finite arithmetic the second avoids subtracting nearby numbers.
Worked example 1.1.6
(Cancellation)
In a four-significant-digit decimal system, take . Rounding to four digits gives , so the first expression returns zero. In the rationalized expression the denominator rounds to and the result is , close to the exact value . This example assumes rounding after each operation; actual hardware and evaluation rules may differ.
Common mistake
(Treating cancellation as the source of the error)
Cancellation is not automatically an error: subtracting two exactly represented numbers can itself be exact. The danger is that their small difference exposes errors already present in the operands. Nor does a small residual alone certify an accurate answer to an ill-conditioned problem.
Forward and backward error
Definition 1.1.7
(Forward error, backward error, and backward stability)
For data , exact answer , and computed answer , forward error measures . Backward error asks how much the data must be perturbed to make an exact answer: find a small with . A backward stable algorithm produces an answer corresponding to a small data perturbation, relative to a stated data measure.
Combining backward stability with good conditioning gives a useful forward-error bound; neither term alone guarantees accuracy in all cases.
Proposition 1.1.8
(Backward error of a square root)
Let and suppose an algorithm returns with . Then
In particular, if , the relative forward error is at most , which is approximately for small .
Proof
(Multiply by the conjugate)
Write , so and . Then
If , the numerator is at most and the denominator is at least , which gives the bound. The identity also shows what the first-order approximation leaves out: the factor equals only at .
The factor is the condition number of the square root. This is the general pattern in miniature: to first order, the forward error is at most the condition number times the backward error.
Error accumulation and evaluation order
Even when each individual operation obeys a small relative-error model, a chain of operations accumulates errors. For instance, if operations each contribute a factor with , then the product of the factors differs from one by at most . For small , this is approximately . This observation is a worst-case bound for that product; it is not automatically an error bound for an arbitrary algorithm containing additions and cancellations.
Worked example 1.1.9
(Order of summation)
Consider summing , , and in three-significant-digit decimal arithmetic. Adding the small terms separately gives , then after rounding . Adding them successively to gives at each step. Neither answer equals the exact sum , but ordering changes the loss. In a long sum, grouping numbers of comparable magnitude can help, though the signs and data distribution matter and no ordering removes every possible error. The exact mathematical sum is independent of order; the floating-point procedure is not.
To reason about a calculation, record the exact problem, the data actually stored, the operations and rounding model, and the output error measure. This separates modeling error from representation and algorithmic error. More digits help with rounding, but cannot correct an inaccurate measurement or an incorrect mathematical model. They also do not change a problem's condition number.
Perturbation intervals and measurement
Suppose a thermometer reports with a known absolute uncertainty of at most . The relative input uncertainty is at most . For the reciprocal , monotonicity gives the rigorous output interval . In contrast, the condition number predicts only that the relative output uncertainty is approximately for small perturbations. The interval includes the nonlinear remainder and therefore supports a concrete guarantee, whereas the condition number supplies a useful local estimate. Both descriptions are valuable but answer different questions.
When several data values are supplied, a condition number requires a rule for measuring their joint perturbation. For subtraction , suppose and . The triangle inequality gives
For the relative output error is bounded by . As and approach one another, this bound becomes large. It describes sensitivity to independently perturbed input operands. By contrast, treating their difference as one already-known input is a different problem. Declaring an operation ill-conditioned without identifying the data can hide this distinction.
For example, take and . If each has an independent uncertainty of , their true difference can range from zero to . The absolute uncertainty is therefore of the nominal difference . Relative error measured against the true difference can be arbitrarily large, and is undefined if that difference is zero. Carrying more digits through the subsequent subtraction cannot reconstruct the unknown true operands. If the operands were exact and stored exactly, the same nominal difference would not have that measurement uncertainty.
A rounding bound
Proposition 1.1.10
(Single-rounding bound)
In the ideal normalized model with unbounded exponent range, let be real and let be a nearest floating-point number to . Then with .
Proof
(Half a gap over the smallest number in the binade)
The gap between adjacent numbers in the binade is . Rounding to nearest produces absolute error no greater than half that gap. Since a number in the binade is at least , its relative error is at most . This proves the single-rounding bound for positive numbers; symmetry gives the negative case. Near boundaries, adjacent spacing changes, but the same bound remains valid under the stated ideal model. Ties require a specified tie-breaking rule, while the bound holds for either nearest choice.
The model is not valid without qualification at the extremes of a finite exponent range. Overflow cannot be represented by a nearby finite normalized number, and subnormal spacing is fixed rather than proportional to magnitude. Thus a proof based on must explicitly exclude those cases or treat them separately.
Counterexample mode
Subnormal numbers break the relative bound
Claim: every nonzero real number within the exponent range rounds with relative error at most . In IEEE binary64, , the smallest positive subnormal number is , and subnormals near zero are spaced apart. The real number lies exactly midway between and , and ties-to-even selects . The relative error is
more than times . The repair is the hypothesis already in the proposition: the relative bound holds for normalized results. In the subnormal range one has instead the absolute bound , half the fixed spacing.
Choosing a representation for a quadratic root
For the quadratic equation has real roots when . Directly evaluating both numerators can lose accuracy when one is the difference of two nearly equal numbers. For , , and , the small root is . The subtraction removes most leading digits. The product of the roots is , so after computing the large root with the addition , obtain the small root as its reciprocal. In exact arithmetic this is the same root. In floating point it avoids that particular cancellation.
A general implementation can set for , then compute roots and when . Special cases such as , , and a repeated or nonreal root require separate handling. Even this rearrangement does not guarantee accuracy if forming the discriminant overflows or suffers severe cancellation, or if the problem itself is sensitive. Near a repeated root the roots are intrinsically sensitive to coefficient changes, so algorithmic rearrangement cannot remove all difficulty.
Interpreting reported digits
Common mistake
(Reading printed digits as correct digits)
Suppose a numerical procedure prints . The number of displayed digits is not evidence that each digit is correct. A trustworthy report needs a bound, a verified residual together with sensitivity information, or another justified error estimate. Rounding a verified interval to a stated number of digits is safer than presenting a long decimal without context. Likewise, two algorithms agreeing to many digits is useful evidence but not proof if they share the same biased input or unstable step.
Different sources of error should be tracked separately. If a mathematical model uses measured parameters, the numerical output may be accurate for those parameters while the parameters differ from reality. A refinement experiment that decreases arithmetic error does not eliminate this modeling or measurement error. The purpose of an error analysis is to identify which uncertainty dominates the conclusion and how much the conclusion can support.
Summary
A numerical analysis starts by identifying the data and error measure. The floating-point model bounds each normal rounding, while conditioning measures sensitivity of the mathematical map. Backward error asks which nearby problem was solved; forward error measures the discrepancy in the answer. These ideas work together: a backward stable algorithm for a well-conditioned problem usually gives a small forward error, provided the assumptions of the error model are met.
Even an algebraically exact rearrangement must be evaluated in context. Rationalization avoids subtraction of nearby terms, but can introduce overflow elsewhere. Similarly, a computation performed at high precision can give an accurate answer to incorrectly recorded data. A useful final report states the scale of the data, the quantities that may have been perturbed, and the extent to which the requested digits are supported. It does not confuse precision of storage with certainty about the underlying measurement.
Exercises
Quick check
(Find the relative condition number of for . Explain its meaning.)
Compute .
Solution · Answer
Since , . A sufficiently small relative input perturbation produces approximately the same relative output perturbation.
Quick check
(In three-digit decimal arithmetic, rounding after every operation, evaluate and . What do the results show?)
Round after each operation, including the one inside the parentheses.
Solution · Answer
The first sum rounds to , giving . The parenthesis in the second expression is , giving . Floating-point addition is not associative, although real addition is.
Quick check
(For with , derive an equivalent expression that avoids subtracting nearby numbers for large .)
Multiply and divide by .
Solution · Answer
Multiply by the conjugate: . The expression avoids cancellation, although a practical implementation must still avoid overflow in forming for very large .
Quick check
(A positive quantity is measured as with absolute uncertainty at most . Bound its square using an interval, and compare this with the first-order condition-number estimate. Explain why the interval is the stronger statement.)
Square the endpoints of the input interval.
Solution · Answer
The input lies in , so its square lies in . The nominal output is and the largest absolute deviation is . Since has relative condition number , the relative input uncertainty predicts a relative output uncertainty of approximately , or an absolute change near . The interval accounts for the quadratic term and provides a bound rather than just a first-order estimate.