Newton–Cotes formulas

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 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.

Description

It is assumed that the value of a function $f$ defined on $[a,b]$ is known at $n+1$ equally spaced points: $a\leq x_{0}<x_{1}<\dots <x_{n}\leq b$ . There are two classes of Newton–Cotes quadrature: they are called "closed" when $x_{0}=a$ and $x_{n}=b$ , i.e. they use the function values at the interval endpoints, and "open" when $x_{0}>a$ and $x_{n}<b$ , i.e. they do not use the function values at the endpoints. Newton–Cotes formulas using $n+1$ points can be defined (for both classes) as^[1] $\int _{a}^{b}f(x)\,dx\approx \sum _{i=0}^{n}w_{i}\,f(x_{i}),$ where

for a closed formula, $x_{i}=a+ih$ , with $h={\frac {b-a}{n}}$ ,
for an open formula, $x_{i}=a+(i+1)h$ , with $h={\frac {b-a}{n+2}}$ .

The number $h$ is called step size, $w_{i}$ are called weights. The weights can be computed as the integral of Lagrange basis polynomials. They depend only on $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_{0},f(x_{0})),(x_{1},f(x_{1})),\ldots ,(x_{n},f(x_{n}))$ , then $\int _{a}^{b}f(x)\,dx\approx \int _{a}^{b}L(x)\,dx=\int _{a}^{b}\left(\sum _{i=0}^{n}f(x_{i})l_{i}(x)\right)\,dx=\sum _{i=0}^{n}f(x_{i})\underbrace {\int _{a}^{b}l_{i}(x)\,dx} _{w_{i}}.$

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^[2] 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.^[3]^[4]

Closed Newton–Cotes formulas

This table lists some of the Newton–Cotes formulas of the closed type. For $0\leq i\leq n$ , let $x_{i}=a+ih$ where $h={\frac {b-a}{n}}$ , and $f_{i}=f(x_{i})$ .

**Closed Newton–Cotes Formulas**
$n$	Step size $h$	Common name	Formula	Error term
1	$b-a$	Trapezoidal rule	${\frac {1}{2}}h(f_{0}+f_{1})$	$-{\frac {1}{12}}h^{3}f^{(2)}(\xi )$
2	${\frac {b-a}{2}}$	Simpson's rule	${\frac {1}{3}}h(f_{0}+4f_{1}+f_{2})$	$-{\frac {1}{90}}h^{5}f^{(4)}(\xi )$
3	${\frac {b-a}{3}}$	Simpson's 3/8 rule	${\frac {3}{8}}h(f_{0}+3f_{1}+3f_{2}+f_{3})$	$-{\frac {3}{80}}h^{5}f^{(4)}(\xi )$
4	${\frac {b-a}{4}}$	Boole's rule	${\frac {2}{45}}h(7f_{0}+32f_{1}+12f_{2}+32f_{3}+7f_{4})$	$-{\frac {8}{945}}h^{7}f^{(6)}(\xi )$

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.^[5]

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 $\xi$ must be taken from the interval $(a, b)$ , therefore, the error bound is equal to the error term when $f(\xi )=\max(f(x)),a<x<b$ .

Open Newton–Cotes formulas

This table lists some of the Newton–Cotes formulas of the open type. For $0\leq i\leq n$ , let $x_{i}=a+(i+1)h$ where $h={\frac {b-a}{n+2}}$ , and $f_{i}=f(x_{i})$ .

**Open Newton–Cotes Formulas**
$n$	Step size $h$	Common name	Formula	Error term
0	${\frac {b-a}{2}}$	Rectangle rule, or midpoint rule	$2hf_{0}$	${\frac {1}{3}}h^{3}f^{(2)}(\xi )$
1	${\frac {b-a}{3}}$		${\frac {3}{2}}h(f_{0}+f_{1})$	${\frac {3}{4}}h^{3}f^{(2)}(\xi )$
2	${\frac {b-a}{4}}$	Milne's rule	${\frac {4}{3}}h(2f_{0}-f_{1}+2f_{2})$	${\frac {14}{45}}h^{5}f^{(4)}(\xi )$
3	${\frac {b-a}{5}}$		${\frac {5}{24}}h(11f_{0}+f_{1}+f_{2}+11f_{3})$	${\frac {95}{144}}h^{5}f^{(4)}(\xi )$

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.

References

