Numerical Quadrature: Newton-Cotes and Adaptive Rules
Derive quadrature rules by integrating interpolating polynomials, compare their error orders, and use local error estimates to guide adaptive refinement.
What a learner can do afterwards
- Derive the trapezium and Simpson rules by integrating interpolating polynomials
- Compare error orders and predict how halving the step changes each error
- Explain when an adaptive rule beats a uniform one and how it decides where to refine
1 · Read
You have built interpolating polynomials. Now integrate them to estimate I = ∫_a^b f(x) dx. On one panel, let W=b-a and t=(x-a)/W. The endpoint line is p(t)=(1-t)f(a)+t f(b). On [0,1], the integrals of 1-t and t are [t-t²/2]_0^1=1/2 and [t²/2]_0^1=1/2. Since dx=W dt, T=(W/2)[f(a)+f(b)]. This is exact for constants and lines.
For n equal trapezium subintervals, let h=(b-a)/n and x_i=a+ih. Adding the panel integrals gives T_n=(h/2)[f(x_0)+2f(x_1)+...+2f(x_(n-1))+f(x_n)]. Each shared interior sample occurs in two panels, so its coefficient is 2. There are n+1 samples.
On one Simpson panel, W=b-a and t=(x-a)/W. The endpoint-midpoint basis is L_0=2t²-3t+1, L_m=4t-4t², L_1=2t²-t. Integrate term by term on [0,1]: [2t³/3-3t²/2+t]_0^1=1/6; [2t²-4t³/3]_0^1=2/3; [2t³/3-t²/2]_0^1=1/6. Multiply each by W because dx=W dt. This gives S=(W/6)[f(a)+4f((a+b)/2)+f(b)].
Simpson is exact for polynomials of degree at most three. Quadratics are exact by construction. For a cubic, put u=x-m, where m is the panel midpoint, and d=W/2. Its difference from the quadratic interpolant is A(u³-d²u), where A is its leading coefficient. Replacing u by -u changes the residual's sign. The contributions at u and -u cancel, so its integral on [-d,d] is zero.
Composite Simpson uses an even number n of equal subintervals of width h=(b-a)/n. Each Simpson panel spans two subintervals, so W=2h. Adding panels gives S_n=(h/3)[f(x_0)+4f(x_1)+2f(x_2)+4f(x_3)+...+4f(x_(n-1))+f(x_n)]. Odd-index samples have coefficient 4; internal even-index samples have coefficient 2.
If f has a continuous second derivative on [a,b] and |f''(x)|≤M_2, the composite trapezium bound is |I-T_n|≤(b-a)M_2 h²/12. Its error is therefore O(h²) on a fixed interval. This is an upper bound; the actual error can be smaller or zero.
If f has a continuous fourth derivative on [a,b] and |f''''(x)|≤M_4, the composite Simpson bound is |I-S_n|≤(b-a)M_4 h⁴/180, with n even. Its error is O(h⁴). For one panel of width W, h=W/2, so the bound becomes M_4 W⁵/2880.
For sufficiently small steps, suppose the absolute error is E(h)≈C h^p with C nonzero and rounding negligible. Halving h predicts E(h/2)≈E(h)/2^p: about E/4 for trapezium or E/16 for Simpson. These are leading-error predictions, not exact ratios for every function. Large steps, cancellation, limited smoothness or rounding can disturb them.
Suppose Q(h)=I+c h^p and Q(h/2)=I+c h^p/2^p model the leading signed errors. Subtracting gives an estimate for the finer result: |Q(h/2)-I|≈|Q(h/2)-Q(h)|/(2^p-1). Divide the difference by 3 for trapezium or by 15 for Simpson when the panel width is halved. This estimates error; it is not a guaranteed bound. A further refinement is needed to check the trend in the differences.
Adaptive quadrature estimates errors separately on subintervals and refines selected parts. One largest-error-first strategy splits the subinterval with the largest estimate, then replaces it with estimates for its children. Other strategies test panels recursively against local tolerances. Equal refinement everywhere is not required.
These bars show error estimates, not function heights. A largest-error-first strategy would split B next.
A detected narrow peak can favor adaptivity: spend more samples near it and fewer on smooth stretches. This can save evaluations compared with uniform refinement. But a peak between all sampled points can be missed, even when the estimated error is zero. Choosing the largest estimate also does not prove which split will reduce the true error most.
Add nonnegative local absolute error estimates to estimate total error. A recursive scheme can assign each child half its parent's tolerance. If e_1≤τ/2 and e_2≤τ/2, then e_1+e_2≤τ, the parent tolerance. For example, a parent tolerance of 0.006 gives each child 0.003. Passing these tests controls estimated error, not a proven true-error bound.
Stop successfully when the chosen estimated-error test meets the tolerance. Also set an evaluation or subdivision limit and check for rounding or inability to split further. If a limit stops the calculation before tolerance is met, report the unmet tolerance. Identical successive floating-point estimates alone do not prove accuracy.
Integrate interpolants to get the rules. Smooth composite errors are O(h²) and O(h⁴). Adaptive refinement follows error estimates, with tolerance and work-limit checks.
Original lesson, questions, worked solutions and flashcards written for this dataset.
Original readings, extra questions, worked solutions and flashcards written for this dataset.
More to read
From sample values to integration weights
An interpolant supplies a formula between sampled values. A Newton-Cotes rule integrates that formula using equally spaced nodes.
Let a panel have width W=b-a and set t=(x-a)/W. Then dx=W dt. The endpoint line is (1-t)f(a)+t f(b). Integrating 1-t and t from 0 to 1 gives 1/2 for each. Multiplication by W gives the trapezium formula W[f(a)+f(b)]/2.
For nodes t=0, 1/2 and 1, the quadratic basis functions are 2t²-3t+1, 4t(1-t) and 2t²-t. Integrate them separately. Their antiderivatives are 2t³/3-3t²/2+t, 2t²-4t³/3 and 2t³/3-t²/2. Evaluating at 0 and 1 gives weights 1/6, 2/3 and 1/6. Simpson's rule is therefore (W/6)[f(a)+4f((a+b)/2)+f(b)].
A cubic need not equal its quadratic interpolant. However, their difference is odd about the panel midpoint. Its contributions on opposite halves cancel when integrated. This makes Simpson exact through degree three.
Composite trapezium counts shared endpoints twice. Composite Simpson joins pairs of equal subintervals. If h is one subinterval's width, a Simpson panel has width 2h. The number of subintervals must be even.
Bounds and refinement predictions
A derivative bound can give a guaranteed quadrature error bound under stated smoothness assumptions. If f has a continuous second derivative and |f''|≤M_2 on [a,b], composite trapezium error is at most (b-a)M_2 h²/12. If f has a continuous fourth derivative and |f''''|≤M_4, composite Simpson error is at most (b-a)M_4 h⁴/180. Simpson needs an even number of equal subintervals, each of width h.
These bounds establish orders O(h²) and O(h⁴) on a fixed interval. The actual error need not equal the bound. A rule can even be exact.
Refinement ratios need an additional assumption. Suppose a nonzero leading absolute error behaves as C h^p and rounding is negligible. Halving h predicts a factor 1/2^p: one quarter for order two and one sixteenth for order four. Large steps, cancellation, limited smoothness or rounding can disrupt this prediction.
When the true integral is unknown, coarse and fine results can estimate error. Write their leading signed errors as Q(h)-I=c h^p and Q(h/2)-I=c h^p/2^p. Subtracting shows that the finer result's absolute error is approximately |Q(h/2)-Q(h)|/(2^p-1). The divisors are 3 for trapezium and 15 for Simpson. This is an estimate under a model, not a guaranteed bound. A further refinement supplies another difference for checking the trend.
Where to refine and when to stop
An adaptive calculation keeps separate error estimates for different parts of an interval. One strategy splits the part with the largest estimate and replaces it with estimates for the two children. A recursive strategy tests panels against assigned local tolerances. Selective refinement does not require one universal visit order.
Add nonnegative local absolute error estimates to estimate total error. A recursive scheme can divide a parent's tolerance equally between its children. If each child estimate is at most half the parent tolerance, their sum is at most the parent tolerance. This controls estimated error, not necessarily true error.
A detected localized feature can make selective refinement useful. Uniform refinement also adds samples in regions that were already adequately resolved. But a finite sample set can miss a narrow feature between its samples, producing a misleadingly small or zero error estimate. Ranking error estimates does not guarantee which split will reduce true error most.
An implementation needs an accuracy test and limits on work. Check whether the estimated error meets tolerance, whether the evaluation or subdivision budget is exhausted, and whether rounding prevents further progress. If a limit is reached while the tolerance test still fails, report the unmet tolerance. Identical successive floating-point results alone do not establish accuracy.
2 · Watch
En anglaisTake it off screen
Where it sits
This opens up
Nothing builds on it yet.
17 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.