Newton-Cotes integration formulae

Contents

Newton-Cotes integration formulae#

The Newton-Cotes formulae are the most common numerical integration methods. They operate on essentially the same idea:

  1. Subdivide the integration domain

  2. On each subdivision, approximate the function with a polynomial which can be integrated exactly

  3. Sum all the subdivisions

Methods differ in the choice of the polynomial degree and the number of data points needed.

NOTE You may wonder why we don’t just fit a high degree polynomial and integrate that. As seen in the Curve Fitting notes, Runge’s Phenomena, which describes the tendency for high order polynomials to exhibit high oscilations torpedos this idea (Note to mention issues with higher dimensionality).

For example: a function being subdivided into a series of increasingly narrower rectangles:

Riemann_integral_regular.gif

Since we are doing a summation over subdivisions, there is no obvious need for consideration of continuity on the edges of our discretization; each block is independant. This implies trivial parallelization:

  1. Divide and distribute the integration domain amoung nodes.

  2. Each node finds the integral on its node.

  3. Sum all nodes.

a scheme which can also be cast as a recursive program.

Error#

It is easy to see that as the step size, \(h \rightarrow 0\), the number of boxes, \(n\rightarrow \infty\), and the approximation becomes the analytic integral.

Different algorithms will converge to the true integral at different rates for decressing step size. As with other numerical methods, the error is characterized by orders of \(h\); \(O(h^k)\).

The error now has to be considered on two levels:

  • integration on a single subdomain

  • summation of subdomains

The approximation would be perfect if either the subdomain integration were perfect, or if each subdomain were infintesiamally small.

Data points are usually equally spaced which has benefits for error analysis on both levels. I.e.: One could have equally spaced data in a subdomain with a different spacing between subdomains.

For example:

Riemann_integral_irregular.gif

Use case#

These formulae are valid for both the cases where the function is given and only sample points are available. However, these methods are typically only used for the case of discrete (tabulated) data.

Methods differ depending on the order of the polynomial used for each section.

Contents