Composite Numerical Integration

Newton-Cotes formulas are unsuitable for large integration intervals. Instead we use the idea of approximating the integrand with piece-wise polynomial functions. We split up the integral domain into $m$ equal parts, as in Figure 46.

Figure 46: Composite integration methods split the total integration domain into smaller parts.

$$\int^b_a f(x)dx=\int^{a_1}_{a_0=a}f(x)dx+\int^{a_2}_{a_1} f(x)dx+\int^{a_3}_{a_2} f(x)dx+\cdots+\int^{a_n=b}_{a_{n-1}}f(x)dx$$

with $a_i=a+i(b-a)/m$ do each one separately. Each integral is then evaluated using a Newton-Cotes formula such as the trapezoid rule or Simpson's rule. In the case of Simpson's rule This involves evaluating $f(x)$ at the midpoint of each subinterval. The points where $x$ must be evaluated for the composite form of Simpson's rule are $x_j=a+jh$ with $h=(b-a)/n$ and $n=2m$. The resulting formula is:

$$\begin{eqnarray*}\int_a^b f(x)\, dx=\frac{h}{6}(&f(x_0)&+4f(x_1)+2f(x_2)+4f(x_3)... ...{n-1})+f(x_n)) -\frac{h^5}{90}\sum_{i=0}^{n/2-1}f^{(iv)}(\xi_i) \end{eqnarray*}$$

Using the weighted mean value theorem it is straightforward to replace the error term with a single term

$$\begin{eqnarray*} \int_a^b f(x)\, dx=\frac{h}{6}(&f(x_0)&+4f(x_1)+2f(x_2)+4f(x_... ...s\\ &&+4f(x_{n-1})+f(x_n)) -\frac{nh^5}{2\cdot 90}f^{(iv)}(\xi) \end{eqnarray*}$$

and since $h=(b-a)/n$ this can be written as

$$\int_a^b f(x)\, dx=\frac{h}{6}( f(x_0) +4f(x_1)+2f(x_2)+4f(x_3)+2f(x_4) +\cdots$$

$$+4f(x_{n-1})+f(x_n)) -\frac{h^4 (b-a)}{180}f^{(iv)}(\xi)$$ (48)

Notice that in going from Simpson's to composite Simpson's rule, the error went from being $O(h^5)$ to $O(h^4)$ Also for this rule $n$ must be even.

A similar, but simpler argument (in this case $m=n$, and n can be any positive number)

using the trapezoid rule yields

$$\int_a^b f(x)\, dx=\frac{h}{2}( f(x_0) +2f(x_1)+2f(x_2)+2f(x_3)+2f(x_4) +\cdots$$

$$+2f(x_{n-1})+f(x_n)) -\frac{h^2 (b-a)}{12}f''(\xi)$$ (49)

Example: Lets look at using the composite method for evaluating the integral

$$\int_0^5 \mbox{e}^x dx.$$

We know that the actual value of this integral is $\mbox{e}^5-\mbox{e}^0=147.4132$. First we will use the trapezoidal rule and look at how the error decreases as we increase the number of intervals, $n$, we use. Then we will use Simpson's rule for the integration and again look at how the error changes as we increase $n$.

Figure 47 shows the function plotted against the two trapezoids that the trapezoidal rule would use to approximate the integral for $n=2$. As you can see this approximation overestimates the area under $\mbox{e}^x$ considerably. The table below gives the error as $69.8$. But the table also shows that as we increase the number of intervals the error decreases significantly. We can also see this in the log-log plot of $n$ versus |$Error$| shown in figure 48. Because this error line is a straight line there is a power law relating $n$ to |$Error$|. If we look at the table and compare the errors for $n=10, 100$ and $1000$ we can see that as $n$ increases by ten the error decreases by approximately 100. Thus we can say that

$$Error(n) \approx C n^2$$

for some constant $C$.

Figure: Plot of the function $f(x)=\mbox{e}^x$ over the interval of integration along with the trapezoidal approximation for $n=2$

Figure: Log-log plot showing the absolute error of the Trapezoidal rule numerical integration of $\int_0^5 \mbox{e}^x dx$ for different numbers of intevals $n$.

$n$	Approximate Integral	Absolute Error
$1$	$373.5329$	$226.12$
$2$	$217.2227$	$69.810$
$5$	$159.4976$	$12.084$
$10$	$150.4715$	$3.0584$
$20$	$148.1801$	$0.76698$
$50$	$147.5360$	$0.12282$
$100$	$147.4439$	$3.0710\times 10^{-02}$
$200$	$147.4208$	$7.6777\times 10^{-03}$
$500$	$147.4144$	$1.2284\times 10^{-03}$
$1000$	$147.4135$	$3.0711\times 10^{-04}$

We can also use Simpson's rule to estimate the integral. Simpson's Rule requires an even number of intervals. Figure 49 shows $f(x)=\mbox{e}^x$ and the polynomial used by the Simpson's rule to approximate $f(x)$ for $n=2$. This polynomial underestimates $f(x)$ for the first interval and overestimates $f(x)$ for the second interval. The table of errors below shows that the error for $n=2$, Simpson's Rule is much less than for the Trapezoidal Rule with the same number of intervals. The table below shows the absolute error for $n$ going from two to two thousand. Figure 50 also shows this graphically on a log-log plot. Again we have a power law relationship between $n$ and |$Error$| but in this case it is

$$Error(n) \approx C n^4$$

for some constant $C$. So not only is the error less for $n=2$ but the rate that the error decreases as $n$ increases is considerably greater. For $n=1000$ we have an error of $5.1187\times 10^{-10}$ compared with an error of $3.0711\times 10^{-04}$ for the trapezoidal rule.

Figure: Plot of the function $f(x)=\mbox{e}^x$ over the interval of integration along with the Simpson's Rule approximation for $n=2$

Figure: Log-log plot showing the absolute error of Simpson's rule numerical integration of $\int_0^5 \mbox{e}^x dx$ for different numbers of intervals $n$.

$n$	Approximate integral	Absolute Error
$2$	$165.1193$	$17.706$
$4$	$149.0933$	$1.6801$
$10$	$147.4629$	$4.9701\times 10^{-02}$
$20$	$147.4163$	$3.1754\times 10^{-03}$
$40$	$147.4134$	$1.9957\times 10^{-04}$
$100$	$147.4132$	$5.1170\times 10^{-06}$
$200$	$147.4132$	$3.1988\times 10^{-07}$
$400$	$147.4132$	$1.9994\times 10^{-08}$
$1000$	$147.4132$	$5.1187\times 10^{-10}$
$2000$	$147.4132$	$3.1974\times 10^{-11}$