^ Quarteroni, Alfio; Sacco, Riccardo; Saleri, Fausto (2006). Numerical Mathematics (Second ed.). Springer. pp. 386–387. ISBN 978-3-540-34658-6.
^ Quarteroni, Alfio; Sacco, Riccardo; Saleri, Fausto (2006). Numerical Mathematics (Second ed.). Springer. pp. 390–391. ISBN 978-3-540-34658-6.
^ Pavel Holoborodko (2011-03-24). "Stable Newton-Cotes Formulas". Retrieved 2015-08-17.
^ Pavel Holoborodko (2012-05-20). "Stable Newton-Cotes Formulas (Open Type)". Retrieved 2015-08-18.
^ Booles Rule at Wolfram Mathworld, with typo in year "1960" (instead of "1860")

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.)
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 4.1. Classical Formulas for Equally Spaced Abscissas", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
Josef Stoer and Roland Bulirsch. Introduction to Numerical Analysis. New York: Springer-Verlag, 1980. (See Section 3.1.)

External links

"Newton–Cotes quadrature formula", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
Newton–Cotes formulas on www.math-linux.com
Weisstein, Eric W. "Newton–Cotes Formulas". MathWorld.
Newton–Cotes Integration, numericalmathematics.com

[1] Quarteroni, Alfio; Sacco, Riccardo; Saleri, Fausto (2006). Numerical Mathematics (Second ed.). Springer. pp. 386–387. ISBN 978-3-540-34658-6.

[2] Quarteroni, Alfio; Sacco, Riccardo; Saleri, Fausto (2006). Numerical Mathematics (Second ed.). Springer. pp. 390–391. ISBN 978-3-540-34658-6.

[3] Pavel Holoborodko (2011-03-24). "Stable Newton-Cotes Formulas". Retrieved 2015-08-17.

[4] Pavel Holoborodko (2012-05-20). "Stable Newton-Cotes Formulas (Open Type)". Retrieved 2015-08-18.

[5] Booles Rule at Wolfram Mathworld, with typo in year "1960" (instead of "1860")

[1]

[2]

[3]

[4]

[5]

v t e Sir Isaac Newton
Publications	Fluxions (1671) De Motu (1684) Principia (1687) Opticks (1704) Queries (1704) Arithmetica (1707) De Analysi (1711)
Other writings	Quaestiones (1661–1665) "standing on the shoulders of giants" (1675) Notes on the Jewish Temple (c. 1680) "General Scholium" (1713; "hypotheses non fingo" ) Ancient Kingdoms Amended (1728) Corruptions of Scripture (1754)
Contributions	Calculus fluxion Impact depth Inertia Newton disc Newton polygon Newton–Okounkov body Newton's reflector Newtonian telescope Newton scale Newton's metal Spectrum Structural coloration
Newtonianism	Bucket argument Newton's inequalities Newton's law of cooling Newton's law of universal gravitation post-Newtonian expansion parameterized gravitational constant Newton–Cartan theory Schrödinger–Newton equation Newton's laws of motion Kepler's laws Newtonian dynamics Newton's method in optimization Apollonius's problem truncated Newton method Gauss–Newton algorithm Newton's rings Newton's theorem about ovals Newton–Pepys problem Newtonian potential Newtonian fluid Classical mechanics Corpuscular theory of light Leibniz–Newton calculus controversy Newton's notation Rotating spheres Newton's cannonball Newton–Cotes formulas Newton's method generalized Gauss–Newton method Newton fractal Newton's identities Newton polynomial Newton's theorem of revolving orbits Newton–Euler equations Newton number kissing number problem Newton's quotient Parallelogram of force Newton–Puiseux theorem Absolute space and time Luminiferous aether Newtonian series table
Personal life	Woolsthorpe Manor (birthplace) Cranbury Park (home) Early life Later life Apple tree Religious views Occult studies Scientific Revolution Copernican Revolution
Relations	Catherine Barton (niece) John Conduitt (nephew-in-law) Isaac Barrow (professor) William Clarke (mentor) Benjamin Pulleyn (tutor) Roger Cotes (student) William Whiston (student) John Keill (disciple) William Stukeley (friend) William Jones (friend) Abraham de Moivre (friend)
Depictions	Newton by Blake (monotype) Newton by Paolozzi (sculpture) Isaac Newton Gargoyle Astronomers Monument
Namesake	Newton (unit) Newton's cradle Isaac Newton Institute Isaac Newton Medal Isaac Newton Telescope Isaac Newton Group of Telescopes XMM-Newton Sir Isaac Newton Sixth Form Statal Institute of Higher Education Isaac Newton Newton International Fellowship
Categories	Isaac Newton

v t e Numerical integration
Newton–Cotes formulas	Trapezoidal rule Simpson's rule Simpson's 3/8 rule Adaptive Simpson's method Boole's rule Romberg's method
Gaussian quadrature	Gauss–Hermite quadrature Gauss–Jacobi quadrature Gauss–Kronrod quadrature formula Gauss–Laguerre quadrature Gauss–Legendre quadrature Chebyshev–Gauss quadrature
Other	Barnes–Hut simulation Bayesian quadrature Clenshaw–Curtis quadrature Filon quadrature Lebedev quadrature Tanh-sinh quadrature