Implementing numerical integration from scratch — trapezoidal, Simpson's: Visual walkthrough

We will only ever assume you can:

read a graph (a curve, an $x$ -axis going left-to-right, a $y$ -axis going up),
multiply a width by a height to get the area of a rectangle.

Everything else is built here.

Step 1 — What "area under a curve" means

WHAT. We name the goal: the shaded area in the figure.

WHY. Many curves have no clean formula for this area (no nice antiderivative), or we only have data points, not a formula. So we will never compute it exactly — we will cover the region with shapes whose area we already know and add those up.

PICTURE. The green region is the exact area we chase. Notice it has a curved lid — that curve is the whole difficulty.

Figure — Implementing numerical integration from scratch — trapezoidal, Simpson's

Step 2 — Chop the region into equal strips

WHAT. We slice $[a, b]$ into $n$ vertical strips of equal width $h$ .

WHY. Equal width means every strip is treated the same way — one formula per strip, then just add. It also makes the shared-edge bookkeeping (coming in Step 5) clean.

PICTURE. Dotted verticals drop from each node; the base is split into $n$ equal chunks of width $h$ .

Step 3 — Cover ONE strip with a straight roof (trapezoid)

The area of a trapezoid is average of the two parallel heights, times the base: $A_{i} = average height \frac{f ( x _{i} ) + f ( x _{i + 1} )}{2} \times width h .$ Term by term: $f (x_{i})$ is the left height, $f (x_{i + 1})$ the right height; adding and halving gives the middle height of the slanted lid; multiplying by width $h$ gives area — exactly a rectangle whose height is that average.

WHAT. One strip's area, approximated by a trapezoid.

WHY this shape and not a rectangle? A flat rectangle uses only one height and ignores the tilt of the curve; the slanted lid uses both edge heights, so it follows the curve's slope. That is a strictly better guess for the same effort.

PICTURE. The teal trapezoid; its slanted lid touches the curve at both node dots. The small green gap between lid and curve is the error we make on this strip.

Step 4 — Add all trapezoids → the composite Trapezoidal rule

We add up every strip's area and look at what each node contributes: $\sum_{i = 0}^{n - 1} \frac{f ( x _{i} ) + f ( x _{i + 1} )}{2} h .$

WHAT / WHY. Watch a single interior node, say $x_{1}$ . It is the right edge of strip 0 and the left edge of strip 1, so its height $f (x_{1})$ appears in two trapezoids — it gets counted twice. The two far ends, $x_{0}$ and $x_{n}$ , belong to only one trapezoid each — counted once. Collecting like terms:

PICTURE. The whole region tiled with trapezoids. The end nodes glow once; each shared interior node glows twice — literally the weight-2.

Recall Why trapezoid error is

$O (h^{2})$ The straight lid is exact for a straight curve (degree-1). For a bending curve the leftover gap per strip shrinks like $h^{3}$ , and there are about $1/ h$ strips, so the total error scales as $h^{2}$ . Halve $h$ → error drops ~4×. See Taylor series.

Step 5 — The bend that trapezoids can't catch

WHAT. We show, on a single hump, the sliver of area a straight lid always leaves on the table.

WHY a parabola next? The next-simplest curve after a line is a parabola — a shape of the form $α + β x + γ x^{2}$ . That extra $γ x^{2}$ term is exactly a bend. A parabola is fixed by three points, so we must widen our view from one strip to a pair of strips (three nodes). This is why Simpson's rule works in pairs — and why $n$ must be even.

PICTURE. Straight lid (dashed teal) vs the true curve; the orange sliver is the unavoidable trapezoid error on a bend.

Step 6 — Fit a parabola through three points, integrate it exactly

Take one pair of strips: nodes $x_{0}, x_{1}, x_{2}$ , equally spaced by $h$ . Clever move: slide the origin so the middle node sits at $0$ . Then the three nodes are at $- h, 0, + h$ . This symmetry is what makes the algebra collapse.

Call the parabola $p (x) = α + β x + γ x^{2}$ :

$α$ = its height at the centre (value at $x = 0$ ),
$β$ = its tilt (linear part),
$γ$ = its bend (curviness).

Integrate it across the pair: $\int_{- h}^{h} (α + β x + γ x^{2}) d x = 2 α h + \frac{2}{3} γ h^{3} .$ Term by term: $α$ integrates to $α \cdot (length 2 h) = 2 α h$ . The tilt term $β x$ integrates to zero — because over the symmetric span $[- h, h]$ it adds as much on the right as it subtracts on the left. The bend $γ x^{2}$ integrates to $γ \cdot \frac{2 h ^{3}}{3}$ .

PICTURE. The parabola through the three dots on the shifted axis $- h, 0, h$ ; the $β x$ tilt shaded as equal-and-opposite red/blue lobes that cancel.

Step 7 — Turn $α, γ$ into the data → the 1-4-1 stencil appears

Plug the three node positions into $p$ : $f (- h) = α - β h + γ h^{2}, f (0) = α, f (h) = α + β h + γ h^{2} .$

Two facts drop out immediately:

The middle equation says $α = f (0)$ — the centre height is the middle data point.
Add the outer two: the $β h$ cancels, giving $f (- h) + f (h) = 2 α + 2 γ h^{2}$ , so $γ h^{2} = \frac{f ( - h ) + f ( h )}{2} - f (0) .$

Substitute both into the area $2 α h + \frac{2}{3} γ h^{3} = 2 α h + \frac{2}{3} h (γ h^{2})$ :

