Motivation
A numerical method often contains two competing mechanisms. Reducing the step can improve a mathematical approximation while magnifying errors in the supplied values. Performing more arithmetic may remove a truncation term while introducing additional rounding. A meaningful accuracy claim therefore needs an error budget whose terms describe the same final quantity under clearly stated assumptions.
We first turn central differences into a fourth-order derivative formula and prove its error constant. We then examine the arithmetic used to combine samples. Summation provides a particularly clear setting: an algorithm can be backward stable, yet its relative forward error can be large when the exact sum nearly cancels. Pairwise and compensated summation improve different aspects of this problem.
Definitions
Definition 8.1.1
(Richardson-extrapolated central difference)
At a point with all indicated sample locations available, define
Expanding the second expression gives the five-point formula
The function value at the center has coefficient zero, so only four off-center evaluations are needed. The term “five-point” refers to the underlying equally spaced stencil including that center. Richardson extrapolation constructs a new approximation by canceling a known leading power of the step. It is not simply averaging two answers.
Definition 8.1.2
(Floating-point rounding model)
For arithmetic, assume round to nearest in a floating-point system with unit roundoff , and assume all operations under discussion obey
Overflow and operations outside the normal relative-error model are excluded from the theorem below. Put when .
Definition 8.1.3
(Sum condition number)
For exact supplied numbers , write . If , define the relative componentwise sum condition number
This measures sensitivity to separate relative changes in the inputs. It can be huge even though every individual addition is accurately rounded. At a relative forward error with denominator is undefined; absolute error remains meaningful.
Theorem/Proposition
Theorem 8.1.4
(Fourth-order derivative with a separate data bound)
If , , and there, then
If each of the four supplied function values has absolute error at most , exact evaluation of the formula on those supplied values satisfies
For , this upper bound is minimized over positive at , provided the required sampling interval and derivative bound remain valid there.
Theorem 8.1.5
(Summation is backward stable under the rounding model)
Sequentially summing numbers with rounded additions, with , gives
Consequently . For , relative forward error is at most . A balanced pairwise addition tree of maximum depth instead gives the corresponding absolute bound , assuming and the same rounding model.
The backward statement means that the answer is the exact sum of slightly perturbed inputs. It does not say the original sum has small relative error. The condition number is precisely the missing link between those statements.
Concept lensStructural
Spend an error budget, rather than chase one term
Extrapolation removes a leading approximation term. Pairwise summation shortens the chain of rounding factors. Compensation carries lost low-order information forward. Conditioning describes how errors already present in the inputs affect the requested output. These mechanisms act at different stages; combining them responsibly means tracking their contributions to one final absolute or relative error statement.
Proof sketch or proof idea
Cancellation of the leading derivative error
Taylor expansion with a continuous fifth derivative gives
Substituting into the same expansion shows that cancels the second-order term. Thus . This identifies the leading coefficient, but by itself is not the uniform bound stated in the theorem. For that we control the whole remainder.
Proof
(Peano kernel bound for the five-point formula)
Scale to and let . Direct evaluation shows vanishes on every polynomial of degree at most four. The integral Taylor formula based at represents a function as a degree-four polynomial plus the integral of . Applying gives
where the kernel is even and, on its nonnegative half,
For nonnegative , the derivative at zero of the truncated power contributes zero; substituting the two positive sample locations gives these expressions. Substitution for negative gives the same values by evenness. On , , so the numerator is nonpositive; it is also nonpositive on . Finally,
Therefore . Taking gives , while ; division by proves the bound. The sample-error weights have absolute sum , giving the independent data term. Differentiating the displayed combined upper bound gives its stated minimizer; this is a choice within the model, not a universally optimal machine step.
Proof X-ray
Why a one-sign kernel gives the sharp constant
Two ideas carry the proof. Exactness on polynomials of degree at most four lets the Peano representation discard the whole Taylor polynomial, so depends on alone. The kernel then never changes sign, and that is what turns the crude estimate into , a number that any single quintic can compute: for both and . Because , the bound is attained whenever is constant, so cannot be improved, and a positive fifth derivative forces a negative error. The hypothesis is used because the kernel lives on ; evenness only halves the computation. Scaling contributes from and one factor from , leaving .
Expanding the rounding factors
Proof
(Expanding the rounding factors)
Set and . Repeated substitution writes each input multiplied by a product of at most factors . A product of such factors differs from one in magnitude by at most . One way to verify the bound is to bound its maximum by and its minimum by , then use
The first inequality follows by induction for , and the second is Bernoulli's inequality. Thus every input has a bounded multiplicative perturbation. Taking absolute values proves the forward bound, and dividing by introduces the sum condition number. In a pairwise tree, each leaf passes through at most additions, so the same product argument replaces by . No random rounding assumption has entered the proof.
The pairwise bound improves the worst-case depth dependence; it does not guarantee that every individual dataset produces a smaller error than every possible sequential order. An all-positive sum has condition number one, while a nearly canceling sum can remain sensitive under either algorithm. The bounds also presume that the inputs themselves are represented as intended; conversion of external decimal data is a separate perturbation to account for.
What compensation records
One common compensated scheme maintains a sum and a correction , initially zero. For each input , perform, in this order,
The correction estimates the low part lost in the latest addition and subtracts it from the next input. The order and rounding of these operations matter; algebraically simplifying the expression for to zero destroys the method. Compensation often improves accumulation dramatically, but this paragraph is an algorithmic explanation, not a proof that it always returns the correctly rounded exact sum. Stronger bounds need additional analysis of the exact implementation and rounding assumptions. We do not attach the sequential-summation theorem to this different recurrence.
The derivative error budget also clarifies what additional measurements can achieve. If the uncertainty bound is fixed by an instrument, collecting values at smaller spacing does not automatically reduce that uncertainty. Repeated measurements might improve a statistical estimate under a justified noise model, but a deterministic absolute bound does not shrink simply because the number of samples grows. The minimization above treats its two constants as fixed; if either constant depends on the chosen step, a new optimization problem must be analyzed.
Finally, printed digits should reflect the error information actually obtained. A long floating-point decimal display records a representation, rather than a proof of that many accurate decimal places. A verified absolute interval is often clearer near a zero derivative or canceling sum, where relative error is undefined or misleading. Conversely, relative error is useful when outputs vary substantially in scale. The appropriate report describes the quantity, norm, assumptions, and bound together, so that a reader can judge which digits or decisions are supported.
Worked examples
Worked example 8.1.6
(A sharp derivative constant)
For at zero, the numerator of is . Thus , while . Since , the error equals , attaining the theorem. The extrapolation is the same stencil with spacing , so its error is . A smaller truncation term has been obtained using closer samples and correspondingly larger uncertainty weights.
Worked example 8.1.7
(Compensation in a tiny binary system)
Use binary arithmetic with three significant bits and round-to-nearest ties-to-even. Sum followed by four copies of . At magnitude one the spacing is , so each ordinary addition of ties and rounds back to one. Sequential summation returns one instead of the exact . In the compensated recurrence, after the first small input ; after the second, ; after the third, ; and after the fourth, . The correction retains enough lost information to recover this exact sum.
Worked example 8.1.8
(Backward stability meets a sensitive sum)
For inputs , the exact sum is one and . The sequential theorem gives a relative bound . In a system with this bound is about four, although every addition obeys a small relative rounding bound. This is a bound under the specified model, not a claim about a particular decimal or binary format's output. It explains why a backward-stable algorithm can offer a weak relative guarantee for a canceling sum.
Common mistakes
Counterexample mode
Compensation is not a universal exact-sum algorithm
In standard binary64 round-to-nearest ties-to-even arithmetic, the compensated recurrence above applied to returns zero, whereas the exact real sum is one. After adding one, the correction is , but forming the next corrected input rounds back to . The saved unit is lost in that operation. A successful small example does not justify an unconditional exactness claim.
Common mistake
(Taking the smallest possible step for a high-order formula)
Fourth order does not mean that arbitrarily small steps are best. The truncation term decreases as , but bounded sample uncertainty grows as . Moreover, the actual coordinates and may become the same floating-point number. Neither the derivative theorem nor its data term includes a complete floating-point analysis of coordinate formation, function evaluation, weighted addition, and division.
Common mistake
(Reading backward stability as small relative error)
A tiny backward error cannot overcome an ill-conditioned problem: for a canceling sum the relative forward bound is , and may be enormous. Error reports should name both the model and the quantity being bounded.
Summary
Richardson cancellation produces a fourth-order stencil, whose one-sign kernel gives a sharp derivative bound. Sample errors add a separate inverse-step term. Sequential summation is componentwise backward stable under a normal rounding model, while cancellation can amplify forward relative error. Pairwise trees reduce depth-dependent accumulation; compensated schemes retain low-order information but require their own analysis and do not guarantee exact sums universally.
Exercises
Quick check
(Apply to and at zero. Explain exactness for the first function and the error sign for the second.)
Use the numerator .
Solution · Answer
For the cubic, the numerator is , agreeing with . The formula reproduces derivatives of all polynomials through degree four. For the quintic the value is as calculated above; its positive fifth derivative and the nonpositive kernel give a negative signed error.
Quick check
(Suppose and each derivative sample has absolute uncertainty . Write the combined bound, find its minimizing positive step, and state two reasons the chosen step might be inadmissible in practice.)
Combine with from the theorem.
Solution · Answer
The bound is . Its stationary point satisfies , giving approximately . The required points may lie outside the available domain, or the assumed derivative/uncertainty bounds may not hold throughout that sampling interval. Coordinate rounding and evaluation errors also need a separate budget. The minimizer optimizes this bound, not an unspecified full hardware computation.
Quick check
(For and , compare the sequential and balanced-tree constants. If every input is nonnegative and the sum is positive, what is the sum condition number?)
A balanced tree on leaves has depth .
Solution · Answer
Sequential depth is , giving . Balanced depth is ten, giving . For nonnegative inputs with positive sum, . The improvement concerns the proved worst-case constants, not a strict error ranking for every dataset.
Quick check
(The exact sum of three numbers is zero. Explain why a relative forward-error report based on that sum is undefined. Give an appropriate absolute bound for sequential summation, and distinguish it from a claim that the computed sum must be zero.)
Use the absolute form of the backward-stability theorem with .
Solution · Answer
Dividing an absolute error by the exact zero sum is undefined. The theorem instead gives when . This interval can contain nonzero computed answers. Backward stability permits slight componentwise input perturbations whose exact sum need not preserve an exact cancellation relation.