Interactive Educational Modules in
Scientific Computing

Cancellation of Errors

This module illustrates the cancellation of errors in odd-order Newton-Cotes quadrature rules for approximating the integral of a function of one variable over a given interval. An n-point Newton-Cotes quadrature rule approximates the integral of a function f(x) on an interval [a, b] by interpolating f(x) at n equally-spaced points with a polynomial of degree n − 1. Thus, if f(x) itself is a polynomial of degree n − 1 or less, then the interpolant is identical to the integrand, and hence the value given by the quadrature rule must be the exact integral. One would not expect this to be true for polynomials of degree n or higher, in general, because the polynomial interpolant is then no longer identical to the integrand f(x). When n is odd, however, it turns out that an n-point Newton-Cotes quadrature rule is exact when f(x) is a polynomial of degree n. This module graphically illustrates why we obtain the exact integral in this case despite the inexactness of the interpolant.

The user selects the (odd) degree n for a polynomial f(x), then selects Random Polynomial or Symmetric Polynomial to generate f(x) randomly, or Edit Polynomial to enter or edit the coefficients for f(x). The graph plots f(x) and the polynomial interpolant to f(x) that the n-point Newton-Cotes quadrature rule is based on. Areas that are included in the integral of the interpolant but not in the integral of f(x) (positive error) are shaded light blue, and areas that are not included in the integral of the interpolant but are included in the integral of f(x) (negative error) are shaded pink. When n is odd, the blue and pink regions are equal in area and opposite in sign and hence cancel, giving the exact integral. When the polynomial is symmetric about the midpoint of the interval, the blue and pink regions not only have equal areas, they are geometrically congruent.

Reference: Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 8.3.1, especially Figure 8.3.

Developers: Evan VanderZee and Michael Heath