Root finding using bisection method in Python

Question

This code below is supposed to calculate the root of a function using bisection method. I am a newbie to Python, so I do not know how to raise errors. Also, I would like to have a general review on this algorithm design, where I could have optimised, utilised some tricks or any sort of improvements. I feel like I am really not using the full funcionality of Python somehow.

Any comments on how to write a succinct code is appreciated. Thanks.

"""
Program to find root of a function using bisection method
"""
import sys
import math

def is_equal(a,b):
    return abs(b-a) < sys.float_info.epsilon

def bisection(f, a, b, TOL=0.01, MAX_ITER=100):
    """
    f is the cost function, [a,b] is the initial bracket, 
    TOL is tolerance, MAX_ITER is maximum iteration.
    """
    f_a = f(a)
    f_b = f(b)

    iter = 0
    while iter < MAX_ITER:
        c = (a+b)/2
        f_c = f(c)

        if math.isclose(f_c,0.0,abs_tol=1.0E-6) or abs(b-a)/2<TOL:
            return (c, iter)
        else:
            if f_a * f_c < 0:
                b = c
                f_b = f_c
            else:
                a = c
                f_a = f_c
            iter = iter + 1
    return None

def func(x):
    """
    The cost function: f(x) = cos(x) - x
    """
    return math.cos(x) - x

root, iter = bisection(func, -1, 1, TOL=1.0E-6)
print("Iteration = ", iter)
print("root = ", root, ", func(x) = ", func(root))

Answer 1

Type hints

They can help; an example:

def is_equal(a: float, b: float) -> bool:

The return type of bisection should probably be Optional[float].

Argument format

MAX_ITER and TOL should be lower-case because they are the arguments to a function, not a global constant.

Early-return

        return (c, iter)
    else:

does not need the else, so you can drop it.

In-place addition

        iter = iter + 1

can be

        iter += 1

Return parens

This does not need parentheses:

        return (c, iter)

The tuple is implied.

Answer 2

• I don't see the point of passing MAX_ITER. Bisection is guaranteed to terminate in \$\log \dfrac{b - a}{TOL}\$ iterations.

• I strongly advise against breaking the loop early at math.isclose(f_c,0.0,abs_tol=1.0E-6). It only tells you that the value at c is close to 0, but doesn't tell you where the root is (consider the case when the derivative at root is very small). After all, tolerance is passed for a reason!

  If you insist on early termination, at least return the (a, b) interval as well. The caller deserves to know the precision.

• You may want to do this test right before returning (like, is there a root at all):

  if math.isclose(f_c,0.0,abs_tol=1.0E-6):
      return None
  return c
  

  but I'd rather let the caller worry about that.

• abs in abs(b - a) seems excessive.

  if a > b:
      a, b = b, a
  

  at the very beginning of bisection takes care of it once and forever.

• (a + b) may overflow. c = a + (b - a)/2 is more prudent.

• I don't see where is_equal(a,b) is ever used.