3.6 Numerical Integration

Big idea

The fundamental theorem converts a definite integral into a subtraction, but only if you can produce an antiderivative. The previous section showed that some integrands have none in elementary form, and in applied work you often have no formula for the integrand at all, only a table of measured values. In both situations the integral still exists and still means something, so you need a way to compute it from values of the function alone.

Riemann sums already do this. Partition the interval, evaluate the function somewhere in each piece, multiply by the widths, and add. What this section adds is accuracy. A left or right endpoint sum approximates the function on each subinterval by a constant, which is a crude fit, and the error shrinks only in proportion to $1/n$. Better approximations of the function on each piece buy better approximations of the integral for the same amount of arithmetic.

Two upgrades matter. Join consecutive points with a straight line instead of a horizontal one, and each subinterval contributes the area of a trapezoid; the error now shrinks like $1/n^2$. Fit a parabola through each consecutive triple of points, and the error shrinks like $1/n^4$. That last rate is why doubling the work on a Simpson computation typically buys you more than four extra digits, and why it is the default rule in software.

The other half of the section is the error bounds. An approximation with no bound on its error is a number you cannot act on. Each rule comes with an inequality involving a bound on a derivative of the integrand, and that inequality is used in reverse: given a tolerance, solve for the number of subintervals that guarantees it. Notice that the bounds are guarantees, not estimates, so the actual error is usually well inside them.

Decoder

The trapezoidal rule replaces the integrand by a straight line on each subinterval, and Simpson rule replaces it by a parabola through each consecutive pair of subintervals, so the second requires an even number of subintervals.

The requirement of an even $n$ is not a convention; it is forced by the construction. A parabola is determined by three points, so each parabolic piece spans two subintervals. If $n$ were odd, the last piece would have only two points to work with and the rule would be undefined there.

The weights in the two formulas come directly from the geometry. In the trapezoidal rule every interior point is shared by two trapezoids, which is why the interior coefficients are $2$ and the endpoints are $1$. In Simpson rule the alternating $4, 2, 4, 2, \dots$ pattern is what integrating a parabola over a pair of subintervals produces, with interior points that end a piece and begin the next one getting counted twice.

The classic mistake is mismatching the weight pattern to the index, usually by putting a $4$ on an even-indexed interior point. A quick audit: the coefficients must sum to $3n$, since applying the rule to the constant function $1$ has to return $b-a$.

Definitions and results

The setup. Partition $[a,b]$ into $n$ subintervals of equal width $\Delta x = \frac{b-a}{n}$, with nodes $x_i = a + i\,\Delta x$ for $i = 0,1,\dots,n$, and write $f_i = f(x_i)$.

The midpoint rule. Approximate $f$ by its value at the centre of each subinterval:

$$ M_n = \Delta x\left[f\!\left(\tfrac{x_0+x_1}{2}\right) + \cdots + f\!\left(\tfrac{x_{n-1}+x_n}{2}\right)\right] $$

This is a Riemann sum, and it is usually about twice as accurate as the trapezoidal rule for the same $n$.

The trapezoidal rule.

$$ T_n = \frac{\Delta x}{2}\Big[f_0 + 2f_1 + 2f_2 + \cdots + 2f_{n-1} + f_n\Big] $$

Equivalently $T_n$ is the average of the left and right endpoint sums.

Simpson rule. For even $n$,

$$ S_n = \frac{\Delta x}{3}\Big[f_0 + 4f_1 + 2f_2 + 4f_3 + \cdots + 4f_{n-1} + f_n\Big] $$

Odd-indexed nodes carry weight $4$, even-indexed interior nodes carry weight $2$.

Trapezoidal error bound. If $|f''(x)| \le M$ for all $x$ in $[a,b]$, then

$$ \left|\int_a^b f(x)\,dx - T_n\right| \le \frac{M(b-a)^3}{12n^2} $$

The midpoint rule satisfies the same bound with $24$ in place of $12$.

Simpson error bound. If $\big|f^{(4)}(x)\big| \le M$ for all $x$ in $[a,b]$, then

$$ \left|\int_a^b f(x)\,dx - S_n\right| \le \frac{M(b-a)^5}{180n^4} $$

