Motivation
A uniform rule spends the same number of samples in a quiet part of an integrand as in a region of rapid change. An adaptive rule asks which subintervals appear to need more work and divides those intervals again. The idea is simple, but an implementation must keep track of shared samples, local tolerances and unsuccessful exits. More fundamentally, it must say what a successful exit actually proves.
We develop two versions of the same subdivision strategy. The first uses a useful comparison between coarse and fine Simpson values. The second assumes a known fourth-derivative bound and obtains a genuine absolute error guarantee in exact arithmetic.
Definitions
For , let and define the one-panel Simpson rule
Write and , and set . The two rules together use the five points . Their difference gives the estimated fine-rule error . The signed corrected approximation is ; the sign is essential. The indicator estimates the error of the uncorrected under the model, not the error of ; it remains heuristic when returned alongside . In the smooth leading-order model, estimates , not .
An absolute tolerance is a budget for error, in the units of the integral. On a split we give each child . This allocates budget; it does not itself establish that any actual error is below the allocation. Relative tolerance needs separate treatment when an integral is zero or suffers cancellation.
Theorem/Proposition
Theorem 6.6.1
(What the difference estimates)
Let be a fixed compact interval and , with . For panels , as , the following expansions hold uniformly:
Consequently and . The constants in these terms can depend on a bound for . No inequality follows from this statement.
Theorem 6.6.2
(A derivative-bound certificate)
Suppose and a known number is valid. For any finite partition into panels of lengths , compute the two-child Simpson value on each. In exact arithmetic,
If a local bound is known on each , it may replace in its corresponding term. For the corrected values , the separately valid bound is the sum of .
A bound is useful only if its derivative hypothesis has been established on the whole panel, not merely sampled at the five nodes. In validated computation, one can obtain such bounds by proved analytic inequalities or suitable interval arithmetic. Approximations to , evaluation error, summation error, overflow and rounded endpoints require additional bounds; the exact-arithmetic certificate alone does not cover them.
Proof sketch or proof idea
Proof
(Taylor expansion about the panel midpoint)
Taylor-expand about through degree five. The integral, and are symmetric about , and both rules integrate cubics exactly. Thus the odd fifth-degree term also cancels. For the quartic centered at , direct substitution with gives , , so . Multiplying by yields . On each child, expand the centered quartic about the child midpoint. The remaining terms have degree at most three and are integrated exactly, so scaling both child widths by one half makes their quartic errors sum to one sixteenth of the parent error. Taylor's remainder is uniformly pointwise when is bounded, so each integral or weighted rule contributes . Subtracting the two expansions gives and the stated relation. If , the leading term vanishes and a relative interpretation of the estimate becomes especially unreliable.
Proof
(Summing the one-panel Simpson bound)
The Simpson bound for a single panel of width is . Apply it separately to both children, each of width . Their bounds add to . Sum over the partition and use the triangle inequality. Since , another triangle inequality supplies the displayed corrected-rule bound. This bound is conservative; it does not assert that the correction improves the certified result.
Proof X-ray
Why one proof yields an estimate and the other a bound
The first proof has one key move: because both rules are symmetric about and exact for cubics, the error of each is a pure multiple of up to the remainder, and halving the panel multiplies that quartic error by . The number in comes entirely from this scaling. The hypothesis is spent only on the remainder, to make it pointwise and hence after integration against weights of total mass . Its constant is not computed, so the proof closes with an equality up to an unknown term and never with an inequality. That is why remains an estimate even for very smooth .
The second proof never looks at . It uses only and a number valid on every whole panel, applies the known one-panel inequality to each child, and adds absolute values. Remove the hypothesis on and nothing in the computed samples can replace it, as the counterexample below shows.
Worked examples
Worked example 6.6.3
(A complete adaptive trace for a quartic)
Take on and absolute tolerance . At the root, , and , so . Split and give each half tolerance . On , the coarse and fine values are and . On they are and . Each difference is , hence each estimate is and both leaves pass.
The corrected leaf values are and , adding to . At the root there were five distinct samples; testing the two children requires four more, at odd multiples of . The common endpoint and midpoints are reused. For this quartic the correction happens to be exact; that is not a general promise of the stopping test.
Worked example 6.6.4
(A guaranteed tolerance from the same tree)
For , . Each half-panel's fine-rule bound is . Their sum is . Returning the sum of the two fine values, , therefore has a proved error at most in exact arithmetic. In fact this example attains that bound: . The corrected answer is exact here, but that fact comes from the quartic calculation, not from its estimated error.
Worked example 6.6.5
(Edge case: a square-root singularity)
Take on , whose integral is . Here is unbounded near , so neither theorem applies on a panel touching the origin. To six decimal places the root values are
The actual error of the fine value is , about eight times . With the heuristic test accepts at the root and returns , whose error exceeds the tolerance by a factor of more than four. The sign of the correction is right, but the size predicted by the scaling is wrong, because that scaling assumed a bounded fourth derivative. Further subdivision near , or a change of variable such as , is needed before the estimate can be trusted.
Implementable recursion
The following pseudocode uses exact real arithmetic for the mathematical description. simpson(u,v,fu,fm,fv) uses the formula above. eval(x) must either supply a value or report failure. depth is a finite nonnegative integer, and an implementation must also check that newly computed floating-point nodes are strictly ordered.
integrate(f, a, b, tolerance, maxDepth):
require a < b, tolerance > 0, maxDepth >= 0
m = (a+b)/2
evaluate fa=f(a), fm=f(m), fb=f(b), or return failure
A = simpson(a,b,fa,fm,fb)
return visit(a,b,fa,fm,fb,A,tolerance,maxDepth)
visit(u,v,fu,fm,fv,A,tau,depth):
m = (u+v)/2; l = (u+m)/2; r = (m+v)/2
if nodes are not strictly ordered: return failure
evaluate fl=f(l), fr=f(r), or return failure
left = simpson(u,m,fu,fl,fm)
right = simpson(m,v,fm,fr,fv)
B = left + right; D = B-A
if abs(D)/15 <= tau: return success(B+D/15, abs(D)/15)
if depth == 0: return failure
leftResult = visit(u,m,fu,fl,fm,left,tau/2,depth-1)
rightResult = visit(m,v,fm,fr,fv,right,tau/2,depth-1)
if either child failed: return failure
return success(leftResult.value+rightResult.value,
leftResult.estimate+rightResult.estimate)
The returned estimate is the sum of accepted local indicators; it is not a proven upper bound. An implementation may return partial work along with failure, but must not label that work a successful tolerance guarantee. It should also handle nonfinite function values and intermediate results. In floating-point code use an overflow-safe midpoint construction suited to the allowed domain and explicitly detect collapsed nodes and underflowed tolerances; a depth cap by itself does not certify accuracy.
To obtain the certified variant, replace the acceptance condition by and return with that bound. Keep the same split and failure rules. If the known global is finite and arithmetic is exact, uniform subdivision to depth makes the ratio of each leaf bound to its allocated budget equal to . Thus a sufficiently large finite guarantees acceptance, and summing leaf budgets proves global error at most . This argument uses the same global at every node; sharper local bounds can also certify leaves, but require their own valid bounds and termination argument. A finite maxDepth smaller than required can still cause failure. This termination result does not apply to the heuristic test with arbitrary non-smooth or inaccurate evaluations.
Common mistakes
Counterexample mode
Five samples cannot certify every smooth function
Let on . It is a nonnegative polynomial, positive except at finitely many points. Both root rules sample only zeros, so and the heuristic accepts any positive tolerance, although . Scaling can make the missed integral arbitrarily large. There is no contradiction with the derivative-bound theorem: the bound changes when the function is scaled.
Adding leaf estimates below a budget is bookkeeping, not proof that the true errors obey those estimates. Conversely, a rigorous bound can be much larger than the actual error; failure to certify is not proof that the numerical answer is wrong. Using for each child is valid even on an uneven final tree because the sum of all leaf budgets equals the root budget.
Concept lensStructural
Three separate statements
The difference measures agreement between two finite sample formulas. The asymptotic model relates this difference to a leading error term. A certificate bounds the whole error under quantitative assumptions. None of these statements can be silently substituted for another.
Common mistake
(Correcting in the wrong direction)
Since and the model gives , the correction is . Writing , or using , moves the answer away from the integral. For on the correct formula gives exactly, while the reversed sign gives , whose error is twice that of the uncorrected .
Common mistake
(Passing the full tolerance to each child)
If each child receives instead of , a tree with leaves can accept local estimates adding up to almost . The halving rule is what makes the leaf budgets add up to the root tolerance; without it even the bookkeeping total exceeds the requested budget.
Quick check
Quick check
(If , what sign is the correction added to ?)
Recall the definition of and of .
Solution · Answer
It is positive: . This answers a sign question in the model; it does not prove that underestimates the integral.
Exercises
Quick check
(On with , use to find the fine-rule certificate at the root. Does it meet ?)
Use the certificate with a single panel of length .
Solution · Answer
The bound is , which exceeds . The test does not certify that tolerance. This is also the actual fine-rule error for this quartic: .
Quick check
(Prove that the sum of the allocated tolerances of all leaves is the root tolerance for any finite binary subdivision tree.)
Track what one split does to the total.
Solution · Answer
Initially there is one leaf with the whole budget. Splitting replaces one leaf of budget by two of budget , preserving the sum. Induction over the finite number of splits proves the assertion.
Quick check
(Suppose each sampled value has absolute error at most . Bound the resulting perturbation of a partition sum of fine Simpson values in exact weighted arithmetic.)
Simpson weights are positive.
Solution · Answer
Simpson weights on each child are positive and sum to that child's length. Hence perturbation on each panel is at most , and the partition sum is at most . Reused samples are not assumed independent. Rounding and evaluation bias outside this assumed bound remain separate.
Quick check
(Express as a weighted rule on the five equally spaced root nodes, and deduce why it integrates every polynomial of degree at most five exactly.)
Write and collect the coefficient of each sample.
Solution · Answer
With and , and combining weights gives . It is exact through cubics because both and are. The correction cancels the quartic error exactly; symmetry then makes the centered fifth power integrate to zero in both rule and integral. Linear combination proves exactness through degree five, with no claim for degree six.