Newton–Cotes formulas

From Wikipedia, the free encyclopedia

In numerical analysis, the Newton–Cotes formulas, also called the Newton–Cotes rules, are a group of formulas for numerical integration (also called quadrature) based on evaluating the integrand at n+1 equally-spaced points. They are named after Isaac Newton and Roger Cotes.

Newton–Cotes formulas can be useful if the value of the integrand at equally-spaced points is given. If it is possible to change the points at which the integrand is evaluated, then other methods such as Gaussian quadrature and Clenshaw–Curtis quadrature are probably more suitable.

1 Description
2 Instability for high degree
3 Closed Newton–Cotes formulas
4 Open Newton–Cotes formulas
5 Composite rules
6 References
7 External links

[edit] Description

It is assumed that the value of a function f is known at equally spaced points x_i, for i = 0, …, n. There are two types of Newton–Cotes formulas, the "closed" type which uses the function value at all points, and the "open" type which does not use the function values at the endpoints. The closed Newton-Cotes formula of degree n is stated as

$\int_a^b f(x) \,dx \approx \sum_{i=0}^n w_i\, f(x_i)$

where x_i = h i + x₀, with h (called the step size) equal to (x_n − x₀)/n. The w_i are called weights.

As can be seen in the following derivation the weights are derived from the Lagrange basis polynomials. This means they depend only on the x_i and not on the function f. Let L(x) be the interpolation polynomial in the Lagrange form for the given data points (x₀, f(x₀) ), …, (x_n, f(x_n) ), then

$\int_a^b f(x) \,dx \approx \int_a^b L(x)\,dx = \int_a^b \sum_{i=0}^n f(x_i)\, l_i(x)\, dx = \sum_{i=0}^n f(x_i) \underbrace{\int_a^b l_i(x)\, dx}_{w_i}.$

The open Newton–Cotes formula of degree n is stated as

$\int_a^b f(x)\, dx \approx \sum_{i=1}^{n-1} w_i\, f(x_i)$

The weights are found in a manner similar to the closed formula.

[edit] Instability for high degree

A Newton–Cotes formula of any degree n can be constructed. However, for large n a Newton–Cotes rule can sometimes suffer from catastrophic Runge's phenomenon where the error grows exponentially for large n. Methods such as Gaussian quadrature and Clenshaw–Curtis quadrature with unequally spaced points (clustered at the endpoints of the integration interval) are stable and much more accurate, and are normally preferred to Newton–Cotes. If these methods can not be used, because the integrand is only given at the fixed equidistributed grid, then Runge's phenomenon can be avoided by using a composite rule, as explained below.

[edit] Closed Newton–Cotes formulas

This table lists some of the Newton–Cotes formulas of the closed type. The notation $f i$ is a shorthand for $f (x i)$ .

**Closed Newton–Cotes Formulas**
Degree	Common name	Formula	Error term
1	Trapezoid rule	$\frac{h}{2} (f_0 + f_1)$	$-\frac{h^3}{12}\,f^{(2)}(\xi)$
2	Simpson's rule	$\frac{h}{3} (f_0 + 4 f_1 + f_2)$	$-\frac{h^5}{90}\,f^{(4)}(\xi)$
3	Simpson's 3/8 rule	$\frac{3h}{8} (f_0 + 3 f_1 + 3 f_2 + f_3)$	$-\frac{3h^5}{80}\,f^{(4)}(\xi)$
4	Boole's rule, or Bode's Rule [sic]	$\frac{2h}{45} (7 f_0 + 32 f_1 + 12 f_2 + 32 f_3 + 7 f_4)$	$-\frac{8h^7}{945}\,f^{(6)}(\xi)$

Boole's rule is sometimes mistakenly called Bode's rule due to propagation of an early typo in Abramowitz and Stegun, an early reference book.[1].

The exponent of the step size h in the error term shows the rate at which the approximation error decreases. The derivative of f in the error term shows which polynomials can be integrated exactly (i.e., with error equal to zero). Note that the derivative of f in the error term increases by 2 for every other rule. The number $ξ$ is between a and b.

[edit] Open Newton–Cotes formulas

This table lists some of the Newton–Cotes formulas of the open type.

**Open Newton–Cotes Formulas**
Degree	Common name	Formula	Error term
0	Rectangle rule	$2 h f_1\,$	$\frac{h^3}{24}\,f^{(2)}(\xi)$
1	No name	$\frac{3h}{2} (f_1 + f_2)$	$\frac{h^3}{4}\,f^{(2)}(\xi)$
2	No name	$\frac{4h}{3} (2 f_1 - f_2 + 2 f_3)$	$\frac{28h^5}{90}f^{(4)}(\xi)$
3	No name	$\frac{5h}{24} (11 f_1 + f_2 + f_3 + 11 f_4)$	$\frac{95h^5}{144}f^{(4)}(\xi)$

[edit] Composite rules

For the Newton–Cotes rules to be accurate, the step size h needs to be small, which means that the interval of integration $[a, b]$ must be small itself, which is not true most of the time. For this reason, one usually performs numerical integration by splitting $[a, b]$ into smaller subintervals, applying a Newton–Cotes rule on each subinterval, and adding up the results. This is called a composite rule, see Numerical integration.

[edit] References

M. Abramowitz and I. A. Stegun, eds. Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. New York: Dover, 1972. (See Section 25.4.)
George E. Forsythe, Michael A. Malcolm, and Cleve B. Moler. Computer Methods for Mathematical Computations. Englewood Cliffs, NJ: Prentice-Hall, 1977. (See Section 5.1.)
William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling. Numerical Recipes in C. Cambridge, UK: Cambridge University Press, 1988. (See Section 4.1.)
Josef Stoer and Roland Bulirsch. Introduction to Numerical Analysis. New York: Springer-Verlag, 1980. (See Section 3.1.)