27 Root Finding
Iterative methods for solving \(f(x) = 0\) for continuous \(f : \fR \to \fR\).
Common stopping tests are \[ \begin{align} |f(x_k)|\leq `tol`_f, \qquad |x_{k+1}-x_k|\leq `tol`_x(1+|x_k|). \end{align} \] A small residual alone can be misleading when \(f'(x^*)\) is small. A small step alone can be misleading when the iteration stagnates.
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\).
Use the intermediate value theorem to prove that the initial bracket contains a root.
Show that the bisection update preserves the sign-change bracket.
Prove that the bracket length after \(n\) steps is \((b-a)/2^n\).
Derive the error bound in the result above.
(Bisection trade-off) Bisection is robust because it preserves a bracket, but its convergence is only linear. Each step gains exactly one bit of accuracy.
(Bracketing default) If a sign-changing interval is known and function evaluations are cheap, use a bracketed method. It gives a certificate that a root remains inside the current interval.
27.2 Open Methods
Faster local convergence, but sensitive to the initial guess \(x_0\) and may diverge.
A root problem can be rewritten as \(x=g(x)\) and iterated by \[ \begin{align} x_{k+1}=g(x_k). \end{align} \] If \(|g'(x^*)|<1\), the fixed point is locally attracting.
Use the mean value theorem to show \(|x_{k+1}-x^*|\leq L|x_k-x^*|\) if \(|g'(x)|\leq L<1\) near \(x^*\).
Rewrite Newton’s method as a fixed-point iteration.
Compute \(g'(x^*)\) for Newton’s fixed-point map at a simple root.
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 formula.
Divide by \(f'(x_k)\) and isolate the Newton correction \(f(x_k)/f'(x_k)\).
Substitute \(x_{k+1}=x_k-f(x_k)/f'(x_k)\).
Show that \(|x_{k+1}-x^*| \leq C|x_k-x^*|^2\) once \(x_k\) is close enough to a simple root.
Explain why the assumption \(f'(x^*)\neq 0\) is essential.
(Newton 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\).
If \(f(x)=(x-x^*)^m q(x)\) with \(q(x^*)\neq 0\) and \(m>1\), then Newton’s method converges locally linearly with asymptotic factor \[ \begin{align} 1-\frac{1}{m}. \end{align} \]
Compute \(f'(x)\) for \(f(x)=(x-x^*)^m q(x)\).
Substitute \(f\) and \(f'\) into the Newton update.
Keep the leading term as \(x_k\to x^*\).
Derive the factor in the result above.
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'\)).
Derive the secant update by replacing \(f'(x_k)\) in Newton’s method with a finite difference through \((x_{k-1},f(x_{k-1}))\) and \((x_k,f(x_k))\).
Compare the information used by Newton and secant.
Numerically estimate the convergence order for \(f(x)=x^2-2\).
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.
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 using the result above.
Newton on \(f(x) = x^2 - 2\) from \(x_0 = 1\). Verify the doubling of digits using the result above.
Prove that for \(f(x) = x^2\), Newton converges to \(0\) with linear rate \(1/2\) using the result above.
Find the root of \(e^x = 3x\) near \(x=1\) via Secant method. Compare evaluations vs. Newton.
Construct an example where \(|f(x_k)|\) is small but \(|x_k-x^*|\) is not small. Relate it to the result above.