# Unreasonable effectiveness of the left endpoint rule

The left endpoint rule, and its twin right endpoint rule, are ugly ducklings of integration methods. The left endpoint rule is just the average of the values of the integrand over left endpoints of equal subintervals:

$\displaystyle \int_a^b f(x)\,dx \approx \frac{b-a}{n} \sum_{i=0}^{n-1} f(a+i/n)$

Here is its graphical representation with ${n=10}$ on the interval ${[-1,1]}$: the sample points are marked with vertical lines, the length of each line representing the weight given to that point. Every point has the same weight, actually.

Primitive, ineffective, with error ${O(1/n)}$ for ${n}$ points used.

Simpson’s rule is more sophisticated, with error ${O(1/n^4)}$. It uses weights of three sizes:

Gaussian quadrature uses specially designed (and difficult to compute) sample points and weights: more points toward the edges, larger weights in the middle.

Let’s compare these quadrature rules on the integral ${\int_{-1}^1 e^x \cos \pi x\,dx}$, using ${10}$ points as above. Here is the function:

• The exact value of the integral is ${\dfrac{e^{-1}-e}{1+\pi^2}}$, about -0.216.
• Simpson’s rule gets within 0.0007 of the exact value. Well done!
• Gaussian quadrature gets within 0.000000000000003 of the exact value. Amazing!
• And the lame left endpoint rule outputs… a positive number, getting even the sign wrong! This is ridiculous. The error is more than 0.22.

Let’s try another integral: ${\int_{-1}^1 \sqrt{4+\cos \pi x +\sin \pi x} \,dx}$, again using ${10}$ points. The function looks like this:

The integral can be evaluated exactly… sort of. In terms of elliptic integrals. And preferably not by hand:

• Simpson’s rule is within 0.00001 of the exact value, even better than the first time.
• Gaussian quadrature is within 0.00000003, not as spectacular as in the first example.
• And the stupid left endpoint rule is … accurate within 0.00000000000000005. What?

The integral of a smooth periodic function over its period amounts to integration over a circle. When translated to the circle, the elaborate placement of Gaussian sample points is… simply illogical. There is no reason to bunch them up at any particular point: there is nothing special about (-1,0) or any other point of the circle.

The only natural approach here is the simplest one: equally spaced points, equal weights. Left endpoint rule uses it and wins.

## One thought on “Unreasonable effectiveness of the left endpoint rule”

1. This phenomenon is reviewed in the following very readable paper by Trefethen and Weideman, “The exponentially convergent trapezoid rule”, http://eprints.maths.ox.ac.uk/1734/1/NA-13-15.pdf

Also perhaps of interest – applying a function of a matrix can be converted into a problem of integrating along a complex contour surrounding the spectrum of the matrix. One can construct a conformal map to map the contour to a circle on the complex plane, and then use this rule to integrate it numerically, yielding very efficient algorithms. See for example the paper by Hale, Higham, and Trefethen,