Sahithyan's S2 — Methods of Mathematics
Bisection Method
Suppose is a continuous function on the interval such that .
A root exists on the interval chosen above by Intermediate Value Theorem. The bisection method is an iterative algorithm that approximates the root of .
Let the midpoint .
- If , then is the root
- If , then the root lies in , so the interval is updated to
- If , then the root lies in , so the interval is updated to .
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 is continuous in and . The bisection generates a sequence such that:
Here is a root of .
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