Numerical Integration

Abstract

Numerical integration (quadrature) of proper integrals is characterized by a big variety of methods. This chapter discusses the rectangular rules (based on the forward, backward, and central difference approximation), the trapezoidal rule, and the Simpson rule as a multi-point integration method. It moves on to a more general description - the Newton - Cotes rules and, in particular, to the Romberg method. The Gauss - Legendre quadrature is introduced as a very efficient alternative. Finally, the treatment of improper integrals and of multiple integrals is discussed. Particular emphasis is on the errors involved.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Numerical integration is certainly one of the most important concepts in computational analysis since it plays a major role in the numerical treatment of differential equations. Given a function $f(x)$ which is continuous on the interval $[a,b]$, one wishes to approximate the integral by a discrete sum of the form

$$\begin{aligned} \int \limits _a^b \mathrm {d}x f(x) \approx \sum _{i = 1}^N \omega _i f(x_i), \end{aligned}$$

(3.1)

where the $\omega _i$ are referred to as weights and $x_i$ are the grid-points at which the function needs to be evaluated. Such methods are commonly referred to as quadrature.

We will mainly discuss two different approaches to the numerical integration of arbitrary functions. We start with a rather simple approach, the rectangular rule. The search of an improvement of this method will lead us first to the trapezoidal rule, then to the Simpson rule and, finally, to a general formulation of the method, the Newton-Cotes quadrature. This will be followed by a more advanced technique, the Gauss-Legendre quadrature. At the end of the chapter we will discuss an elucidating example and briefly sketch extensions of all methods to more general problems, such as integration of non-differentiable functions or the evaluation of multiple integrals.

Another very important approach, which is based on random sampling methods, is the so called Monte-Carlo integration. This method will be presented in Sect. 14.2.

2 Rectangular Rule

The straight forward approach to numerical integration is to employ the concept of finite differences developed in Sect. 2.2. We regard a smooth function $f(x)$ within the interval $[a,b]$, i.e. $f(x) \in {\fancyscript{C}}^\infty [a,b]$. The Riemann definition of the proper integral of $f(x)$ from $a$ to $b$ states that:

$$\begin{aligned} \int \limits _a^b \mathrm {d}x f(x) = \lim _{N \rightarrow \infty } \frac{b-a}{N} \sum _{i = 0}^N f \left( a + i \frac{b - a}{N} \right) . \end{aligned}$$

(3.2)

We approximate the right hand side of this relation using equally spaced grid-points$x_i\in [a,b]$ according to Eq. ( 2.1) and find

$$\begin{aligned} \int \limits _a^b \mathrm {d}x f(x) \approx h \sum _{i = 1}^{N-1} f_i. \end{aligned}$$

(3.3)

However, it is clear that the quality of this approach strongly depends on the discretization chosen, i.e. on the values of $x_i$ as illustrated schematically in Fig. 3.1. Again, a non-uniform grid may be of advantage. We can estimate the error of this approximation by expanding $f(x)$ into a Taylor series.

Fig. 3.1

Illustration of the numerical approximation of a proper integral according to Eq. (3.3)

We note that

$$\begin{aligned} \int \limits _a^b \mathrm {d}x f(x) = \sum _{i = 1}^{N-1} \int \limits _{x_i}^{x_{i+1}} \mathrm {d}x f(x), \end{aligned}$$

(3.4)

hence, the approximation (3.3) is equivalent to the approximation

$$\begin{aligned} \int \limits _{x_i}^{x_{i+1}}\! \mathrm {d}x\, f(x) \approx h f_i, \end{aligned}$$

(3.5)

with $\int \limits _{x_i}^{x_{i+1}}\! \mathrm {d} x\, f(x)$ the elemental area. According to (2.9a) we have

