Numerical Methods: Root-Finding & Newton's Method
Bisection, Newton's method, and the price/benefit of higher-order convergence.
Root-finding: solve $f(x) = 0$ numerically.
- Bisection: assume $f(a)f(b) < 0$; repeatedly halve. Error halves each step ($\sim 2^{-k}$). Robust but slow.
- Newton's method: $x_{k+1} = x_k - f(x_k)/f'(x_k)$. Locally quadratic convergence near simple roots, $|x_{k+1} - x^*| \lesssim C |x_k - x^*|^2$ — number of correct digits roughly doubles each step.
- Secant method: replace $f'(x_k)$ by a finite difference; order $\varphi \approx 1.618$ (golden ratio).
Newton can fail or diverge: zero derivative, overshoot into a basin of attraction of a different root, oscillation. The basins of attraction for polynomial roots are fractal (Newton fractals).
Related ideas show up across numerical analysis: floating-point error, condition number $\kappa$ of a problem, stability of an algorithm — and the universal advice that big steps with strong second-order info beat tiny steps with first-order info.