18. Definite Integrals, Part 2: The Composite Trapezoid and Midpoint Rules¶

Expanded on Monday, March 8, adding an Appendix on the Composite Left-hand Endpoint Rule

References:

Section 5.2.4 Open Newton-Cotes Methods in Sauer
Section 4.4 Composite Numerical Integration of Burden&Faires

18.1. Introduction¶

The “elementary” integral approximations of the definite integral

\[I = \int_a^b f(x) \, dx\]

seen in the previous section the Trapzoid Rule

\[T_1 = \int_a^b L(x) \, dx = \frac{f(a) + f(b)}{2} (b-a) \]

and the Midpoint Rule

\[M_1 = f \left(\frac{a+b}{2}\right)(b-a)\]

are of course of very low accuracy in themselves. They are however central building blocks for various more accurate methods and also for some good methods for numerical solution of differential equations.

The basic strategy for improving accurcy is to derive the domain of integration \([a, b]\) into numerous smaller intervals, and use these rls on each such sub-interval teh composite rules.

In turn, the most straightforward way to do this is to use \(n\) sub-intervals of equal width \(h = (b-a)/n\), so that the sub-interval endpoints are \(x_0 = a + ih\), \(0 \leq i \leq n\): that is

sub-intervals \([x_{i-1}, x_i]\), \(1 \leq i \leq n\) separated by the nodes.

\[a, a+h, a+2h, \dots, b-h, b\]

18.1.1. The Composite Midpoint Rule¶

Using the Midpoint Rule on each interval and summing gives a formula that could be familiar:

\[\begin{split} \begin{split} M_n &:= f \left( \frac{x_0+x_1}{2}\right)h + f \left(\frac{x_1+x_2}{2}\right)h + \cdots + f \left( \frac{x_{n-1}+x_n}{2}\right)h \\ &= f \left(\frac{a+(a+h)}{2}\right)h + f \left(\frac{(a+h) + (a+2h)}{2}\right)h + \cdots + f \left(\frac{(b-h)+b}{2}\right)h \\ &= \left[ f(a+h/2) + f(a+3h/2) + \cdots + f(b-h/2) \right] h \end{split} \end{split}\]

This is a Riemann Sum as used in the definition of the defnite integral; possibly the best and natural one in most situations, by using the midpoints of each interval. The theory of definite integrals also guarantees that \(M_n \to I\) as \(n \to \infty\) so long as the function \(f\) is continuous — the next question for us will be “how fast?

18.1.2. The Composite Trapezoid Rule¶

Using the Trapezoid Rule on each interval instead gives

