In numerical analysis, the NewtonâÂÂCotes formulas, also called the NewtonâÂÂCotes quadrature rules or simply NewtonâÂÂCotes rules, are a group of formulas for numerical integration (also called quadrature) based on evaluating the integrand at equally spaced points. They are named after Isaac Newton, who originated the formulas, and Roger Cotes, who expanded upon Newton's work.
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.
It is assumed that the value of a function defined on is known at equally spaced points: . There are two classes of NewtonâÂÂCotes quadrature: they are called "closed" when and , i.e. they use the function values at the interval endpoints, and "open" when and , i.e. they do not use the function values at the endpoints. NewtonâÂÂCotes formulas using points can be defined (for both classes) as
where
The number is called step size, are called weights. The weights can be computed as the integral of Lagrange basis polynomials. They depend only on and not on the function . Let be the interpolation polynomial in the Lagrange form for the given data points , then
A NewtonâÂÂCotes formula of any degree can be constructed. However, for large a NewtonâÂÂCotes rule can sometimes suffer from catastrophic Runge's phenomenon where the error grows exponentially for large . 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.
This table lists some of the NewtonâÂÂCotes formulas of the closed type. For , let where , and .
Newton-Cotes rules using 7 or more points exist but are not used because they involve negatively weighted nodes which is generally viewed as contributing to Runge's phenomena (see above). 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 step size h in the error term gives the rate at which the approximation error decreases. The order of the derivative of f in the error term gives the lowest degree of a polynomial which can no longer be integrated exactly (i.e. with error equal to zero) with this rule. The number must be taken from the interval , therefore, the error bound is equal to the error term when .
This table lists some of the NewtonâÂÂCotes formulas of the open type. For , let where , and .
For the NewtonâÂÂCotes rules to be accurate, the step size needs to be small, which means that the interval of integration must be small itself, which is not true most of the time. For this reason, one usually performs numerical integration by splitting 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.