Trapezoidal rule in Python

Question

I'm trying to implement the trapezoidal rule in Python 2.7.2. I've written the following function:

def trapezoidal(f, a, b, n):
    h = float(b - a) / n
    s = 0.0
    s += h * f(a)
    for i in range(1, n):
        s += 2.0 * h * f(a + i*h)
    s += h * f(b)
    return s

However, f(lambda x:x**2, 5, 10, 100) returns 583.333 (it's supposed to return 291.667), so clearly there is something wrong with my script. I can't spot it though.

Answer 1

You are off by a factor of two. Indeed, the Trapezoidal Rule as taught in math class would use an increment like

s += h * (f(a + i*h) + f(a + (i-1)*h))/2.0

(f(a + i*h) + f(a + (i-1)*h))/2.0 is averaging the height of the function at two adjacent points on the grid.

Since every two adjacent trapezoids have a common edge, the formula above requires evaluating the function twice as often as necessary.

A more efficient implementation (closer to what you posted), would combine common terms from adjacent iterations of the for-loop:

f(a + i*h)/2.0 + f(a + i*h)/2.0 =  f(a + i*h) 

to arrive at:

def trapezoidal(f, a, b, n):
    h = float(b - a) / n
    s = 0.0
    s += f(a)/2.0
    for i in range(1, n):
        s += f(a + i*h)
    s += f(b)/2.0
    return s * h

print( trapezoidal(lambda x:x**2, 5, 10, 100))

which yields

291.66875

Answer 2

The trapezoidal rule has a big /2 fraction (each term is (f(i) + f(i+1))/2, not f(i) + f(i+1)), which you've left out of your code.

You've used the common optimization that treats the first and last pair specially so you can use 2 * f(i) instead of calculating f(i) twice (once as f(j+1) and once as f(i)), so you have to add the / 2 to the loop step and to the special first and last steps:

s += h * f(a) / 2.0
for i in range(1, n):
    s += 2.0 * h * f(a + i*h) / 2.0
s += h * f(b) / 2.0

You can obviously simplify the loop step by replacing the 2.0 * … / 2.0 with just ….

However, even more simply, you can just divide the whole thing by 2 at the end, changing nothing but this line:

return s / 2.0