Newton-Cotes formulas

Let $f:[a,b] \rightarrow \mathbf{R}$ be a continuous function. The aim is to compute the following integral:

$$I(f)=\int_a^bf(x)dx$$

We start by partitioning the interval $[a,b]$ into $n$ intervals $[x_i,x_{i+1}],i=0,\ldots,n-1$ with

$$a = x_{0} < x_{1} < \ldots < x_{n} =b.$$

Therefore:

$$I(f)=\int_a^bf(x)dx=\sum_{i=0}^{n-1}\int_{x_i}^{x_{i+1}}f(x)dx$$

We then have to determine the following integral:

$$\int_{x_i}^{x_{i+1}}f(x)dx,i=0,\ldots,n-1.$$

It is easy to switch to the interval $[-1,1]$ via the following substitution

$$t=2\frac{x-x_{i}}{x_{i+1}-x_{i}}-1$$
or

$$x=\frac{x_{i+1}-x_{i}}{2}(t+1)+x_i$$
therefore

$$\int_{x_i}^{x_{i+1}}f(x)dx=\frac{x_{i+1}-x_{i}}{2} \int_{-1}^{1}g_i(t)dt$$
where

$$g_i(t)=f\left(\frac{x_{i+1}-x_{i}}{2}(t+1)+x_i\right),i=0,\ldots,n-1.$$

Quadrature rule

Let $g$ be a continuous function on $[-1,1]$. The application $J$

$$J:g \longmapsto \sum_{j=0}^p\omega_j g(t_j)$$
is said to be a quadrature rule. The points defined by

$$-1\leq t_0 < t_1 < \ldots < t_p \leq 1$$
are called points of integration of the quadrature $J$ and

$$\omega_0,\omega_1,\ldots,\omega_p$$ are the weights of the quadrature rule $J$.

The weights and the points of integration are chosen such that:

$$\int_{-1}^{1}g(t)dt\simeq\sum_{j=0}^p\omega_j g(t_j)$$

Exact quadrature rule

Let $Q\in\mathbf{P}_q$ be the set of polynomials of degree at most equal to q. The quadrature rule $J$ is said to be exact in $\mathbf{P}_q$ if

$$\forall Q\in\mathbf{P}_q,\quad \int_{-1}^{1}Q(t)dt=J(Q)$$
Alternatively stated, if

$$\forall Q\in\mathbf{P}_q,\quad \int_{-1}^{1}Q(t)dt=\sum_{j=0}^p\omega_j Q(t_j)$$

Exact quadrature rule: Lagrange basis

Theorem.

Let $L_0,L_1,\ldots,L_p$ be the Lagrange-basis of $\mathbf{P}_{p}$ relatively to the points

$$-1 \leq t_0 < t_1 < \ldots < t_p \leq 1.$$
We have the following equivalence:

$$ J(g)=\sum_{j=0}^p\omega_j g(t_j)\mbox{ exact on } \mathbf{P}_{p} \Longleftrightarrow \omega_j=\int_{-1}^{1}L_j(t)dt,\quad j=0,1,\ldots,p. $$

Newton-Cotes formula

Newton-Cotes’s method is obtained from the above mentioned methods for which the points $(x_i)_{i=0,\ldots,n}$ are equidistant

$$x_i=x_0+hi$$
where $h=\frac{b-a}{n}$. This being so:

$$ \begin{array}{ccl} \displaystyle\int_{x_i}^{x_{i+1}}f(x)dx &=& \displaystyle\frac{x_{i+1}-x_{i}}{2} \int_{-1}^{1}g_i(t)dt\\ &\simeq& \displaystyle\frac{h}{2}J(g_i)\\ &\simeq& \displaystyle\frac{h}{2}\sum_{j=0}^p\omega_j g_i(t_j)\\ &\simeq& \displaystyle\frac{h}{2}\sum_{j=0}^p\omega_j f\left(\frac{h}{2}(t_j+1)+x_i\right) \end{array} $$
We can now approach $I(f)=\int_a^bf(x)dx$ by the composite formula $I_h(f)$:

$$ \begin{array}{ccl} \displaystyle I(f)=\int_a^bf(x)dx&=&\displaystyle\sum_{i=0}^{n-1}\int_{x_i}^{x_{i+1}}f(x)dx\\ &\simeq&\displaystyle\frac{h}{2}\sum_{i=0}^{n-1}\sum_{j=0}^p\omega_j f\left(\frac{h}{2}(t_j+1)+x_i\right) \end{array} $$
where

$$ I_h(f)=\frac{h}{2}\sum_{i=0}^{n-1}\sum_{j=0}^p\omega_j f\left(\frac{h}{2}(t_j+1)+x_i\right) $$

Following are some classical Newton formulas as well as the degree $p$ of
$\mathbf{P}_{p}$.

Method of rectangles

The method of rectangles is a one-point method. In this case, $p=0$ and
$t_0=0$. Lagrange basis associated to $\mathbf{P}_{0}$ is

$$ L_0(t)=1 $$
Consequently:

$$\omega_0=\int_{-1}^{1}L_0(t)dt=\int_{-1}^{1}dt=2$$
The quadrature rule is defined by:

$$J(g)=\omega_0g(t_0)=2g(0)$$

We thus have the composite rectangle formula:

$$I_h(f)=h \sum_{i=0}^{n-1}f\left(\frac{x_i+x_{i+1}}{2}\right)$$

Method of trapezes

The method of trapezes is a two-point method. In this case, $p=1$ and
$t_0=-1,t_1=1$. Lagrange basis associated to $\mathbf{P}_{1}$ is

$$ L_0(t)=\frac{1-t}{2},L_1(t)=\frac{t+1}{2} $$
Consequently:

$$\omega_0=\int_{-1}^{1}L_0(t)dt=1;\omega_1=\int_{-1}^{1}L_1(t)dt=1$$
The quadrature rule is defined by:

$$J(g)=\omega_0g(t_0)+\omega_1g(t_1)=g(-1)+g(1)$$

We thus have the composite trapezes formula:

$$I_h(f)=\frac{h}{2}\sum_{i=0}^{n-1}(f(x_i)+f(x_{i+1}))$$

Simpson’s method

Simpson’s method is a three-point method. In this case, $p=2$ and
$t_0=-1,t_1=0,t_2=1$. Lagrange basis associated to $\mathbf{P}_{2}$ is

$$ L_0(t)=\frac{t^2-t}{2},L_1(t)=1-t^2,L_2(t)=\frac{t^2+t}{2} $$
Consequently:

$$\omega_0=\int_{-1}^{1}L_0(t)dt=\frac{1}{3}; \omega_1=\int_{-1}^{1}L_1(t)dt=\frac{4}{3}; \omega_2=\int_{-1}^{1}L_1(t)dt=\frac{1}{3}; $$
The quadrature rule is defined by:

$$J(g)=\omega_0g(t_0)+\omega_1g(t_1)+\omega_2g(t_2) =\frac{1}{3}g(-1)+\frac{4}{3}g(0)+\frac{1}{3}g(1)$$

We thus have Simpson’s composite formula:

$$I_h(f)=\frac{h}{6}\sum_{i=0}^{n-1}(f(x_i)+4 f(\frac{x_i+x_{i+1}}{2}) +f(x_{i+1}))$$