<<Up     Contents

Newton-Cotes formulas

Newton-Cotes formulas (so named after Isaac Newton and Roger Cotes) are a group of formulas used for numerical integration (quadrature), a subject of numerical analysis. They deal with classifying a number of possible solutions to this problem under the assumption that you have gained samples of a function <math>f(x)</math> on <math>n</math> equidistant points <math>x_0, x_1, x_2, ..., x_n</math> such that <math>x_0 < x_1 < x_2 ... x_n</math> and <math>x_1-x_0 = x_2-x_1 = ... x_{n}-x_{n-1}= h</math>. Under this assumption Newton-Cotes formula holds that:

<math>\int_a^b f(x) dx \approx \sum_0^n w_i f(x_i)</math>

The <math>w_i</math>:s are called weights and are derived from computing the corresponding Lagrange polynomials thusly:

<math>\int_a^b f(x) dx \approx \int_a^b P(x) = \int_a^b \sum_{i=0}^n f(x_i) L_i(x) dx =</math>
<math>\sum_{i=0}^n \int_{x_{i-1}}^{x_i} f(x_i) L_i(x) dx =
\sum_{i=0}^n f(x_i) \underbrace{\int_{x_{i-1}}^{x_i} L_i(x) dx}_{w_i}</math>

Here the <math>w_i</math>:s are fix constants depending only on the chosen <math>x_i</math>:s. Computing this integral for different numbers of points <math>n</math> will yield some famous quadrature formulas:

<math>n</math> Common name Short form Exact for
0 Midpoint rule <math>M(x)</math> <math>f \in \pi_1</math>
1 Trapezoid rule <math>T(x)</math> <math>f \in \pi_1</math>
2 Simpson's rule <math>S(x)</math> <math>f \in \pi_3</math>
3 ? ? <math>f \in \pi_3</math>
4 Bode's rule[?] ? <math>f \in \pi_5</math>
... ... ... ...

These are the actual Newton-Cotes formulas. The <math>\pi</math>:s on the left signify on which monomial[?] bases the solution is exact, e.g. a solution that is exact for <math>\pi_2</math> will be exact on the monomials in the set <math>\{1, x, x^2\}</math>. Note that the formulas' exactness increase in odd steps, so using the trapezoid rule for integrating is actually no better than using the midpoint rule, and just a waste of time. In the same manner, Simpson's rule will be exact for monomials in <math>\{1, x, x^2, x^3\}</math> which will suffice for most functions found in practice.

If you also let the distance <math>h</math> between each sample point vary, you obtain another group of quadrature formulas, the best of which is know as Gaussian quadrature.

External Links

wikipedia.org dumped 2003-03-17 with terodump