Bisection method for finding different valued roots in Python

Question

I am trying to implement the bisection method for finding different valued roots. Lets say I have y = 2x + 1, what value of x will give me y = 1.

I am not sure how to phrase the if statement in the while loop. This just converges on 'a' as the answer.

def f(x):
    return 2*x + 1

def bisection_method(f, a, b, tol):
    if f(a) > 1 and f(b) > 1: 
        print("No root found.")
    else:
        iter = 0
        while (b - a)/2.0 > tol:
            print(a, b, (b-a)/2)
            midpoint = (a + b)/2.0

            if f(a) < 1:
                b = midpoint
            else:
                a = midpoint

            iter += 1
        return midpoint, iter

x, its = bisection_method(f, -10, 10, 0.000001)
print(x, its)

Answer 1

To fix your code you sahouls change if to

...
            if  f(midpoint) > 1:
                b = midpoint
            else:
                a = midpoint
...

But this will only work for increasing functions f, ie that cross 1 from below to above. To handle decreasing functions as well you need to modify the code in a couple of places. Yo ubasically want to find a subinterval on which f switches from being above 1 to below 1, or vice versa

def bisection_method(f, a, b, tol):
    if (f(a) - 1) *(f(b) - 1) > 0: # change here
        print("No root found.")
    else:
        iter = 0
        while (b - a)/2.0 > tol:
            # print(a, b, (b-a)/2)
            midpoint = (a + b)/2.0

            if  (f(a) -1)*(f(midpoint)-1) <= 0: # change here
                b = midpoint
            else:
                a = midpoint

            iter += 1
        return midpoint, iter