7.4 The Bisection Method
191
The sketched strategy seems reasonable, so let us write a reusable function that
can solve a general algebraic equation f (x) = 0 (bisection_method.py):
import sys
def bisection(f, x_L, x_R, eps):
f_L = f(x_L)
if f_L*f(x_R) > 0:
print(’Error! Function does not have opposite \
signs at interval endpoints!’)
sys.exit(1)
x_M = (x_L + x_R)/2.0
f_M = f(x_M)
iteration_counter = 1
while abs(f_M) > eps:
if f_L*f_M > 0:
# i.e. same sign
x_L = x_M
f_L = f_M
else:
x_R = x_M
x_M = (x_L + x_R)/2
f_M = f(x_M)
iteration_counter = iteration_counter + 1
return x_M, iteration_counter
if __name__ == ’__main__’:
def f(x):
return x**2 - 9
a = 0;
b = 1000
solution, no_iterations = bisection(f, a, b, eps=1.0e-6)
print(’Number of function calls: {:d}’.format(1 + 2*no_iterations))
print(’A solution is: {:f}’.format(solution))
Note that we first check if f changes sign in [a, b], because that is a requirement
for the algorithm to work. The algorithm also relies on a continuous f (x) function,
but this is very challenging for a computer code to check.
We get the following printout to the screen when bisection_method.py is run:
Number of function calls: 63
A solution is: 3.000000
We notice that the number of function calls is much higher than with the previous
methods.