Evaluating a definite integral¶

From your calculus class [Stewart] you learned about integrals and their valuable role in many applications. Computing the exact value of an integral can be very difficult, hence many numerical techniques have been developed to compute high quality approximations. This module focuses on a straight forward quadrature method, the Trapezoidal Rule.

Intuitively, the integral of a function $$f(x)$$ over an interval $$[a,b]$$ corresponds to the area between the curve and the x-axis. However, remember that this is not correct, since the area can be negative. In the discussion that follows, the word area is used loosely. Properly area must be a non-negative number. However, we will refer to the area between a curve and x-axis, but is important to understand this area can be negative. Please examine the figure below to clarify this idea for yourself.

Area between the curve $$f(x)$$ and the x-axis over $$[-1.0,1.3]$$

Next, we will quickly review the mathematical idea of the Trapezoidal Rule, as which you have seen previously in a calculus class. In the next unit, we will discuss a simple sequential algorithm [CLR], along with its implementation in C++. Finally in another unit, we will develop a parallel algorithm.

Trapezoidal Rule¶

The basic idea is to approximate the value of the integral $$\int_{a}^{b}f(x)dx$$ by approximating the area under the curve $$f(x)$$ by adding up the areas of a number of trapezoids. Consider the trapezoid based over the interval $$[x_{i-1},x_{i}]$$ whose area is $$\frac{x_{i}-x_{i-1}}{2}\left(f(x_{i})+f(x_{i-1})\right)$$.

Approximation by area of a trapezoid

Let us subdivide $$[a,b]$$ into n intervals, $$[x_{i-1},x_{i}]$$, each of the same length, $$\Delta x = x_{i}-x_{i-1}$$. For the interval $$[x_{i-1},x_{i}]$$ the integral over it can be approximated by the area of the trapezoid determined by the four points: $$(x_{i-1},0)$$, $$(x_{i-1},f(x_{i-1}))$$, $$(x_{i},0)$$, and $$(x_{i},f(x_{i}))$$:

$\int_{x_{i-1}}^{x_{i}}f(x)dx \approx \frac{x_{i}-x_{i-1}}{2}\left(f(x_{i})+f(x_{i-1})\right)$

giving the Trapezoidal Rule for the approximation of the integral

$\begin{split}\int_{a}^{b}f(x)dx &= \sum_{i=1}^{n}\int_{x_{i-1}}^{x_{i}}f(x)dx \\ &\approx \sum_{i=1}^{n}\frac{x_{i}-x_{i-1}}{2}\left(f(x_{i})+f(x_{i-1})\right) \\ &= \frac{\Delta x}{2} \sum_{i=1}^{n}\left(f(x_{i})+f(x_{i-1})\right) \\ &= \frac{\Delta x}{2} \left[ f(x_{0}) + 2f(x_{1}) + \ldots + 2f(x_{n-1})+ f(x_{n}) \right] \\ &= \frac{\Delta x}{2} \left[ f(a) + 2 \sum_{i=1}^{n-1}f(x_{i}) + f(b) \right] \\ &= \frac{\Delta x}{2} \sum_{i=0}^{n-1} \left(f(x_{i}) + f(x_{i+1}) \right)\end{split}$

These last two expressions provide simple algorithmic strategies for computing an integral. Essentially, it is only necessary to compute the sum of a number of $$f(x_{i})$$ values.

Questions¶

1. In your calculus class, how was the idea of area formalized to make the definition of integral?
2. Make sure you understand each step of the derivation of the Trapezoidal Rule.
3. Why is the last expression shown so significant?
4. In the final steps of the derivation of the Trapezoidal Rule, in order to replace the $$\approx$$ with an $$=$$, what mathematically must be done?
5. If the lengths of the subintervals are not constant, what form does the Trapezoidal Rule take. Computationally, is this form significantly more complicated that the one we derived? Justify.

References¶

 [CLR] Cormen, Lieserson, and Rivest, Algorithms.
 [Stewart] Stewart, Calculus.

Table Of Contents

Module Goal

Next topic

Sequential Algorithm