Skip to content
Sahithyan's S2
Sahithyan's S2 — Methods of Mathematics

Bisection Method

Suppose ff is a continuous function on the interval [a,b][a, b] such that f(a)f(b)<0f(a) \cdot f(b) < 0.

A root exists on the interval chosen above by Intermediate Value Theorem. The bisection method is an iterative algorithm that approximates the root cc of ff.

Let the midpoint m=12(a+b)m = \frac{1}{2}(a + b).

  • If f(m)=0f(m) = 0, then mm is the root
  • If f(a)f(m)<0f(a) \cdot f(m) < 0, then the root lies in [a,m][a, m], so the interval is updated to [a,m][a, m]
  • If f(m)f(b)<0f(m) \cdot f(b) < 0, then the root lies in [m,b][m, b], so the interval is updated to [m,b][m, b].

Code example

def bisection(f, a, b, tolerance=1e-6):
if f(a) * f(b) >= 0:
raise ValueError("f(a) and f(b) must have opposite signs")
while (b - a) / 2 > tolerance:
m = (a + b) / 2
if f(m) == 0:
return m
elif f(a) * f(m) < 0:
b = m
else:
a = m
return (a + b) / 2

Bisection theorem

Suppose ff is continuous in [a,b][a, b] and f(a)f(b)<0f(a) \cdot f(b) < 0. The bisection generates a sequence pnp_n such that:

pncba2n|p_n - c| \leq \frac{b - a}{2^n}

Here cc is a root of ff.

Properties

  • Always convergent
  • Linear convergence rate
  • Order of convergence is 1.
  • Error can be controlled
  • Error is bounded
  • Error decreases with each iteration
  • Simpler calculations

Limitations

  • Slow convergence
  • Cannot approximate solutions for even functions and more
  • Cannot determine complex roots
  • Cannot be applied if there are discontinuities or its sign doesn’t change in the interval