Implementing root-finding from scratch — Newton-Raphson, bisection: Exercises

Level 1 — Recognition

Exercise 1.1

You are given $f (x) = x^{3} - x - 2$ and asked to find a root by bisection. Someone hands you three candidate intervals: $[0, 1]$ , $[1, 2]$ , $[2, 3]$ . Which one is a valid bracket, and which method requirement decides it?

Recall Solution

What we need: a bracket $[a, b]$ is valid only if $== f (a) \cdot f (b) < 0 ==$ — the function changes sign, so by the Intermediate Value Theorem a continuous curve must cross zero inside.

Evaluate the endpoints:

$f (0) = - 2$ , $f (1) = 1 - 1 - 2 = - 2$ → product $= + 4 > 0$ . Not valid (both negative — the curve may never dip to zero here).
$f (1) = - 2$ , $f (2) = 8 - 2 - 2 = 4$ → product $= - 8 < 0$ . Valid ✓ (negative → positive, a guaranteed crossing).
$f (2) = 4$ , $f (3) = 27 - 3 - 2 = 22$ → product $= + 88 > 0$ . Not valid.

Answer: only $[1, 2]$ brackets a root.

The figure below shows the curve with this valid bracket, its first bisection midpoint (plum), and the Newton tangent from Exercise 2.2 (orange) — glance at it now to see how the two methods approach the same crossing differently.

Figure — Implementing root-finding from scratch — Newton-Raphson, bisection

Notice how the plum midpoint at $m = 1.5$ sits close to zero already (because the curve is nearly straight here), while the orange tangent's x-intercept from $x_{0} = 2$ jumps almost onto the true root in one leap.

Exercise 1.2

Match each situation to the better first choice — bisection or Newton-Raphson:

