Approximating Zeros of a Continuous Function
You are given a polynomial $f(x) = c_0 + c_1 x + \dots + c_d x^d$, specified by its coefficient list coeffs = [c0, c1, ..., cd], on an interval $[a, b]$ where $f(a)$ and $f(b)$ have strictly opposite signs. By the Intermediate Value Theorem a zero lies in $[a, b]$.
Implement the function:
```python def find_root(coeffs, a, b, tol): ... ```
Use bisection: repeatedly halve the bracketing interval, keeping the half that still contains a sign change, until the interval width is $\le$ tol. Return the midpoint of the final bracket (a float).
- Explain the simplest guaranteed approach (bisection) and analyze its convergence.
- Describe at least one faster alternative (Newton's method, secant, or Brent) and explain the trade-off.
- What method would you recommend in practice, and why?
Example
find_root([-2.0, 0.0, 1.0], 0.0, 2.0, 1e-10) -> 1.414213562355144
Here $f(x) = x^2 - 2$ on $[0, 2]$: $f(0) = -2 < 0$ and $f(2) = 2 > 0$, so bisection narrows the bracket to width $\le 10^{-10}$ around $\sqrt{2}$ and returns the final midpoint.
Hints
- The Intermediate Value Theorem guarantees a zero exists in $[a, b]$ when $f(a)$ and $f(b)$ have opposite signs. How can you systematically shrink that interval?
- Bisection halves the interval each step, giving linear convergence. For faster convergence, think about using local information like the slope of $f$ -- what does the tangent line tell you?
- Newton's method iterates $x_{n+1} = x_n - f(x_n)/f'(x_n)$ for quadratic convergence, but needs a derivative and good starting point. Compare the trade-offs with bisection.
Worked Solution
How to Think About It: The Intermediate Value Theorem guarantees a zero exists in $[a, b]$ when $f(a)$ and $f(b)$ have opposite signs. The most natural strategy is to narrow that interval. If you can query $f$ at one point, the midpoint gives the most information — it halves the search space every step. That is bisection: rock-solid, linear convergence (one bit of accuracy per iteration). Faster methods (Newton, secant, Brent) trade robustness for speed.
Contract for this problem: You must implement find_root(coeffs, a, b, tol) where coeffs = [c0, c1, ..., cd] describes $f(x) = c_0 + c_1 x + \dots + c_d x^d$. It is guaranteed that $f(a)$ and $f(b)$ have strictly opposite signs. Halve the bracket until its width is $\le$ tol, then return the midpoint of the final bracket (a float), not the list of coefficients or the number of iterations.
Key details that make the tests pass: - Evaluate the polynomial with Horner's rule for stability. - Loop while (b - a) > tol. - Keep the sub-interval that still brackets the root: if f(a) * f(m) <= 0 set b = m, otherwise set a = m (and refresh the cached f(a)). Using <= 0 (not strict <) matters when f(m) lands exactly on zero — the root then sits at the b end of the retained bracket.
```python def find_root(coeffs, a, b, tol): # Bisection on a polynomial f(x) = c0 + c1*x + ... + cd*x**d. def f(x): r = 0.0 for c in reversed(coeffs): r = r * x + c return r
fa = f(a) while (b - a) > tol: m = (a + b) / 2.0 fm = f(m) if fa * fm <= 0: b = m else: a = m fa = fm return (a + b) / 2.0 ```
Faster alternatives (interview talking points): Newton's method $x_{n+1} = x_n - f(x_n)/f'(x_n)$ converges quadratically but needs a derivative and a good starting guess. The secant method is superlinear (order $\approx 1.618$) with no derivative. Brent's method is the production standard (scipy.optimize.brentq): it combines bisection's guaranteed convergence with interpolation's speed. In practice, recommend Brent for general use, or bisection when you need a guarantee with a possibly nasty function.
Intuition
Root-finding is one of the most fundamental numerical tasks in quant finance -- it shows up every time you invert a pricing function (e.g., solving for implied volatility from an option price). The core tension is between reliability and speed. Bisection is the tortoise: it always wins the race, but slowly, because it only uses the sign of $f$ and ignores everything else. Newton's method is the hare: it uses local curvature information to leap toward the answer, converging blazingly fast when things go well, but it can overshoot or cycle when the function misbehaves.
The practical lesson is that you rarely want a pure method. Production-grade solvers like Brent's method are hybrids -- they try the fast interpolation step when it looks safe, and fall back to a bisection step when it does not. This "trust but verify" pattern appears throughout numerical computing and, more broadly, in any system where you balance aggressive optimization against safety constraints. In an interview, demonstrating this practical judgment -- not just reciting formulas -- is what separates a strong candidate.