$$\begin{aligned} \int \limits _{x_i}^{x_{i+1}} \mathrm {d}x f(x)&=\int \limits _{x_i}^{x_{i+1}} \mathrm {d}x \left[ f_i + (x - x_i) f_i' + (x - x_i)^2 f_{i+\varepsilon _\zeta }'' \right] \nonumber \\&=f_i h + \frac{h^2}{2} f_i' + \fancyscript{O}(h^3). \end{aligned}$$

(3.6)

In the last step we applied the first mean value theorem for integration which states that if $f(x)$ is continuous in $[a,b]$, then there exists a $\zeta \in [a,b]$ such that

$$\begin{aligned} \int \limits _a^b \mathrm {d}x f(x) = (b - a) f(\zeta ). \end{aligned}$$

(3.7)

(We shall come back to the mean value theorem in the course of our discussion of Monte-Carlo integration in Chap. 14.) According to (3.6) the error we make with approximation (3.3) is of order $\fancyscript{O}(h^2)$.

This procedure corresponds to a forward difference approach and in a similar fashion a backward difference approach can be chosen. It results in:

$$\begin{aligned} \int \limits _a^b \mathrm {d}x f(x) = h \sum _{i = 2}^N f_i + \fancyscript{O}(h^2). \end{aligned}$$

(3.8)

Let us now define the forward and backward rectangular rule by

$$\begin{aligned} {}_iI^+_{i+1} = h f_i, \end{aligned}$$

(3.9)

and

$$\begin{aligned} {}_i I^-_{i+1} = h f_{i+1}, \end{aligned}$$

(3.10)

respectively. Thus we have

$$\begin{aligned} \int \limits _{x_i}^{x_{i+1}} \mathrm {d}x f(x)&= {}_iI^+_{i+1} + \frac{h^2}{2} f_i' + \frac{h^3}{3 !} f''_{i} + \cdots \nonumber \\&= {}_iI^-_{i+1} - \frac{h^2}{2} f_{i+1}' + \frac{h^3}{3 !} f''_{i+1} \mp \cdots . \end{aligned}$$

(3.11)

However, an even more accurate way to proceed is to make use of the central difference approximation. We consider the integral

$$\begin{aligned} \int \limits _{x_i}^{x_{i+1}} \mathrm {d}x f(x), \end{aligned}$$

(3.12)

expand $f(x)$ in a Taylor series around the midpoint $x_{i + \frac{1}{2}}$, and obtain:

$$\begin{aligned} \int \limits _{x_i}^{x_{i+1}} \mathrm {d}x f(x)&= \int \limits _{x_i}^{x_{i+1}} \mathrm {d}x \Bigg \{ f_{i+\frac{1}{2}} + \left( x- x_{i+\frac{1}{2}} \right) f'_{i+\frac{1}{2}} \nonumber \\&\quad +\,\, \frac{\left( x - x_{i+\frac{1}{2}} \right) ^2}{2} f''_{i+\frac{1}{2}} + \fancyscript{O}\left[ \left( x - x_{i+\frac{1}{2}} \right) ^3 \right] \Bigg \}\nonumber \\&= h f_{i +\frac{1}{2}} + \frac{h^3}{24} f''_{i+\varepsilon _\zeta } \nonumber \\&= {}_i I_{i+1} + \frac{h^3}{24} f''_{i+\varepsilon _\zeta }. \end{aligned}$$

(3.13)

Thus, the error generated by this method, the central rectangular rule, scales as $\fancyscript{O}(h^3)$ which is a significant improvement in comparison to Eqs. (3.3) and (3.8). We obtain

$$\begin{aligned} \int \limits _a^b \mathrm {d}x f(x) = h\sum _{i = 1}^{N-1} f_{i + \frac{1}{2}} + \fancyscript{O}(h^3). \end{aligned}$$

(3.14)

This approximation is known as the rectangular rule. It is illustrated in Fig. 3.2. Note that the boundary points $x_1 = a$ and $x_N = b$ do not enter Eq. (3.14). Such a procedure is commonly referred to as an open integration rule . On the other hand, if the end-points are taken into account by the method it is referred to as a closed integration rule .

3 Trapezoidal Rule

An elegant alternative to the rectangular rule is found when the area between two grid-points is approximated by a trapezoid as is shown schematically in Fig. 3.3. The elemental area is calculated from

Fig. 3.2

Scheme of the rectangular integration rule according to Eq. (3.14). Note that boundary points do not enter the evaluation of the elemental areas

Fig. 3.3

Sketch of how the elemental areas under the curve $f(x)$ are approximated by trapezoids

$$\begin{aligned} \int \limits _{x_i}^{x_{i+1}} \mathrm {d}x f(x) \approx \frac{h}{2} \left( f_i + f_{i+1} \right) . \end{aligned}$$

(3.15)

Hence, we obtain

$$\begin{aligned} \int \limits _a^b \mathrm {d}x f(x)&\approx \frac{h}{2} \sum _{i=1}^{N-1} \left( f_i + f_{i+1} \right) \nonumber \\&= h \left( \frac{f_1}{2} + f_2 + \cdots + f_{N-1} + \frac{f_N}{2} \right) \nonumber \\&= \frac{h}{2} \left( f_1 + f_N \right) + h \sum _{i = 2}^{N-1} f_i \nonumber \\&= {}_1 I^T_N . \end{aligned}$$

(3.16)

Note that this integration rule is closed, although the boundary points $f_1$ and $f_N$ enter the summation (3.16) only with half the weight in comparison to all other function values $f_i$ which is a quite reasonable result because the boundary points contribute only to one elemental area, the first and the last one. Another noticeable feature of the trapezoidal rule is that, in contrast to the rectangular rule (3.14), only function values at grid-points enter the summation, which can be desirable in some cases.

The error of this method can be estimated by inserting expansion (2.9a) into Eq. (3.16). One obtains for an elemental area:

$$\begin{aligned} {}_i I_{i+1}^T&= \frac{h}{2} \left( f_i + f_{i+1} \right) \nonumber \\&= h f_i + \frac{h^2}{2} f_i' + \frac{h^3}{4} f_i'' + \cdots . \end{aligned}$$

(3.17)

On the other hand, we know from Eq. (3.6) that

$$\begin{aligned} h f_i = \int \limits _{x_i}^{x_{i+1}} \mathrm {d}x f(x) - \frac{h^2}{2} f_i' - \frac{h^3}{3!} f''_i - \cdots , \end{aligned}$$

(3.18)

which, when inserted into (3.17), yields

$$\begin{aligned} {}_i I_{i+1}^T = \int \limits _{x_i}^{x_{i+1}} \mathrm {d}x f(x) + \frac{h^3}{12}f_i'' + \fancyscript{O}(h^4). \end{aligned}$$

(3.19)

Hence, we observe that the error induced by the trapezoidal rule is comparable to the error of the rectangular rule, namely $\fancyscript{O}(h^3)$. However, since we do not have to compute function values at intermediate grid-points, this rule may be advantageous in many cases. We remember from Chap. 2 that a more accurate estimate of a derivative was achieved by increasing the number of grid-points which in the case of integration leads us to the Simpson rule.

4 The Simpson Rule

The basic idea of the Simpson rule is to include higher order derivatives into the expansion of the integrand. These higher order derivatives, which are primarily unknown, are then approximated by expressions we obtained within the context of finite difference derivatives. Let us discuss this procedure in greater detail. To this purpose we will study the integral of $f(x)$ within the interval $[x_{i-1}, x_{i+1}]$ and expand the integrand around the midpoint $x_i$:

$$\begin{aligned} \int \limits _{x_{i-1}}^{x_{i+1}} \mathrm {d}x f(x)&= \int \limits _{x_{i-1}}^{x_{i+1}} \mathrm {d}x \left[ f_i + (x - x_i) f_i' + \frac{(x - x_i)^2}{2!} f_i''\right. \nonumber \\&\quad \left. +\,\, \frac{(x - x_i)^3}{3!} f_i''' + \cdots \right] \nonumber \\&= 2h f_i + \frac{h^3}{3} f_i'' + \fancyscript{O}( h^5 ). \end{aligned}$$

(3.20)

Inserting Eq.  (2.34) for $f_i''$ yields

$$\begin{aligned} \int \limits _{x_{i-1}}^{x_{i+1}} \mathrm {d}x f(x)&= 2 h f_i + \frac{h}{3} \left( f_{i+1} - 2 f_i + f_{i-1} \right) + \fancyscript{O}( h^5 ) \nonumber \\&= h \left( \frac{1}{3} f_{i-1} + \frac{4}{3} f_i + \frac{1}{3} f_{i+1} \right) + \fancyscript{O}( h^5 ). \end{aligned}$$

(3.21)

Note that in contrast to the trapezoidal rule, the procedure described here is a three point method since the function values at three different points enter the expression. We can immediately write down the resulting integral from $a \rightarrow b$. Since,

$$\begin{aligned} \int \limits _a^b \mathrm {d}x f(x) = \int \limits _{x_{0}}^{x_{2}} \mathrm {d}x f(x) + \int \limits _{x_{2}}^{x_{4}} \mathrm {d}x f(x) + \cdots + \int \limits _{x_{N-2}}^{x_{N}} \mathrm {d}x f(x), \end{aligned}$$

(3.22)

where we assumed that $N$ is even and employed the discretization $x_i = x_0 + i h$ with $x_0 = a$ and $x_N = b$. We obtain:

$$\begin{aligned} \int \limits _a^b \mathrm {d}x f(x) = \frac{h}{3} \left( f_0 + 4 f_1 + 2 f_2 + 4 f_3 + \cdots +2 f_{N-2} + 4 f_{N-1} + f_N \right) + \fancyscript{O}(h^5). \end{aligned}$$

(3.23)

This expression is exact for polynomials of order $n \le 3$ since the first term in the error expansion involves the fourth derivative. Hence, whenever the integrand is satisfactorily reproduceable by a polynomial of degree three or less, the Simpson rule might give almost exact estimates, independent of the discretization $h$.

The arguments applied above allow for a straightforward extension to four- or even more-point rules. We find, for instance,

$$\begin{aligned} \int \limits _{x_i}^{x_{i+3}} \mathrm {d}x f(x) = \frac{3h}{8} \left( f_i + 3 f_{i+1} + 3f_{i+2} + f_{i+3} \right) + \fancyscript{O}(h^5), \end{aligned}$$

(3.24)

which is usually called Simpson’s three-eight rule.

It is important to note that all the methods discussed so far are special cases of a more general formulation, the Newton-Cotes rules which will be discussed in the next section.

5 General Formulation: The Newton-Cotes Rules

We define the Lagrange interpolating polynomial$P(x)$ of order $n$ [1, 2] to a function $f(x)$ as

$$\begin{aligned} P(x) = \sum _{j = 1}^n P_j(x), \end{aligned}$$

(3.25)

where

$$\begin{aligned} P_j(x) = f_j \prod _{k = 1 \atop {k \ne j}}^n \frac{x - x_k}{x_j - x_k}. \end{aligned}$$

(3.26)

An arbitrary smooth function $f(x)$ can then be expressed with the help of an $n$-th order Lagrange polynomial by

$$\begin{aligned} f(x) = P(x) + \frac{f^{(n)}[\zeta (x)]}{n!} (x - x_1) (x - x_2) \ldots (x - x_n). \end{aligned}$$

(3.27)

If we neglect the second term on the right hand side of this equation and integrate the Lagrange polynomial of order $n$ over the $n$ grid-points from $x_1 \rightarrow x_N$ we obtain the closed $n$-point Newton-Cotes formulas. For instance, if we set $n = 2$, then

$$\begin{aligned} P(x)&= P_1(x) + P_2(x) \nonumber \\&= f_1 \frac{x - x_2}{x_1 - x_2} + f_2 \frac{x - x_1}{x_2 - x_1} \nonumber \\&= \frac{1}{h} \left[ x (f_2 - f_1) - x_1 f_2 + x_2 f_1 \right] , \end{aligned}$$

(3.28)

with $f_1 \equiv f(x_1)$ and $f_2 \equiv f(x_2)$. Integration over the respective interval yields

$$\begin{aligned} \int \limits _{x_1}^{x_2}\mathrm {d}x\, P(x)&= \frac{1}{h}\left. \left[ \frac{x^2}{2} (f_2 -f_1) + x(x_2 f_1 - x_1 f_2 )\right] \right| _{x_1}^{x_2} \nonumber \\&= \frac{1}{h} \left[ \frac{x_2^2 - x_1^2}{2} (f_2 - f_1) + ( x_2 - x_1) (x_2 f_1 - x_1 f_2 ) \right] \nonumber \\&= \frac{1}{2} \left[ (x_2 + x_1) (f_2 - f_1) + 2 x_2 f_1 - 2 x_1 f_2 \right] \nonumber \\&= \frac{h}{2} \left[ f_2 + f_1 \right] + \fancyscript{O}(h^3), \end{aligned}$$

(3.29)

which is exactly the trapezoidal rule . By setting $n = 3$ one obtains Simpson’s rule and setting $n = 4$ gives the Simpson’s three-eight rule.

The open Newton-Cotes rule can be obtained by integrating the polynomial $P(x)$ of order $n$ which includes the grid-points $x_1, \ldots , x_n$ from $x_0 \rightarrow x_{n+1}$. The fact that these relations are open means that the function values at the boundary points $x_0 = x_1 - h$ and $x_{n+1} = x_n + h$ do not enter the final expressions. The simplest open Newton-Cotes formula is the central integral approximation, which we encountered as the rectangular rule (3.14). A second order approximation is easily found with help of the two-point Lagrange polynomial (3.28)

$$\begin{aligned} \int \limits _{x_0}^{x_3} \mathrm {d}x P(x)&= \frac{1}{h} \left. \left[ \frac{x^2}{2} (f_2 -f_1) + x(x_2 f_1 - x_1 f_2 )\right] \right| _{x_0}^{x_3} \nonumber \\&= \frac{1}{h} \left[ \frac{x_3^2 - x_0^2}{2} (f_2 - f_1) + ( x_3 - x_0) (x_2 f_1 - x_1 f_2 ) \right] \nonumber \\&= \frac{x_3 - x_0}{h} \left[ \frac{1}{2} (x_3 + x_0 ) (f_2 - f_1 ) + (x_2 f_1 - x_1 f_2 ) \right] \nonumber \\&= \frac{3}{2} \left[ (x_3 + x_0 -2 x_1) f_2 + (2 x_2 - x_3 - x_0 ) f_1 \right] \nonumber \\&= \frac{3h}{2} \left[ f_2 + f_1 \right] + \fancyscript{O}(h^3). \end{aligned}$$

(3.30)

Higher order approximations can be obtained in a similar fashion. To conclude this section let us briefly discuss an idea which is referred to as Romberg’s method.

So far, we approximated all integrals by expressions of the form

$$\begin{aligned} I = \fancyscript{I}^N + \fancyscript{O}(h^m), \end{aligned}$$

(3.31)

where $I$ is the exact, unknown, value of the integral, $\fancyscript{I}^N$ is the estimate obtained from an integration scheme using $N$ grid-points and $m$ is the leading order of the error. Let us review the error of the trapezoidal approximation: we learned that the error for the integral over the interval $[x_i, x_{i+1}]$ scales like $h^3$. Since we have $N$ such intervals, we conclude that the total error behaves like $(b-a) h^2$. Similarly, the error of the three-point Simpson rule is for each sub-interval proportional to $h^5$ and this gives in total$(b-a) h^4$. We assume that this trend can be generalized and conclude that the error of an $n$-point method with the estimate $\fancyscript{I}_n$ behaves like $h^{2 n - 2}$. Since, $h \propto N^{-1}$ we have

$$\begin{aligned} I = \fancyscript{I}^N_n + \frac{C_N}{N^{2n -2}}, \end{aligned}$$

(3.32)

where $C_N$ depends on the number of grid-points $N$. Let us double the amount of grid-points and we obtain:

$$\begin{aligned} I = \fancyscript{I}^{2N}_n + \frac{C_{2N}}{(2N)^{2n -2}}. \end{aligned}$$

(3.33)

Obviously, Eqs. (3.32) and (3.33) can be regarded as a linear system of equations in $I$ and $C$ if $C_N \approx C_{2N} \approx C$. Solving Eqs. (3.32) and (3.33) for $I$ yields

$$\begin{aligned} I \approx \frac{1}{4^{n-1} - 1} \left( 4^{n-1}\fancyscript{I}_n^{2N} - \fancyscript{I}_n^N \right) . \end{aligned}$$

(3.34)

It has to be emphasized that in the above expression $I$ is no longer the exact value because of the approximation $C_N \approx C$. However, it is an improvement of the solution and it is possible to demonstrate that this new estimate is exactly the value one would have obtained with an integral approximation of order $n+1$ and $2N$ grid-points! Thus

$$\begin{aligned} \fancyscript{I}_{n+1}^{2N} = \frac{1}{4^{n-1} - 1} \left( 4^{n-1}\fancyscript{I}_n^{2N} - \fancyscript{I}_n^N \right) . \end{aligned}$$

(3.35)

Fig. 3.4

Illustration of the Romberg method. Here, the $\fancyscript{I}(m,n)$ are synonyms for integrals $\fancyscript{I}^n_m$ where the first index $m$ refers to the order of the quadrature while the second index $n$ refers to the number of grid-points used. Note that we only have to use a second order integration scheme (left row, inside the box), all other values are determined via Eq. (3.35) as indicated by the arrows

This suggests a very elegant and rapid procedure: We simply calculate the integrals using two point rules and add the results according to Eq. (3.35) to obtain more-point results. For instance, calculate $\fancyscript{I}_2^2$ and $\fancyscript{I}_2^4$, add these according to Eq. (3.35) and get $\fancyscript{I}_3^4$. Now calculate $\fancyscript{I}_2^8$, add $\fancyscript{I}_2^4$, get $\fancyscript{I}_3^8$, add $\fancyscript{I}_3^4$ and get $\fancyscript{I}_4^8$. This pyramid-like procedure can be continued until convergence is achieved, that is $\vert \fancyscript{I}^N_m - \fancyscript{I}^{N}_{m+1} \vert < \varepsilon$ where $\varepsilon > 0$ can be chosen arbitrarily. An illustration of this elegant method is given in Fig. 3.4.

6 Gauss-Legendre Quadrature

In order to prepare for the Gauss-Legendre quadrature we define the function $F(x)$ as

$$\begin{aligned} F(x) = \frac{b - a}{2} f \left( \frac{b-a}{2} x + \frac{b+a}{2} \right) , \end{aligned}$$

(3.36)

such that

$$\begin{aligned} \int \limits _a^b \mathrm {d}x f(x) = \int \limits _{-1}^1 \mathrm {d}x F(x). \end{aligned}$$

(3.37)

Furthermore, let us introduce a set of orthogonal Legendre polynomials $P_\ell (x)$ [1–3] which are solutions of the Legendre differential equation

$$\begin{aligned} \left( 1 - x^2 \right) P_\ell ''(x) - 2 x P_\ell '(x) + \ell (\ell +1) P_\ell (x) = 0. \end{aligned}$$

(3.38)

This equation is, for instance, the result of a transformation of the Laplace equation to spherical coordinates. Here, we will introduce only the most important properties of Legendre polynomials which will be useful for our purpose.

Legendre polynomials are defined as

$$\begin{aligned} P_\ell (x) = \sum _{k = 0}^\infty a_{k,\ell } x^k, \end{aligned}$$

(3.39)

where the coefficients $a_{k,\ell }$ can be determined recursively:

$$\begin{aligned} a_{k+2, \ell } = \frac{k(k+1) - \ell ( \ell +1)}{(k+1)(k+2)} a_{k, \ell }. \end{aligned}$$

(3.40)

Hence, for even values of $\ell$ the Legendre polynomial involves only even powers of $x$ and for odd $\ell$ only odd powers of $x$. Note also that according to Eq. (3.40) for $k \ge \ell$ the coefficients are equal to zero and, thus, the $P_\ell (x)$ are according to Eq. (3.39) polynomials of order $\ell$. Furthermore, the Legendre polynomials fulfill the normalization condition

$$\begin{aligned} \int \limits _{-1}^1 \mathrm {d}x P_\ell (x) P_{\ell '}(x) = \frac{2}{2 \ell ' +1} \delta _{\ell \ell '}, \end{aligned}$$

(3.41)

where $\delta _{ij}$ is Kronecker’s delta. One obtains

$$\begin{aligned} P_0(x) = 1, \end{aligned}$$

(3.42)

and

$$\begin{aligned} P_1(x) = x. \end{aligned}$$

(3.43)

Another convenient description of the Legendre polynomials is based on Rodrigues’ formula

$$\begin{aligned} P_\ell (x) = \frac{1}{2^\ell \ell !} \frac{{\mathrm {d}}^\ell }{{\mathrm {d}}x^\ell } \left( x^2 - 1 \right) ^\ell . \end{aligned}$$

(3.44)

We now assume that the function $F(x)$ can be well approximated by some polynomial of order $2n-1$, i.e.

$$\begin{aligned} F(x) \approx p_{2n - 1}(x). \end{aligned}$$

(3.45)

Please note that this means that according to Eq. ( 2.7) the error introduced is proportional to $F^{(2n)}(x)$.

We write the integral (3.37) as

$$\begin{aligned} \int \limits _{-1}^1 \mathrm {d}x F(x) = \sum _{i = 1}^n \omega _i F(x_i), \end{aligned}$$

(3.46)

with weights$\omega _i$ and grid-points$x_i$, $i = 1, \ldots , n$ which are yet undetermined! Therefore, we will determine the weights $\omega _i$ and grid-points $x_i$ in such a way, that the integral is well approximated even if the polynomial $p_{2n - 1}$ in Eq. (3.45) is unknown. For this purpose we decompose $p_{2n-1}(x)$ into

$$\begin{aligned} p_{2n -1} (x) = p_{n-1}(x) P_n(x) + q_{n-1}(x), \end{aligned}$$

(3.47)

where $P_n(x)$ is the Legendre polynomial of order $n$ and $p_{n-1}(x)$ and $q_{n-1}(x)$ are polynomials of order $n-1$. Since $p_{n-1}(x)$ itself is a polynomial of order $n-1$, it can also be expanded in Legendre polynomials of orders up to $n-1$ by

$$\begin{aligned} p_{n-1}(x) = \sum _{i = 0}^{n-1} a_i P_i(x). \end{aligned}$$

(3.48)

Using Eq. (3.48) in (3.47) we obtain together with normalization relation (3.41)

$$\begin{aligned} \int \limits _{-1}^1 \mathrm {d}x\, p_{2n - 1} (x) = \sum _{i = 0}^{n-1} a_i \int \limits _{-1}^1 \mathrm {d}x P_i(x) P_n(x) + \int \limits _{-1}^1 \mathrm {d}x\, q_{n-1}(x) = \int \limits _{-1}^1 \mathrm {d}x\, q_{n-1}(x). \end{aligned}$$

(3.49)

Moreover, since $P_n(x)$ is a Legendre polynomial of order $n$ it has $n$-zeros in the interval $[-1,1]$ and Eq. (3.47) results in

$$\begin{aligned} p_{2n-1}(x_i) = q_{n-1}(x_i), \end{aligned}$$

(3.50)

where $x_1, x_2, \ldots , x_n$ denote the zeros of $P_n(x)$ and these zeros determine the grid-points of our integration routine. It is interesting to note, that these zeros are independent of the function $F(x)$ we want to integrate. We also expand $q_{n-1}(x)$ in terms of Legendre polynomials

$$\begin{aligned} q_{n-1}(x) = \sum _{i = 0}^{n-1} b_i P_i(x), \end{aligned}$$

(3.51)

and use it in Eq. (3.50) to obtain

$$\begin{aligned} p_{2n-1}(x_i) = \sum _{k = 0}^{n-1} b_k P_k(x_i), \quad i = 1, \ldots , n, \end{aligned}$$

(3.52)

which can be written in a more compact form by defining $p_i \equiv p_{2n-1}(x_i)$ and $P_{ki} \equiv P_k(x_i)$:

$$\begin{aligned} p_i = \sum _{k = 0}^{n-1} b_k P_{ki}, \quad i = 1, \ldots , n. \end{aligned}$$

(3.53)

It has to be emphasized again that the grid-points $x_i$ are independent of the polynomial $p_{2n-1}(x)$ and, therefore, independent of $F(x)$. Furthermore, we can replace $p_i \approx F(x_i) \equiv F_i$ according to Eq. (3.45). We recognize that Eq. (3.53) corresponds to a system of linear equations which can be solved for the weights $b_k$. We obtain

$$\begin{aligned} b_k = \sum _{i = 1}^{n} F_i \left[ \mathbf {P}^{-1} \right] _{ik}, \end{aligned}$$

(3.54)

where $\mathbf {P}$ is the matrix $\mathbf {P} = \{P_{ij} \}$, which is known to be non-singular. We can now rewrite the integral (3.37) with the help of Eqs. (3.45), (3.49), and (3.51) together with the properties of the zeros of Legendre polynomials [3] as

$$\begin{aligned} \int \limits _{-1}^1\! \mathrm {d}x\, F(x) \approx \int \limits _{-1}^1 \mathrm {d}x p_{2n-1}(x) = \sum _{k=0}^{n-1} b_k \int \limits _{-1}^1\! \mathrm {d}x\, P_k(x). \end{aligned}$$

(3.55)

Since $P_0(x) = 1$ according to Eq. (3.42), we deduce from Eq. (3.41)

$$\begin{aligned} \int \limits _{-1}^1 \mathrm {d}x P_k(x) = \int \limits _{-1}^1 \mathrm {d}x P_k(x) P_0(x) = \frac{2}{2k+1} \delta _{k0} = 2 \delta _{k0}. \end{aligned}$$

(3.56)

Hence, Eq. (3.55) reads

$$\begin{aligned} \int \limits _{-1}^1\! \mathrm {d}x\, F(x) \approx 2 b_0 = 2 \sum _{i = 1}^{n} F_i \left[ \mathbf {P}^{-1} \right] _{i0}. \end{aligned}$$

(3.57)

By defining

$$\begin{aligned} \omega _i = 2 \left[ \mathbf {P}^{-1} \right] _{i0}, \end{aligned}$$

(3.58)

we arrive at the desired expansion

$$\begin{aligned} \int \limits _{-1}^1 \mathrm {d}x F(x) \approx \sum _{i = 1}^n \omega _i F_i. \end{aligned}$$

(3.59)

Moreover, since we approximated $F(x)$ by a polynomial of order $2n - 1$, the Gauss-Legendre quadrature is exact for polynomials of order $2n - 1$, i.e., the error is proportional to a derivative of $F(x)$ of order $2n$. Furthermore, expression (3.58) can be put in a more convenient form. One can show that

$$\begin{aligned} \omega _i = \frac{2}{(1-x_i^2) \left[ P_n'(x_i) \right] ^2}, \end{aligned}$$

(3.60)

where

$$\begin{aligned} P_n'(x_i) = \left. \frac{{\mathrm {d}}}{{\mathrm {d}}x} P_n(x) \right| _{x = x_i}. \end{aligned}$$

(3.61)

Let us make some concluding remarks. The grid-points$x_i$ as well as the weights$\omega _i$ are independent of the actual function $F(x)$ we want to integrate. This means, that one can table these values once and for all [3] and use them for different types of problems. The grid-points $x_i$ are symmetrically distributed around the point $x = 0$, i.e. for every $x_j$ there is a $-x_j$. Furthermore, these two grid-points have the same weight $\omega _j$. The density of grid-points increases approaching the boundary, however, the boundary points themselves are not included, which means that the Gauss-Legendre quadrature is an open method. Furthermore, it has to be emphasized that low order Gauss-Legendre parameters can easily be calculated by employing relation (3.44). This makes the Gauss-Legendre quadrature the predominant integration method. In comparison to the trapezoidal rule or even the Romberg method, it needs in many cases a smaller number of grid-points, is simpler to implement, converges faster and yields more accurate results. One drawback of this method is that one has to compute the reduced function $F(x)$ at the zeros of the Legendre polynomial $x_i$. This can be a problem if the integrand at hand is not known analytically.

Table 3.1 Summary of the quadrature methods discussed in this chapter applied to the integral $\int _a^b \mathrm {d}x f(x)$

It is important to note at this point that comparable procedures exist which use other types of orthogonal polynomials, such as Hermite polynomials. This procedure is known as the Gauss-Hermite quadrature.

Table 3.1 lists the methods, discussed in the previous sections, which allow to calculate numerically an estimate of integrals of the form:

$$\begin{aligned} \int \limits _{a}^{b} \mathrm {d}x f(x). \end{aligned}$$

(3.62)

Equal grid-spacing $h$ is assumed, with the Gauss-Legendre method as the only exception. The particular value of $h$ depends on the order of the method employed and is given in Table 3.1.

7 An Example

Let us discuss as an example the following proper integral

$$\begin{aligned} I = \int \limits _{-1}^1 \frac{{\mathrm {d}}x}{x+2} = \ln (3) - \ln (1) \approx 1.09861. \end{aligned}$$

(3.63)

The numerical value was obtained with a TI-30XIIB pocket calculator. We will now apply the various methods of Table 3.1 to solve this problem. Note that these methods could give better results if a finer grid had been chosen. However, since this is only an illustrative example, we wanted to keep it as simple as possible. The rectangular rule gives

$$\begin{aligned} \fancyscript{I}_R = 1 \cdot \frac{1}{2} = 0.5, \end{aligned}$$

(3.64)

the trapezoidal rule

$$\begin{aligned} \fancyscript{I}_T = \frac{2}{2} \left( \frac{1}{1} + \frac{1}{3} \right) = \frac{4}{3} = 1.333\ldots , \end{aligned}$$

(3.65)

and an application of the Simpson rule yields

$$\begin{aligned} \fancyscript{I}_S = \frac{1}{3} \left( \frac{1}{1} + \frac{4}{2} + \frac{1}{3} \right) = \frac{10}{9} = 1.111\ldots . \end{aligned}$$

(3.66)

Finally, we apply the Gauss-Legendre quadrature in a second order approximation. We could look up the parameters in Ref. [3], however, for illustrative reasons we will calculate those in this simple case. For a second order approximation we need the Legendre polynomial of second order. It can be obtained from Rodrigues’ formula (3.44):

$$\begin{aligned} P_2(x)&= \frac{1}{2^2 2!} \frac{{\mathrm {d}}^2}{{\mathrm {d}}x^2} \left( x^2 - 1 \right) ^2 \nonumber \\&= \frac{1}{8} \frac{{\mathrm {d}}}{{\mathrm {d}}x} 4 x (x^2 -1) \nonumber \\&= \frac{1}{2} \left[ (x^2 - 1) + 2 x^2 \right] \nonumber \\&= \frac{1}{2} \left( 3 x^2 -1 \right) . \end{aligned}$$

(3.67)

In a next step the zeros $x_1$ and $x_2$ of $P_2(x)$ are determined from Eq. (3.67) which results immediately in:

$$\begin{aligned} x_{1,2} = \pm \frac{1}{\sqrt{3}} \approx \pm 0.57735. \end{aligned}$$

(3.68)

The weights $\omega _1$ and $\omega _2$ can now be evaluated according to Eq. (3.60):

$$\begin{aligned} \omega _i = \frac{2}{(1-x_i^2) \left[ P_2'(x_i) \right] ^2}. \end{aligned}$$

(3.69)

It follows from Eq. (3.67) that

$$\begin{aligned} P_2'(x) = 3 x, \end{aligned}$$

(3.70)

and, thus,

$$\begin{aligned} P_2'(x_1) = -\sqrt{3} \qquad \text { and }\qquad P_2'(x_2) = \sqrt{3}. \end{aligned}$$

(3.71)

This is used to calculate the weights from Eq. (3.69):

$$\begin{aligned} \omega _1 = \omega _2 = \frac{2}{\left( 1 - \frac{1}{3} \right) \cdot 3} = 1. \end{aligned}$$

(3.72)

We combine the results (3.68) and (3.72) to arrive at the Gauss-Legendre estimate of the integral (3.63):

$$\begin{aligned} \fancyscript{I}_{GL} = \frac{1}{-\frac{1}{\sqrt{3}}+2} + \frac{1}{\frac{1}{\sqrt{3}}+2} = 1.090909\ldots . \end{aligned}$$

(3.73)

Obviously, a second order Gauss-Legendre approximation results already in a much better estimate of the integral (3.63) than the trapezoidal rule which is also of second order. It is also better than the estimate by the Simpson rule which is of third order. Another point which makes the Gauss-Legendre quadrature so attractive from the numerical point of view is the fact that all coefficients in the Gauss-Legendre quadrature are independent of the function one wishes to integrate.

There is a drawback though: it is not easy to apply the Gauss-Legendre algorithm to calculate numerically estimates of integrals over functions $f(x)$ not defined analytically. All other methods listed in Table 3.1 are not restricted at all to an analytic representation of the integrand.

8 Concluding Discussion

Let us briefly discuss some further aspects of numerical integration. In many cases one is confronted with improper integrals of the form

$$\begin{aligned} \int \limits _a^\infty \mathrm {d}x f(x), \qquad \int \limits _{-\infty }^a \mathrm {d}x f(x), \quad \text { or }\qquad \int \limits _{-\infty }^\infty \mathrm {d}x f(x). \end{aligned}$$

(3.74)

The question arises whether or not we can treat such an integral with the methods discussed so far. The answer is yes, it is possible as we will demonstrate using the integral

$$\begin{aligned} I = \int \limits _a^\infty \mathrm {d}x f(x). \end{aligned}$$

(3.75)

as an example; other integrals can be treated in a similar fashion. We rewrite Eq. (3.75) as

$$\begin{aligned} I = \lim _{b \rightarrow \infty } \int \limits _a^b \mathrm {d}x f(x) = \lim _{b \rightarrow \infty } I(b). \end{aligned}$$

(3.76)

One now calculates $I(b_1)$ for some $b_1 > a$ and $I(b_2)$ for some $b_2 > b_1$. If $\vert I(b_2) - I(b_1) \vert < \varepsilon$, where $\varepsilon > 0$ is the required accuracy, the resulting value $I(b_2)$ can be regarded as the appropriate estimate to $I$.¹ However, in many cases it is easier to perform an integral transform in order to map the infinite interval onto a finite interval. For instance, consider [4]

$$\begin{aligned} I = \int \limits _0^\infty \mathrm {d}x\frac{1}{\left( 1+ x^2 \right) ^{\frac{4}{3}}}. \end{aligned}$$

(3.77)

The transformation

$$\begin{aligned} t = \frac{1}{1+x} \end{aligned}$$

(3.78)

gives

$$\begin{aligned} I = \int \limits _0^1 \mathrm d t \frac{t^{\frac{2}{3}}}{\left[ t^2 + (1 - t)^2 \right] ^{\frac{4}{3}}}. \end{aligned}$$

(3.79)

Thus, we mapped the interval $[0,\infty ) \rightarrow [0,1]$. Integral (3.79) can now be approximated with help of the methods discussed in the previous sections. These can also be applied to approximate convergent integrals whose integrand shows singular behavior within $[a,b]$.

An interesting situation arises when the integrand $f(x)$ is not smooth within the interval $I : x\in [a,b]$. Nevertheless, it will be safe to assume that $f(x)$ will at least be piecewise smooth within this interval. In this case the total integral is split into a sum over sub-intervals within which $f(x)$ is smooth. Let us, for instance, regard the function

$$\begin{aligned} f(x) = \left\{ \begin{array}{ll} x\,\cos (x),\quad x < 0,\\ x\,\sin (x),\quad x \ge 0, \end{array} \right. \end{aligned}$$

and calculate the integral over the interval $I : x\in [-10,10]$ as

$$\begin{aligned} \int \limits _{-10}^{10}\!\mathrm{d}x\,f(x) = \int \limits _{-10}^0\!\mathrm{d}x\,x\cos (x)+ \int \limits _0^{10}\!\mathrm{d}x\,x\sin (x). \end{aligned}$$

We generalize this result and write

$$\begin{aligned} \int \limits _I\!\mathrm{d}x\,f(x) = \sum _k\int \limits _{I_k}\!\mathrm{d}x\,f(x), \end{aligned}$$

(3.80)

with sub-intervals $I_k\in I,\forall k$ and the integrand $f(x)$ is assumed to be smooth within each sub-interval $I_k$ but not necessarily within the interval $I$. We can then apply one of the methods discussed in this chapter to calculate an estimate of the integral over any of the sub-intervals $I_k$.

Another interesting question is whether or not we can also evaluate multiple integrals with the help of the above formalisms. Again, the answer is yes. Similar to the discussion in Sect. 2.5 about the approximation of partial derivatives on the basis of finite differences, one can apply the rules of quadrature developed here for different dimensions to obtain an estimate of the desired integral. However, the complexity of the problem is significantly increased if the integration boundaries are functions of the variables rather than constants. For instance,

$$\begin{aligned} \int \limits _a^b \mathrm {d}x \int \limits _{\phi _1(x)}^{\phi _2(x)} \mathrm d y f(x,y). \end{aligned}$$

(3.81)

Such cases are rather difficult to handle and the method to choose depends highly on the form of the functions $\phi _1(x)$, $\phi _2(x)$ and $f(x,y)$. We will not deal with integrals of this kind because this is beyond the scope of this book. The interested reader is referred to books by Dahlquist and Björk [5] and by Press et al. [6].

Summary The starting point was the concept of finite differences (Sect. 2.2). Based on this concept proper integrals over smooth functions $f(x)$ have been approximated by a sum over elemental areas with the elemental area defined as the area under $f(x)$ between two consecutive grid-points. The simplest method, the rectangular rule, was based on forward/backward differences. It is a closed method, i.e. the functional values at the boundaries are included. On the other hand, a rectangular rule based on central differences is an open method, i.e. the functional values at the boundaries are not included. Using the Taylor expansion (2.7) revealed that the methodological error of the rectangular rule was of order $\fancyscript{O}(h^2)$. With the elemental area approximated by a trapezoid we arrived at the trapezoidal rule. It is a closed method and the methodological error is of order $\fancyscript{O}(h^3)$. If higher order derivatives of $f(x)$ are included the Simpson rules of quadrature are derived. They allowed a remarkable reduction of the methodological error. A more general formulation of all these methods was based on the interpolation of the function $f(x)$ using Lagrange interpolating polynomials of order $n$ and resulted in the class of Newton-Cotes rules. For various orders of $n$ of the interpolating polynomial all the above rules have been derived. Within this context a particularly useful method, the Romberg method, was discussed. By adding diligently only two-point rules the error of the numerical estimate of the integral has been made arbitrarily small. An even more general approach was offered by the Gauss-Legendre quadrature which used Legendre polynomials of order $\ell$ to approximate the function $f(x)$. The grid-points were defined by the zeros of the $\ell$-th order polynomial and the weights $\omega _i$ in Eq. (3.1) were proportional to the square of the inverse first derivative of the polynomial. This method had the enormous advantage that the grid-points and weights were independent of the function $f(x)$ and, thus, can be determined once and for all for any polynomial order $\ell$. Error analysis proved that this method had the smallest methodological error.

Problems We consider the interval $I = [-5,5]$ together with the functions $g(x)$ and $h(x)$:

$$\begin{aligned} g(x) = \exp \left( - x^2 \right) \quad \text { and } \quad h(x) = \sin (x). \end{aligned}$$

We discretize the interval $I$ by introducing $N$ equally spaced grid-points. The corresponding $N-1$ sub-intervals are denoted by $I_j$, $j = 1, \ldots N-1$. In the following we wish to calculate estimates of the integrals

$$\begin{aligned} \fancyscript{I}_1 = \int \limits _I\! \mathrm {d}x\, g(x) \qquad \text { and } \qquad \fancyscript{I}_2 = \int \limits _I\! \mathrm {d}x\, h(x). \end{aligned}$$

Furthermore, we add a third integral of the form

$$\begin{aligned} \fancyscript{I}_3 = \int \limits _I\! \mathrm {d}x\, h^2(x) = \int \limits _I\! \mathrm {d}x\, \sin ^2 (x), \end{aligned}$$

to our discussion.

• 1. Evaluate $\fancyscript{I}_1$ with the help of the error function $\mathrm{erf}(x)$, which should be supplied by the environment you use as an intrinsic function. Note that the error function is defined as

  $$\begin{aligned} \mathrm{erf}(x) = \frac{2}{\sqrt{\pi }} \int \limits _{0}^x \mathrm d z \exp ( - z^2 ). \end{aligned}$$

  (3.82)

  Hence you should be able to express $\fancyscript{I}_1$ in terms of $\mathrm{erf}(x)$.

• 2. Calculate $\fancyscript{I}_2$ and $\fancyscript{I}_3$ analytically.

• 3. In order to approximate $\fancyscript{I}_1$, $\fancyscript{I}_2$ and $\fancyscript{I}_3$ with the help of the two second order methods we discussed in this chapter, employ the following strategy: First the integrals are rewritten as

  $$\begin{aligned} \int \limits _I \mathrm {d} x ~ \cdot = \sum _i \int \limits _{I_i} \mathrm {d}x ~ \cdot \;, \end{aligned}$$

  where $\cdot$ is a placeholder for $g(x)$, $h(x)$ and $h^2(x)$. In a second step the integrals are approximated by

  $$\begin{aligned} \int \limits _{I_i} \mathrm {d}x ~ \cdot , \qquad i = 1, \ldots , N-1\;, \end{aligned}$$

  with (i) the central rectangular rule and (ii) the trapezoidal rule.

• 4. In addition, we approximate the integrals $\fancyscript{I}_1$, $\fancyscript{I}_2$ and $\fancyscript{I}_3$ by employing Simpson’s rule for odd $N$. Here

  $$\begin{aligned} \int \limits _I\! \mathrm {d}x ~ \cdot = \int \limits _{I_1 \cup I_2} \mathrm {d}x ~ \cdot + \int \limits _{I_3 \cup I_4} \mathrm {d}x ~ \cdot + \cdots + \int \limits _{I_{N-2} \cup I_{N-1}} \mathrm {d}x ~\cdot \;, \end{aligned}$$

  is used as it was discussed in Sect. 3.4.

• 5. Compare the results obtained with different algorithms and different numbers of grid-points, $N$. Plot the absolute- and the relative error as a function of $N$.