Editing Newton–Cotes formulas

{{Short description|Formulas for numerical integration}}
[[File:Simpson rule.png|thumb|Newton–Cotes formula for&nbsp;<math>n=2</math>]]
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 {{mvar|f}} defined on <math>[a, b]</math> is known at <math>n + 1</math> equally spaced points: <math>a \leq x_0 < x_1 < \dots < x_n \leq b</math>. There are two classes of Newton–Cotes quadrature: they are called "closed" when <math>x_0 = a</math> and <math>x_n = b</math>, i.e. they use the function values at the interval endpoints, and "open" when <math>x_0 > a</math> and <math>x_n < b</math>, i.e. they do not use the function values at the endpoints. Newton–Cotes formulas using <math>n+1</math> points can be defined (for both classes) as<ref>{{cite book |author-link1=Alfio Quarteroni |last1=Quarteroni |first1=Alfio |last2=Sacco |first2=Riccardo |last3=Saleri |first3=Fausto |title=Numerical Mathematics |date=2006 |publisher=Springer |isbn=978-3-540-34658-6 |pages=386–387 |edition=Second}}</ref>
<math display="block">\int_a^b f(x)\, dx \approx \sum_{i = 0}^n w_i\, f(x_i),</math>
where
*for a closed formula, <math>x_i = a + ih</math>, with <math>h = \frac{b - a}{n}</math>,
*for an open formula, <math>x_i = a + (i + 1)h</math>, with <math>h = \frac{b - a}{n + 2}</math>.

The number {{mvar|h}} is called ''step size'', <math>w_i</math> are called ''weights''. The weights can be computed as the integral of [[Lagrange polynomial|Lagrange basis polynomial]]s. They depend only on <math>x_i</math> and not on the function {{mvar|f}}. Let <math>L(x)</math> be the interpolation polynomial in the Lagrange form for the given data points <math>(x_0, f(x_0)), (x_1, f(x_1)), \ldots, (x_n, f(x_n))</math>, then
<math display="block"> \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}.</math>

== Instability for high degree ==
A Newton–Cotes formula of any degree {{mvar|n}} can be constructed. However, for large {{mvar|n}} a Newton–Cotes rule can sometimes suffer from catastrophic [[Runge's phenomenon]]<ref>{{cite book |author-link1= Alfio Quarteroni|last1=Quarteroni |first1=Alfio |last2=Sacco |first2=Riccardo |last3=Saleri |first3=Fausto |title=Numerical Mathematics |date=2006 |publisher=Springer |isbn=978-3-540-34658-6 |pages=390–391 |edition=Second}}</ref> where the error grows exponentially for large {{mvar|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.<ref>{{cite web|url=http://www.holoborodko.com/pavel/numerical-methods/numerical-integration/stable-newton-cotes-formulas/|title=Stable Newton-Cotes Formulas|author=Pavel Holoborodko|date=2011-03-24|access-date=2015-08-17}}</ref><ref>{{cite web|url=http://www.holoborodko.com/pavel/numerical-methods/numerical-integration/stable-newton-cotes-formulas-open-type/|title=Stable Newton-Cotes Formulas (Open Type)|author=Pavel Holoborodko|date=2012-05-20|access-date=2015-08-18}}</ref>

== Closed Newton–Cotes formulas ==
This table lists some of the Newton–Cotes formulas of the closed type. For <math>0 \le i \le n</math>, let <math>x_i = a + ih</math> where <math>h = \frac{b - a}{n}</math>, and <math>f_i = f(x_i)</math>.

<!-- background style used to match TeX formulas rendered as PNG -->
{|class="wikitable" style="margin:1em auto 1em auto; text-align: center;"
|+'''Closed Newton–Cotes Formulas'''
!{{mvar|n}} !!Step size {{mvar|h}} !!Common name !!Formula !!Error term
|-
|1 ||<math>b - a</math> ||[[Trapezoidal rule]] ||<math>\frac{1}{2} h(f_0 + f_1)</math> ||<math>-\frac{1}{12}h^3f^{(2)}(\xi)</math>
|-
|2 ||<math>\frac{b - a}{2}</math> ||[[Simpson's rule]] ||<math>\frac{1}{3} h(f_0 + 4f_1 + f_2)</math> ||<math>-\frac{1}{90} h^5f^{(4)}(\xi)</math>
|-
|3 ||<math>\frac{b - a}{3}</math> ||[[Simpson's rule#Simpson's 3/8 rule|Simpson's 3/8 rule]] ||<math>\frac{3}{8} h(f_0 + 3f_1 + 3f_2 + f_3)</math> ||<math>-\frac{3}{80} h^5f^{(4)}(\xi)</math>
|-
|4 ||<math>\frac{b - a}{4}</math> ||[[Boole's rule]] ||<math>\frac{2}{45} h(7f_0 + 32f_1 + 12f_2 + 32f_3 + 7f_4)</math> ||<math>-\frac{8}{945} h^7f^{(6)}(\xi)</math>
|}

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.<ref>[http://mathworld.wolfram.com/BoolesRule.html Booles Rule at Wolfram Mathworld, with typo in year "1960" (instead of "1860")]</ref>

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

== Open Newton–Cotes formulas ==
This table lists some of the Newton–Cotes formulas of the open type. For <math>0 \le i \le n</math>, let <math>x_i = a + (i + 1)h</math> where <math>h = \frac{b - a}{n + 2}</math>, and <math>f_i = f(x_i)</math>.

{|class="wikitable" style="margin:1em auto 1em auto; text-align: center;"
|+'''Open Newton–Cotes Formulas'''
!{{mvar|n}} !!Step size {{mvar|h}} !!Common name !!Formula !!Error term
|-
|0 ||<math>\frac{b - a}{2}</math> ||[[Rectangle method|Rectangle rule]], or<br />midpoint rule ||<math>2hf_0</math> ||<math>\frac{1}{3} h^3f^{(2)}(\xi)</math>
|-
|1 ||<math>\frac{b - a}{3}</math> || ||<math>\frac{3}{2} h(f_0 + f_1)</math> ||<math>\frac{3}{4}h^3f^{(2)}(\xi) </math>
|-
|2 ||<math>\frac{b - a}{4}</math> ||Milne's rule ||<math>\frac{4}{3} h(2f_0 - f_1 + 2f_2)</math> ||<math>\frac{14}{45} h^5f^{(4)}(\xi)</math>
|-
|3 ||<math>\frac{b - a}{5}</math> || ||<math>\frac{5}{24} h(11f_0 + f_1 + f_2 + 11f_3)</math> ||<math>\frac{95}{144} h^5f^{(4)}(\xi)</math>
|}

== Composite rules ==
For the Newton–Cotes rules to be accurate, the step size {{mvar|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 (geometry)|Quadrature (mathematics)]]
* [[Interpolation]]
* [[Spline interpolation]]

== References ==
<references />
* M. Abramowitz and I. A. Stegun, eds. [[Abramowitz and Stegun|''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.)''
* {{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 ==
* {{SpringerEOM|title=Newton–Cotes quadrature formula|id=Newton-Cotes_quadrature_formula}}
* [http://www.math-linux.com/spip.php?article74 Newton–Cotes formulas] on www.math-linux.com
* {{MathWorld | urlname= Newton-CotesFormulas | title=Newton–Cotes Formulas }}
* [http://www.numericalmathematics.com/integration_and_differentiation.htm Newton–Cotes Integration], numericalmathematics.com

{{Isaac Newton}}
{{Numerical integration}}
{{DEFAULTSORT:Newton-Cotes formulas}}
[[Category:Numerical integration]]