From Local Accuracy to a Global Target
An adaptive quadrature calculation divides an integration interval into panels and approximates the integral on each panel. The approximation on any one panel can be imperfect, so a practical accuracy goal must account for the errors across all panels—not just the error on the panel currently being examined.
The central bookkeeping rule is simple: local error allowances must fit within the global allowance. When the local errors are only estimates, their sum gives a useful stopping indicator, but not necessarily a mathematical guarantee. Keeping that distinction clear makes the method easier to use and interpret.
Panels, Errors, and Tolerances
Suppose an interval \([a,b]\) is partitioned into \(m\) panels, with endpoints \(x_0=a<x_1<\cdots<x_m=b\). Write \(I_i\) for the exact integral over panel \(i\), and \(Q_i\) for its quadrature approximation. The signed local error is \(I_i-Q_i\); its absolute error is \(|I_i-Q_i|\). The composite approximation is \(Q=\sum_{i=1}^m Q_i\).
A local tolerance \(\tau_i\) is the amount of error allowed for panel \(i\). A global tolerance \(\varepsilon>0\) is the desired allowance for the full interval. A valid allocation satisfies \(\sum_{i=1}^m\tau_i\le\varepsilon\). If every local absolute error is at most its tolerance, the global absolute error is at most \(\varepsilon\).
The inequality in the middle is the triangle inequality. It explains why local errors are added by magnitude rather than allowed to cancel. In practice, the exact local errors are unknown. Adaptive Simpson methods instead use estimated errors, commonly obtained by comparing a Simpson approximation on a panel with the sum of Simpson approximations on its two halves.
Allocating the Local Tolerances
There is no single allocation that is best for every integrand. One straightforward choice is to divide the global tolerance in proportion to panel width. For panels of widths \(w_i=x_i-x_{i-1}\), define \(\tau_i=\varepsilon w_i/(b-a)\). Since the widths sum to \(b-a\), the local tolerances sum exactly to \(\varepsilon\). This gives a longer panel a larger share of the error budget, but it does not account for how difficult the integrand is on that panel.
Another choice is to divide the tolerance equally among the current panels. That is simple, but after repeated subdivision the number and widths of panels may not reflect where the approximation is hardest. A flexible alternative is to assign positive local tolerances according to known features of the problem, while always checking that their sum does not exceed the global target.
During adaptive refinement, a parent panel’s tolerance must be reassigned to its children. Splitting it equally is a convenient default: each child receives half. This preserves the total budget. Other distributions are possible, but the children’s tolerances must still sum to no more than the parent’s allowance.
Why the Largest Estimated Errors Are Refined First
Suppose several panels remain, each with an estimated absolute error \(e_i\). Their combined estimate is \(E=\sum_i e_i\). If refinement is limited by time or function evaluations, a panel contributing a large share of \(E\) is a natural priority: reducing that contribution can lower the total estimate substantially. This is a practical prioritization rule, not a claim that every split will reduce error by a fixed factor.
Use the chosen quadrature error estimator to obtain a nonnegative value \(e_i\).
Compute \(E=\sum_i e_i\). If \(E\leq\varepsilon\), the estimated global target has been met.
If \(E>\varepsilon\), select a panel with a largest estimated error, or one of the largest errors.
Bisect the selected panel, compute new estimates for its children, and replace the parent’s estimate by the sum of the two child estimates.
Recalculate \(E\) over the current leaves of the partition and compare it with \(\varepsilon\).
The leaves are the panels that currently make up the partition. A refined parent is no longer one of those panels, so its estimate must not be counted alongside its children. Otherwise the same part of the interval is counted twice.
Worked Example: Allocate a Budget by Panel Width
Worked Example: Allocate a Budget by Panel Width
Suppose \([0,1]\) has two current panels, \([0,0.4]\) and \([0.4,1]\), and the global tolerance is \(\varepsilon=0.02\). Allocate tolerance in proportion to width.
The widths are \(w_1=0.4\) and \(w_2=1-0.4=0.6\). The interval width is \(b-a=1\). Therefore
Check the allocation: \(\tau_1+\tau_2=0.008+0.012=0.020=\varepsilon\). Suppose the computed estimates are \(e_1=0.006\) and \(e_2=0.015\). The first panel meets its local allowance because \(0.006\leq0.008\), but the second does not because \(0.015>0.012\). The total estimate is \(0.021\), which is also greater than \(0.020\). Refinement is therefore needed.
If the second panel is bisected and its tolerance is split equally, each child receives \(0.012/2=0.006\). Suppose their new estimates are \(0.004\) and \(0.005\). The current total estimate is now \(0.006+0.004+0.005=0.015\), which is below \(0.020\). The local checks also pass: \(0.006\leq0.008\), \(0.004\leq0.006\), and \(0.005\leq0.006\). The allocation and the total are consistent with the global target.
Worked Example: Refine the Largest Estimate First
Worked Example: Refine the Largest Estimate First
Suppose three panels have estimates \(0.040\), \(0.025\), and \(0.015\), with global target \(\varepsilon=0.050\). The initial sum is
Refine the panel with estimate \(0.040\). Its two children have estimates \(0.009\) and \(0.011\). Remove the parent estimate and use the children instead. The updated total is
The target is still unmet. The largest current estimate is \(0.025\), so refine that panel. Suppose its children have estimates \(0.008\) and \(0.006\). Replacing \(0.025\) gives
Now \(E=0.049\leq0.050\), so the combined estimated error meets the global target. As a bookkeeping check, the final total contains five current panels: the two children of the first split, the two children of the second split, and the original third panel. Neither refined parent is included.
Worked Example: Estimate Error on a Simpson Panel
Worked Example: Estimate Error on a Simpson Panel
For \(f(x)=x^4\) on \([0,1]\), compare the single-panel Simpson approximation \(S\) with the sum \(S_2\) from bisecting the interval. Simpson’s rule on \([u,v]\) is \((v-u)[f(u)+4f((u+v)/2)+f(v)]/6\).
On \([0,1]\), the function values are \(f(0)=0\), \(f(1/2)=1/16\), and \(f(1)=1\). Hence
On \([0,1/2]\), the midpoint is \(1/4\), with \(f(1/4)=1/256\). Thus
On \([1/2,1]\), the midpoint is \(3/4\), with \(f(3/4)=81/256\). Therefore
The refined sum is \(S_2=S_L+S_R=154/768=77/384\). The usual adaptive Simpson error estimate on the original panel is \(|S_2-S|/15\), so
For a check in this particular example, \(\int_0^1x^4\,dx=1/5=384/1920\), while \(S_2=77/384=385/1920\). The actual error of \(S_2\) is \(1/1920\), matching this estimate here. This agreement for \(x^4\) is not a general guarantee that an estimated error equals the actual error.
What the Stopping Test Does—and Does Not—Say
For adaptive Simpson quadrature, a common local estimate on a panel is the absolute difference between the refined two-half Simpson sum and the original Simpson approximation, divided by \(15\). This estimator is useful for comparing panels and guiding refinement. When the current panel estimates sum to at most \(\varepsilon\), the method’s estimated global error is within the requested target.
The stopping test is only as trustworthy as the estimates. Unless an independent error analysis supplies valid bounds for all current panels, the test is not a proof that the true integration error is below \(\varepsilon\). Rapid changes that the sampled values fail to reveal can make an estimate misleading. Thus, report the target and the result as an estimated accuracy when using estimates rather than certified bounds.
Common Pitfall: Letting Signed Errors Cancel
A tempting but incorrect approach is to add signed local errors and treat a small sum as evidence of small global error. For example, suppose two panels have signed errors \(+0.020\) and \(-0.018\). Their signed sum is \(0.002\), but the triangle inequality only assures an absolute global error no greater than the sum of their magnitudes, \(0.020+0.018=0.038\). The errors might partially cancel, but relying on cancellation can substantially understate the possible error.
Adaptive tolerance accounting avoids this mistake by using nonnegative error estimates or bounds. Another frequent bookkeeping error is to keep a refined parent in the total after adding its children. Always sum over the current panels only.
Check Your Understanding
Use the local-budget and refinement rules to answer these questions.
- If three proven local error bounds are \(0.004\), \(0.007\), and \(0.003\), what global tolerance is sufficient to certify their combined error?
- A global target is \(0.024\), and an interval of width \(3\) is split into panels of widths \(1\) and \(2\). What tolerances result from allocation in proportion to width?
- Current panel estimates are \(0.018\), \(0.011\), and \(0.006\), with target \(0.030\). Does the estimated stopping test pass? Which panel would the largest-error rule refine first?
- After splitting a panel with estimate \(0.020\), its child estimates are \(0.004\) and \(0.009\). What change should be made to the total estimate?
- Why does a total of estimated errors below the target not always certify the true integration error?