(a) You have $f$ but no formula for $f^{'}$ , and a known sign change.
(b) You have $f$ , $f^{'}$ , and a starting guess already very close to the root.
(c) $f^{'}$ is nearly zero right where you'd start.

Recall Solution

(a) Bisection. Newton needs a derivative; bisection only needs $f$ and a sign change.
(b) Newton. Close start + derivative = quadratic convergence, few steps.
(c) Bisection. A tiny $f^{'} (x_{n})$ makes the Newton step $- f (x_{n}) / f^{'} (x_{n})$ explode — the tangent is almost flat and its x-intercept flies far away.

Level 2 — Application

Exercise 2.1

Do two bisection steps on $f (x) = x^{3} - x - 2$ over $[1, 2]$ . Report the bracket after each step and the midpoint you'd return if you stopped.

Recall Solution

Store $f_{a} = f (1) = - 2$ (negative), $f_{b} = f (2) = 4$ (positive).

Step 1: midpoint $m = (1 + 2) /2 = 1.5$ . Compute $f (1.5) = 3.375 - 1.5 - 2 = - 0.125$ (negative). Compare with the stored $f_{a}$ : $f_{a} \cdot f_{m} = (- 2) (- 0.125) = + 0.25 > 0$ → same sign on the left, so the crossing is on the right half. New bracket: $[1.5, 2]$ , and now $f_{a} = f (1.5) = - 0.125$ .

Step 2: midpoint $m = (1.5 + 2) /2 = 1.75$ . Compute $f (1.75) = 5.359375 - 1.75 - 2 = 1.609375$ (positive). $f_{a} \cdot f_{m} = (- 0.125) (1.609) < 0$ → sign change on the left, keep left half. New bracket: $[1.5, 1.75]$ .

If you stopped now you'd return the midpoint $(1.5 + 1.75) /2 = 1.625$ . (The true root is $\approx 1.5214$ .)

Exercise 2.2

Do two Newton steps on the same $f (x) = x^{3} - x - 2$ , with $f^{'} (x) = 3 x^{2} - 1$ , starting at $x_{0} = 2$ .

Recall Solution

Update rule: $x_{n + 1} = x_{n} - \frac{x _{n}^{3} - x _{n} - 2}{3 x _{n}^{2} - 1}$ .

Step 1 ( $x_{0} = 2$ ): $f (2) = 4$ , $f^{'} (2) = 3 \cdot 4 - 1 = 11$ . $x_{1} = 2 - \frac{4}{11} = 2 - 0.363636 \dots = 1.636364.$

Step 2 ( $x_{1} = 1.636364$ ): $f (x_{1}) = 1.63636 4^{3} - 1.636364 - 2 = 4.380697 - 3.636364 = 0.744333$ ; $f^{'} (x_{1}) = 3 (1.636364)^{2} - 1 = 8.032231 - 1 = 7.032231$ . $x_{2} = 1.636364 - \frac{0.744333}{7.032231} = 1.636364 - 0.105844 = 1.530520.$

Two Newton steps got us to $1.53052$ (true root $1.52138$ ); two bisection steps only reached $1.625$ . Newton pulls ahead fast once the guess is near.

Level 3 — Analysis

Exercise 3.1

Bisection on $[1, 2]$ (width $= 1$ ). How many steps guarantee the returned midpoint is within $ε = 1 0^{- 6}$ of the true root? First derive the error bound geometrically, then solve for the step count.

Recall Solution

Deriving the bound (the geometric "why"): Start with interval width $w_{0} = b - a$ . Each bisection step cuts the live interval exactly in half, because we split at the midpoint and keep one side. So the width after $n$ steps is: $w_{n} = \frac{w _{0}}{2 ^{n}} = \frac{b - a}{2 ^{n}} .$ Now — where inside that final interval is the true root? We return the midpoint of the surviving interval. The root is somewhere in the interval, and the midpoint sits dead-centre, so the worst the root can be from the midpoint is half the interval width (root at one end, midpoint in the middle). That is why the error carries the extra factor of two: $error \leq \frac{w _{n}}{2} = \frac{b - a}{2 ^{n + 1}} .$ The $2^{n + 1}$ is not a magic constant: the $2^{n}$ counts the halvings, and the extra $2$ is the "midpoint is at most half a width away" geometry.

Solving for the step count. We require: $\frac{b - a}{2 ^{n + 1}} \leq ε ⟺ \frac{1}{2 ^{n + 1}} \leq 1 0^{- 6} ⟺ 2^{n + 1} \geq 1 0^{6} .$ Take $lo g_{2}$ : $n + 1 \geq lo g_{2} (1 0^{6}) = 6 lo g_{2} 10 \approx 6 \times 3.32193 = 19.9316$ . So $n \geq 18.93$ , meaning $n = 19$ steps suffice. (Each step buys one bit; $2^{20} = 1048576 > 1 0^{6}$ .)

Exercise 3.2

Newton on $f (x) = x^{2} - 2$ starting at $x_{0} = 1.5$ has error $e_{0} = 1.5 - 2 \approx 0.085786$ . Derive the quadratic-convergence estimate $e_{n + 1} \approx \frac{f ^{''} ( x ^{*} )}{2 f ^{'} ( x ^{*} )} e_{n}^{2}$ from Taylor Series, then use it to predict $e_{1}$ and compare to the actual next error.

Recall Solution

Deriving $C$ from Taylor's theorem. Let $e_{n} = x_{n} - x^{*}$ be the error, where $x^{*}$ is the true root ( $f (x^{*}) = 0$ ). Taylor-expand $f$ and $f^{'}$ about $x^{*}$ , keeping terms up to $e_{n}^{2}$ : $f (x_{n}) = f (x^{*}) + f^{'} (x^{*}) e_{n} + \frac{1}{2} f^{''} (x^{*}) e_{n}^{2} + \dots = f^{'} (x^{*}) e_{n} + \frac{1}{2} f^{''} (x^{*}) e_{n}^{2},$ (the $f (x^{*})$ term vanishes because $x^{*}$ is a root), and $f^{'} (x_{n}) = f^{'} (x^{*}) + f^{''} (x^{*}) e_{n} + \dots .$ The next Newton error is $e_{n + 1} = x_{n + 1} - x^{*} = e_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ . Substitute the two expansions: $e_{n + 1} = e_{n} - \frac{f ^{'} ( x ^{*} ) e _{n} + \frac{1}{2} f ^{''} ( x ^{*} ) e _{n}^{2}}{f ^{'} ( x ^{*} ) + f ^{''} ( x ^{*} ) e _{n}} .$ Factor $f^{'} (x^{*}) e_{n}$ out of the numerator and $f^{'} (x^{*})$ out of the denominator: $e_{n + 1} = e_{n} - e_{n} \cdot \frac{1 + \frac{f ^{''} ( x ^{*} )}{2 f ^{'} ( x ^{*} )} e _{n}}{1 + \frac{f ^{''} ( x ^{*} )}{f ^{'} ( x ^{*} )} e _{n}} .$ Now use $\frac{1 + α e _{n}}{1 + β e _{n}} \approx (1 + α e_{n}) (1 - β e_{n}) \approx 1 + (α - β) e_{n}$ for small $e_{n}$ (geometric-series approximation of the denominator). With $α = \frac{f ^{''}}{2 f ^{'}}$ and $β = \frac{f ^{''}}{f ^{'}}$ : $e_{n + 1} \approx e_{n} - e_{n} (1 + (α - β) e_{n}) = - e_{n}^{2} (α - β) = e_{n}^{2} (β - α) .$ And $β - α = \frac{f ^{''}}{f ^{'}} - \frac{f ^{''}}{2 f ^{'}} = \frac{f ^{''}}{2 f ^{'}}$ . So the constant is: $e_{n + 1} \approx \frac{f ^{''} ( x ^{*} )}{2 f ^{'} ( x ^{*} )} e_{n}^{2} \Rightarrow C = \frac{f ^{''} ( x ^{*} )}{2 f ^{'} ( x ^{*} )} .$ This is why $C$ has that exact form — it is the ratio of the leading curvature term $f^{''} /2$ to the slope $f^{'}$ , straight out of the Taylor remainder.

Applying it here. For $f (x) = x^{2} - 2$ : $f^{'} (x) = 2 x$ so $f^{'} (x^{*}) = 22$ ; $f^{''} (x) = 2$ so $f^{''} (x^{*}) = 2$ . $C = \frac{2}{2 \cdot 2 2} = \frac{1}{2 2} \approx 0.353553.$ Predicted $e_{1} \approx C e_{0}^{2} = 0.353553 \times (0.085786)^{2} = 0.353553 \times 0.0073593 = 0.0026019$ .

Actual: $x_{1} = \frac{1.5}{2} + \frac{1}{1.5} = 0.75 + 0.666667 = 1.416667$ , so $e_{1} = 1.416667 - 1.414214 = 0.002453$ .

Predicted $0.002602$ vs actual $0.002453$ — same order, ~6% apart (the difference is the neglected higher-order terms we dropped in the expansion). The prediction confirms the squaring behaviour: $e_{0} \approx 0.086$ became $e_{1} \approx 0.0025$ , roughly $e_{0}^{2}$ scaled — the digits of accuracy doubled.

Level 4 — Synthesis

Exercise 4.1

Write a safeguarded Newton step function: given a current bracket $[a, b]$ with a sign change and a current guess $x$ , take a Newton step; if it lands outside $[a, b]$ (or $f^{'}$ is zero), fall back to a bisection midpoint. Explain each guard. (Pseudocode + one hand trace.)

Recall Solution

def safe_step(f, df, a, b, x, fa):
    dfx = df(x)
    if dfx != 0:
        xn = x - f(x) / dfx        # try Newton
        if a < xn < b:             # accept only if it stays inside the bracket
            x_new = xn
        else:
            x_new = (a + b) / 2    # Newton escaped -> bisect
    else:
        x_new = (a + b) / 2        # flat tangent -> bisect
    # shrink the bracket using the new point's sign
    fx = f(x_new)
    if fa * fx < 0:
        b = x_new                  # sign change on the left half
    else:
        a, fa = x_new, fx          # sign change on the right half
    return a, b, x_new, fa

Why each guard:

dfx != 0: a flat tangent gives an infinite/undefined step — the exact failure mode of Newton. Fall back to bisection, which never divides by a slope.
a < xn < b: if Newton's tangent points out of the trapped region, the root can't be there — the guess is worse than a blind midpoint. Reject it.
Updating a/b with the sign test keeps a valid bracket at all times, so we inherit bisection's guarantee while enjoying Newton's speed when it behaves.

Hand trace on $f (x) = x^{3} - x - 2$ , $[1, 2]$ , start $x = 2$ , $f_{a} = f (1) = - 2$ :

$df (2) = 11$ , Newton $x_{n} = 2 - 4/11 = 1.6364$ , which lies inside $[1, 2]$ → accept. $f (1.6364) = 0.7443 > 0$ ; $f_{a} \cdot f_{x} = (- 2) (0.744) < 0$ → shrink right end: bracket becomes $[1, 1.6364]$ .

This is exactly the philosophy behind scipy.optimize.brentq: keep a bracket, use fast interpolation inside it, bisect when the fast step misbehaves.

Exercise 4.2

The parent note mentions the Secant method as a derivative-free cousin of Newton. Derive its update from Newton's by replacing $f^{'} (x_{n})$ with a finite difference using the two most recent points $x_{n - 1}, x_{n}$ . State what it costs and gains versus Newton — and identify the edge case that can break the update, with a guard.

Recall Solution

Newton is $x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ . When we have no formula for $f^{'}$ , approximate the slope by the line through the last two points (a finite difference, closely related to the definition of a derivative): $f^{'} (x_{n}) \approx \frac{f ( x _{n} ) - f ( x _{n - 1} )}{x _{n} - x _{n - 1}} .$ Substitute: $x_{n + 1} = x_{n} - f (x_{n}) \cdot \frac{x _{n} - x _{n - 1}}{f ( x _{n} ) - f ( x _{n - 1} )} .$ Gain: no derivative needed, and only one new $f$ -evaluation per step (Newton needs $f$ and $f^{'}$ ). Cost: convergence order drops from $2$ to the golden ratio $φ \approx 1.618$ — still superlinear, faster than bisection, slower than a true Newton. It also inherits Newton's fragility (no bracket guarantee).

The edge case — vanishing denominator. The formula divides by $f (x_{n}) - f (x_{n - 1})$ . If the two most recent function values are equal (or nearly so), this denominator is zero (or tiny) and the step blows up or crashes with a division error. Geometrically this is a horizontal secant line: a flat line never crosses the x-axis, so "where does the secant hit zero?" has no finite answer — the exact analogue of Newton's flat-tangent failure. It happens near a local extremum, or when two iterates accidentally land at the same height.

Guard:

def secant_step(f, x_prev, x_cur, f_prev, f_cur, a, b):
    denom = f_cur - f_prev
    if denom == 0:                        # horizontal secant -> no intercept
        return (a + b) / 2                # fall back to a bracketed bisection
    return x_cur - f_cur * (x_cur - x_prev) / denom

At mastery level the same lesson from Exercise 4.1 applies: the raw secant is fragile, so production code safeguards it — check the denominator, and keep a bracket to fall back on when the secant point escapes or the denominator collapses. This denominator guard plus a bracket fallback is precisely why real solvers such as scipy.optimize.brentq never divide by a degenerate slope.

Level 5 — Mastery

Exercise 5.1 (Newton's runaway)

For $f (x) = x^{1/3}$ (the cube root, with root $x^{*} = 0$ ), show algebraically that Newton diverges from any nonzero start, and explain geometrically why. Then state which method you'd use instead.

Recall Solution

Here $f (x) = x^{1/3}$ so $f^{'} (x) = \frac{1}{3} x^{- 2/3}$ . The Newton step: $x_{n + 1} = x_{n} - \frac{x _{n}^{1/3}}{\frac{1}{3} x _{n}^{- 2/3}} = x_{n} - 3 x_{n}^{1/3} x_{n}^{2/3} = x_{n} - 3 x_{n} = - 2 x_{n} .$ So each iteration gives $x_{n + 1} = - 2 x_{n}$ : the guess doubles in magnitude and flips sign every step. From $x_{0} = 1$ : $1 \to - 2 \to 4 \to - 8 \to \dots$ — it flies away from $0$ forever.

Geometry: $f$ has an infinitely steep tangent at the root (a vertical inflection). Away from $0$ the tangent is so shallow that its x-intercept lands farther out than where you started. The figure below sketches this runaway — follow the three dashed tangents (orange, plum, teal): each one's x-intercept (the triangle marker) sits farther from the root than the point it came from.

Read the figure left-to-right: $x_{0} = 1$ produces an intercept at $- 2$ , whose tangent produces an intercept at $4$ , and so on — the markers march outward in both directions, never toward the central star at $0$ .

Fix: use bisection. With any bracket like $[- 1, 2]$ (signs $-$ and $+$ ), it marches inexorably toward $0$ . This is the parent note's headline warning: bisection is guaranteed, Newton is not.

Exercise 5.2 (Degenerate bracket)

A caller runs bisection(f, a, b) where by bad luck $f (a) = 0$ exactly. Trace what the parent's code does, and explain why the endpoint check must come before the sign-product test.

Recall Solution

Recall the parent code:

if fa == 0:
    return a
...
if fa * fb > 0:
    raise ValueError(...)

With $f (a) = 0$ : the first guard fa == 0 fires and returns a immediately — correct, it's an exact root.

Why order matters: if we had checked fa * fb > 0 first, note $f (a) \cdot f (b) = 0 \cdot f (b) = 0$ , which is neither $< 0$ nor $> 0$ . It fails the strict bracket test (> 0 is False, so no error raised) but the loop's termination (b-a)/2 < tol might never trigger a return of the true root, and worse, the sign-update logic assumes a genuine strict sign change. A zero endpoint breaks that assumption. Checking endpoints first sidesteps the whole degenerate case cleanly. This is exactly the second steel-man in the parent note.

Exercise 5.3 (Floating-point stopping)

Newton on $f (x) = x^{2} - 2$ reaches $x_{n}$ with $f (x_{n}) = 3 \times 1 0^{- 17}$ while the step $∣ x_{n + 1} - x_{n} ∣ = 1 \times 1 0^{- 11}$ . Your tolerance is $tol = 1 0^{- 12}$ . Should the loop stop? What does Floating point arithmetic tell us about pushing tolerance to $1 0^{- 20}$ ?

Recall Solution

The step $1 0^{- 11}$ is larger than $tol = 1 0^{- 12}$ , so the abs(step) < tol test is False → the loop continues one more iteration. (After that next step it will almost certainly drop below tol and stop.)

On pushing to $tol = 1 0^{- 20}$ : impossible to reliably meet. Double-precision floats carry about $15$ – $16$ significant decimal digits; the spacing between representable numbers near $x \approx 1.41$ (the machine epsilon scale, $\approx 2.2 \times 1 0^{- 16}$ times the value) is roughly $2 \times 1 0^{- 16}$ . You cannot resolve a step smaller than that gap — the loop would spin to maxit without ever satisfying $∣ s t e p ∣ < 1 0^{- 20}$ . Set tolerances at or above a few times machine epsilon; asking for more precision than the number system holds is a guaranteed non-termination bug.