Interactive Educational Modules in
Scientific Computing

Romberg Integration

This module illustrates Romberg integration, which is a numerical quadrature technique based on repeated Richardson extrapolation of values obtained using the composite trapezoid rule with successively halved mesh spacing. For k ≥ 0, define Tk, 0 to be the composite trapezoid approximation to the integral of a function f(x) over an interval [a, b] using mesh spacing h = (ba) ⁄ 2k. For j = 1,…,k, let Tk, j be the value obtained by Richardson extrapolation based on the values Tk−1, j−1 and Tk, j−1. The values Tk, j form a triangular array. As k increases, the approximations to the integral become more accurate because the composite trapezoid rule is applied with decreasing mesh spacing. Accuracy also increases with j, because the order of accuracy of Tk, j is 2 ( j +1).

The user begins by selecting an integrand function from the menu provided. The integrand function is displayed in the left panel and the triangular array of values Tk, j in a scrollable window below. Each value in the triangular array that currently may be calculated (initially only T0, 0) is displayed in green. When the user clicks on any green entry Tk, j in the array, the corresponding value is computed and replaces Tk, j. If j = 0 (i.e., for the leftmost column of the triangular array), the upper panel on the left displays the composite trapezoid approximation to the integral. For j > 0, the upper panel on the right plots the function used to obtain Tk, j by extrapolation. The previously computed values used in the extrapolation are indicated in blue and magenta, and the resulting extrapolated value in red, both in the graph and the triangular array. The correct numerical value I of the integral is shown below the selected function for comparison with the values in the triangular array, and is also plotted as a black point (which may be obscured by the red point) in the right panel.

Reference: Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 8.7, especially Example 8.9 and Figure 8.6.

Developers: Evan VanderZee and Michael Heath