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

True or false — justify

Bisection is guaranteed to find a root of any function on

[a, b]

once

f (a) f (b) < 0

False. It needs

f

continuous on

[a, b]

; the guarantee comes from the Intermediate Value Theorem, which requires no jumps. On

f (x) = 1/ x

over

[- 1, 1]

the signs flip but there is no root — the "crossing" is a vertical asymptote.

f (a) f (b) > 0

then there is definitely no root in

[a, b]

False. It only means bisection cannot start. A parabola like

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

[- 2, 2]

has

f (- 2) f (2) = 2 \cdot 2 > 0

yet holds two roots — an even number of crossings hides the sign change.

Newton-Raphson always needs fewer

f

-evaluations than bisection to hit a tolerance.

False in cost, even when true in step count. Each Newton step costs one

f

and one

f^{'}

evaluation, so a single iteration is roughly twice as expensive; the win only shows once quadratic convergence kicks in near the root.

Quadratic convergence means the error is squared each step, so the error shrinks no matter where you start.

False. The

e_{n + 1} \approx C e_{n}^{2}

law is a local statement — it only holds once

e_{n}

is small. Far away,

e_{n}^{2}

can be bigger than

e_{n}

, so the "squaring" makes things worse, not better.

Halving the tolerance

ε

costs bisection one extra iteration.

True. Steps scale like

lo g_{2} \frac{b - a}{ε}

; dividing

ε

by 2 adds exactly

lo g_{2} 2 = 1

to that count — one more bit of accuracy per step.

Newton's method is a special case of Fixed-point iteration.

True. Writing

g (x) = x - \frac{f ( x )}{f ^{'} ( x )}

, Newton is just iterating

x_{n + 1} = g (x_{n})

; a root of

f

is a fixed point of

g

, and

g^{'} (x^{*}) = 0

is exactly why it converges quadratically.

The Secant method is just Newton with the derivative replaced by a slope through two points.

True. It swaps

f^{'} (x_{n})

for

\frac{f ( x _{n} ) - f ( x _{n - 1} )}{x _{n} - x _{n - 1}}

, needing no derivative; the price is slower (order

\approx 1.618

, not 2) convergence.

Bisection's convergence rate depends on the shape of

f

False. The bracket width halves every step regardless of

f

— the rate is always exactly

\frac{1}{2}

. Only the starting width

b - a

and where the root sits inside affect the constant, not the ratio.

Spot the error

"I'll store fa once, then each loop check if f(a)*f(m) < 0." — what's wrong?

You recompute f(a) every iteration (wasted calls) — and worse, after you move a, that fresh f(a) is a new value while your logic may still assume the old sign. Compare the stored fa against fm and update fa only when you keep the left endpoint.

"My bisection returned the midpoint even though f(a)f(b)>0, so it still works."

A red flag. With no sign change the returned midpoint is meaningless — there may be no root at all. The routine must raise on a bad bracket, not silently hand back a number.

"Newton diverged, so my derivative formula must be wrong." — is that the only cause?

No. Even a correct

f^{'}

diverges if

x_{0}

is far away, if

f^{'} (x_{n}) \approx 0

(a giant step), or if the iterates cycle. Check the starting guess and flat-derivative cases before suspecting an algebra bug.

"To stop Newton I test f(x) == 0."

Floating point arithmetic almost never lands exactly on 0, so this rarely triggers and you loop to maxit. Test abs(step) < tol (or abs(f(x)) < tol) — a neighbourhood, not an exact hit.

"Bisection stops when f(m) == 0, so the (b-a)/2 < tol check is redundant."

Backwards. The exact-zero case is the rare one; the width test is what normally ends the loop. Remove it and bisection runs to maxit on almost every real problem.

"I passed bisection(f, 2, 1, ...) (a>b) and got garbage."

The width

b - a

is now negative, so (b-a)/2 < tol is true immediately and you exit on step zero. Bisection assumes

a < b

; either sort the endpoints or document the precondition.

"Newton on

x^{2} - 2

starting at

x_{0} = 0

is fine, it's a nice smooth function."

f^{'} (0) = 2 \cdot 0 = 0

, so the very first step divides by zero — the tangent is horizontal and never meets the x-axis. Smoothness doesn't save you; a zero derivative does you in.

Why questions

Why does bisection get one bit of accuracy per step, no more, no less?

Each step halves the interval, and halving means the leading uncertain binary digit becomes known — exactly one bit. This ties bisection conceptually to Binary search, which also discards half the space each comparison.

Why does Newton need

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

at the root for quadratic convergence?

The error law carries

\frac{f ^{''} ( x ^{*} )}{2 f ^{'} ( x ^{*} )}

; if

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

this constant blows up. Geometrically the root is a tangent touch (a repeated root), the tangent line is nearly flat, and convergence degrades to merely linear.

Why is Taylor Series the right tool to explain Newton's speed, rather than just drawing the tangent?

The tangent picture shows what Newton does; the Taylor expansion of

f

about

x^{*}

quantifies the leftover error term

\propto e_{n}^{2}

, telling us how fast. The picture gives intuition, the series gives the exponent.

Why can a hybrid like brentq beat both pure methods?

It keeps a guaranteed bracket (bisection's safety) but tries fast interpolation inside it (Newton/secant-like speed), falling back to a bisection step whenever the fast guess would leave the bracket — you get robustness and speed. See scipy.optimize.

Why does scipy.optimize.brentq not need a derivative even though Newton does?

Brent uses the Secant method and inverse-quadratic interpolation, both of which estimate curvature from function values alone — no

f^{'}

callback required, which is why it's the go-to for black-box functions.

Why is "step size below tolerance" a better stopping test than "function value below tolerance"?

Near a steep root a tiny

x

-error gives a large

∣ f ∣

, so an

∣ f ∣

test may never trigger; near a flat root a large

x

-error gives a tiny

∣ f ∣

, so an

∣ f ∣

test stops too early. The step

∣ x_{n + 1} - x_{n} ∣

measures actual position change and behaves more predictably.

Edge cases

What happens in bisection when the root sits exactly at an endpoint, e.g.

f (a) = 0

Then

f (a) f (b) = 0

, not

< 0

, so the bracket test fails and the loop never runs — you'd lose a real root. That's why you check and return endpoints before the loop.

What does Newton do on

f (x) = x^{1/3}

starting anywhere but the root?

It diverges — each step overshoots to the opposite side, farther out:

x_{n + 1} = - 2 x_{n}

. The root at 0 has an infinite-slope tangent, so the linear model is a lie and the iterates run away. Bisection would have nailed it.

Two roots sit inside one bracket, e.g.

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

[0, 2]

[- 2, 2]

— what does bisection give?

[0, 2]

there is one sign change so it finds

2

; on

[- 2, 2]

signs match (

f (- 2) f (2) > 0

) so it refuses to start. Bisection finds a root inside a valid odd-crossing bracket, never promises which if you sneak in an even count.

A perfectly flat plateau:

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

during Newton — what should code do?

Division by zero (flat tangent, no x-intercept). Raise an error or nudge the guess; blindly computing

f / f^{'}

yields inf/nan and silently corrupts the run.

Newton cycles:

x_{0} \to x_{1} \to x_{0} \to \dots

forever — is that possible?

Yes. For some

f

and starting points the tangent bounces between two values and never converges (e.g. certain odd functions symmetric about the root). Only a maxit guard saves you — the step size never shrinks below tol.

The bracket is astronomically wide, say

[- 1 0^{9}, 1 0^{9}]

— is bisection still fine?

Yes, just slower by the log: width

2 \cdot 1 0^{9}

needs about

lo g_{2} (2 \cdot 1 0^{9} / ε) \approx 61

steps for

ε = 1 0^{- 9}

. Linear-per-bit means even enormous brackets cost only tens of iterations — robustness barely notices the size.

What if

f

returns a NaN somewhere in the bracket (e.g.

x

for negative

x

Every sign comparison with NaN is False, so bisection may repeatedly keep the wrong half and converge to a garbage value. Guard against NaN/inf function outputs; a valid bracket assumes

f

is defined on all of

[a, b]

Recall One-line summary

Bisection trades speed for an ironclad guarantee (needs continuity + a sign change); Newton trades the guarantee for quadratic speed (needs a derivative, a good start, and a non-flat root). Every trap above is one of those preconditions being quietly violated.