An estimate is not automatically a certificate
An adaptive quadrature program often compares a coarse rule with a refined rule. Agreement is useful evidence, but samples can miss a narrow or oscillatory feature. A certificate needs an assumption that constrains what happens between samples. Here that assumption is a proven bound on the second derivative on every subinterval.
Definition 7.4.1
(Midpoint certificate data)
Let , with . Choose a partition , and write and . The certificate data consist of
- numbers with throughout , and
- for each midpoint, a computed interval that contains the exact value .
The data may come from analytic inequalities or rigorously rounded interval calculations; evaluating only at the midpoint generally does not prove the bound.
Theorem 7.4.2
(A certified integral interval)
Under these hypotheses,
For a computer certificate, the partition geometry, exact midpoints, sample enclosures and endpoint arithmetic must all be represented exactly or enclosed with outward rounding; in particular each sample interval must contain the value at the exact midpoint used in the proof.
Proof
(Taylor remainder and symmetry about the midpoint)
For in the th interval, Taylor's theorem with a bounded remainder gives
Integrating, the linear term vanishes by symmetry, and
Because , replacing by its lower or upper enclosure preserves the respective inequality. Sum the inequalities over all cells. This proves (1).
Proof X-ray
Where the guarantee comes from
There are two distinct uncertainties: the midpoint values lie in intervals, while curvature bounds the unsampled part of the graph. Formula (1) combines both. An interval evaluation enclosing a sample alone cannot control the spaces between samples; a derivative estimate without safe arithmetic does not certify a floating-point endpoint.
Common mistake
(Sampling at one point per cell)
A value of at the midpoint can be small while is much larger elsewhere in the cell. The number must bound on the whole cell, by an analytic inequality or an interval enclosure of over the cell. A single sample gives an estimate, not a certificate.
A calculation and the effect of refinement
Worked example 7.4.3
(Quadratic on one and two cells)
For on , the exact midpoint value is and . One cell gives
With two equal cells the midpoint sum is , and (1) gives and the narrower enclosure . The true integral is . The one-sided sharpness here is special to this convex quadratic; (1) is deliberately valid without knowing the sign of .
Proposition 7.4.4
(Width of the enclosure)
If all and , then
If the samples are intervals, the width of (1) is
In particular, if each midpoint interval has width at most , the total width is at most .
Proof
(Summing the cell widths)
. The upper endpoint of (1) minus the lower endpoint is . With and this is at most , and (2) bounds by .
Thus, with exact samples and a common bound across the whole sequence of partitions, the enclosure width tends to zero whenever the maximum cell length does. Continuity of supplies a finite theoretical global bound, but a numerical bounding procedure must actually provide uniformly bounded valid . Refining the partition controls only the second term of (3). To reach a target width, the sample intervals and their arithmetic must also be accurate enough. An adaptive algorithm can refine cells according to their certified contributions ; it must recompute or retain valid derivative bounds after splitting; the child midpoints are new sample locations. Guaranteed termination from (2) requires that its refinement actually drives to zero and that the sample and arithmetic uncertainties can be made sufficiently small. Fixed precision may impose a positive uncertainty floor that refinement cannot remove.
Worked example 7.4.5
(The sine integral on four cells)
Take on with and four equal cells, . The exact midpoint values are , whose sum is about . The midpoint sum is , and . The enclosure is about , which contains the exact value . One cell gives the much wider .
Worked example 7.4.6
(Zero curvature and interval samples)
For the linear function on with one cell, is a valid bound, so . The exact midpoint value is and the enclosure is , matching . If instead the sample is only known to lie in , then (3) gives width , and the enclosure is . All remaining width comes from the sample interval, not from curvature.
Counterexample mode
A zero error estimate can miss a positive integral
On let
All samples of the one-panel and two-half-panel Simpson rules lie in , so both give zero. Their difference is zero, yet is continuous, nonnegative and positive away from those five points, hence . In fact the integral is . Agreement of two formulas is not a proof of accuracy without additional information about the integrand.
This limitation is not peculiar to Simpson's rule. Given any fixed finite set of sample locations, the square of the product of their linear factors is a smooth nonnegative function that vanishes at every sampled point but has positive integral. Even an adaptive deterministic algorithm using only point evaluations that stops after finitely many samples on the zero function sees the same zero values for a positive scalar multiple of the corresponding product, and therefore follows the same sampling path. Scaling makes that product's positive integral arbitrarily large, so a fixed finite-width enclosure cannot be valid for both functions without a class restriction.
Common mistake
(Rounding endpoints to nearest)
A certificate computed with ordinary round-to-nearest endpoints can fail by one unit in the last place: the lower endpoint may round up, or the upper endpoint round down, and the stored interval no longer contains the exact enclosure. Compute the lower endpoint rounded down and the upper endpoint rounded up, as the theorem requires.
Practice and solutions
Quick check
(Apply (1) to on using one cell, the exact midpoint value, and .)
Solution · Answer
The midpoint rule gives and , so the interval is .
Quick check
(For on , give a bound on the certified interval width using equal cells and exact midpoint values.)
Solution · Answer
Here , , and (2) gives .
Quick check
(A computed midpoint interval has width on each cell of a partition of . What contribution do sample intervals make to (3)?)
Solution · Answer
Exactly when every interval has that width; if each has width at most , this is an upper bound.
Quick check
(Why does sampling at one point per cell not by itself justify ?)
Solution · Answer
A continuous second derivative may be small at that point and larger elsewhere.
Quick check
(If the coarse and fine Simpson rules agree to machine precision, what additional information would make a rigorous enclosure possible?)
Solution · Answer
For example, verified derivative bounds on each cell together with rigorous enclosures for the samples and outward-rounded arithmetic give the midpoint certificate (1). Agreement alone supplies none of these bounds.