Many numerical integration formulas over a finite interval have the form

int_a^b f(x), dx = sum_{i=1}^n w_i, f(x_i) + C f^{(k)}(xi)

That is, the integral on the left can be approximated by evaluating the integrand f at particular nodes and taking the weighted sum, and the error is some multiple of a derivative of f evaluated at a point in the interval [a, b].

This post will give several examples, showing how they all fit into to framework above, then discuss the impossibility of extending this framework to infinite integrals.

Simpson’s 3/8 rule

Simpson’s rule says

int_{x_0}^{x_3} f(x) , dx = frac{3h}{8} Big(f(x_0) + 3f(x_1) + 3f(x_2) + f(x_3) Big)- frac{3f^{(4)}(xi) h^5}{80}

In this case the x‘s are evenly spaced a distance of h apart. The weights are 3h/8, 9h/8, 9h/8, and 3h/8.

We have n = 4, k = 4, and C = −3h5/80.

We don’t know a priori what the value of ξ will be, only that there will be some value of ξ between x0 and x3 that makes the equation hold. If we have an explicit bound on the 4th derivative of f then we have an explicit bound on the error in approximating the integral by the weighted sum.

Bode’s rules

A sequence of quadrature rules go by the name “Bode’s rule.” Here is one example, also known as Weddle’s rule.

begin{align*} int_{x_0}^{x_6} f(x), dx = frac{h}{140}&Big(41 f(x_0) + 216f(x_1) + 27 f(x_2) +272 f(x_3) \ &+ 27 f(x_4) + 216 f(x_5) + 41 f(x_6) Big) \ &-frac{9 f^{(8)}(xi) h^9}{1400} end{align}

As with Simpson’s 3/8 rule, you could map the formula for Bode’s rule(s) to the template at the top of the post.

Gauss quadrature

Gauss’ formula says

int_{-1}^1 f(x), dx = sum_{i=1}^n w_i, f(x_i) + C f^{(2n)}(xi)

for some ξ in [−1, 1]. Here the limits of integration are fixed, though you could use a change of variables to integrals over other finite integrals into this form.

Unlike Bode’s rule and Simpson’s rule, the x‘s are not evenly spaced but are the zeros of Pn, the Legengre polynomial of degree n. The weights are related to the x‘s and the derivative P′n evaluated at the x‘s. The constant C is a complicated function of n but is independent of f.

Note that the error term involves the (2n)th derivative of f. This explains why Gaussian integration can be more accurate than other methods using the same number of function evaluations. The non-uniform spacing of the integration nodes enables higher-order error terms.

Non-existence theorem

Although many integration rules over a finite interval have the form

int_a^b f(x), dx = sum_{i=1}^n w_i, f(x_i) + C f^{(k)}(xi)

Davis and Rabinowitz [1] proved that there cannot be an integration rule of the form

int_0^infty f(x), dx = sum_{i=1}^n w_i, f(x_i) + C f^{(k)}(xi)

The proof, given in [1], takes only about one page. The entire article is a little more than a page, and about half the article is preamble to the proof.

Related posts

[1] P. J. Davis and P. Rabinowitz. On the Nonexistence of Simplex Integration Rules for Infinite Integrals. Mathematics of Computation, Vol. 26, No. 119 (July, 1972), pp. 687–688

The post Quadrature rules and an impossibility theorem first appeared on John D. Cook.

Previous Post
Next Post