Why subdivide selectively?
A uniform quadrature grid spends the same effort in smooth and rapidly changing regions. An adaptive method compares approximations on a panel and its children, then refines where they disagree most. The comparison is useful only when we understand what it measures: the difference of two approximations is not, by itself, a guaranteed bound on either error.
Definition 7.3.1
(Simpson comparison on a panel)
For an interval of width , let . Simpson's rule is
Write and . Given , and a tolerance , the adaptive problem is to return an approximation of together with a decision of which panels to refine. The quantity is the error indicator of the panel.
The second approximation uses five nodes; the endpoint and midpoint values are shared. When a panel is split again, previously computed values can be reused.
Why a factor of fifteen appears
Theorem 7.3.2
(Simpson error on one panel)
If , then for some
This is the standard Simpson remainder; its derivation, with the sign and the constant, is carried out in the note on composite trapezoid and Simpson rules. The two half-panel errors separately have the same form with width , possibly with different intermediate points. If is nearly constant on the panel, the leading errors approximately satisfy , because two half panels contribute . Subtracting the two equations gives
For a general function the ratio need not be exactly , even when is smooth. For polynomials of degree at most five it is exact.
Theorem 7.3.3
(The correction is exact for polynomials of degree at most five)
Let be a polynomial of degree at most five. Then on every panel ,
and consequently .
Proof
(Symmetry about the midpoint)
Write . Simpson's rule is exact on : for , the integral over is and the rule gives ; the odd powers have zero integral and zero rule value by symmetry. For the integral is and the rule gives , so the error is . Hence , and since this equals .
Apply the same formula to the half panels, of width and midpoints . Because is a polynomial of degree at most one, . Therefore
Subtracting, , so .
Proof X-ray
The two errors share a leading term only under extra information
The factor fifteen comes from subtracting errors in the ratio sixteen to one. In the proof above, the hypothesis "degree at most five" is used exactly once: it makes affine, so the average of at the two half-panel midpoints equals its value at . For a general , the fourth-derivative theorem gives different unknown intermediate points on the two halves; it does not say their derivative values are equal. A reliable stopping decision needs either additional bounds or acceptance that the difference is a heuristic. The absolute quantity is therefore an error indicator, not an unconditional certificate.
A simple refinement rule
Given a local tolerance , calculate on a panel. If , accept the corrected value ; otherwise bisect and recurse, assigning each child tolerance .
Proposition 7.3.4
(Tolerances add up to the original tolerance)
Suppose the recursion stops with accepted panels , where sits at depth and carries the tolerance . If each accepted value has genuine error at most its assigned tolerance, then the total absolute error is at most .
Proof
(Halving preserves the sum)
At the start there is one panel with tolerance . Each bisection replaces a panel of tolerance by two panels of tolerance , which leaves the sum of assigned tolerances unchanged. So the final tolerances sum to , and the triangle inequality bounds the total error by that sum.
The premise, that each accepted value has genuine error within its tolerance, is exactly what the difference test alone does not prove. An implementation also needs a maximum recursion depth or minimum panel width, a policy when the indicator fails to decrease, and accounting for function-evaluation and arithmetic errors. If the midpoint rounds to an endpoint, bisection no longer produces a smaller floating-point panel. Such a stop is a failure to reach the requested accuracy, not evidence that the tolerance was met.
Common mistake
(Giving each child the full tolerance)
If both children inherit instead of , the assigned tolerances add up to after one split, and to more after further splits. The guarantee of the previous proposition is then lost, even when every panel meets its own test.
Proposition 7.3.5
(Function evaluations of the recursion)
If the recursion examines a full bisection tree whose accepted panels number , the total number of distinct evaluations of is .
Proof
(Counting new quarter points)
A full binary tree with leaves has nodes, and each node (accepted or split) computes and . The root needs , three values. For any other node, its endpoints and midpoint were already evaluated: the endpoints are the parent's endpoints or midpoint, and its midpoint is a quarter point of the parent. So each node needs only its own two quarter points as new values. A node at depth has width and its quarter points are odd multiples of from , so quarter points of nodes at different depths differ, and nodes at the same depth have disjoint panels. The total is .
Worked example 7.3.6
(A single panel for on )
On with , and
Thus and the correction is . Indeed . The sign is important: the indicator uses an absolute value, but the corrected approximation uses the signed difference.
Worked example 7.3.7
(Refinement trace with tolerance )
Continue with on and . The top panel has indicator , so it is bisected and each child receives . For and a panel of width , , so both children (width ) have and indicator . Both are accepted. For the left child, and , and the corrected value is . The right child is corrected to , so the total is . The run used evaluations: the five of the root panel plus four new quarter points.
Worked example 7.3.8
(A cubic is accepted at once)
For on , , and . The indicator is zero, so the panel is accepted without any split, and here that decision is correct because Simpson integrates cubics exactly. This is the boundary case where the indicator vanishes; in general a vanishing indicator need not mean zero error, as the next example shows.
Counterexample mode
Matching sampled values do not control what happens between them
Let on . It is a nonnegative polynomial, vanishes at all five nodes used by and , and is positive away from those nodes. Both approximations and their difference are zero, but . Multiplying by any positive constant scales the missed integral while leaving all five sampled values zero. Thus no rule using only these samples can supply a universal error guarantee without further assumptions. A certificate needs an extra hypothesis, for example a verified bound on a derivative of on the panel.
Common mistake
(Reading the indicator as a bound)
Accepting a panel because and then reporting "the error is at most " claims more than was proved. The indicator is an estimate that relies on being nearly constant on the panel. Report it as an estimate unless a separate derivative bound supplies the missing premise.
Practice and solutions
Quick check
(If and , find the indicator and corrected value.)
Solution · Answer
The indicator is , and the corrected value is .
Quick check
(Why are three of the five values in already available from ?)
Solution · Answer
The shared points are ; only the two quarter points are new.
Quick check
(Suppose two accepted child panels have rigorously certified errors at most each. Bound the total absolute error.)
Solution · Answer
Add the errors and apply the triangle inequality to get at most .
Quick check
(Can equality alone prove exact integration for an arbitrary smooth function?)
Solution · Answer
No. The nonnegative polynomial in the counterexample has both approximations zero but a positive integral.
Quick check
(A run accepts panels. How many distinct evaluations of did it use?)
Solution · Answer
By the evaluation count, . Each of the nodes of the bisection tree contributes two quarter points, plus values at the root.