Digit-shift test

To illustrate the ideas of Section 2.3, the second column of Table 1 displays the result of the trapezoid rule (13) for the integral

$$\int_0^1 \frac{1/\ln 2}{1+x}\,dx = 1,$$

as a function of the number of intervals $N$.

Table: Results of trapezoid and Simpson's integration of $\int_0^1 (1/\ln 2)/(1+x)\,dx$ for $N$ intervals

		Trapezoid	Trapezoid	Richardson Extrap	Simpson
N	h	($T(h)$)	(w/ bug)	( $\frac{4}{3} T(h/2) -\frac{1}{3} T(h)$)	($S(h/2)$)
10	0.1000	1.000900562871	1.036067656056	1.000000280034	1.000000280034
100	0.0100	1.000009016731	1.003606737630	1.000000000028	1.000000000028
1000	0.0010	1.000000090168	1.000360673760	1.000000000000	1.000000000000
10000	0.0001	1.000000000901	1.000036067376	1.000000000000	1.000000000000

Displayed in this way the data for the trapezoid rule exhibit an interesting pattern: each increase in the number of intervals $N$ by a factor of ten shifts the pattern of digits (``901'') representing the error two places to the right. This is the visual representation of our mathematical analysis: the shifting to the right by two places corresponds precisely to quadratic scaling of the error with $h$ and the pattern of shifting digits represents precisely the prefactor on $h^2$ in (16),

$$\begin{eqnarray*} \frac{1}{12} \left(f'(b)-f'(a)\right) & = & \frac{1}{12} \left... ...{4}\right) \\ & = & \frac{3}{48 \ln 2}\\ & \approx & 0.090168. \end{eqnarray*}$$

Displaying the results of a numerical calculation in this way is a very powerful tool for detecting bugs and correcting errors. The $h^2$ convergence of the trapezoid rule is quite delicate and even small programming errors will destroy it. The third column of the table, for instance, shows the typical behavior when the factor of 1/2 is forgotten at the end points and/or when dividing by $N-1$ instead of $N$. A routine with either bug indeed converges to the correct result, but the convergence is only linear in $h$ and such subtle bugs are easily detected.