Exercise for the course Python for MATLAB users, by Olivier Verdier¶

In [1]:
%pylab
%matplotlib inline

Using matplotlib backend: MacOSX
Populating the interactive namespace from numpy and matplotlib


A continuous functions $f$ which changes its sign in an interval $[a,b]$, i.e. $f(a)f(b)< 0$, has at least one root in this interval. Such a root can be found by the bisection method.

This method starts from the given interval. Then it investigates the sign changes in the subintervals $[a,\frac{a+b}{2}]$ and $[\frac{a+b}{2},b]$. If the sign changes in the first subinterval $b$ is redefined to be $b:=\frac{a+b}{2}$ otherwise $a$ is redefined in the same manner to $a:=\frac{a+b}{2}$, and the process is repeated until the $b-a$ is less than a given tolerance.

In [2]:
def bisect(f, a, b):
tol = 1e-9
for i in range(100):
if (b-a) < tol:
break
c = (a+b)/2
if f(a)*f(c) <= 0:
b = c
else:
a = c
return c


Implement the function bisect above until the following does not complain:

In [3]:
def lin(x):
return x
assert allclose(bisect(sin, 3., 4.), pi)
assert allclose(bisect(lin, -1,1), 0)