Math-Linux.com

Knowledge base dedicated to Linux and applied mathematics.

Home > Mathematics > Numerical integration > Newton-Cotes formulas

Newton-Cotes formulas

All the versions of this article: [English] [français]

The main objective is to numerically compute an integral. In order to do so, we shall introduce Lagrange interpolation polynomials, present the notions of quadrature rules and of exact quadrature rules on polynomial spaces. Finally, we shall define Newton-Cotes formulas and the particular cases of composite formulas for rectangles, trapezes and Simpson’s formula.

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

PNG - 11.9 kb

We then have to determine the following integral:

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

PNG - 3.5 kb

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.

PNG - 4.6 kb

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}.

Degree p Designation
0 Method of rectangles
1 Method of trapezes
2 Simpson’s method
3 3/8 Simpson’s method
4 Boole’s method

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)

PNG - 4 kb

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)

PNG - 5.8 kb

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)

PNG - 10 kb

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}))

Any message or comments?

comments powered by Disqus