5.3 Integration algorithms

Source: Ideas from Computational Physics (Landau, Páez, Bordeianu), §5.3–§5.3.5. Rewritten in original wording. Continues 5.2 Extrapolated difference. Labs: 5.3b Integration labs.

Problem: integrate a spectrum

A counter records a rate $dN/dt$ — particles per unit time. The number that arrived in the first second is the area under that rate curve:

$$N(1)=\int_0^1 \frac{dN(t)}{dt}\,dt.$$

You may have no antiderivative in closed form — only samples of the rate. The job is numerical quadrature: turn the integral into a finite, stable sum.

Box counting (Riemann sums)

Graph-paper counting of boxes under a curve is the oldest numerical integration picture; the name quadrature stuck even for rules far past plain boxes. On a computer there is no infinitesimal $h$ — every practical rule is a weighted sum of samples. Walk the $\sum f_i w_i$ skeleton, left boxes, and midpoint rule — pick each equation among lookalikes.

Figure 5.2 shows the idea: four equal panels of width $h$, five marked abscissae from $a$ to $b$. The shaded rectangles are one concrete choice of heights (here left-endpoint samples).

Equal-spacing workhorses: trapezoid and Simpson

Partition $[a,b]$ into $N$ panels of width $h=(b-a)/N$ and write $f_i=f(a+ih)$. Walk the one-panel trapezoid, composite trapezoid, and composite Simpson — pick the matching equation at each step.

Simple integration error estimates

Choose a rule that reaches a useful answer with the fewest samples. A crude estimate of the algorithmic error $\mathcal{E}$ for equal-spacing rules expands $f$ in a Taylor series about a panel midpoint, then multiplies by the number of panels to cover $[a,b]$. Relative error is $\varepsilon=|\mathcal{E}|\big/\big|\int_a^b f\big|$ when the integral is not tiny.

Standard leading results for smooth $f$:

$$\mathcal{E}_{\mathrm{trap}}\sim O(h^{2})\sim\frac{(b-a)\,h^{2}}{12}\langle f''\rangle, \qquad \mathcal{E}_{\mathrm{simp}}\sim O(h^{4})\sim\frac{(b-a)\,h^{4}}{180}\langle f^{(4)}\rangle.$$

Those scalings are illuminating:

• Simpson needs fewer points and has less error than trapezoid for the same smooth $f$.
• With Simpson (and other higher-order rules) you can push error near machine precision.
• The best numerical integral is not $N\to\infty$. A modest $N\lesssim 10^{3}$ often sits near the sweet spot; larger $N$ mostly buys round-off.

Higher-order algorithms (Romberg)

As with differentiation, if you know how the error depends on $h$, you can cancel the leading term. Walk the trap/Simpson scalings, the $A(h)$ / $A(h/2)$ expansions, the Romberg combo, and the $\sum w_i=b-a$ audit — pick the matching equation at each step.

Elementary weights and a sanity check

Equal-interval “single-block” rules use a small stencil that you tile across $[a,b]$. Shared endpoints of adjacent blocks are counted twice when blocks are strung together. Typical elementary weights:

Rule	Panels / block	Weights (factor $h$ omitted)
Trapezoid	1	$\tfrac12,\;\tfrac12$
Simpson	2	$\tfrac13,\;\tfrac43,\;\tfrac13$
Three-eighths	3	$\tfrac38,\;\tfrac98,\;\tfrac98,\;\tfrac38$
Milne (Boole)	4	$\tfrac{2}{45}(7,32,12,32,7)$

If your weight list fails $\sum_i w_i=b-a$ (the guide’s last step), the stencil is wrong before you ever touch a nontrivial $f$.

Quiz

Quadrature, errors, Romberg

1 / 4

N(1)=∫₀¹ (dN/dt) dt asks you to…

Pick an answer to see if you are right.

Next: 5.3b Integration labs. Then 5.4 Gaussian quadrature.