Given a continuous function \(f : \fR \to \fR\), find \(x^*\) such that \(f(x^*) = 0\). Root-finding methods are iterative: starting from an initial guess (or bracket), they refine the estimate until convergence. The key distinctions are bracketing methods (guaranteed convergence, slower) versus open methods (faster convergence, may diverge).
Bisection
Suppose \(f\) is continuous on \([a, b]\) with \(f(a)f(b) < 0\). By the Intermediate Value Theorem, there exists \(x^* \in (a, b)\) with \(f(x^*) = 0\). The bisection method halves the bracket at each step: set \(m = (a + b)/2\), then replace \([a,b]\) by \([a,m]\) if \(f(a)f(m) < 0\), otherwise by \([m,b]\). After \(n\) steps, \[|x_n - x^*| \leq \frac{b - a}{2^n}.\]
Bisection converges linearly with rate \(1/2\): each step gains exactly one binary digit of accuracy. It requires only continuity of \(f\) (no derivative) and is guaranteed to converge as long as the initial bracket contains a root.
Newton-Raphson Method
Starting from an initial guess \(x_0\), Newton’s method linearizes \(f\) at the current iterate and solves for the root of the linear approximation: \[x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}.\]
If \(f\) is twice continuously differentiable near a simple root \(x^*\) (i.e., \(f'(x^*) \neq 0\)), then Newton’s method converges locally with quadratic rate: \[|x_{k+1} - x^*| \approx \frac{|f''(x^*)|}{2|f'(x^*)|} |x_k - x^*|^2.\] The number of correct decimal digits roughly doubles at each step.
Let \(e_k = x_k - x^*\). Taylor-expand \(f\) about \(x^*\): \[f(x_k) = f'(x^*)e_k + \tfrac{1}{2}f''(\xi_k)e_k^2\] for some \(\xi_k\) between \(x_k\) and \(x^*\). Similarly, \(f'(x_k) = f'(x^*) + O(e_k)\). Then \[e_{k+1} = e_k - \frac{f(x_k)}{f'(x_k)}
= e_k - \frac{f'(x^*)e_k + \tfrac{1}{2}f''(\xi_k)e_k^2}{f'(x^*) + O(e_k)}
= \frac{f''(\xi_k)}{2f'(x^*)}e_k^2 + O(e_k^3).\]
Newton’s method can diverge if \(x_0\) is far from the root, if \(f'(x_k) \approx 0\) (nearly flat), or at a double root \(f'(x^*) = 0\) (convergence degrades to linear with rate \(1/2\)).
Secant Method
When \(f'\) is unavailable or expensive, approximate \(f'(x_k)\) by a finite difference using the previous iterate: \[x_{k+1} = x_k - f(x_k)\frac{x_k - x_{k-1}}{f(x_k) - f(x_{k-1})}.\] The secant method requires two initial points \(x_0, x_1\) and does not evaluate \(f'\).
Near a simple root \(x^*\) with \(f\) twice differentiable, the secant method converges with order \(\phi = \frac{1 + \sqrt{5}}{2} \approx 1.618\) (the golden ratio): \[|e_{k+1}| \approx C |e_k|^{\phi}, \qquad C = \left|\frac{f''(x^*)}{2f'(x^*)}\right|^{\phi - 1}.\]
The secant method is superlinear — faster than bisection’s linear rate but slower than Newton’s quadratic rate. Each step costs one function evaluation (versus two for finite-difference Newton), making it often more efficient per digit gained.
Brent’s Method
Brent’s method combines three ideas to get the best of bracketing and open methods: (1) bisection as a fallback, always maintaining a bracket; (2) the secant method for fast superlinear convergence near the root; (3) inverse quadratic interpolation (IQI), fitting a quadratic through the last three points \((a, f(a))\), \((b, f(b))\), \((c, f(c))\) and evaluating it at \(y = 0\): \[x = \frac{a f(b)f(c)}{(f(a)-f(b))(f(a)-f(c))} + \frac{b f(a)f(c)}{(f(b)-f(a))(f(b)-f(c))} + \frac{c f(a)f(b)}{(f(c)-f(a))(f(c)-f(b))}.\]
Brent’s method is guaranteed to converge (like bisection) and achieves superlinear convergence near a root (like the secant method). It accepts an IQI or secant step only when it falls inside the bracket and improves sufficiently over bisection; otherwise it takes a bisection step.
Brent’s method is the default solver in scipy.optimize.brentq, the GNU Scientific Library, and MATLAB’s fzero.
Exercises
Apply 4 steps of bisection to find a root of \(f(x) = x^3 - 2\) on \([1, 2]\). What is the guaranteed error bound after these steps? Compare to \(2^{1/3}\).
Apply 3 steps of Newton’s method to \(f(x) = x^2 - 2\) starting from \(x_0 = 1\). Compute \(|x_k - \sqrt{2}|\) at each step and verify quadratic convergence by checking the ratio \(|e_{k+1}|/|e_k|^2\).
Show that Newton’s method applied to \(f(x) = x^2\) converges only linearly to \(x^* = 0\) (double root). What is the linear convergence rate?
Derive the convergence order \(\phi = (1+\sqrt{5})/2\) of the secant method. (Hint: assume \(|e_{k+1}| \approx C|e_k|^\phi\), use \(e_{k+1} \approx
\frac{f''}{2f'} e_k e_{k-1}\), and equate exponents.)
Find the positive root of \(f(x) = e^x - 3x = 0\) near \(x = 1\) using bisection on \([0, 2]\), Newton’s method from \(x_0 = 1\), and the secant method from \(x_0 = 1\), \(x_1 = 1.5\). Compare the number of function evaluations to reach \(|f(x_k)| < 10^{-10}\).