Subject: Calculus

Newton Cotes Formulas

In numerical integration, we are basically studying numerical techniques to approximate a value for the definite integral given by

\int_{a}^{b}f(x)dx

with the interval [a,b] a a finite interval. Let us review the three integration rules namely rectangle method or more commonly known as the midpoint rule, trapezoidal rule, and lastly the Simpsonís rule.

The midpoint rule uses the zeroth order polynomial interpolating a function f in one point, \bar{x}_i = \frac{1}{2} (x_{i-1}+ x_i ) which is just the midpoint of a certain interval [x_{i-1},x_i] . We can therefore approximate the values of the definite integral as follows

\int_{a}^{b}f(x)dx \approx M_{n} \sum_{i=1}^{n}f(\bar{x}_i) \Delta x

where

\Delta x =\frac{b-a}{n}

The trapezoidal rule uses a first order polynomial interpolating f in two points, x_1 = a and x_2 = b. Then

f(x) \approx \frac{b-x}{b-a}f(a) + \frac{x-a}{b-a}f(b)

Denoting this rule as T(f), we can therefore summarize this rule as

T(f)=\int_{a}^{b}f(x)dx \approx (b-a)\frac{f(a) + f(b)}{2}

The Simpsonís rule uses a second order polynomial to interpolate f in three points P_0, P_1, and P_2. We have already showed this (see Simpsonís Rule) which gives as the expression

\int_{a}^{b} f(x)dx \approx S_n =\frac{h}{3}\left [f(x_0) + 4 f(x_1) + 2f(x_2)+ 4f(x_3)+ \cdot \cdot \cdot +2f(x_{n-2}) + 4f(x_{n-}) + f(x_n) \right ]

where n is even, h= ∆x =\frac{b-a}{n} and S_n denotes the Simpsonís rule being applied to the function f. For polynomial of the third degree, we have

\int_{a}^{b} f(x)dx \approx \frac{3h}{8}\left [f(a) + 3f(a+h) + 3f(b-h)+ f(b) \right ]

where h= \frac{b-a}{3}.

For polynomial of the third degree, we have

\int_{a}^{b} f(x)dx \approx \frac{2h}{45}\left [7f(a) + 32f(a+h) + 12f(\frac{a+b}{2}) + 32f(b-h)+ 7f(b) \right ]

where h= \frac{b-a}{4}.

All of the above mentioned methods (and rules) are called the Newton-Cotes Formulas. Newton-Cotes formula is based on equidistant polynomial interpolation. It is the most simple interpolatory numerical methods of integration.

We can write a generalize formula for the Newton-Cotes formulas as

\int_{a}^{b}f(x)dx \approx \sum_{i=1}^{n}w_if(x_i)

where x_i are the nodes and w_i are the weights that minimized the error by ensuring that the quadrature formula was interpolatory. For instance, for the midpoint rule, our w_1 = ∆x= \frac{b-a}{1} =b-a.

The higher order Newton-Cotes are seldom used because the problems encountered for higher order equidistant polynomial interpolation carry over also to interpolatory integration formula. Instead of going into the complex idea of higher order Newton-Cotes, we can use composite or mixed low order of Newton-Cotes rule.

Simple and Composite Rules

In composite rules, we still divide the interval [a, b] into m subintervals which are often equidistant than not. Next, we apply the low order Newton-Cotes rules (i.e. rectangle method, trapezium method, or Simpsonís rule). To distinguish the rules that we are using, let us make use of the term simple to define the original rule being used from the composite rules that we will apply. If the simple rule is interpolatory, then the composite rule corresponds to exact integration of piecewise polynomials.

The simple rules as we are only defined for a specific interval [a, b]. We can however easily apply them to a general interval [α, β]. Let us write Q_k(f, a, b) to indicate that the quadrature formula is applied to the interval [a, b] and suppose that the original rule is the k-point formula

Q_k(f, a, b) = \sum_{i=1}^{n}w_i f(x_i) \approx \int_{a}^{b}f(x)dx

Then by change of variables, x \to ρ(x-a) + α with ρ = \frac{β- α}{b-a}, we will have

\int_{\alpha}^{\beta}f(x)dx = \rho \int_{a}^{b}f(\rho (x-a) +a)dx

The last integral is over the right interval and we use Q_k(f, a, b) to approximate it

\int_{\alpha}^{\beta}f(x)dx \approx \sum_{i=1}^{n} w_i \rho f(\rho (x-a) +a)

This hence defines Q_k(f,α, β) for general intervals [α, β]. We are now ready to define the composite rule corresponding to Q_k. As for piecewise polynomial interpolation we divide the interval [a, b] into m subintervals separated by m+1 points {y_i}, which we for simplicity take to be equidistant,

y_i = a + (i-1)h
,
h = \frac{b-a}{m}

We can then get the following,

\int_{a}^{b}f(x)dx = \sum_{i=1}^{n} \int_{y_1}^{y_1+1}f(x)dx

Our composite rule \mathbf{Q}_n can now be written as

\mathbf{Q}_n (f, a, b) = \sum_{i=1}^{m} Q_k (f, y_i, y_i+1 )

Here n represents the total number of nodes (function evaluations) used in the composite rule, which is of the order k (points per subinterval) multiplied by m (number of subintervals). More precisely, n = (k − 1)m + 1 if Q_k is a closed rule (the interval end points belongs to the nodes) and n = km if Q_k is an open rule (the interval end points do not belong to the nodes).

NEXT TOPIC: Gaussian quadrature