![]() | ||
In numerical analysis, the Newton–Cotes formulae, also called the Newton–Cotes quadrature rules or simply Newton–Cotes rules, are a group of formulae for numerical integration (also called quadrature) based on evaluating the integrand at equally spaced points. They are named after Isaac Newton and Roger Cotes.
Contents
- Description
- Instability for high degree
- Closed NewtonCotes formulae
- Open NewtonCotes formulae
- Composite rules
- References
Newton–Cotes formulae 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.
Description
It is assumed that the value of a function ƒ defined on [a, b] is known at equally spaced points xi, for i = 0, …, n, where x0 = a and xn = b. There are two types of Newton–Cotes formulae, 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
where xi = h i + x0, with h (called the step size) equal to (xn − x0) / n = (b − a) / n. The wi are called weights.
As can be seen in the following derivation the weights are derived from the Lagrange basis polynomials. They depend only on the xi and not on the function ƒ. Let L(x) be the interpolation polynomial in the Lagrange form for the given data points (x0, ƒ(x0) ), …, (xn, ƒ(xn) ), then
The open Newton–Cotes formula of degree n is stated as
The weights are found in a manner similar to the closed formula.
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 cannot 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.
Alternatively, stable Newton–Cotes formulas can be constructed using least-squares approximation instead of interpolation. This allows building numerically stable formulas even for high degrees.
Closed Newton–Cotes formulae
This table lists some of the Newton–Cotes formulae of the closed type. The notation
Boole's rule is sometimes mistakenly called Bode's rule, as a result of the propagation of a typographical error in Abramowitz and Stegun, an early reference book.
The exponent of the segment size b − a in the error term shows the rate at which the approximation error decreases. The derivative of ƒ in the error term shows which polynomials can be integrated exactly (i.e., with error equal to zero). Note that the derivative of ƒ in the error term increases by 2 for every other rule. The number
Open Newton–Cotes formulae
This table lists some of the Newton–Cotes formulae of the open type. Again, ƒi is a shorthand for ƒ(xi), with xi = a + i (b − a) / n, and n the degree.
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