=\frac{h}{3}\big[f(-h)+4f(0)+f(h)\big].$$ **WHAT.** The exact area under the fitted parabola, written purely in the three heights. **WHY the numbers 1, 4, 1?** Collect coefficients over the common denominator $3$. The two **edge** heights each survive with a single $\frac{h}{3}$ → weight **1**. The **centre** height picks up the big $2$ from the $\alpha$ term *plus* the correction, netting $4$. That's the celebrated stencil — not memorised, but *manufactured*. > [!formula] Simpson's rule (one pair) > $$\int_{x_0}^{x_2}f\,dx\approx\frac{h}{3}\big[\,\underbrace{f(x_0)}_{\times 1}+\underbrace{4f(x_1)}_{\times 4}+\underbrace{f(x_2)}_{\times 1}\,\big]$$ **PICTURE.** The three nodes tagged with their falling weights $1,\,4,\,1$; the centre node blazes brightest because the parabola leans on it hardest. ![[deepdives/dd-coding-5.4.24-d2-s07.png]] --- ## Step 8 — Chain the pairs → composite Simpson's rule Now lay these parabolic pairs side by side across $[a,b]$ (this needs $n$ **even**, so the strips pair up with no leftover). Track how often each node is used: - **Ends** $x_0,x_n$: belong to one pair → weight **1**. - **Odd-index** nodes ($x_1,x_3,\dots$): each is the **centre** of its own pair → weight **4**. - **Even interior** nodes ($x_2,x_4,\dots$): each is the **shared boundary** where two pairs meet → weight $1+1=$ **2**. > [!formula] Composite Simpson's rule ($n$ even) > $$S_n=\frac{h}{3}\Big[f(x_0)+f(x_n)+4\!\!\sum_{i\ \text{odd}}\!f(x_i)+2\!\!\sum_{i\ \text{even, interior}}\!\!f(x_i)\Big]$$ > Weight pattern: $1,4,2,4,2,\dots,4,1$. Error $\sim O(h^4)$ — halve $h$, error drops ~16×. > [!mistake] Odd $n$ breaks Simpson > One dangling strip has no partner to form a parabola. The 1-4-1 stencil eats strips in pairs. **Fix:** require $n$ even, or treat the last lone strip with a trapezoid. **PICTURE.** Several parabolic arcs tiling the curve; nodes coloured by their weight $1/4/2$ — the alternating $4,2,4,2$ rhythm made visible. ![[deepdives/dd-coding-5.4.24-d2-s08.png]] --- ## Step 9 — Sanity check on the parent's example > [!example] $\int_0^1 x^2\,dx=\tfrac13$, $n=2$, $h=0.5$ > Nodes $0,0.5,1$ give heights $0,\,0.25,\,1$. > $$S_2=\frac{0.5}{3}\big[\underbrace{0}_{\times1}+\underbrace{4(0.25)}_{\times4}+\underbrace{1}_{\times1}\big]=\frac{0.5}{3}\cdot 2=0.3333\ldots$$ > **Exact.** Because $x^2$ is degree 2 and our lid *is* a parabola — it doesn't just approximate the curve, it **equals** it. (Bonus: Simpson is even exact for degree-3 cubics — the extra odd term cancels just like $\beta x$ did in Step 6.) > Compare $T_2=\frac{0.5}{2}[0+1+2(0.25)]=0.375$ — the straight lids overshoot the convex curve, exactly the Step-5 failure. --- ## The one-picture summary ![[deepdives/dd-coding-5.4.24-d2-s09.png]] One frame, whole derivation: the exact green area → straight trapezoid lids (weights $1,2,\dots,2,1$, error $O(h^2)$) → bendy parabola lids over pairs (weights $1,4,2,4,\dots,4,1$, error $O(h^4)$). Same nodes, smarter lids, smaller gaps. > [!recall]- Feynman retelling — the whole walk in plain words > You want the area of a wiggly hill but you can't measure a wiggle directly. So you cover it with shapes you *do* know. First you slice the base into equal-width strips. Over each thin strip the hill is nearly straight, so you cap it with a slanted-roof box — a trapezoid — and add them up. The edges of the whole hill touch only one box (count once), but every inside cut-line is shared by two boxes (count twice) — that's the $1,2,2,\dots,2,1$ pattern. Trapezoids are quick but their flat roofs can't bend, so over a hump they always miss a little sliver. Fix: use a roof that bends. The simplest bending shape is a parabola, and a parabola needs three points to pin down — so you work two strips at a time. If you cleverly put the middle point at zero, the tilt of the parabola cancels itself out when you find its area, leaving only the middle height and the bend. Turning those back into your three data heights, the numbers $1,4,1$ fall out on their own — the middle counts four times because the parabola leans on it hardest. Chain these parabola-pairs across the hill and the shared boundaries make the rhythm $1,4,2,4,2,\dots,4,1$. Since a parabola actually *is* the curve when the curve is a parabola (or even a cubic), Simpson nails those exactly — that's why it beats trapezoids for the very same amount of work. > [!mnemonic] The whole page in one breath > **Straight roofs = $1,2,\dots,2,1$. Bendy roofs, in pairs = $1,4,2,4,\dots,4,1$. Even $n$ or no partner.** ## Connections - [[Riemann sums]] — the limit-of-sums both rules are secretly refining. - [[Newton-Cotes formulas]] — trapezoid and Simpson are the first two members of this family. - [[Polynomial interpolation]] — Step 6–7 *is* fitting the interpolating parabola. - [[Taylor series]] — where the $O(h^2)$ and $O(h^4)$ error orders come from. - [[Richardson extrapolation]] — blend trapezoid results to *manufacture* Simpson, then Romberg. - [[scipy.integrate.quad]] — the adaptive, production version of this whole idea.