Root Finding
18 min
Finding where f(x) = 0 exactly (algebraically) is only possible for
special functions — most real equations need a numerical approach.
Bisection is the simplest: if f(a) and f(b) have opposite signs,
a root must lie somewhere between them (the Intermediate Value Theorem).
Check the midpoint, keep whichever half still brackets the sign change,
and repeat.
def bisection(f, a, b, tol=1e-6):
while (b - a) / 2 > tol:
mid = (a + b) / 2
if f(a) * f(mid) < 0:
b = mid # root is in the left half
else:
a = mid # root is in the right half
return (a + b) / 2
print(bisection(lambda x: x**2 - 4, 0, 5)) # ~2.0
Bisection is guaranteed to converge (as long as the sign-change assumption holds) -- slow but bulletproof, which is why it's often the fallback when a faster method might diverge.
Newton's method converges much faster by using the function's slope:
approximate f near the current guess with its tangent line, and jump
straight to where THAT line crosses zero:
def newtons_method(f, f_prime, x0, iterations=20):
x = x0
for _ in range(iterations):
x = x - f(x) / f_prime(x)
return x
print(newtons_method(lambda x: x**2 - 2, lambda x: 2*x, 1)) # converges to sqrt(2)
The tradeoff: Newton's method needs the derivative (bisection doesn't), and it isn't guaranteed to converge at all from a bad starting guess — where bisection is slow-but-safe, Newton's method is fast-but-can-fail.
Write `bisection(f, a, b, tol=1e-6)`: find a root of `f` in `[a, b]` (assume `f(a)` and `f(b)` have opposite signs) using the bisection method — repeatedly halve the interval, keeping the half where the sign change still occurs, until the interval width is below `tol`. Return the midpoint, rounded to 4 decimals.
Write `newtons_method(f, f_prime, x0, iterations=20)`: starting at `x0`, repeat `iterations` times: `x = x - f(x)/f_prime(x)`. Return the final `x`, rounded to 4 decimals.
Compared to bisection, why does Newton's method usually converge much faster?
You can find a function's root using bisection (safe, needs no derivative) or Newton's method (fast, needs the derivative), and understand the tradeoff between them.