Newton-Cotes formulas

In numerical analysis, the Newton-Cotes formulas, also called the Newton-Cotes rules, are a group of formulas for numerical integration (also called quadrature).

Related Topics:
Numerical analysis - Numerical integration

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

They are named after Isaac Newton and Roger Cotes.

Related Topics:
Isaac Newton - Roger Cotes

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

It is assumed that the value of a function f is known at equally spaced points xi, for i = 0, ..., n.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

(If the evaluation points are not assumed to be equally spaced,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

another class of formulas, called Gaussian quadrature formulas,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

can be derived.)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

There are two types of Newton-Cotes formulas,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

the "closed" type which uses the function value at all points,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

and the "open" type which does not use the function values at the end points.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The closed Newton-Cotes formula of degree n is stated as

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:int_a^b f(x) ,dx pprox sum_{i=0}^n w_i, f(x_i)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where xi = h i + x0,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

with h (called the step size) equal to (xn - x0)/n. The w_i are called weights.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

As can be seen in the following derivation the weights are derived from the Lagrange basis polynomials. This means they depend only on the xi and not on the function f. L(x) is the interpolation polynomial in the Lagrange form for the given data points (x0, f(x0) ),..,(xn, f(xn) )

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:int_a^b f(x) ,dx pprox int_a^b L(x),dx = int_a^b sum_{i=0}^n f(x_i), l_i(x), dx

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:=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}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The open Newton-Cotes formula of degree n is stated as

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:int_a^b f(x), dx pprox sum_{i=1}^{n-1} w_i, f(x_i)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The weights are found in a manner similar to the closed formula.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

A Newton-Cotes formula of any degree can be constructed.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Some of the formulas of low degree are known by conventional names.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

This table lists some of the Newton-Cotes formulas of the closed type.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The notation f_i is a shorthand for f(x_i).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Degree

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Common name

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Formula

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Error term

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

1

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Trapezoid rule

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

rac{h}{2} (f_0 + f_1)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

-rac{h^3}{12},f^{(2)}(xi)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

2

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Simpson's rule

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

rac{h}{3} (f_0 + 4 f_1 + f_2)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

-rac{h^5}{90},f^{(4)}(xi)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

3

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

3/8 rule

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

rac{3, h}{8} (f_0 + 3 f_1 + 3 f_2 + f_3)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

-rac{3, h^5}{80},f^{(4)}(xi)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

4

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Boole's rule

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

rac{2, h}{45} (7 f_0 + 32 f_1 + 12 f_2 + 32 f_3 + 7 f_4)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

-rac{8, h^7}{945},f^{(6)}(xi)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The exponent of the step size h in the error term shows the rate at which the approximation error decreases.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The derivative of f in the error term shows which polynomials can be integrated exactly (i.e., with error equal to zero).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Note that the derivative of f in the error term increases by 2 for every other rule. The number xi is between a and b.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

This table lists some of the Newton-Cotes formulas of the open type.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Degree

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Common name

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Formula

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Error term

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Rectangle rule

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

2 h f_1

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

rac{h^3}{24},f^{(2)}(xi)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

1

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

rac{3, h}{2} (f_1 + f_2)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

rac{h^3}{4},f^{(2)}(xi)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

2

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

rac{4 ,h}{3} (2 f_1 - f_2 + 2 f_3)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

rac{28, h^5}{90},f^{(4)}(xi)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

3

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

rac{5 ,h}{24} (11 f_1 + f_2 + f_3 + 11 f_4)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

rac{95, h^5}{144},f^{(4)}(xi)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Notice that for the Newton-Cotes rules to be accurate, the step size h needs to be small, which means that the interval of integration

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

must be small itself, which is not true most of the time. For this reason, one usually

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

performs numerical integration by splitting 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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~