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

Step 1 — What is a "root", as a picture?

WHAT. We draw a wiggly curve. The horizontal line is where height $= 0$ . A root is any place where the curve touches or crosses that zero-line.

WHY. Every root-finding method is a hunt for one specific $x$ value: the one directly below (or above) a crossing point. If we cannot see what we are hunting, the algebra later is just noise. So we anchor the whole page to this one picture: root = the x-coordinate of a crossing.

PICTURE. In the figure the curve is drawn in black; the single red dot sits exactly where it pierces the zero-line. Call that dot's horizontal position $x^{*}$ (read "x-star" — the star means the true answer we don't yet know).

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

Step 2 — What is a sign change, and why it traps a root

WHAT. Pick two points $a$ (left) and $b$ (right). Read off the two heights $f (a)$ and $f (b)$ . If one is below the zero-line (negative) and the other is above (positive), we have a sign change.

WHY. A continuous curve cannot jump from below the line to above the line without touching the line somewhere in between — that "somewhere" is a root. This is the Intermediate Value Theorem said in plain words. It is the only guarantee we get for free, and bisection is built entirely on it.

PICTURE. $f (a)$ points down (negative, black arrow below the axis); $f (b)$ points up (positive). The red segment marks the region $[a, b]$ that is now guaranteed to contain a crossing.

Step 3 — Bisection: cut the trapped region in half

WHAT. Take the midpoint $m = \frac{a + b}{2}$ and measure its height $f (m)$ . Compare the sign of $f (m)$ to the sign of $f (a)$ .

WHY. The root is somewhere in $[a, b]$ . The midpoint splits that region into two equal halves. The root lives in whichever half still shows a sign change. We keep that half, throw the other away — and the uncertainty is now exactly half what it was.

PICTURE. The full bracket is black. The midpoint $m$ is the red tick. The kept half (still opposite-signed at its ends) is shaded; the discarded half is faded.

Now let us name what shrinks. Call the length of the surviving interval its width. We do the cut over and over — first cut, second cut, third cut — so let $n$ count how many cuts we have made so far, and write $w_{n}$ for the width after those $n$ cuts. So $w_{0} = b - a$ is the starting width (zero cuts yet), $w_{1}$ is the width after one cut, and so on. This is exactly the loop running $n$ times.

Which half survives a cut? ::: The one whose two endpoint heights still have opposite signs.
Why is bisection unbeatable at reliability? ::: It never lets the root escape the shrinking bracket — the trap only tightens.

Step 4 — Newton's idea: replace the curve with its tangent

