Newton–Cotes formulas

Newton–Cotes formula for n = 2

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.

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 x_i, for i = 0, …, n, where x₀ = a and x_n = 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

\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 = (b − a) / n. The w_i 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 x_i and not on the function ƒ. Let L(x) be the interpolation polynomial in the Lagrange form for the given data points (x₀, ƒ(x₀) ), …, (x_n, ƒ(x_n) ), then

\int _{a}^{b}f(x)\,dx\approx \int _{a}^{b}L(x)\,dx=\int _{a}^{b}{\bigl (}\sum _{i=0}^{n}f(x_{i})\,l_{i}(x){\bigr )}\,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.

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

Closed Newton–Cotes formulae

This table lists some of the Newton–Cotes formulae of the closed type. The notation $f_{i}$ is a shorthand for $f(x_{i})$ , with x_i = a + i (b − a) / n, and n the degree.

**Closed Newton–Cotes Formulae**
Degree	Common name	Formula	Error term
1	Trapezoid rule	${\frac {b-a}{2}}(f_{0}+f_{1})$	$-{\frac {(b-a)^{3}}{12}}\,f^{{(2)}}(\xi )$
2	Simpson's rule	${\frac {b-a}{6}}(f_{0}+4f_{1}+f_{2})$	$-{\frac {(b-a)^{5}}{2880}}\,f^{{(4)}}(\xi )$
3	Simpson's 3/8 rule	${\frac {b-a}{8}}(f_{0}+3f_{1}+3f_{2}+f_{3})$	$-{\frac {(b-a)^{5}}{6480}}\,f^{{(4)}}(\xi )$
4	Boole's rule	${\frac {b-a}{90}}(7f_{0}+32f_{1}+12f_{2}+32f_{3}+7f_{4})$	$-{\frac {(b-a)^{7}}{1935360}}\,f^{{(6)}}(\xi )$

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

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 $\xi$ is between a and b.

Open Newton–Cotes formulae

This table lists some of the Newton–Cotes formulae of the open type. Again, ƒ_i is a shorthand for ƒ(x_i), with x_i = a + i (b − a) / n, and n the degree.

**Open Newton–Cotes Formulae**
Common name	step size	Formula	Error term	Degree
Rectangle rule, or midpoint rule	${\frac {b-a}{2}}$	$(b-a)f_{1}\,$	${\frac {(b-a)^{3}}{24}}\,f^{{(2)}}(\xi )$	2
Trapezoid method	${\frac {b-a}{3}}$	${\frac {b-a}{2}}(f_{1}+f_{2})$	${\frac {(b-a)^{3}}{36}}\,f^{{(2)}}(\xi )$	3
Milne's rule	${\frac {b-a}{4}}$	${\frac {b-a}{3}}(2f_{1}-f_{2}+2f_{3})$	${\frac {7(b-a)^{5}}{23040}}f^{{(4)}}(\xi )$	4
No Name	${\frac {b-a}{5}}$	${\frac {b-a}{24}}(11f_{1}+f_{2}+f_{3}+11f_{4})$	${\frac {19(b-a)^{5}}{90000}}f^{{(4)}}(\xi )$	5

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

↑ 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

M. Abramowitz and I. A. Stegun, eds. Handbook of Mathematical Functions with Formulae, 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

Hazewinkel, Michiel, ed. (2001), "Newton–Cotes quadrature formula", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
Newton–Cotes formulae on www.math-linux.com
Weisstein, Eric W. "Newton–Cotes Formulae". MathWorld.

Module for Newton–Cotes Integration, fullerton.edu
Newton–Cotes Integration, numericalmathematics.com

Isaac Newton

Publications	De analysi per aequationes numero terminorum infinitas (1669, published 1711) Method of Fluxions (1671) De motu corporum in gyrum (1684) Philosophiæ Naturalis Principia Mathematica (1687) General Scholium (1713) Opticks (1704) The Queries (1704) Arithmetica Universalis (1707)

Other writings	Notes on the Jewish Temple Quaestiones quaedam philosophicae The Chronology of Ancient Kingdoms Amended (1728) An Historical Account of Two Notable Corruptions of Scripture (1754)

Newtonianism	Bucket argument Newton's inequalities Newton's law of cooling Newton's law of universal gravitation Post-Newtonian expansion Parameterized post-Newtonian formalism Newton–Cartan theory Schrödinger–Newton equation Gravitational constant Newton's laws of motion Newtonian dynamics Newton's method in optimization Gauss–Newton algorithm Truncated Newton method Newton's rings Newton's theorem about ovals Newton–Pepys problem Newtonian potential Newtonian fluid Classical mechanics Newtonian fluid Corpuscular theory of light Leibniz–Newton calculus controversy Rotating spheres Newton's cannonball Newton–Cotes formulas Newton's method Newton fractal Generalized Gauss–Newton method Newton's identities Newton polynomial Newton's theorem of revolving orbits Newton–Euler equations Newton number Kissing number problem Power number Solar mass Dynamics Absolute time and space Finite difference Table of Newtonian series Impact depth Structural coloration Inertia

Life	Cranbury Park Woolsthorpe Manor Early life of Isaac Newton Later life of Isaac Newton Religious views of Isaac Newton Isaac Newton's occult studies The Mysteryes of Nature and Art Scientific revolution Copernican Revolution

Friends and family	Catherine Barton John Conduitt William Clarke Benjamin Pulleyn William Stukeley William Jones Isaac Barrow Abraham de Moivre John Keill

Discoveries and inventions	Calculus Newton disc Newton polygon Newton–Okounkov body Newton's reflector Newtonian telescope Newton scale Newton's metal Newton's cradle Sextant

Phrases	"Hypotheses non fingo" "Standing on the shoulders of giants"

Theory expansions	Kepler's laws of planetary motion Problem of Apollonius

Related	Writing of Principia Mathematica Newton (Blake) List of things named after Isaac Newton Newton (unit) Isaac Newton in popular culture Elements of the Philosophy of Newton Isaac Newton S/O Philipose

This article is issued from Wikipedia - version of the 11/29/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.