The trapezoidal method of integration
Posted February 23, 2013 at 09:00 AM | categories: integration, math | tags:
Updated February 27, 2013 at 02:54 PM
Matlab post See http://en.wikipedia.org/wiki/Trapezoidal_rule
$$\int_a^b f(x) dx \approx \frac{1}{2}\displaystyle\sum\limits_{k=1}^N(x_{k+1}-x_k)(f(x_{k+1}) + f(x_k))$$
Let us compute the integral of sin(x) from x=0 to \(\pi\). To approximate the integral, we need to divide the interval from \(a\) to \(b\) into \(N\) intervals. The analytical answer is 2.0.
We will use this example to illustrate the difference in performance between loops and vectorized operations in python.
import numpy as np import time a = 0.0; b = np.pi; N = 1000; # this is the number of intervals h = (b - a)/N; # this is the width of each interval x = np.linspace(a, b, N) y = np.sin(x); # the sin function is already vectorized t0 = time.time() f = 0.0 for k in range(len(x) - 1): f += 0.5 * ((x[k+1] - x[k]) * (y[k+1] + y[k])) tf = time.time() - t0 print 'time elapsed = {0} sec'.format(tf) print f
>>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> ... ... >>> >>> time elapsed = 0.0780000686646 sec >>> 1.99999835177
t0 = time.time() Xk = x[1:-1] - x[0:-2] # vectorized version of (x[k+1] - x[k]) Yk = y[1:-1] + y[0:-2] # vectorized version of (y[k+1] + y[k]) f = 0.5 * np.sum(Xk * Yk) # vectorized version of the loop above tf = time.time() - t0 print 'time elapsed = {0} sec'.format(tf) print f
>>> >>> >>> >>> >>> time elapsed = 0.077999830246 sec >>> 1.99999340709
In the last example, there may be loop buried in the sum command. Let us do one final method, using linear algebra, in a single line. The key to understanding this is to recognize the sum is just the result of a dot product of the x differences and y sums.
t0 = time.time() f = 0.5 * np.dot(Xk, Yk) tf = time.time() - t0 print 'time elapsed = {0} sec'.format(tf) print f
>>> >>> time elapsed = 0.0310001373291 sec >>> 1.99999340709
The loop method is straightforward to code, and looks alot like the formula that defines the trapezoid method. the vectorized methods are not as easy to read, and take fewer lines of code to write. However, the vectorized methods are much faster than the loop, so the loss of readability could be worth it for very large problems.
The times here are considerably slower than in Matlab. I am not sure if that is a totally fair comparison. Here I am running python through emacs, which may result in slower performance. I also used a very crude way of timing the performance which lumps some system performance in too.
Copyright (C) 2013 by John Kitchin. See the License for information about copying.