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.

Left endpoint rule
Left endpoint rule

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:

Simpson's rule
Simpson’s rule

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

Gaussian quadrature
Gaussian quadrature

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:

Nice smooth function
Nice smooth 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:

Another nice function
Another nice function

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

Maple output, "simplified"
Maple output, “simplified”
  • 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.

Gaussian nodes on a circle
Gaussian nodes on a circle

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

Equally spaced points
Equally spaced points

1 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,
    http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.131.1310&rep=rep1&type=pdf

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s