Quadrature rules and an impossibility theorem

Many numerical integration formulas over a finite interval have the form

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

In this case the xs 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 = -3h^5/80.

We don't know a priori what the value of will be, only that there will be some value of between x₀ and x₃ 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.

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

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 xs are not evenly spaced but are the zeros of P_n, the Legendre polynomial of degree n. The weights are related to the xs and the derivative P'_n evaluated at the xs. 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

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

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

• Three surprises with the trapezoid rule
• Romberg integration
• Lobatto quadrature
• Orthogonal polynomials

[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.