Simpson's rule

Simpson's rules are several approximations for definite integrals, which are used in numerical integration. They are named after Thomas Simpson (1710–1761).

The most basic of these rules is called Simpson's 1/3 rule, or just Simpson's rule. It estimates an integral using the function's values at the start, the middle, and the end of the integration range. The estimate becomes exact if the function is a polynomial up to and including 3rd degree.

In German and some other languages, the rule is named after Johannes Kepler, who derived it in 1615 after seeing it used for wine barrels. In German it is called the barrel rule.

Applying the 1/3 rule to several equal parts of the integration range gives the composite Simpson's 1/3 rule. A second rule, Simpson's 3/8 rule, also called Simpson's second rule, uses one more function value inside the range and gives lower error bounds, but it does not improve the order of the error. Its version for several equal parts is the composite Simpson's 3/8 rule. Both the 1/3 and 3/8 rules are special cases of closed Newton–Cotes formulas.

The name is also used in other fields. In naval architecture and ship stability, there is a Simpson's third rule, which is not especially important in general numerical analysis. Simpson's name is also used for a voting rule, described in Minimax Condorcet, and for rules in naval architecture, described in Simpson's rules (ship stability).

Simpson's 1/3 rule

Simpson's 1/3 rule, also simply called Simpson's rule, is a method for numerical integration proposed by Thomas Simpson. It is based on quadratic interpolation, which means fitting a curve shaped like a parabola. It is the composite Simpson's 1/3 rule evaluated with two subintervals. The rule gives exact results for any polynomial of degree three or less. It can be seen as the weighted average of the midpoint rule and the trapezoidal rule.

When a function is not smooth over the interval, the interval is split into smaller pieces, and Simpson's rule is applied to each piece. This is called the composite Simpson's rule. The examples in the source show it approximating the natural logarithm of 2 and the number π. For a comparison, the Composite Trapezoidal Rule needed far more calculations to reach the same accuracy. Other methods, such as Romberg's method and the adaptive Simpson's method, build on these ideas.

Simpson's 3/8 rule

Simpson's 3/8 rule, also called Simpson's second rule, is another method for numerical integration proposed by Thomas Simpson. It is based on a cubic curve instead of a quadratic one. It uses four equally spaced points, and compared with the standard method, it is about twice as accurate but uses one more function value. A composite version of the rule also exists, and a further generalization for polynomials of any degree is the Newton–Cotes formulas.

The rule can be used to estimate the arc length of a sine curve over half a period. Using six intervals, the estimate is about 3.823688376. This has a relative error of only 0.0913%. The exact value is a nonelementary integral that can be shown to be about 3.820197789, where the value is found using the lemniscate constant.

Alternative extended Simpson's rule

This is another way of using Simpson's rule. Instead of applying the rule to separate pieces of the area being measured, it is applied to pieces that overlap. The final result is the average of two formulas.

Simpson's rules are not very good at measuring the total area of narrow, peak-like shapes. For these, the trapezoidal rule works better, since the composite Simpson's 1/3 rule needs about 1.8 times more points to reach the same accuracy. Some of these rules are linked to the Euler–MacLaurin formula, and they involve the second derivative of the function.

Composite Simpson's rule for irregularly spaced data

Sometimes the interval needs to be split into parts of different sizes, perhaps because data was sampled unevenly, or because some data points are missing or corrupted. If the interval is divided into an even number of smaller pieces with different widths, a version of Simpson's rule called the composite Simpson's rule is used.

If the number of pieces is odd, the same method is used up to the second-to-last piece. The last piece is handled separately, with an extra adjustment added to the result.

Algorithms

The following pseudocode describes the various forms of Simpson's rule. The first form needs an even number of intervals, and the second needs a number of intervals that is a multiple of 3. The third form works with data points that are not evenly spaced. Each one gives an estimate of the integral of a function between two limits.

Numerical stability

Simpson's rule has an important property: it is stable when it comes to round-off error, which is the small error that builds up when numbers are rounded during calculation. This property is shared by all Newton–Cotes formulas.

If each round-off error is bounded by a small number ε, then the total accumulated error stays below (b − a)ε. This bound does not depend on the step size h, so the method stays stable as h approaches zero. This is different from numerical differentiation techniques, which are ill-conditioned.