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

Before you can read a single line of the parent note, you need to own every symbol it throws at you. This page builds each one from absolute zero, in an order where each idea leans on the one before it. Nothing here assumes you've seen the notation.

1. What is a function $f$ ? What does $f (x)$ mean? What is $y$ ?

Picture a curve drawn on graph paper. The horizontal axis carries the input $x$ ; the vertical axis carries the height $y = f (x)$ . Every input $x$ picks out one height on the curve.

Figure s01 — "A function turns an input into one height." A cyan curve $y = f (x)$ on blueprint grid. An amber input value $x$ on the horizontal axis is traced up with a dashed line to the curve, then across to its height $y = f (x)$ on the vertical axis — showing the single input-to-output mapping, and the white line $y = 0$ .

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

2. What is a root $x^{*}$ ? Reading the star

On the graph, a root is a point where the curve touches or crosses the horizontal axis — because the axis is exactly the line $y = 0$ ("height $= 0$ ," from §1).

Figure s02 — "A root is where the curve meets the line $y = 0$ ." A cyan curve crossing the white horizontal axis at two amber dots; each dot is labelled $x^{*}$ with $f (x^{*}) = 0$ , showing that a root is exactly a crossing point of the curve and the zero line.

3. Subscripts: $x_{0}, x_{1}, x_{n}, x_{n + 1}$

4. Continuity — the "no gaps, no jumps" property

Figure s05 — "Continuity vs a jump." Left: a smooth cyan curve drawn in one unbroken stroke (continuous — pen never lifts). Right: an amber curve that leaps from below the axis straight to above it — an open circle below and a filled circle above mark the jump, with an arrow noting "no crossing here," showing how a discontinuity lets the curve skip over $y = 0$ without ever touching it.

5. The interval $[a, b]$ , its endpoints, and the product $f (a) \cdot f (b)$

Figure s03 — "Opposite signs bracket a root." A cyan straight-through curve on the grid; amber dots mark the left endpoint $a$ with $f (a) < 0$ (below the white axis) and the right endpoint $b$ with $f (b) > 0$ (above it). The shaded band between them and a white dot on the axis show the root is trapped inside $[a, b]$ whenever the endpoint heights have opposite signs.

6. The absolute value $∣ x ∣$ and the idea of "error"

7. What is a slope, and the derivative $f^{'} (x)$ ?

Figure s04 — "The derivative is the slope of the tangent line." A cyan curve with an amber tangent line touching it at a point $x = p$ . A white right-triangle under the tangent labels its "rise" and "run," and an annotation reads $f^{'} (p) = rise / run$ — defining the derivative as the steepness of the curve at that point.

8. The fraction $\frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ — putting it together

9. Logarithm base 2: $lo g_{2}$ , the ceiling $⌈ \cdot ⌉$ , and the bisection step count

Formula Deriving the bisection step count

Bisection starts with interval width $b - a$ and halves it every step, so after $n$ steps the width is $w_{n} = \frac{b - a}{2 ^{n}} .$ The midpoint sits within half a width of the true root, so the error is at most $error \leq \frac{w _{n}}{2} = \frac{b - a}{2 ^{n + 1}} .$ To guarantee this is below our tolerance $ε$ we need

\;\Longrightarrow\; 2^{\,n+1} \ge \frac{b-a}{\varepsilon} \;\Longrightarrow\; n+1 \ge \log_2\!\frac{b-a}{\varepsilon} \;\Longrightarrow\; n \ge \log_2\!\frac{b-a}{\varepsilon} - 1.$$ The last step *undoes* the power of 2 by taking $\log_2$ — that's exactly the question "how many halvings?" made precise. But $n$ counts whole loop iterations, so it must be a **whole number**. The real bound gives a value like $32.2$; you can't stop mid-step, so you **round up** with the ceiling: $$\boxed{\; n = \left\lceil \log_2\!\frac{b-a}{\varepsilon} - 1 \right\rceil \;}$$ Rounding *up* (not down) guarantees we actually reach the tolerance — one fewer step would leave the error above $\varepsilon$.

Prerequisite map

The diagram below shows how these foundations feed the topic: the plain function idea splits into two branches (sign-tracking → bisection, slope-tracking → Newton), and both feed the parent topic Root-Finding from Scratch.

Equipment checklist

Test yourself — cover the right side.

I can read

f (x)

aloud and say what it means

"f of x": feed input

x

to machine

f

, read the output height off the curve.

I know what

y

and the line

y = 0

are

y

is the vertical coordinate (the height

f (x)

);

y = 0

is the horizontal axis, all points at height zero.

I know what

x^{*}

The exact true root — the input where

f (x^{*}) = 0

; the star just marks "the real answer," distinct from guesses.

I can decode the subscripts in

x_{n}

and

x_{n + 1}

Labels for "the current guess" and "the next guess"; a subscript is a name tag, not a power.

I can define a continuous function on

[a, b]

One you can draw across the entire closed interval

[a, b]

without lifting the pen — no jumps or holes anywhere in it.

I know what

[a, b]

and its endpoints are

The interval of inputs from left endpoint

a

to right endpoint

b

;

f (a), f (b)

are the heights there.

I know what

f (a) \cdot f (b) < 0

tells me — and its edge case

Opposite signs at the endpoints, so a continuous curve crosses zero inside; but if an endpoint is itself a root then

f (a) \cdot f (b) = 0

, so use

\leq 0

or check endpoints first.

I can state the Intermediate Value Theorem in words

f

is continuous on all of

[a, b]

and goes from below the axis to above it, it must pass through zero somewhere in between.

I know what

∣ e_{n} ∣

and

ε

mean

∣ e_{n} ∣

is the size of the gap between guess and true root;

ε

is the "close enough" tolerance where we stop.

I can explain slope and the tangent line

Slope = rise over run; the tangent is the straight line that matches the curve's direction at a point.

I know what

f^{'} (x)

is and where it comes from

The derivative: another machine giving the curve's steepness (tangent slope) at

x

; e.g. for

x^{2} - 2

it is

2 x

I know the precondition of the Newton step

The step

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

is only valid when

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

; a flat tangent means divide-by-zero and no crossing.

I understand why

f (x_{n}) / f^{'} (x_{n})

appears in Newton

It's height divided by slope = the horizontal run along the tangent needed to reach the axis.

I can derive the bisection step count with the ceiling

Width halves to

(b - a) / 2^{n}

; error

\leq ε

gives

n = ⌈ lo g_{2} \frac{b - a}{ε} - 1 ⌉

(round up, since steps are whole numbers).