Motivation
An integral collects information over an interval, yet a computer usually sees only finitely many function values. The trapezoid rule uses straight-line pieces. More accurate rules can exploit symmetry, exactness on larger polynomial spaces, or freedom to choose the sampling nodes. Accuracy must still be justified by assumptions on the integrand. A rule that integrates every cubic exactly need not accurately integrate a sharply localized continuous function that its nodes never encounter.
We develop two complementary ways of assessing a rule. A derivative bound supplies a rigorous a priori guarantee. Comparing coarse and fine approximations can instead estimate error under an asymptotic model. Adaptive methods use those comparisons to distribute effort unevenly. Understanding the distinction is essential: a small comparison is evidence under a model, whereas a certified bound needs hypotheses that actually control the unknown integrand.
Definitions
A quadrature rule on has the form . Its degree of precision is the largest integer for which it integrates every polynomial of degree at most exactly. Exactness conditions can be checked on because integration and quadrature are linear.
For a uniform partition with subintervals of width , define composite midpoint and, when is even, Simpson rules by
The Gaussian construction here uses the positive inner product . Let be the monic degree- polynomial orthogonal to all lower-degree polynomials. Its roots will be the nodes. Existence follows by subtracting the orthogonal projection of onto ; the Gram matrix is positive definite because the integral of a nonzero polynomial's square is positive.
For error estimation, write and suppose a family satisfies
with fixed and nonzero leading coefficient . A Richardson estimate uses two mesh widths to eliminate or estimate that leading term. The nonzero condition matters when interpreting ratios; if , a higher-order term may dominate. This is an assumption about a family of computations, not an identity implied by two numerical answers.
Theorem/Proposition
Theorem 6.1.1
(Smoothness bounds for midpoint and Simpson rules)
If and , then
If , is even, and , then
Midpoint has degree of precision one, and Simpson has degree of precision three. For convex , . If , . Equality is possible in each statement.
Theorem 6.1.2
(Gaussian precision and positive weights)
The polynomial has distinct roots in . Let be the degree- Lagrange basis polynomial for the th node. Using these nodes and weights gives a rule exact on . Every weight is positive and their sum is two. No rule using only real nodes in can be exact on all of .
Consequently bounded sample errors perturb the Gaussian result by at most . After affine mapping to , the bound is .
These uncertainty bounds concern exact weighted sums of perturbed input values. They do not include floating-point summation or the error of numerically evaluating the integrand. Positive weights prevent worst-case cancellation amplification in this absolute data model, but cannot rescue a rule that misses the integrand's essential structure.
An implementation also has to choose between increasing a rule's degree on one interval and splitting the interval into smaller pieces. These are different sources of new information. Splitting localizes a difficulty, whereas adding Gaussian nodes improves polynomial precision across the whole current interval. A function evaluation may itself be expensive, so the relevant cost can be the number of distinct sampled points rather than the number of additions. A composite method must scale each local weight by its own interval length and combine shared endpoint contributions using their actual local weights. For example, two adjacent trapezoids each contribute a half-weight to their common endpoint. These accounting choices are part of the mathematical rule being implemented; changing them changes the approximation, even if each function evaluation is accurate.
Proof sketch or proof idea
Midpoint symmetry and the Simpson kernel
Proof
(Taylor symmetry and a positive kernel)
On one panel of width and center , Taylor's theorem gives with . The odd linear term integrates to zero on . Integrating the remainder bound gives . Adding panels proves the global bound. Convexity gives , so the integral is at least the midpoint value times panel width.
For Simpson, work first on and write , where . Direct substitution shows vanishes on . The integral form of Taylor's theorem, based at , expresses any function as a cubic plus
Here . Apply and interchange finite weighted sums and continuous integrals. Then , with
For , only the endpoint contributes to the sampled truncated cubic, giving ; this is the displayed kernel. The negative half follows by direct calculation or symmetry of . Thus . Mapping a two-subinterval panel to supplies a factor , because integration contributes one power and the fourth derivative four. Adding panels gives . Kernel positivity proves the sign assertion. Applying the rules to and respectively shows that their stated degrees cannot be increased.
Why orthogonality doubles polynomial precision
Proof
(Root counting and polynomial division)
Let the sign-changing roots of inside be . If , take , with if . The product has constant sign on the interval except at its zeros: multiplication removes every interior sign change. It is nonzero on some subinterval, so its integral cannot vanish. But makes it orthogonal to , a contradiction. Thus there are at least sign-changing roots. Degree forces exactly distinct simple roots, all interior.
For any , polynomial division gives , with . Orthogonality makes the integral of zero; evaluating at the nodes also makes its quadrature zero. The interpolatory weights integrate exactly, proving precision. Apply this exactness to , of degree : its quadrature is , so
Exactness for the constant gives the weight sum. Finally, the square of the node product is a nonnegative degree- polynomial with positive integral, but it vanishes at every node. No -node rule can integrate it correctly. This proves the optimal precision claim without claiming that Gaussian quadrature is best for every nonpolynomial integrand.
Proof X-ray
Two uses of a positive inner product
The proof turns on one division. Writing reduces exactness on to exactness on , which interpolatory weights supply for any distinct nodes. The remaining piece is disposed of twice: its integral vanishes by orthogonality because , and its quadrature vanishes because the nodes are the roots of . That is the only place where the choice of nodes matters.
Positivity of the inner product is spent twice. In the root count, the nonzero polynomial of constant sign must have nonzero integral. In , exactness is applied to a polynomial of degree , so positive weights are a consequence of the extra precision rather than a separate computation. The optimality step closes the argument with the single test polynomial of degree ; it defeats any nodes, Gaussian or not.
What the adaptive estimator assumes
Under the stated asymptotic model,
The fine-grid leading error is therefore estimated by
The signed leading term cancels in , leaving . To claim a specific higher order requires a stronger expansion with a controlled next term. For Simpson, , so the familiar divisor is fifteen. Adaptive Simpson compares one panel with its two children, accepts the finer result or corrected result when the estimated local error is small, and otherwise subdivides. Dividing a parent's absolute tolerance between children ensures that a sum of valid local bounds would stay within the total budget. It does not transform heuristic local estimates into proved bounds.
Practical stopping must also account for a maximum subdivision depth, an integrand evaluation failure, indistinguishable floating-point nodes, and a requested tolerance below the data or arithmetic floor. These are outcomes to report, not reasons to label an unfinished computation successful. Reusing shared endpoint and midpoint values reduces work and preserves consistency. Absolute and relative tolerance should be distinguished when the true integral is near zero; a purely relative target can become meaningless there.
Worked examples
Worked example 6.1.3
(Midpoint and Simpson on a quartic)
For on , the exact integral is . With two subintervals, midpoint gives , an underestimate. Simpson gives , exceeding the integral by . Since and , the Simpson bound is , exactly attained.
Worked example 6.1.4
(Deriving the two-node Gaussian rule)
Orthogonality gives , so the nodes are . Symmetry and the constant moment give weights one each. Thus integrates cubics exactly. For , however, whereas the integral is . Gaussian precision is optimal for the number of samples, yet it remains finite precision on polynomial spaces, not exactness for all smooth functions.
They are the eigenvalues of a symmetric tridiagonal matrix, and the weights come from its eigenvectors.
A natural next question
How are the nodes computed when m is large?
They are the eigenvalues of a symmetric tridiagonal matrix, and the weights come from its eigenvectors.
The monic polynomials satisfy with . Hence the roots of are the eigenvalues of the symmetric tridiagonal matrix with zero diagonal and off-diagonal entries . If is a unit eigenvector for , then . For this returns and weights one.
Worked example 6.1.5
(Richardson removes a known leading error)
For on , composite Simpson has exact error . Thus , while . Their difference is , and the fine-grid estimator is . This equals the actual fine-grid error. The corrected value is exactly . The equality is special: this polynomial has no higher Simpson error terms.
Common mistakes
Counterexample mode
Zero coarse-fine difference need not mean zero error
On , take . It is nonnegative, positive between its finitely many zeros, and has strictly positive integral. The parent Simpson panel samples ; its two children additionally sample . The function vanishes at all five points. Both return zero, so their difference and the adaptive estimate are zero. Smoothness alone does not prevent this failure; a quantitative derivative bound or other validated function-class information is needed for certification.
An error order describes a limiting family, not a guarantee at the first coarse mesh. Discontinuities, endpoint singularities, rapid oscillation, and inaccurate function values can invalidate the assumed regime. Gaussian nodes are interior and do not automatically resolve endpoint behavior. More subdivisions can increase arithmetic cost without reducing input uncertainty. A trustworthy implementation records whether its target was met by a proved bound, a model-based estimate, or only an iteration limit.
Concept lensStructural
Exactness is an information budget
Choosing Gaussian nodes and weights creates enough freedom to satisfy moments through degree . The squared node product proves an unavoidable blind spot one degree later. Adaptive methods seek new information by sampling where a comparison suggests difficulty, but no finite deterministic sample set can rule out every smooth hidden bump without additional bounds.
Common mistake
(Mapping the nodes but not the weights)
On the Gaussian nodes are and the weights are . Rescaling only the nodes is a frequent slip. For the mapped two-node rule has nodes , where takes values summing to . With the correct weights the rule returns exactly; with the unscaled weights it returns .
Common mistake
(Using Simpson’s divisor for a rule of another order)
The divisor depends on the order of the rule being refined. For the trapezoid rule . On with , and , so the fine error is . The correct estimate matches it, while dividing by fifteen gives , five times too small.
Summary
Midpoint symmetry gives a second-order global bound; Simpson's positive fourth-derivative kernel gives fourth order and its error sign. Orthogonal polynomial roots generate positive Gaussian weights and optimal polynomial precision. Richardson comparisons estimate leading errors only in a justified asymptotic regime. Adaptive subdivision can allocate effort and tolerances effectively, while stopping reports must preserve the difference between estimates and guarantees.
Exercises
Quick check
(For on , compute and its error. Use in the midpoint theorem to find the smallest guaranteeing error at most .)
Midpoint with one panel samples only .
Solution · Answer
, so the underestimate is . The global bound is , attained for this quadratic. We need , hence . The notation denotes a derivative bound, not the two-panel midpoint approximation.
Quick check
(Map the two-node Gaussian rule to , list nodes and weights, and apply it to . Bound input uncertainty if each supplied function value has error at most .)
The affine map has scale factor one.
Solution · Answer
The nodes become and both weights remain one because the affine scale is one. The sum of cubed nodes is , equal to . The absolute weights sum to two, so input uncertainty is at most , attained by equal-sign errors.
Quick check
(Assume the exact model . For , compute the coarse and fine errors, the Richardson estimate for the fine result, and the corrected error.)
Use , so the divisor is .
Solution · Answer
The coarse error is and fine error . Their difference has magnitude . Dividing by gives , exactly the fine error. The corrected value has zero error in this exact two-term model. Unspecified higher terms would generally leave a remainder.
Quick check
(An adaptive routine accepts two child intervals using estimated errors and against a total absolute target . What can be asserted if these numbers are proved upper bounds? What changes if they are merely Simpson differences divided by fifteen?)
Distinguish a proved bound from a model estimate.
Solution · Answer
If they are valid local upper bounds and the domain is their union, the triangle inequality gives total quadrature error at most , before any separately excluded arithmetic or input error. Model-based estimates support only a conditional accuracy statement; the hidden-polynomial counterexample shows they need not bound the actual error. Report estimated convergence rather than a certified guarantee.