WHAT. Stand at a guess $x_{n}$ on the curve. Draw the straight line that just grazes the curve there — the tangent line. Its steepness is called $f^{'} (x_{n})$ (read "f-prime"), the slope of the curve at that spot.

WHY. Finding where a curve hits zero is hard. Finding where a straight line hits zero is grade-school algebra. So Newton's trick is a swap: pretend, just for one step, that the curve IS its tangent line, and use the line's easy zero as the next guess. Near $x_{n}$ the tangent hugs the curve, so its zero lands close to the real root.

PICTURE. Black curve, red tangent line touching at the guess $x_{n}$ . Notice the red line dives down to cross the zero-line at a new point — that crossing is our next guess.

Step 5 — Derive the update from the tangent, term by term

WHAT. Write the equation of that red tangent line and ask: where does it hit height zero?

WHY. That zero-crossing is the next guess $x_{n + 1}$ . Solving for it gives the exact Newton formula — no magic, just line-crossing algebra.

PICTURE. The same tangent, now with the two moving parts labelled: the current height $f (x_{n})$ (vertical black drop) and the horizontal jump $x_{n + 1} - x_{n}$ (red arrow along the axis).

Line through the point $(x_{n}, f (x_{n}))$ with slope $f^{'} (x_{n})$ :

$height on the line y = start height f (x_{n}) + slope f^{'} (x_{n}) horizontal walk (x - x_{n})$

We want the crossing, so set $y = 0$ and rename the special $x$ as $x_{n + 1}$ :

$0 = f (x_{n}) + f^{'} (x_{n}) (x_{n + 1} - x_{n})$

Isolate the horizontal walk (subtract, then divide by the slope):

$x_{n + 1} - x_{n} = - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$

$x_{n + 1} = x_{n} - \frac{f ( x _{n} ) how far off zero}{how steep f ^{'} ( x _{n} )}$

Step 6 — The degenerate case: a flat tangent ( $f^{'} = 0$ )

WHAT. Suppose the tangent at $x_{n}$ is horizontal — slope $f^{'} (x_{n}) = 0$ .

WHY. A horizontal line never crosses the zero-line (unless it is the zero-line). Algebraically we'd divide by zero in $\frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ . The step is undefined — the method has no next guess.

PICTURE. Red horizontal tangent shooting off to the sides, never meeting the axis; the "next guess" flies to infinity.

What goes wrong when $f^{'} (x_{n}) = 0$ ? ::: The tangent is horizontal, has no zero-crossing, and the update divides by zero — the step is undefined / infinite.

Step 7 — The other degenerate case: endpoint already a root

WHAT. In bisection a caller might hand you $[a, b]$ where $f (a) = 0$ (or $f (b) = 0$ ) exactly.

WHY. Then $f (a) \cdot f (b) = 0$ , which is not $< 0$ . The strict bracket test fails, the loop never runs, and you'd throw away a perfectly good root sitting right at the endpoint.

PICTURE. The curve grazes the zero-line exactly at $a$ — the red dot sits on the boundary, not inside.

What goes wrong if $f (a) = 0$ exactly and you skip the endpoint check? ::: The product $f (a) f (b) = 0$ is not $< 0$ , the loop never runs, and the real root at $a$ is discarded.

Step 8 — Why Newton doubles your digits (quadratic convergence)

WHAT. Let $e_{n} = x_{n} - x^{*}$ be the error — how far the guess is from the true root. We track how $e_{n + 1}$ depends on $e_{n}$ .

WHY. This is the payoff picture: Newton's error turns out to be proportional to the square of the previous error. Squaring a small number makes it tiny — that's why correct digits roughly double each step. But to earn that claim we must derive it, and to derive it we need one more tool: the second derivative.

PICTURE. Two nested red gaps: a wide gap $e_{n}$ at step $n$ , and a dramatically narrower gap $e_{n + 1} \approx (const) e_{n}^{2}$ at step $n + 1$ .

The derivation, term by term. We use the Taylor Series — the recipe that rebuilds a curve near a point out of its height, slope, and bending. Expand $f$ and $f^{'}$ about the true root $x^{*}$ , assuming $f$ is twice differentiable so that $f^{''}$ exists. Write everything in terms of the error $e_{n} = x_{n} - x^{*}$ :

$f (x_{n}) = = 0 f (x^{*}) + f^{'} (x^{*}) e_{n} + \frac{1}{2} f^{''} (x^{*}) e_{n}^{2} + \dots$

The first term is $0$ because $x^{*}$ is a root. So $f (x_{n}) \approx f^{'} (x^{*}) e_{n} + \frac{1}{2} f^{''} (x^{*}) e_{n}^{2}$ .

$f^{'} (x_{n}) = f^{'} (x^{*}) + f^{''} (x^{*}) e_{n} + \dots$

Now form the Newton correction and subtract $x^{*}$ from both sides. Since $x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ and $x_{n} - x^{*} = e_{n}$ :

$e_{n + 1} = e_{n} - \frac{f ^{'} ( x ^{*} ) e _{n} + \frac{1}{2} f ^{''} ( x ^{*} ) e _{n}^{2}}{f ^{'} ( x ^{*} ) + f ^{''} ( x ^{*} ) e _{n}}$

Now the key move — WHY the leading terms cancel. Factor $f^{'} (x^{*})$ out of top and bottom of the fraction so we can see its shape clearly. Let $r = \frac{f ^{''} ( x ^{*} )}{f ^{'} ( x ^{*} )}$ (a fixed number: bending divided by slope). Then

$\frac{f ( x _{n} )}{f ^{'} ( x _{n} )} = e_{n} \cdot \frac{1 + \frac{1}{2} r e _{n}}{1 + r e _{n}} .$

The messy part is $\frac{1 + \frac{1}{2} r e _{n}}{1 + r e _{n}}$ . For a small $e_{n}$ we expand $\frac{1}{1 + r e _{n}}$ as a geometric series $1 - r e_{n} + (r e_{n})^{2} - \dots$ (this is the binomial/geometric expansion; it is valid because $r e_{n}$ is tiny, so squared-and-higher terms are negligible). Multiplying out and keeping only up to $e_{n}$ :

$\frac{1 + \frac{1}{2} r e _{n}}{1 + r e _{n}} = (1 + \frac{1}{2} r e_{n}) (1 - r e_{n} + \dots) = 1 - \frac{1}{2} r e_{n} + \dots$

So the whole correction is

$\frac{f ( x _{n} )}{f ^{'} ( x _{n} )} = e_{n} (1 - \frac{1}{2} r e_{n} + \dots) = e_{n} - \frac{1}{2} r e_{n}^{2} + \dots$

Subtract this from $e_{n}$ — and here the $e_{n}$ terms cancel exactly, which is the whole point: the $+ e_{n}$ and the $- e_{n}$ annihilate, leaving only the squared piece:

$e_{n + 1} = e_{n} - (e_{n} - \frac{1}{2} r e_{n}^{2} + \dots) = \frac{1}{2} r e_{n}^{2} + \dots$

$e_{n + 1} \approx fixed bending constant \frac{f ^{''} ( x ^{*} )}{2 f ^{'} ( x ^{*} )} error, squared e_{n}^{2}$

Everything we dropped (the " $\dots$ ") is proportional to $e_{n}^{3}$ or smaller — for tiny $e_{n}$ those are utterly negligible next to $e_{n}^{2}$ , which is why we may throw them away. The boxed line quietly assumes $f^{'} (x^{*}) \neq = 0$ (otherwise $r$ divides by zero — Newton's flat-spot disease from Step 6, now at the root itself) and $f$ twice differentiable (otherwise $f^{''}$ has no meaning and the expansion collapses).

If $e_{n} = 1 0^{- 3}$ (3 good digits), then $e_{n}^{2} = 1 0^{- 6}$ — 6 good digits. 3 → 6 → 12, matching the parent's worked example $x_{0} = 2$ for $2$ . Compare bisection: it multiplies the error by $\frac{1}{2}$ each step, buying only one bit — this is the linear-vs-quadratic speed gap, and why scipy.optimize's brentq blends a bracket (safety) with fast interpolation (the Secant method idea).

The one-picture summary

One canvas, both methods on the same curve: bisection's shrinking red bracket crawls in from both sides; Newton's red tangents leap toward the root. Slow-but-safe versus fast-but-fragile.

Recall Feynman retelling — say it back in plain words

A root is just where a curve touches the zero-line. If the curve is below the line at one point and above it at another, it had to cross somewhere between — that's a trap for the root. Bisection exploits the trap: check the middle, keep the half that still straddles the line, and the trap shrinks by half every single time. Dead slow, never fails.

Newton is impatient. It stands on the curve, draws the straight line that grazes it there, and slides down that line to where the line hits zero — because a straight line's zero is trivial to compute. That landing spot is the new guess. The formula "current height ÷ steepness, stepped backwards" is just that line-crossing solved on paper. When the slope is healthy, each jump roughly squares the error (because the only thing the tangent misses is the curve's bending, measured by $f^{''}$ ), so the number of correct digits doubles — but if the slope goes flat, the line never meets the axis, the step blows up, and Newton runs away. That's the whole story: bisection tightens a trap; Newton rides a tangent; one is safe, the other is fast, and the pros glue them together.

Flashcards

Geometrically, what is the Newton next-guess

x_{n + 1}

The point where the tangent line at

x_{n}

crosses the zero-line (the x-intercept of the tangent).

In the Newton formula, what does dividing by

f^{'} (x_{n})

do to the step?

A steep slope gives a small step; a flat slope gives a huge (dangerous) step — the step is height ÷ steepness.

Why does a sign change

f (a) f (b) < 0

guarantee a root?

A continuous curve can't go from below the zero-line to above it without touching it — the Intermediate Value Theorem.

What breaks Newton geometrically when

f^{'} (x_{n}) = 0

The tangent is horizontal, so it never crosses the zero-line; the update divides by zero and the guess flies off.

Why must bisection check endpoints before looping?

f (a) = 0

f (b) = 0

exactly, the product

f (a) f (b) = 0

is not

< 0

, so the strict bracket test fails, the loop is skipped, and a real root sitting on the boundary is silently discarded; returning the endpoint first prevents this.

Why does Newton "double the digits"?

Its error obeys

e_{n + 1} \approx \frac{f ^{''} ( x ^{*} )}{2 f ^{'} ( x ^{*} )} e_{n}^{2}

; squaring a small error roughly doubles the number of correct digits.

What two assumptions make Newton's quadratic convergence hold?

f^{'} (x^{*}) \neq = 0

(no flat spot at the root) and

f

twice differentiable (so

f^{''}

exists).