\[\begin{split} \begin{split} T_n &:= \frac{f(x_0) + f(x_1)}{2} h + \frac{f(x_1) + f(x_2)}{2} h + \cdots + \frac{f(x_{n-1}) + f(x_n)}{2} h \\ &:= \frac{f(a + f(a+h)}{2} h + \frac{f(a+h + f(a+2h)}{2} h + \cdots + \frac{f(b-h) + f(b)}{2} h \\ &= \left[ \frac{f(a)}{2} + f(a+h) + f(a+2h) + \cdots + f(b-h) + \frac{f(b)}{2} \right] h \end{split} \end{split}\]

This is also a Riemann sum, with intervals if length \(h/2\) at each end, using value at teh ends of thos intervals, and the rest of width \(h\), with the Midpoint Rule used. So again, we know that \(T_n \to I\) as \(n \to \infty\) and next want to know “how fast?*

18.1.3. Accuracy and Error Formulas¶

In brief, the errors for ech of rhese rules is the sum of the errors for each of the pieces; I will just state them for now.

Firstly,

\[ I - M_n= \sum_{i=1}^n \frac{h^3}{24}f''(\xi_i), \quad \text{ for some } \xi_i \in [x_{i-1}, x_i] \]

This can be rewitten as

\[ I - M_n= \frac{h^3}{24} \sum_{i=1}^n f''(\xi_i) \]

and as we will see, this sum can have each \(f''(\xi_i)\) replace by an “average value” \(f''(\xi_i)\), \(\xi \in[a, b]\):

\[ I - M_n= \frac{h^3}{24} \sum_{i=1}^n f''(\xi) = \frac{h^3}{24} n f''(\xi) = \frac{h^2}{24} (b-a) f''(\xi) \]

and the most important conclusion for now is that

\[ I - M_n = O(h^2) \]

Similarly,

\[ I - T_n = - \frac{h^2}{12} (b-a) f''(\xi) = O(h^2) \]

again with \(\xi \in[a, b]\), but note well: these two \(\xi\) values are probably not the same!

18.2. Cancelling Some Error Terms: The Composite Simpson’s Rule¶

Ignoring the \(\xi\) values being different, this suggests again that we can cancel some of the errors wi ha weighted average:

\[ S_{2n} := \frac{2M_n + T_n}{3} \]

Indeed we will see that the main, \(O(h^2)\), errors cancel out, and also due to symmetry, the error is even in \(h\), so that

\[I - S_{2n}= O(h^4)\]

The name is because this is the Composite Simpson’s Rule, and the interleaving of the different \(x\) values used by \(M_n\) and \(T_n\) means that is uses \(2n+1\) nodes, and so \(2n\) sub-intervals.

18.2.1. The Missing Step: A Generalized Mean Value Theorem¶

A key step in getting more useful error formulas for approximations of integrals is the following result:

Theorem

For any continuous function \(f\) on an interval \([a, b]\) and any collection of points \(x_i \in [a,b]\), \(1 \leq i \leq n\), there is a point \(\xi \in [a,b]\) for which

\[ f(c) = \frac{\sum_{i=1}^n f(x_i)}{n}, \text{ so } \sum_{i=1}^n f(x_i) = n f(c) \]

That is, the value of the function at \(c\) is the average of its values at those other points.

Proof:

The proof is rather similar to that of Theorme 3 in th previos section; essenrial repaltin teh interal tehr by a sum here:

As \(f\) is continuous on the closed, bounded interval \([a, b]\), the Extreme Value Theorem from calculus says that \(f\) has a minimum \(L\) and a maximum \(H\) on this interval. Each of the values \(f(x_i)\) is in interval \([L, H]\) so their average is also:

\[ f(x_i) \in [L, H] \quad \text{and thus} \quad \frac{\sum_{i=1}^n f(x_i)}{n} \in [L, H] \]

The Mean Value Theorem then says that \(f\) attains this mean value for some \(\xi \in [L, H]\).

18.2.2. Completing the derivation of the error formulas for these composite rules¶

I will spell this out for the Composite Trapezoid Rule; it works very similarly for the “midpoint” case.

First, break the exact integral up as

\[ I = \int_a^b f(x) \, dx = \sum_{i=1}^n I^{(i)}, \quad \text{where} \quad I^{(i)} = \int_{x_{i-1}}^{x_i} f(x) \, dx \]

Similarly,

\[ T_n = \sum_{i=1}^n T^{(i)} \]

where each \(T^{(i)}\) is the Trapezoid Rule approximation of \(I^{(i)}\):

\[T^{(i)} = \frac{f(x_{i-1}) + f(x_i)}{2} h\]

The error in \(T_n\) is the sum of the errors in each piece:

\[\begin{split} \begin{split} I - T_n &= \sum_{i=1}^n I^{(i)} - \sum_{i=1}^n T^{(i)} \\&= \sum_{i=1}^n ( I^{(i)} - T^{(i)} ) \\&= \sum_{i=1}^n -\frac{h^3}{12} f''(\xi_i), \quad x_i \in [x_{i-1}, x_i] \\&= -\frac{h^3}{12} \sum_{i=1}^n f''(\xi_i) \end{split} \end{split}\]

Now we can use the above mean value result (with \(f''\) in place of \(f\)) to replace the last sum above by \(n f''(\xi)\), some \(\xi \in [a, b]\), so that as claimed,

\[I - T_n = -\frac{h^3}{12} n f''(\xi), = -\frac{h^2}{12} (b-a) f''(\xi) = O(h^2),\]

using \(h n = b-a\).

18.2.3. Another error formula, useful for Richardson Extrapolation¶

Starting from

\[ I - T_n = -\frac{h^3}{12} \sum_{i=1}^n f''(\xi_i), = -\frac{h^2}{12} \sum_{i=1}^n ( f''(\xi_i) h) \]

note that the sum in the second version is a Riemann sum for approximating the integral

\[I'' := \int_a^b f''(x) \, dx, = [f'(x)]_a^b = f'(b) - f'(a),\]

so it seems that

\[ I - T_n \approx -\frac{f'(b) - f'(a)}{12} h^2, = O(h^2) \]

A virtue of this form is that now we have a good chance of evaluating the coefficient of \(h^2\), so this given a “practical error formula” when \(f'(x)\) is known.

Another useful fact (not proven in these notes) is that the error for the basic Trapezoid rule can be computed with the help of Taylor’s Theorem in a series:

\[ T_1 = \int_a^b f(x) \, dx = B_2 D^2f(\xi_2) h^3 + B_4 D^4(\xi_4) h^5 + \cdots \]

(where \(B_2 = 1/12\) as seen above).

Putting the higher power terms into the above argument one can get

\[\begin{split} \begin{split} T_n &= \int_a^b f(x) \, dx + B_2 [Df(b) - Df(a)] h^2 + B_4 [D^3f(b) - D^3f(a)] h^4 + \cdots + B_{2k} [D^{2k-1}f(b) - D^{2k-1}f(a)] h^{2k} + \cdots \\&= O(h^2) + O(h^4) + \cdots + O(h^{2k}) \end{split} \end{split}\]

so that

\[ T_n = \int_a^b f(x) \,dx + \frac{Df(b) - Df(a)}{12} h^2 + O(h^4) \]

The last form is the setup for Richardson extrapolation — and the previous one with a succession of “big-O” terms is the setup for repeated Richardson extrapolation, to get a succession of approximations with errors \(O(h^2)\), then \(O(h^4)\), then \(O(h^6)\), and so on: Romberg Integration.

There are similar formulas for the Composite Midpoint Rule, like

\[ I - M_n = \frac{h^2}{24} (b-a) f''(\xi) = \frac{Df(b) - Df(a)}{24} h^2 + O(h^4) \]

but we will see why the Composite Trapezoid Rule is far more useful for Richardson extrapolation.

18.3. Appendix: The Composite Left-hand Endpoint Rule, and its Error¶

The Composite Left-hand Endpoint Rule with \(n\) sub-intervals of equal width \(h = (b-a)/n\) is

\[L_n = \sum_{i=0}^{n-1} f(x_i) h, \; = \sum_{i=0}^{n-1} f(a + i h) h\]

To study its errors, start as with the Compound Trapezoid Rule: break the integral up as

\[ I = \int_a^b f(x) \, dx = \sum_{i=1}^n I^{(i)}, \quad \text{where} \quad I^{(i)} = \int_{x_{i-1}}^{x_i} f(x) \, dx \]

and the approximation as

\[ L_n = \sum_{i=1}^n L^{(i)} \]

where each \(L^{(i)}\) is the Left-hand Endpoint Rule approximation of \(I^{(i)}\):

\[L^{(i)} = f(x_{i-1}) h\]

Then the error in \(L_n\) is again the sum of the errors in each piece:

\[\begin{split} \begin{split} I - L_n &= \sum_{i=1}^n I^{(i)} - \sum_{i=1}^n L^{(i)} \\&= \sum_{i=1}^n ( I^{(i)} - L^{(i)} ) \\&= \sum_{i=1}^n \frac{h^2}{2} f'(\xi_i), \quad x_i \in [x_{i-1}, x_i] \\&= \frac{h^2}{2} \sum_{i=1}^n f'(\xi_i) \end{split} \end{split}\]

The Generalized Mean Value Theorem — now with \(f'\) in place of \(f\) — allows us to replace the last sum above by \(n f'(\xi)\), some \(\xi \in [a, b]\), so that as claimed,

\[I - L_n = \frac{h^2}{2} n f'(\xi), = \frac{h}{2} (b-a) f'(\xi) = O(h)\]

Aside: As with the Composite Trapezoid Rule, one can also get

\[ L_n = \int_a^b f(x) \,dx + \frac{f(b) - f(a)}{2} h + O(h^2) \]

This work is licensed under Creative Commons Attribution-ShareAlike 4.0 International

MATH 375. Elementary Numerical Analysis (with Python)