27 Root Finding
Iterative methods for solving \(f(x) = 0\) for continuous \(f : \fR \to \fR\).
27.1 Bracketing Methods
Guaranteed convergence to a root within a known interval.
Given \(f \in C[a, b]\) with \(f(a)f(b) < 0\), a root \(x^* \in (a, b)\) exists. The method repeatedly halves the interval:
\(m = (a + b)/2\)
If \(f(a)f(m) < 0\), new interval is \([a, m]\), else \([m, b]\).
Error Bound: After \(n\) steps, \(|x_n - x^*| \leq (b - a)/2^n\).
Stability: Bisection is the most robust method; it always converges if a bracket exists. Convergence: Linear with rate \(1/2\). Gains exactly 1 bit of accuracy per step.
27.2 Open Methods
Faster local convergence, but sensitive to the initial guess \(x_0\) and may diverge.
Linearizes \(f\) at the current iterate: \[ \begin{align} x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}. \end{align} \]
If \(f''(x)\) is continuous near a simple root \(x^*\) (\(f'(x^*) \neq 0\)), Newton’s method converges quadratically: \[ \begin{align} |x_{k+1} - x^*| \approx \frac{|f''(x^*)|}{2|f'(x^*)|} |x_k - x^*|^2. \end{align} \]
Expand \(f(x^*)\) about \(x_k\) using a second-order Taylor polynomial: \[ \begin{align} 0 = f(x^*) = f(x_k) + f'(x_k)(x^* - x_k) + \frac{f''(\xi_k)}{2}(x^* - x_k)^2 \end{align} \] for some \(\xi_k\) between \(x^*\) and \(x_k\). Dividing by \(f'(x_k)\): \[ \begin{align} 0 = \frac{f(x_k)}{f'(x_k)} + x^* - x_k + \frac{f''(\xi_k)}{2f'(x_k)}(x^* - x_k)^2. \end{align} \] Substituting the Newton update \(x_{k+1} = x_k - f(x_k)/f'(x_k)\): \[ \begin{align} 0 &= -(x_{k+1} - x_k) + x^* - x_k + \frac{f''(\xi_k)}{2f'(x_k)}(x^* - x_k)^2 \\ x_{k+1} - x^* &= \frac{f''(\xi_k)}{2f'(x_k)}(x_k - x^*)^2. \end{align} \] As \(x_k \to x^*\), we have \(\xi_k \to x^*\), yielding the quadratic error relation.
Failure Modes: 1. \(x_0\) too far from \(x^*\). 2. \(f'(x_k) \approx 0\) (zero derivative). 3. Multiple roots (\(f'(x^*) = 0\)): convergence degrades to linear with rate \(1/2\).
Approximates \(f'\) via finite differences of the last two iterates: \[ \begin{align} x_{k+1} = x_k - f(x_k)\frac{x_k - x_{k-1}}{f(x_k) - f(x_{k-1})}. \end{align} \] Requires two initial points (\(x_0, x_1\)).
The secant method converges with order \(\phi = (1 + \sqrt{5})/2 \approx 1.618\) (the golden ratio). Efficiency: Faster than bisection, slower than Newton, but requires only 1 function evaluation per step (Newton requires 2: \(f\) and \(f'\)).
27.3 Brent’s Method
A standard robust algorithm for one-dimensional root-finding.
Brent’s method combines:
Bisection: For guaranteed global convergence.
Secant: For fast local convergence.
IQI: Inverse Quadratic Interpolation using 3 points.
Rule: It uses fast open steps by default, falling back to bisection only if the step is outside the bracket or not improving quickly enough.
Implementation: Used in scipy.optimize.brentq.
27.4 Exercises
Bisection on \(f(x) = x^3 - 2\) on \([1, 2]\) for 4 steps. Find the guaranteed error.
Newton on \(f(x) = x^2 - 2\) from \(x_0 = 1\). Verify the doubling of digits.
Prove that for \(f(x) = x^2\), Newton converges to \(0\) with linear rate \(1/2\).
Find the root of \(e^x = 3x\) near \(x=1\) via Secant method. Compare evaluations vs. Newton.