Numerical Root Finding

Numerical root finding is the process of finding an approximate value $x$ such that $f(x) = 0$ for a given continuous function $f$.

The Bisection Method

The Bisection method is a robust but slow root-finding algorithm. It works by repeatedly bisecting an interval and then selecting a subinterval in which a root must lie for further processing. It requires that the function values at the endpoints of the interval have opposite signs (Bolzano’s Theorem).

def f(x):
  return x**3 - x - 2

def bisection(a, b, tol=1e-5):
  if f(a) * f(b) >= 0:
      return "Bisection fails (no sign change)."
  
  while (b - a) / 2 > tol:
      midpoint = (a + b) / 2
      if f(midpoint) == 0:
          return midpoint
      elif f(a) * f(midpoint) < 0:
          b = midpoint
      else:
          a = midpoint
  return (a + b) / 2

root = bisection(1, 2)
print(f"Bisection root: {root:.6f}")
print(f"f(root): {f(root):.6e}")

Newton-Raphson Method

The Newton-Raphson method uses the first two terms of the Taylor series to iteratively improve an estimate. $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$

def f(x):
  return x**3 - x - 2

def df(x):
  return 3*x**2 - 1

def newton(x0, tol=1e-5, max_iter=100):
  x = x0
  for i in range(max_iter):
      delta = f(x) / df(x)
      x = x - delta
      if abs(delta) < tol:
          return x, i
  return x, max_iter

root, iterations = newton(1.5)
print(f"Newton root: {root:.6f} found in {iterations} iterations")

Convergence and Stability

Newton’s method converges quadratically ($e_{n+1} \approx C e_n^2$), meaning the number of correct digits roughly doubles each iteration. However, it can fail or diverge if $f'(x)$ is near zero or if the initial guess is far from a root.