Root-Finding Beyond Newton: Bisection and the Secant Method
You want to solve $f(x) = 0$ for a differentiable function $f$ of one variable. Newton's method is the obvious choice, but suppose you cannot or do not want to use it (the derivative may be expensive, unavailable, or the iteration may be diverging from your starting point).
(a) Describe at least two other root-finding algorithms. For each, state what it requires, how each iteration works, whether convergence is guaranteed, and its order of convergence.
(b) Explain briefly when you would prefer each of them over Newton's method.
Hints
- If $f$ is continuous and changes sign on $[a, b]$, the intermediate value theorem guarantees a root inside. Can you shrink the interval systematically?
- Newton's step uses the tangent slope $f'(x_k)$. If derivatives are unavailable, replace the slope by a finite difference through the last two iterates: a secant line.
- Bisection halves the error every step (linear convergence, rate $1/2$). The secant method's error satisfies $e_{k+1} \approx C\, e_k e_{k-1}$, which gives order $\phi = (1 + \sqrt{5})/2 \approx 1.618$.
Worked Solution
How to Think About It: Every root-finder is a rule for producing the next guess from information about $f$ at the current guesses. Newton uses the value and the derivative at one point. Removing the derivative leads to the secant method (two values, one slope estimate); removing all smoothness assumptions leads to bisection (two values and a sign change).
Approach: Describe bisection and the secant method side by side (requirements, iteration, guarantee, convergence order), then say when each beats Newton.
Formal Solution:
Part (a): Alternative algorithms
*Method 1 -- Bisection.* - Requires: $f$ continuous on $[a, b]$ with $f(a)f(b) < 0$ (a sign-changing bracket). No derivative. - Iteration: let $m = (a + b)/2$. If $f(m) = 0$ stop; if $f(a)f(m) < 0$ set $b = m$, otherwise set $a = m$. The bracket always contains a root by the intermediate value theorem. - Guarantee: always converges once a bracket is found. After $k$ steps the root is pinned to an interval of length $(b - a)/2^k$, so reaching tolerance $\varepsilon$ takes $\lceil \log_2\frac{b-a}{\varepsilon}\rceil$ steps. - Order: linear (order $1$) with rate $1/2$: the error bound halves each step, roughly one new binary digit per iteration.
*Method 2 -- Secant method.* - Requires: two starting points $x_0, x_1$ and function values only. No derivative, no bracket. - Iteration: replace $f'(x_k)$ in Newton's formula by the slope of the chord through the last two iterates, $$x_{k+1} = x_k - f(x_k)\,\frac{x_k - x_{k-1}}{f(x_k) - f(x_{k-1})}.$$ - Guarantee: not guaranteed globally; like Newton it can diverge from a poor start, and the denominator can vanish. - Order: superlinear. Near a simple root $e_{k+1} \approx \left|\frac{f''(r)}{2f'(r)}\right| e_k e_{k-1}$, which yields order $\phi = \frac{1 + \sqrt{5}}{2} \approx 1.618$ (versus $2$ for Newton). Since each step costs one function evaluation instead of Newton's two (value plus derivative), two secant steps (order $\phi^2 \approx 2.618$) often beat one Newton step per unit of work.
*Other options worth naming.* Regula falsi (false position) keeps a bracket like bisection but picks the secant point instead of the midpoint; fixed-point iteration $x_{k+1} = g(x_k)$ converges linearly when $|g'| < 1$; Brent's method combines bisection, secant, and inverse quadratic interpolation for a guaranteed and fast hybrid.
Part (b): When to prefer each
- Bisection: when robustness matters more than speed, when $f$ is cheap but ugly (non-smooth, noisy, or with unknown derivative), or as the safety net in a hybrid.
- Secant: when derivatives are unavailable or expensive (e.g. $f$ is itself the output of a pricing routine) but $f$ is smooth and you have a reasonable start; it gets most of Newton's speed at half the cost per step.
- Newton: when $f'$ is cheap and analytic (implied volatility, where the derivative is vega) and the starting point is good, because quadratic convergence gives machine precision in a handful of steps.
Answer: (a) Bisection: needs a continuous $f$ with a sign change on $[a,b]$; halves the bracket each step; always converges; linear convergence with rate $1/2$. Secant: needs two starting points and function values only; replaces $f'$ by the chord slope through the last two iterates; not guaranteed; superlinear convergence of order $(1+\sqrt5)/2 \approx 1.618$. (b) Bisection for guaranteed robustness, secant when derivatives are unavailable or costly, Newton when an analytic derivative and a good start are available; production solvers combine them (Brent).
Intuition
Root-finders trade robustness for speed: bisection is slow but cannot fail once you have a sign change, Newton is fast but needs derivatives and a good start, and the secant method sits between them with superlinear convergence of order $\phi \approx 1.618$ and no derivative at all. In practice solvers for implied volatility or bond yields use a hybrid (Brent's method): bracket with bisection for safety, then accelerate with secant or Newton steps.