The trapezium rule and Simpson's rule, their error formulae, and why Simpson's rule, exact for cubics, wins the race by a factor that grows with the work done.
Most definite integrals cannot be evaluated in closed form: ∫01e−x2dx has no elementary antiderivative, and even when one exists it may be clumsy. In practice integrals are computed numerically, from a few values of the integrand. §169 gives the two classical rules, the trapezium rule and Simpson’s rule, and, more importantly, exact formulae for their errors, so that an approximation comes with a guarantee. The proof for Simpson’s rule is a fine example of the Rolle-type argument behind Taylor’s theorem.
The idea
The trapezium rule replaces the curve between x=a and x=b by the straight chord, and the area by that of a trapezium: 21(b−a){f(a)+f(b)}. It is exact when f is linear, and its error is governed by how much the graph bends, that is, by f′′.
Simpson’s rule uses one more value, at the midpoint, and replaces the curve by the parabola through three points:
∫abf(x)dx≈61(b−a){f(a)+4f(2a+b)+f(b)}.
A parabola is exact for quadratics, as one would expect; the surprise is that Simpson’s rule is exact for cubics as well, because the symmetric placing of the three points makes the cubic term cancel. So its error is governed by f(4), and it is proportional to the fifth power of the interval length. Split [a,b] into n panels and apply a rule to each: the total error falls like 1/n2 for the trapezium rule and like 1/n4 for Simpson’s. Doubling the work divides the errors by about 4 and 16.
ExploreTrapezium against Simpson
Try this.With ex, move the slider and read how much each doubling of the work divides each error. Then try 1/(1+x2) and sinx; then the cubic x3−x; and last x.
∫01exdx=1.7182818: error against the number of function values used
ordinates (log scale)log₁₀|error|
trapezium rule
midpoint rule
Simpson’s rule
the row shown below
Integrand
With 9 ordinates: trapezium error 0.00224, Simpson error 2.33×10−6 (midpoint with 8 values: −0.00112).
Doubling the work divided the trapezium error by 4 and the Simpson error by 15.9 (the formulae predict about 4 and 16 for smooth integrands).
What to notice
For smooth integrands the points lie close to straight lines of slope about −2 (trapezium and midpoint) and −4 (Simpson), on these log scales, and the ratios settle near 4 and 16. Simpson reaches the limit of machine accuracy with about a thousand function values; the trapezium rule would need several thousand times as many (millions of values) to reach the same accuracy. For the cubic, Simpson is exact from the start. For x, whose derivatives are infinite at 0, the error formulae do not apply, and all three rules crawl along at the same slow rate.
The composite errors come from adding the panel errors, −121H3∑f′′(ξi), and noting that n1∑f′′(ξi) is an average of values of a continuous function, hence itself a value f′′(ξ) (the intermediate value theorem). Simpson’s case is identical.
Proofs
Hardy’s proof works with a symmetric interval. Write c for the midpoint and h for the half-width, so that a=c−h, b=c+h, and Simpson’s rule reads 31h{f(c−h)+4f(c)+f(c+h)}.
ProofThe error in Simpson’s rule
Strategy
Let the interval grow from nothing: let ψ(t) be the error of Simpson’s rule on [c−t,c+t]. It vanishes at t=0 together with its first two derivatives, and its third derivative is t2 times a value of f(4). Subtract a multiple of t5 chosen to vanish also at t=h, and apply Rolle’s theorem three times, as in the proof of Taylor’s theorem.
The error as a function of the half-width
For 0≤t≤h let
ψ(t)=∫c−tc+tf(x)dx−31t{f(c+t)+4f(c)+f(c−t)}.
We want ψ(h). Clearly ψ(0)=0.
Differentiate three times
By the fundamental theorem, dtd∫c−tc+tf=f(c+t)+f(c−t). Differentiating and simplifying,
ϕ(0)=ϕ(h)=0, so ϕ′(t1)=0 for some t1 in (0,h). Then ϕ′(0)=ϕ′(t1)=0, so ϕ′′(t2)=0 for some t2 in (0,t1). Then ϕ′′(0)=ϕ′′(t2)=0, so ϕ′′′(t3)=0 for some t3 in (0,t2).
Read off the error
Since t3=0, the bracket vanishes at t=t3: ψ(h)=−90h5f(4)(ξ) with ξ in (c−t3,c+t3)⊂(a,b). With h=21(b−a), h5/90=(b−a)5/2880, which is the formula. If f is a cubic then f(4)=0 and the rule is exact.
∎
The trapezium rule is proved the same way (Examples LXVII, 2): with ψ(t)=∫c−tc+tf−t{f(c+t)+f(c−t)} and ϕ(t)=ψ(t)−(t/h)3ψ(h), one application of Rolle’s theorem and one of the mean value theorem give an error −32h3f′′(ξ)=−121(b−a)3f′′(ξ).
Here are the parabolas themselves, panel by panel.
ExploreChords and parabolas
Try this.Switch between the trapezium rule and Simpson’s rule with n=1 and n=2 panels, and compare the errors in the read-out.
∫01exdx, trapezoid rule with n=1
xy
y = f(x)
pieces above the axis count +
below the axis count −
Rule
Trapezoid sum S1=1.85914; exact value 1.71828; error 0.141 (refine and watch how fast it shrinks).
What to notice
With a single panel the chord misses the curve visibly, while the parabola through the ends and the midpoint is hard to tell from it. The trapezium error is about −121f′′ times the cube of the width; Simpson’s is smaller by a large factor and shrinks much faster as n grows.
Worked examples and exercises
ExerciseComputing π●○○Hardy: Examples LXVII, 4
Apply Simpson’s rule to 41π=∫011+x2dx, first with the single panel [0,1], then with the two panels [0,21] and [21,1].
Hint
The values you need: f(0)=1, f(41)=1716, f(21)=54, f(43)=2516, f(1)=21.
The true value is 41π=0.7853982… (Hardy prints 0.7853916 for the two-panel value; the arithmetic above gives 0.7853922). Halving the panel width reduced the error from 0.0021 to 0.0000060, a factor of about 340, much more than 16: the asymptotic factor 16 is only reached once the panels are small, and the first panel here is wide for this function.
ExerciseThe second difference●●○Hardy: Examples LXVII, 1
Prove that if f has a second derivative, then f(x+h)−2f(x)+f(x−h)=h2f′′(ξ) for some ξ between x−h and x+h.
Hint
Use Hardy’s auxiliary function ϕ(t)=f(x+t)−2f(x)+f(x−t)−(t/h)2{f(x+h)−2f(x)+f(x−h)}, for 0≤t≤h.
Hint
ϕ(0)=ϕ(h)=0 and ϕ′(0)=0.
Solution
Let D=f(x+h)−2f(x)+f(x−h) and take ϕ as in the hint (with h>0; the case h<0 is the same with −h). Then ϕ(0)=0, ϕ(h)=D−D=0, and ϕ′(t)=f′(x+t)−f′(x−t)−2tD/h2, so ϕ′(0)=0. By Rolle, ϕ′(t1)=0 for some t1 in (0,h); then, applying the mean value theorem to f′ on [x−t1,x+t1],
0=ϕ′(t1)=2t1f′′(ξ)−h22t1D
for some ξ in (x−t1,x+t1). Dividing by 2t1=0 gives D=h2f′′(ξ). This is the case n=2 of Misc. Ex. 5, and it is the reason why {f(x+h)−2f(x)+f(x−h)}/h2→f′′(x) when f′′ is continuous.
Prove that ∫abf(x)dx=(b−a)f(2a+b)+241(b−a)3f′′(ξ) for some ξ in (a,b), if f′′ exists and f′ is continuous. Compare with the trapezium rule, and deduce a combination of the two that is exact for cubics.
Hint
Use ψ(t)=∫c−tc+tf−2tf(c) and the same device: ϕ(t)=ψ(t)−(t/h)3ψ(h).
Hint
The trapezium error is −2× the midpoint error (to leading order). Weight them to cancel.
Solution
With c=21(a+b), h=21(b−a) and ψ as in the hint, ψ(0)=0, ψ′(t)=f(c+t)+f(c−t)−2f(c), so ψ′(0)=0, and ψ′′(t)=f′(c+t)−f′(c−t). With ϕ(t)=ψ(t)−(t/h)3ψ(h): ϕ(0)=ϕ(h)=0 and ϕ′(0)=0. Rolle gives ϕ′(t1)=0, then ϕ′′(t2)=0 with 0<t2<t1<h. Now ϕ′′(t)=f′(c+t)−f′(c−t)−6tψ(h)/h3=2tf′′(ξ)−6tψ(h)/h3 by the mean value theorem, so ψ(h)=31h3f′′(ξ)=241(b−a)3f′′(ξ).
The midpoint error is +241(b−a)3f′′, the trapezium error −121(b−a)3f′′: opposite signs, the trapezium one twice as large. So 32(midpoint)+31(trapezium) cancels the f′′ term, and
which is Simpson’s rule. (In the widget, the midpoint and trapezium errors have opposite signs and ratio about −21.)
ExerciseWhen the error formula does not apply●●○Hardy: Examples LXVII, 6
Apply Simpson’s rule with five ordinates (two panels) to ∫12x−1/xdx. The true value is 0.85422…. Why is the result so much worse than for ∫011+x2dx?
Hint
The ordinates at x=1,1.25,1.5,1.75,2 are 0, 0.67082, 0.91287, 1.08562, 1.22474.
The error is about 0.015, which is large for five ordinates (compare 0.000006 for π/4). The reason: near x=1, x−1/x≈2(x−1), so the integrand behaves like 2(x−1) and its derivative is infinite at x=1. The error formula needs a bounded fourth derivative on the whole interval, and there is none here: it is the x case of the widget. A cure is a substitution that removes the square-root behaviour, for instance x=1+u2, after which the integrand is smooth.
Exercise●●○Hardy: Examples LXVII, 7
Show that ∫04x34x−x2dx=28π≈88.
Hint
4x−x2=4−(x−2)2. Put x=2+2sinθ.
Solution
With x=2+2sinθ, θ from −21π to 21π, we have 4x−x2=2cosθ and dx=2cosθdθ. The integral becomes
The odd powers of sinθ integrate to 0 over the symmetric interval. ∫cos2θ=21π and ∫sin2θcos2θ=81π over [−21π,21π]. So the value is 32(21π+83π)=28π=87.96…. (Simpson with five ordinates gives only about 75: the integrand has square-root behaviour at both ends, as in the previous exercise.)
Check yourself
Check yourselfEnter a number
For a smooth integrand, by roughly what factor does the error of composite Simpson’s rule fall when the number of panels is doubled?
Why
The composite error is −2880(b−a)H4f(4)(ξ); halving H divides H4 by 16. (For the trapezium rule, H2 gives 4.)
Check yourselfChoose one
For which of these is Simpson’s rule (one panel) exact on every interval?
Why
The error is a multiple of f(4)(ξ), which vanishes for cubics. The parabola through the three points is not the cubic, but the difference between them is a multiple of (x−a)(x−c)(x−b), an odd function about c whose integral over [a,b] is 0. For x4 on [0,1] the rule gives 61(0+164+1)=245, not 51.
Check yourselfTrue or false?
Since Simpson’s error is O(H4), doubling the number of panels always divides the error by about 16.
Why
False. The error formula assumes a fourth derivative on the closed interval. For x on [0,1] the derivatives are infinite at 0, and the error falls only like H3/2 for every one of the rules (the widget’s last integrand).
Check yourselfEnter a number
Simpson’s rule with a single panel for ∫011+x2dx gives what value?
Why
61{f(0)+4f(21)+f(1)}=61(1+3.2+0.5)=0.78333. The true value is 0.78540.
Hardy’s language
In practice again we divide the range of integration into pieces and apply the rule to each.
— G. H. Hardy, §169
Summary
Summary
Trapezium: ∫abf=21(b−a){f(a)+f(b)}−121(b−a)3f′′(ξ); exact for linear f.
Simpson: ∫abf=61(b−a){f(a)+4f(2a+b)+f(b)}−28801(b−a)5f(4)(ξ); exact for cubics.
The proof: the error on [c−t,c+t] as a function of t, corrected by a multiple of t5, and Rolle’s theorem three times.
Composite rules: errors fall like H2 and H4; doubling the work gains factors 4 and 16, but only for integrands with bounded derivatives of the relevant order.