findZeroWithBisection(f, x0, x1, epsilon) [15 pts]
As we will cover more carefully later in the course, a function may
take another function as an argument. For example, consider this code:
def h(n):
return n+5
def f(g, x):
return 2*g(x)
print(f(h,3)) # prints 16
Here, we define a function f whose first argument is another function. On the last line, we call f providing the function h, which is bound in f to the parameter g. Hence, calls to g in f are really calls to h. Play around
with the sample code to get the hang of this idea.
In mathematics, one way to numerically (as opposed to algebraically) find a
zero of a function f(x) is to search for the zero in between two points, using smaller steps as we get closer. (This is similar to binary search, which we will learn about in a later week.)
To start, we need to know two values, x0 and x1, with x0<x1, where f(x0) and f(x1)
have different signs (so one is positive and the other is negative). We know there is some value x in the
range [x0,x1] such that f(x)=0. (This is described by the Intermediate Value Theorem, if you're curious.)
Our goal is to find the x where f(x) == 0. First, we evaluate f(xmid), which is the midpoint between x0 and x1. If f(xmid) is exactly 0, we are done! Otherwise, we can divide our range in
half as such: if f(xmid) and f(x0) are the same sign, use the range [xmid,
x1]. Otherwise, f(xmid) and f(x1) must share the same sign, so use the
range [x0, xmid]. We repeat the process of evaluating f at the midpoint of our new range, then choosing a new range, and so forth until x0 and x1 are very close (i.e. within some suitably small epsilon).
With this in mind, write the function findZeroWithBisection that takes a
function f, a float x0, a float x1, and a float epsilon, and returns an
approximate value x in [x0,x1] where f(x) is approximately zero. Your
function should stop when x0 and x1 are within epsilon, and at that time
should return the midpoint of that range. Note that if it is not true that
exactly one of f(x0) and f(x1) is negative, your function should return the
Python value None, signifying that the bisection method cannot be used on
the given range.
Let's see this in action! First, we'll use it to approximate the square
root of 2 without the ** operator:
print("Use bisection to approximate sqrt(2):")
def f1(x): return x*x - 2 # root at x=sqrt(2)
x = findZeroWithBisection(f1, 0, 2, 0.000000001)
print(f" x = {x}") # prints x = 1.41421356192
print(f" check: x**2 = {x*x}") # prints check: x**2 = 1.99999999871 (really close!)
Next, let's use it to approximate phi (the
golden ratio), without using the closed-form solution ((1 + sqrt(5))/2),
instead using the interesting property of phi that adding one to it is the
same as squaring it. That is, ((phi + 1) == phi**2). How do use that?
We convert it into an equation equal to 0: phi**2 - (phi + 1) == 0.
Now we're set! (Of course, we could just use the Quadratic Formula here,
but it's more interesting to use bisection, now that we have it!).
print("use bisection to approximate phi (the golden ratio):")
def f2(x): return x**2 - (x + 1) # root at x=phi
x = findZeroWithBisection(f2, 0, 2, 0.000000001)
print(f" x = {x}") # prints x = 1.61803398887
phi = (1 + 5**0.5)/2 # the actual value (to within Python's floating point accuracy)
print(f" check: x/phi = {x/phi}") # prints check: check: x/phi = 1.00000000007 (nice!)
The previous two examples are nice, but simpler techniques than bisection
would have worked as well. So let's solve a problem that would be hard to
solve without bisection (or some other numeric approximation algorithm).
Specifically, find a number x such that x**5 == 2**x:
print("use bisection to approximate x where x**5 == 2**x")
def f3(x): return x**5 - 2**x # f(1)<0, f(2)>0
x = findZeroWithBisection(f3, 1, 2, 0.000000001)
print(f" x = {x}") # prints x = 1.17727855081
print(f" check: x**5 - 2**x = {x**5 - 2**x}") # prints check: x**5 - 2**x = 3.63570817896e-09 (great!)
Hopefully this bisection excursion helps you appreciate the awesome
computational power that about 10 lines of Python can have!