Root Finding

Numerical Root-Finding & Bisection

Most equations $f(x) = 0$ defy algebra—there is no general formula for degree-5 polynomials, let alone mixtures of exponentials and trig. Root-finding algorithms locate solutions numerically to any desired accuracy by iterating.

Bisection is the simplest and most robust method. It relies on the Intermediate Value Theorem: if a continuous $f$ has opposite signs at $a$ and $b$, a root lies between them.

Bisection repeatedly halves the interval, keeping the half where the sign change persists. Each step halves the error, guaranteeing convergence (given an initial sign change) with linear speed.

Newton's Method & Trade-offs

Newton's method uses the tangent line from a guess $x_n$ to find the next zero:

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

Near a root, Newton's converges quadratically: correct digits roughly double each step.

Common pitfall: Assuming Newton's method always converges. It fails if $f'(x_n) = 0$ (division by zero) or from poor starts. Hybrid methods use bisection for safety, then Newton's for speed.