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

This page is self-contained: everything it needs — the guard tests, the tangent formula, the error argument — is restated here in full before it is used. When a word is new, we rebuild it from zero.

The scenario matrix

Root-finding has a small number of situations that behave differently. Here is the full list. Each row's "Example" column names the section that works it (the labels C1…C10 match the headings below exactly).

#	Case class	What is special	Which method	Example
C1	Clean bracket, opposite signs	textbook bisection	bisection	C1
C2	Sign convention: which half survives	quadrant/sign bookkeeping	bisection	C2
C3	Endpoint is exactly a root	degenerate: $f (a) = 0$	bisection	C3
C4	Newton, good start, $f^{'} \neq = 0$	quadratic bliss	Newton	C4
C5	Newton near a flat spot ( $f^{'} \to 0$ )	huge/undefined step	Newton	C5
C6	Newton that diverges / cycles	limiting bad behaviour	Newton	C6
C7	Double root ( $f = f^{'} = 0$ together)	convergence slows to linear	Newton	C7
C8	Real-world word problem	units, modelling	either	C8
C9	Exam twist: no derivative given	pick the robust engine	bisection	C9
C10	Invalid bracket ( $f (a) f (b) > 0$ ), and midpoint hits root	error case + early exit	bisection	C10

We will meet all three, plus the pure error cases.

C1 — Clean bracket, textbook bisection

Worked example Find

$5$ as the root of $f (x) = x^{2} - 5$ on $[2, 3]$ . Forecast: guess where $5$ sits, and guess how many halvings you need for 3 decimals. (Answer near $2.236$ ; roughly $lo g_{2} (1/0.001) \approx 10$ steps.)

Step 1 — Check the bracket. $f (2) = 4 - 5 = - 1$ , $f (3) = 9 - 5 = 4$ . Why this step? Bisection is only legal when $f (a) f (b) < 0$ ; here $(- 1) (4) = - 4 < 0$ ✓ — a sign change, so by the Intermediate Value Theorem a root is trapped inside.

Step 2 — Midpoint. $m = \frac{2 + 3}{2} = 2.5$ , $f (2.5) = 6.25 - 5 = 1.25 > 0$ . Why? The midpoint splits the uncertainty exactly in half — that is the one move that guarantees each step buys one bit (one halving of uncertainty, as defined above).

Step 3 — Keep the half that still changes sign. $f (2) = - 1 < 0$ and $f (2.5) = + 1.25 > 0$ : the sign flip is on the left half. Keep $[2, 2.5]$ . Why? The root lives where the endpoints still disagree in sign.

Step 4 — Repeat. $m = 2.25$ , $f = 0.0625 > 0$ → keep $[2, 2.25]$ . $m = 2.125$ , $f = - 0.484 < 0$ → keep $[2.125, 2.25]$ . Why does each repeat help? Every step replaces one endpoint by the midpoint, so the interval width goes $1 \to 0.5 \to 0.25 \to 0.125 = \frac{1}{2 ^{n}}$ — exactly halved each time, adding one bit of precision per step (linear convergence with ratio $\frac{1}{2}$ ). The figure

shows this as a stack of coloured bars: the top bar is

[2, 3]

; each bar below it is a sub-interval that sits inside the one above and is half its length (

[2, 2.5]

, then

[2, 2.25]

, then

[2.125, 2.25]

), and every bar straddles the red dashed vertical line at

x = 5 \approx 2.236

— so you can watch the root stay trapped while the bars close in on it.

Verify: the true root is $5 = 2.2360679 \dots$ ; after 4 steps our bracket $[2.125, 2.25]$ indeed contains it, width $0.125 = \frac{1}{2 ^{3}}$ . ✓

C2 — Sign bookkeeping: which half survives

Worked example

$f (x) = x^{3} - x - 2$ on $[1, 2]$ : track the stored sign carefully. Forecast: cubics can wiggle. Will this bracket keep pointing at the same root? (Yes — there is only one real root here, near $1.52$ .)

Step 1 — Bracket. $f (1) = 1 - 1 - 2 = - 2$ , $f (2) = 8 - 2 - 2 = 4$ . Product $- 8 < 0$ ✓. Store $f_{a} = - 2$ (negative).

Step 2 — Midpoint. $m = 1.5$ , $f (1.5) = 3.375 - 1.5 - 2 = - 0.125$ . Why store $f_{a}$ and compare to $f_{m}$ ? Compare stored $f_{a} = - 2$ against $f_{m} = - 0.125$ : same sign (both negative), so the crossing is not in the left half. Storing $f_{a}$ (rather than recomputing $f (a)$ each loop) also saves function calls.

What "mixing conventions" concretely means. There are two consistent ways to decide which half to keep: (A) "keep the half whose endpoints have a sign change" — i.e. keep the left half $[a, m]$ when $f_{a} \cdot f_{m} < 0$ ; or (B) the mirror test "keep the right half $[m, b]$ when $f_{m} \cdot f_{b} < 0$ ". Each is correct on its own. The bug is using test (A) to decide but then updating the endpoint as if you had used test (B) — e.g. concluding "sign change is on the left" yet moving $a$ up to $m$ instead of moving $b$ down to $m$ . That single mismatch keeps the half that does not contain the root, and the next iteration silently converges to the wrong place (or hits the raise when the false bracket loses its sign change). The safe rule: pick one stored value ( $f_{a}$ ), compare it to $f_{m}$ , and update the matching-sign endpoint — one convention, start to finish.

Step 3 — Move the left endpoint up. Because $f_{a} \cdot f_{m} > 0$ , the root is in $[1.5, 2]$ . Set $a = 1.5, f_{a} = - 0.125$ . Why? We update the endpoint whose sign matched ( $a$ , since $f_{a}$ and $f_{m}$ agree), preserving one valid bracket.

Step 4 — Continue. $m = 1.75$ , $f = 5.359 - 1.75 - 2 = 1.609 > 0$ → now $f_{a} = - 0.125$ and $f_{m} = + 1.609$ disagree → keep $[1.5, 1.75]$ .

Verify: the real root of $x^{3} - x - 2$ is $1.52137 \dots$ , which lies in $[1.5, 1.75]$ ✓. The stored-sign convention never lost it.

C3 — Degenerate: an endpoint is already the root

Worked example

$f (x) = x^{2} - 4$ on $[2, 5]$ — someone handed you a lucky endpoint. Forecast: $f (2) = 0$ . Does the standard bracket test even run? (No! $f (2) f (5) = 0$ , not $< 0$ .)

Step 1 — The guard tests (stated in full here). Any correct bisection opens with three guards, in this order:

fa, fb = f(a), f(b)
if fa == 0: return a       # endpoint already an exact root
if fb == 0: return b       # other endpoint already an exact root
if fa * fb > 0:            # STRICTLY > 0, not >= 0
    raise ValueError("f(a) and f(b) must have opposite signs")

Why is the reject test > 0 and not >= 0? A product equal to zero means one endpoint is a root — that is not an error, it is a win. So > 0 rejects only the truly no-sign-change case, while the two == 0 checks above it catch the exact-root endpoints first. Why this exact order? The == 0 checks must come before the product test, so a zero endpoint is returned rather than falling through.

Step 2 — Trace our inputs. $f (2) = 0$ , so the very first guard if fa == 0 fires and returns a. Why order matters: had we reached fa*fb, we'd get $0 \cdot 21 = 0$ , which is not > 0, so no error would raise — but the loop would then run and could discard the exact zero. Checking fa == 0 first is what saves us.

Step 3 — Return. We return $x^{*} = 2$ immediately, zero iterations.

Verify: $f (2) = 2^{2} - 4 = 0$ ✓ exact. Skipping the endpoint check on $[2, 5]$ would waste evaluations or lose the root.

C4 — Newton, good start, quadratic bliss

Worked example Newton on

$f (x) = x^{2} - 2$ , $f^{'} (x) = 2 x$ , from $x_{0} = 1.5$ . Forecast: count correct digits after each step — do they roughly double? (Yes: this is the hallmark of quadratic convergence.)

Step 1 — The update (derived here, not borrowed). The tangent line to $f$ at $x_{n}$ is $y = f (x_{n}) + f^{'} (x_{n}) (x - x_{n})$ . Setting $y = 0$ and solving for $x$ gives the Newton step $x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ — the x-intercept of that tangent. For this $f$ it simplifies to the Babylonian rule $x_{n + 1} = \frac{x _{n}}{2} + \frac{1}{x _{n}}$ . Why this simplification? $x - \frac{x ^{2} - 2}{2 x} = x - \frac{x}{2} + \frac{1}{x}$ .

Step 2 — Iterate. The figure

shows the blue parabola

f (x) = x^{2} - 2

, and at each guess a yellow straight tangent line; follow each tangent down to where it crosses the horizontal axis (a red dot) to read off the next guess.

$x_{1} = \frac{1.5}{2} + \frac{1}{1.5} = 0.75 + 0.6667 = 1.41667$ (3 good digits).
$x_{2} = \frac{1.41667}{2} + \frac{1}{1.41667} = 0.708333 + 0.705882 = 1.414216$ (6 digits).

Step 3 — Why so fast (with the second derivative made explicit). Write the error $e_{n} = x_{n} - x^{*}$ where $x^{*} = 2$ . The convergence rate depends on the second derivative $f^{''}$ , which measures how the slope itself changes — the curve's bending. Here $f (x) = x^{2} - 2$ , so $f^{'} (x) = 2 x$ and $f^{''} (x) = 2$ (a constant: the parabola bends the same everywhere). The standard error bound is $e_{n + 1} \approx \frac{f ^{''} ( x ^{*} )}{2 f ^{'} ( x ^{*} )} e_{n}^{2} .$ Plug in $f^{''} (x^{*}) = 2$ and $f^{'} (x^{*}) = 22$ : the constant is $\frac{2}{2 \cdot 2 2} = \frac{1}{2 2} \approx 0.354$ . Because $f^{'} (x^{*}) = 22 \neq = 0$ , this bound holds and the error is proportional to $e_{n}^{2}$ — it squares each step, so the number of correct digits roughly doubles.

Verify: $2 = 1.41421356 \dots$ ; $x_{2} = 1.414216$ matches to 5 places ✓. Digit count went $3 \to 6$ : doubling confirmed. Check of the constant: $e_{1} = 1.5 - 2 \approx 0.0858$ , $e_{2} = x_{2} - 2 \approx 0.0000024$ , and $e_{2} / e_{1}^{2} \approx 0.33$ — close to the predicted $0.354$ . ✓

C5 — Newton near a flat spot ( $f^{'} \to 0$ )

Worked example Newton on

$f (x) = x^{2} - 2$ but starting at $x_{0} = 0.001$ (almost the flat bottom-ish region of the slope). Forecast: the slope $f^{'} (0.001) = 0.002$ is tiny. Will the first step be small or gigantic? (Gigantic — dividing by a near-zero slope launches you far away.)

Step 1 — Compute the step. $f (0.001) = 0.00 1^{2} - 2 = - 1.999999$ , $f^{'} (0.001) = 2 (0.001) = 0.002$ . Step $= \frac{- 1.999999}{0.002} = - 999.9995$ . Why so large? The tangent is nearly horizontal, so its x-intercept is far off — a horizontal line meets the axis at infinity.

Step 2 — Jump. $x_{1} = 0.001 - (- 999.9995) = 1000.0005$ . See

: the blue curve carries a shallow yellow tangent at the near-zero-slope point, and a red arrow shows the next guess flung far to the right along the axis.

Step 3 — Recovery. From $x_{1} = 1000$ the slope is now huge and honest, so Newton does eventually come back — but it wasted iterations. If $x_{0}$ had been exactly $0$ , then $f^{'} (0) = 0$ and the code raises ZeroDivisionError — a flat tangent points nowhere.

Verify: step magnitude $∣ - 999.9995 ∣ = 999.9995$ ✓, and $x_{1} = 1000.0005$ ✓. The lesson: near a flat spot the step size blows up, the opposite of the tiny confident steps in C4.

C6 — Newton that diverges / cycles (limiting disaster)

Worked example Newton on

$f (x) = x^{1/3}$ (cube root), starting anywhere except the root $x^{*} = 0$ . Forecast: the only root is $0$ . Will Newton walk toward it or away? (Away — it diverges geometrically.)

Step 1 — Derivative. $f (x) = x^{1/3}$ , so $f^{'} (x) = \frac{1}{3} x^{- 2/3}$ . Why check $f^{'}$ ? Newton divides by it; here it grows the wrong way.

Step 2 — The update simplifies. $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}$ . Why is this catastrophic? Each step multiplies $x$ by $- 2$ : it flips sign and doubles the distance from the root.

Step 3 — Iterate from $x_{0} = 1$ . $x_{1} = - 2$ , $x_{2} = 4$ , $x_{3} = - 8$ , … See

: the guess dots (red) sit on the axis and yellow curved arrows hop each guess to the next —

1 \to - 2 \to 4 \to - 8

— leaping outward left, right, farther left, never toward the green root at

0

Verify: $x_{n + 1} = - 2 x_{n}$ gives $∣ x_{n} ∣ = 2^{n}$ , which $\to \infty$ ✓. Bisection on $[- 1, 1]$ (with $f (- 1) = - 1 < 0$ , $f (1) = 1 > 0$ ) would trap $0$ safely — the eternal robustness-vs-speed trade-off.

C7 — Double root: quadratic convergence breaks down

Worked example Newton on

$f (x) = (x - 3)^{2}$ , a root of multiplicity two, from $x_{0} = 5$ . Forecast: at $x^{*} = 3$ , both $f (3) = 0$ and $f^{'} (3) = 0$ . Does Newton still double its digits? (No — a double root demotes it to linear, halving the error only.)

Step 1 — Update. $f (x) = (x - 3)^{2}$ , $f^{'} (x) = 2 (x - 3)$ . So $x_{n + 1} = x_{n} - \frac{( x _{n} - 3 ) ^{2}}{2 ( x _{n} - 3 )} = x_{n} - \frac{x _{n} - 3}{2} = \frac{x _{n} + 3}{2}$ . Why does this matter? The error obeys $e_{n + 1} = \frac{1}{2} e_{n}$ — linear, not quadratic.

Step 2 — Iterate. $x_{0} = 5$ (error 2) → $x_{1} = 4$ (error 1) → $x_{2} = 3.5$ (error 0.5) → $x_{3} = 3.25$ (error 0.25). Each step halves the error, exactly like bisection.

Step 3 — Why the slowdown? The quadratic bound $e_{n + 1} \approx \frac{f ^{''} ( x ^{*} )}{2 f ^{'} ( x ^{*} )} e_{n}^{2}$ from C4 assumes $f^{'} (x^{*}) \neq = 0$ . At a double root $f^{'} (x^{*}) = 0$ , that formula divides by zero and is invalid; the true rate collapses to linear. (For multiplicity $m$ , both $f$ and its first $m - 1$ derivatives vanish, and the linear rate becomes $1 - \frac{1}{m}$ .)

Verify: $x_{1} = \frac{5 + 3}{2} = 4$ ✓, $x_{2} = \frac{4 + 3}{2} = 3.5$ ✓, $x_{3} = 3.25$ ✓. Errors $2, 1, 0.5, 0.25$ — ratio $\frac{1}{2}$ , linear ✓.

C8 — Real-world word problem (units matter)

Worked example A projectile's height is

$h (t) = 20 t - 4.9 t^{2}$ metres, with $t$ in seconds. When does it hit the ground ( $h = 0$ , other than launch)? Forecast: launch is $t = 0$ ; landing should be a few seconds later (guess near $4$ s).

Step 1 — Set up the root problem. We want $h (t) = 0$ , i.e. $t (20 - 4.9 t) = 0$ . Why factor? One root is the trivial $t = 0$ ; the physical landing is the other factor's root.

Step 2 — Bracket the landing. $h (3) = 60 - 44.1 = 15.9 > 0$ , $h (5) = 100 - 122.5 = - 22.5 < 0$ : sign change on $[3, 5]$ ✓. Why bisection here? A clean bracket exists and we want a guaranteed answer with correct units.

Step 3 — Squeeze.

$m = 4$ : $h (4) = 80 - 78.4 = 1.6 > 0$ . Why keep $[4, 5]$ ? $h (4) > 0$ and $h (5) < 0$ still disagree in sign, so the crossing is on the right half.
$m = 4.5$ : $h (4.5) = 90 - 99.225 = - 9.225 < 0$ . Why keep $[4, 4.5]$ ? Now $h (4) > 0$ and $h (4.5) < 0$ disagree, so the root is in the left half. Converging toward $t^{*} = 20/4.9$ .

Verify (algebra + units): solving $20 - 4.9 t = 0$ gives $t^{*} = 20/4.9 = 4.0816 \dots$ seconds, which sits in $[4, 4.5]$ ✓. Units: $[m\cdots^{- 1}] / [m\cdots^{- 2}] = [s]$ ✓ — the answer is a time, as it must be.

C9 — Exam twist: no derivative supplied

Worked example "Find a root of

$f (x) = e^{x} + x$ on $[- 1, 0]$ . You are not given $f^{'}$ ." Which engine, and why? Forecast: Newton needs $f^{'}$ ; can you get away without differentiating? (Yes — use bisection, or the derivative-free Secant method.)

Step 1 — Read the constraint. No $f^{'}$ ⇒ Newton is off the table unless you differentiate by hand. Why? The Newton update divides by $f^{'} (x_{n})$ ; without it there is nothing to divide by.

Step 2 — Bracket. $f (- 1) = e^{- 1} - 1 = 0.3679 - 1 = - 0.6321 < 0$ , $f (0) = 1 + 0 = 1 > 0$ : sign change ✓. Why this is enough? Bisection needs only $f$ values and a sign flip — no calculus.

Step 3 — Squeeze. $m = - 0.5$ : $f = e^{- 0.5} - 0.5 = 0.6065 - 0.5 = 0.1065 > 0$ → keep $[- 1, - 0.5]$ . $m = - 0.75$ : $f = 0.4724 - 0.75 = - 0.2776 < 0$ → keep $[- 0.75, - 0.5]$ . Converging near $- 0.567$ .

Verify: the true root of $e^{x} + x = 0$ is $x^{*} = - 0.567143 \dots$ (the negative Omega constant), which lies in $[- 0.75, - 0.5]$ ✓. Exam-safe choice: bisection, because it demands zero derivatives.

C10 — Invalid bracket, and a midpoint that lands on the root

Worked example Two edge behaviours of the bisection loop itself: (a)

$f (a) f (b) > 0$ handed in as a "bracket", and (b) a midpoint that is exactly a root, needing the early exit if fm == 0: return m. Forecast: what should the code do in each case? (a) refuse with an error; (b) stop instantly and return the midpoint.

Step 1 — Invalid bracket (a). Take $f (x) = x^{2} - 2$ on $[2, 3]$ . $f (2) = 2 > 0$ , $f (3) = 7 > 0$ : product $14 > 0$ . Why refuse? No sign change means the Intermediate Value Theorem gives no guarantee of a root inside — the guard if fa*fb > 0: raise ValueError (stated in full in C3) fires. Continuing would be meaningless: bisection cannot invent a crossing that is not bracketed.

Step 2 — Midpoint hits the root (b). Take $f (x) = x^{2} - 4$ on $[1, 3]$ . $f (1) = - 3 < 0$ , $f (3) = 5 > 0$ : valid bracket. The midpoint is $m = \frac{1 + 3}{2} = 2$ , and $f (2) = 0$ exactly. Why an early exit? The loop body carries the guard if fm == 0 or (b - a)/2 < tol: return m. Without the fm == 0 test, the code would compare fa*fm — but $f_{a} \cdot 0 = 0$ is neither <0 nor handled, so it would fall into the else branch and walk away from the exact root. The early exit catches this lucky bullseye.

Step 3 — Contrast. Case (a) returns no answer (an error — the input was illegal); case (b) returns the exact answer in one step. Both are handled by two tiny guards; this example shows precisely when each fires.

Verify: (a) $f (2) f (3) = 2 \cdot 7 = 14 > 0$ ✓ so raise triggers. (b) $f (2) = 2^{2} - 4 = 0$ ✓ exact, so if fm == 0: return 2 fires — and the true root of $x^{2} - 4$ on $[1, 3]$ is indeed $2$ . ✓

Recall Quick self-test across the matrix

Which cell breaks Newton's quadratic convergence even with a perfect start? ::: C7 — a double root, because $f^{'} (x^{*}) = 0$ demotes it to linear. Why does starting at $x_{0} = 0.001$ (C5) send Newton far away? ::: The slope $f^{'}$ is near zero, so the tangent is nearly flat and its x-intercept is enormous — a giant step. On $f (x) = x^{1/3}$ (C6), what does the Newton update reduce to? ::: $x_{n + 1} = - 2 x_{n}$ , doubling the distance and flipping sign each step — pure divergence. Given no derivative (C9), name two safe options. ::: Bisection or the secant method — both need only $f$ values. What two guards handle the bisection edge cases in C10? ::: if fa*fb > 0: raise (no valid bracket) and if fm == 0: return m (midpoint is exactly a root). What does "one bit of precision" mean for bisection? ::: One halving of the uncertainty interval — a single yes/no answer about which half hides the root. For a root of multiplicity $m$ , which derivatives vanish there? ::: $f = f^{'} = \dots = f^{(m - 1)} = 0$ but $f^{(m)} \neq = 0$ .

See also the parent note, Fixed-point iteration for another view of iteration, scipy.optimize for production tooling, and Floating point arithmetic for why f(m)==0 almost never happens exactly.