Exactness. The trapezoidal rule is exact for linear integrands, since $f'' = 0$ makes the bound zero. Simpson rule is exact for cubics as well as quadratics, because the fourth derivative of a cubic vanishes. Getting one extra degree for free is why the rule outperforms its parabolic construction.

Sizing $n$ for a tolerance. To guarantee an error below $\varepsilon$, set the appropriate bound less than or equal to $\varepsilon$ and solve for $n$, then round up, and round up again to the next even integer for Simpson rule.

Worked examples

Trapezoids on a known integral

Approximate $\int_1^2 \frac{dx}{x}$ with $n = 4$.

Here $\Delta x = 0.25$ and the nodes are $1, 1.25, 1.5, 1.75, 2$, with values $1$, $0.8$, $0.666667$, $0.571429$, $0.5$. The rule gives

$$ T_4 = \frac{0.25}{2}\Big[1 + 2(0.8) + 2(0.666667) + 2(0.571429) + 0.5\Big] = 0.125(5.576190) = 0.697024 $$

The exact value is $\ln 2 = 0.693147$, so the actual error is $0.003877$. Compare that with the guarantee: $f''(x) = \frac{2}{x^3}$ is largest at $x = 1$, so $M = 2$ and the bound is

$$ \frac{2(1)^3}{12(4)^2} = \frac{2}{192} = 0.010417 $$

The actual error sits comfortably below it, as a bound requires.

Parabolas on the same integral

Approximate $\int_1^2 \frac{dx}{x}$ with $n = 4$ using Simpson rule.

Same nodes, different weights:

$$ S_4 = \frac{0.25}{3}\Big[1 + 4(0.8) + 2(0.666667) + 4(0.571429) + 0.5\Big] = 0.083333(8.319048) = 0.693254 $$

The error is now $0.000107$, roughly forty times smaller than the trapezoidal error for identical function evaluations. The bound agrees: $f^{(4)}(x) = \frac{24}{x^5}$ has $M = 24$ on $[1,2]$, giving

$$ \frac{24(1)^5}{180(4)^4} = \frac{24}{46080} = 0.000521 $$

Choosing $n$ from a tolerance

How many subintervals guarantee an error below $0.001$ for $\int_1^2 \frac{dx}{x}$?

For the trapezoidal rule, require $\frac{2}{12n^2} \le 0.001$. That is $n^2 \ge \frac{2}{0.012} = 166.67$, so $n \ge 12.9$ and $n = 13$ suffices.

For Simpson rule, require $\frac{24}{180n^4} \le 0.001$. That is $n^4 \ge \frac{24}{0.18} = 133.3$, so $n \ge 3.40$, and rounding up to the next even integer gives $n = 4$. The computation above already met the tolerance, which confirms the arithmetic.

Thirteen evaluations against four, for the same guarantee. The gap widens as the tolerance tightens, because one rate is $n^{-2}$ and the other is $n^{-4}$.

An integral with no elementary antiderivative

Approximate $\int_0^1 e^{-x^2}\,dx$ with $n = 4$ using Simpson rule.

No antiderivative exists in elementary form, so the numerical route is the only route. With $\Delta x = 0.25$ the values are $1$, $0.939413$, $0.778801$, $0.569783$, $0.367879$, and

$$ S_4 = \frac{0.25}{3}\Big[1 + 4(0.939413) + 2(0.778801) + 4(0.569783) + 0.367879\Big] = 0.083333(8.962265) $$

which is $0.746855$. The true value to six places is $0.746824$, so four parabolas over the whole interval already deliver four correct digits. A sanity check on the size: the integrand decreases from $1$ to about $0.368$ on an interval of length $1$, so any answer between those two numbers is plausible, and a value nearer the upper end is what the shape of the curve predicts.

Practice

Begin with the sums themselves. These problems build partitions, evaluate at the required nodes, and assemble left, right, midpoint and trapezoidal approximations by hand.

Then compare approximations against exact values. Computing the definite integral exactly is what lets you measure an error and check it against the guaranteed bound.

Quiz

Five items on the trapezoidal and Simpson formulas, the even-$n$ requirement, and using error bounds to choose the number of subintervals.