View source for GCD

[[File:Simpson rule.png|thumb|Newton–Cotes formula for&nbsp;''n''&nbsp;=&nbsp;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 ''&fnof;'' defined on [''a'',&nbsp;''b''] is known at equally spaced points ''x''<sub>''i''</sub>, for ''i'' = 0, …, ''n'', where ''x''<sub>0</sub>&nbsp;= ''a'' and ''x''<sub>''n''</sub>&nbsp;= ''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

:<math>\int_a^b f(x) \,dx \approx \sum_{i=0}^n w_i\, f(x_i)</math>

where {{nowrap|''x''<sub>''i''</sub> {{=}} ''h'' ''i'' + ''x''<sub>0</sub>}},
with ''h'' (called the ''step size'') equal to {{nowrap|(''x''<sub>''n''</sub> &minus; ''x''<sub>0</sub>)&thinsp;/&thinsp;''n'' {{=}} (''b'' &minus; ''a'')&thinsp;/&thinsp;''n''}}.  The ''w''<sub>''i''</sub> are called ''weights''.

As can be seen in the following derivation the weights are derived from the [[Lagrange polynomial|Lagrange basis polynomial]]s.  This means they directly depend only on the ''x''<sub>''i''</sub> and not on the function ''&fnof;''. Indirectly, the weights do depend on ''&fnof;'', via the ''&fnof;''-dependence of the [[Lagrange polynomial]]s. Let ''L''(''x'') be the interpolation polynomial in the Lagrange form for the given data points {{nowrap|(''x''<sub>0</sub>, ''&fnof;''(''x''<sub>0</sub>)&thinsp;), …, (''x''<sub>''n''</sub>, ''&fnof;''(''x''<sub>''n''</sub>)&thinsp;)}}, then

:<math> \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}. </math>

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

:<math>\int_a^b f(x)\, dx \approx \sum_{i=1}^{n-1} w_i\, f(x_i).</math>

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.

==Closed Newton–Cotes formulae==
This table lists some of the Newton–Cotes formulae of the closed type. The notation <math>f_i</math> is a shorthand for <math>f(x_i)</math>, with ''x''<sub>''i''</sub>&nbsp;= {{nowrap|''a'' + ''i''&thinsp;(''b'' &minus; ''a'')&thinsp;/&thinsp;''n''}}, and ''n'' the degree.

<!-- background style used to match TeX formulae rendered as PNG --> 
{| class="wikitable" style="margin:1em auto 1em auto; background:white"
|+ '''Closed Newton–Cotes Formulae'''
! Degree !! Common name !! Formula !! Error term
|- align="center"
| 1 || [[Trapezoid rule]] || <math> \frac{b-a}{2} (f_0 + f_1) </math> || <math>-\frac{(b-a)^3}{12}\,f^{(2)}(\xi)</math>
|- align="center"
| 2 || [[Simpson's rule]] || <math> \frac{b-a}{6} (f_0 + 4 f_1 + f_2) </math> || <math>-\frac{(b-a)^5}{2880}\,f^{(4)}(\xi)</math>
|- align="center"
| 3 || Simpson's 3/8 rule || <math> \frac{b-a}{8} (f_0 + 3 f_1 + 3 f_2 + f_3) </math> || <math>-\frac{(b-a)^5}{6480}\,f^{(4)}(\xi)</math>
|- align="center"
| 4 || [[Boole's rule]] || <math> \frac{b-a}{90} (7 f_0 + 32 f_1 + 12 f_2 + 32 f_3 + 7 f_4) </math> || <math>-\frac{(b-a)^7}{1935360}\,f^{(6)}(\xi)</math>
|- align="center"  
|}
Boole's rule is sometimes mistakenly called Bode's rule  due to propagation of a typo in Abramowitz and Stegun, an early reference book.<ref>[http://mathworld.wolfram.com/BoolesRule.html Booles Rule at Wolfram Mathworld]</ref> 

The exponent of the segment size ''b''&nbsp;−&nbsp;''a'' in the error term shows the rate at which the approximation error decreases. The derivative of ''&fnof;'' in the error term shows which polynomials can be integrated exactly (i.e., with error equal to zero). Note that the derivative of ''&fnof;'' in the error term increases by 2 for every other rule. The number <math>\xi</math> is between ''a'' and&nbsp;''b''.

==Open Newton–Cotes formulae==
This table lists some of the Newton–Cotes formulae of the open type. Again, ''&fnof;''<sub>''i''</sub> is a shorthand for ''&fnof;''(''x''<sub>''i''</sub>), with ''x''<sub>''i''</sub>&nbsp;= {{nowrap|''a'' + ''i''&thinsp;(''b'' &minus; ''a'')&thinsp;/&thinsp;''n''}}, and ''n'' the degree. 

{| class="wikitable" style="margin:1em auto 1em auto; background:white"
|+ '''Open Newton–Cotes Formulae'''
! Common name !! step size !! Formula !! Error term !! Degree
|- align="center" 
| [[Rectangle method|Rectangle rule]], or<br>midpoint rule || <math>\frac{b-a}{2}</math>|| <math>(b-a) f_1\,</math> || <math>\frac{(b-a)^3}{24}\,f^{(2)}(\xi)</math> || 2
|- align="center" 
| Trapezoid method || <math>\frac{b-a}{3}</math>|| <math> \frac{b-a}{2} (f_1 + f_2) </math> || <math> \frac{(b-a)^3}{36}\,f^{(2)}(\xi) </math> || 3
|- align="center"
| Milne's rule || <math>\frac{b-a}{4}</math>|| <math> \frac{b-a}{3} (2 f_1 - f_2 + 2 f_3) </math> || <math> \frac{7(b-a)^5}{23040}f^{(4)}(\xi) </math> || 4
|- align="center"
| No Name <!-- do not add a name without giving supporting evidence --> || <math>\frac{b-a}{5}</math>|| <math> \frac{b-a}{24} (11 f_1 + f_2 + f_3 + 11 f_4) </math> || <math> \frac{19(b-a)^5}{90000}f^{(4)}(\xi) </math> || 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 <math>[a, b]</math> must be small itself, which is not true most of the time. For this reason, one usually performs numerical integration by splitting <math>[a, b]</math> 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]].

==See also==
*[[Quadrature (mathematics)]]
*[[Interpolation]]
*[[Spline interpolation]]

==References==
<references />
* M. Abramowitz and I. A. Stegun, eds. [[Abramowitz and Stegun|''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.)''
* {{Citation |last1=Press|first1=WH|last2=Teukolsky|first2=SA|last3=Vetterling|first3=WT|last4=Flannery|first4=BP|year=2007|title=Numerical Recipes: The Art of Scientific Computing|edition=3rd|publisher=Cambridge University Press| publication-place=New York|isbn=978-0-521-88068-8|chapter=Section 4.1. Classical Formulas for Equally Spaced Abscissas|chapter-url=http://apps.nrbook.com/empanel/index.html?pg=156}}
* Josef Stoer and Roland Bulirsch. ''Introduction to Numerical Analysis''. New York: Springer-Verlag, 1980. ''(See Section 3.1.)''

==External links==
*{{springer|title=Newton–Cotes quadrature formula|id=p/n066510}}
*[http://www.math-linux.com/spip.php?article74 Newton–Cotes formulae] on www.math-linux.com
*[http://hades.ph.tn.tudelft.nl/Internal/PHServices/Documentation/MathWorld/math/math/n/n080.htm Newton–Cotes Formulae]
*{{MathWorld | urlname= Newton-CotesFormulas | title= Newton–Cotes Formulae }}
*[http://math.fullerton.edu/mathews/n2003/NewtonCotesMod.html Module for Newton–Cotes Integration], fullerton.edu
*[http://www.numericalmathematics.com/integration_and_differentiation.htm Newton–Cotes Integration], numericalmathematics.com

{{DEFAULTSORT:Newton-Cotes formulas}}
[[Category:Numerical integration (quadrature)]]