The trapezoid rule's error is not just $O(h^{2})$: for a smooth integrand it is a whole series in even powers, $$T(h) = I + c_1h^{2} + c_2h^{4} + c_3h^{6} + \cdots$$ (the Euler–Maclaurin formula). Richardson extrapolation can cancel these terms one after another, using trapezoid values with $h$ halved each time.
🔑 Key idea
Fill a triangle: $R(k, 0) = T(h/2^{k})$, and $$R(k, m) = \frac{4^{m}R(k, m - 1) - R(k - 1, m - 1)}{4^{m} - 1}.$$ Column $m$ has error $O(h^{2m + 2})$. Column 1 is Simpson's rule; column 2 is Boole's rule.
💡 Why it works
Each column removes the next even power. Column 0 has error $c_1h^{2} + \cdots$; halving $h$ divides the $h^{2}$ term by 4, so $\frac{4R(k, 0) - R(k - 1, 0)}{3}$ removes it and leaves $O(h^{4})$. In column 1 the leading term is $h^{4}$, which halving divides by $16 = 4^{2}$, so the factor becomes 16. In column $m$ it is $4^{m}$. And halving $h$ in the trapezoid rule reuses all the old points: only the new midpoints need new function values.
✏️ Worked example: A Romberg triangle
Compute $R(2, 2)$ for $\int_0^1 e^{x}\,dx$ from $T(1)$, $T(\frac{1}{2})$, $T(\frac{1}{4})$.
The exact value $e - 1 = 1.7182818$: error $9 \times 10^{-7}$ from only 5 function values, while $T(\frac{1}{4})$ alone was off by $9 \times 10^{-3}$.
Answer: $R(2, 2) \approx 1.7182827$
The Romberg triangle for the integral of eˣ from 0 to 1. Each column is far more accurate than the one before.
$k$
$R(k, 0)$
$R(k, 1)$
$R(k, 2)$
0
$1.8591409$
1
$1.7539311$
$1.7188612$
2
$1.7272219$
$1.7183188$
$1.7182827$
Trapezoid errors (blue) for the integral of eˣ from 0 to 1, with the first two Romberg columns: slopes 2, 4 and 6, until round-off stops them.
✏️ Worked example: Which factor?
In which column does the factor $64$ appear, and why?
$64 = 4^{3}$: column 3.
Its inputs (column 2) have leading error $h^{6}$, and halving $h$ divides that by $2^{6} = 64$.
Answer: column 3
In practice the triangle grows one row at a time, and the computation stops when two neighboring diagonal entries agree to the required tolerance. For smooth integrands this converges very fast. It relies on the even-power error series, so it works poorly for integrands with a singularity or a kink; adaptive integration handles those better.
Cost: row $k$ needs the trapezoid rule with $2^{k}$ panels, but only its $2^{k-1}$ new midpoints are new function values. The whole triangle up to row $k$ therefore costs $2^{k} + 1$ evaluations of $f$, the same as the single finest trapezoid rule; the extrapolation itself is nearly free.
⚠️ Common mistake
Using the factor 4 in every column. Only column 1 uses 4; column 2 needs 16 and column $m$ needs $4^{m}$. Using 4 again cancels the $h^{2}$ term that is already gone and leaves the $h^{4}$ term in place, so the column gives no improvement. Check: each column should agree with the true value to clearly more digits than the column before.
Practice
Pass with 3 right answers, the last 2 in a row. Each right answer earns 3 XP.