COPPERBELT UNIVERSITY · School of ICT · Computer Science Dept

CS 351 — Numerical Analysis · Module 2

WEEK 4 · MODULE 2, WEEK

2

Root Finding & Nonlinear

Equations
Newton's Method · Secant Method · Brent’s Method

Dr Z. Lifelo
Reference: Sauer — Numerical Analysis (2nd ed.) · §1.4 Newton's Method · §1.5 Root-Finding without Derivatives
Newton's Method Sauer §1.4, p.51

Newton's Method draws the tangent line at the current guess, then uses where it hits the x-axis as the next guess. This
simple geometric idea gives spectacular speed.
Step-by-step geometric derivation

Start: current guess xᵢ with tangent line at f(xᵢ)

1 The tangent line at xᵢ has slope f′(xᵢ) and passes through
the point (xᵢ, f(xᵢ)). Point-slope form: y − f(xᵢ) = f′(xᵢ)(x − xᵢ)

Find where the tangent line hits the x-axis

Set y = 0:
2 0 − f(xᵢ) = f′(xᵢ)(x − xᵢ)
Solve for x: x = xᵢ − f(xᵢ)/f′(xᵢ)

That intersection is the next guess xᵢ₊₁

Repeat the process from xᵢ₊₁.
3 If f is smooth near the root, each tangent line is a better
approximation to f, so xᵢ₊₁ is closer to r than xᵢ was.

Newton's Method:
xᵢ₊₁ = xᵢ − f(xᵢ) / f′(xᵢ) for i=1, 2, 3,……

Starting guess x₀ given. Requires f′(xᵢ) ≠ 0 at each step. Figure 1: Newton’s method
Newton's Method Sauer §1.4, p.51

Newton's Method draws the tangent line at the current guess, then uses where it hits the x-axis as the next guess. This
simple geometric idea gives spectacular speed.
Newton as Fixed-Point Iteration (key insight)

Newton's Method is a SPECIAL CASE of FPI with: Why g′(r) = 0 matters:

From FPI, when g′(r)=0, FPI has QUADRATIC convergence — digits
g(x) = x − f(x)/f′(x) double each step. Newton's method is designed to ALWAYS satisfy
this condition at a simple root.
This is the FPI function g. Newton's iterate is exactly xᵢ₊₁ = g(xᵢ).

Why is this so powerful? Compute g′(r):

g′(x) = 1 − [f′(x)² − f(x)f″(x)] / f′(x)²

= f(x)f″(x) / f′(x)²

At the root r: f(r) = 0 g′(r) = f(r)·f″(r)/f′(r)² = 0 because f(r) = 0. This is the product rule
applied to the FPI function. The same derivative analysis from
error propagation tells us Newton will converge quadratically.
→ g′(r) = 0 for ANY function f with f(r)=0, f′(r)≠0 !
 Worked Example — f(x) = x³ + x − 1, Starting from x₀ = −0.7 Sauer §1.4, Ex. 1.11

Newton's method applied to x³+x−1=0. True root r ≈ 0.6823278.

Setting up the Newton formula Full 7-step table — watch correct digits double
f(x) = x³ + x − 1 Step i xᵢ eᵢ = |xᵢ − r| eᵢ/eᵢ₋₁²
f′(x) = 3x² + 1
xᵢ₊₁ = xᵢ − (xᵢ³ + xᵢ − 1)/(3xᵢ² + 1) = (2xᵢ³ + 0 −0.70000000 1.38232780 —
1)/(3xᵢ² + 1) 1 0.12712551 0.55520230 0.2906
Simplified by multiplying out: −(x³+x−1)/(3x²+1) + x = (2x³+1)/(3x²+1) 2 0.95767812 0.27535032 0.8933
First two steps 3 0.73482779 0.05249999 0.6924

x₀ = −0.7 4 0.68459177 0.00226397 0.8214

5 0.68233217 0.00000437 0.8527
x₁ = [2(−0.7)³ + 1] / [3(−0.7)² + 1]
= [2(−0.343) + 1] / [3(0.49) + 1] 6 0.68232780 0.00000000 0.8541
= [−0.686 + 1] / [1.47 + 1] 7 0.68232780 0.00000000 —
= 0.314 / 2.47 ≈ 0.1271
✓ Digits approximately DOUBLE at each step (steps 4→5→6).
x₂ = [2(0.1271)³ + 1] / [3(0.1271)² + 1] Why do the first steps look irregular?
= [2(0.00205) + 1] / [3(0.01615) + 1] The quadratic convergence formula eᵢ₊₁ ≈ M·eᵢ² only kicks in when xᵢ
≈ 1.00410 / 1.04846 ≈ 0.9577 is CLOSE to r. Steps 0–3 have irregular ratios because x₀=−0.7 is far
Notice: x₀=−0.7 is far from r≈0.68. After just 2 steps: x₂≈0.96 — getting from r≈0.68. Once nearby (step 3+), quadratic convergence takes
much closer! over fully.
Sauer §1.4.1, Thm
1.11
 Sauer §1.4.2, Ex. 1.12–
Linear Convergence at Multiple Roots 1.14

Newton's quadratic convergence breaks down at multiple roots where f′(r)=0. Understanding why — and the fix — is
essential for production code.
Theorem — Modified Newton Step Standard Newton xᵢ Modified Newton
xᵢ
If multiplicity m is known, use Modified Newton:
0 1.00000000 1.00000000
xᵢ₊₁ = xᵢ − m·f(xᵢ)/f′(xᵢ) 1 0.72159024 0.16477072

This restores
Example QUADRATIC
— triple convergence even at multiple roots.
root at r=0 2 0.52137095 0.01620734
3 0.37530831 0.00024654
f(x) = sin x + x² cos x − x² − x has a triple root at r=0 (m=3).
4 0.26836349 0.00000006
Standard Newton: S=(3−1)/3=2/3 → needs ~36 steps for 6 places. 5 0.19026161 ≈ 0 ✓
Modified Newton (m=3): restores quadratic convergence.

Modified Newton saves ~31 steps:

Standard: 36 steps. Modified (m=3): 5 steps. When multiplicity is
known, always use Modified Newton for production code.
When Newton's Method Fails Sauer §1.4.2, Ex. 1.15

Newton's method is powerful but not infallible. Knowing when it fails is as important as knowing when it succeeds.

Three ways Newton can fail

1. Oscillation between non-roots Local convergence guarantee:

Example 1.15: f(x)=4x⁴−6x²−11/4, x₀=1/2. Theorems 1.11/1.12 guarantee convergence for x₀ NEAR r.
Newton alternates: 1/2 → −1/2 → 1/2 → ··· Far from r, all bets are off.
The tangent lines at ±1/2 are inflection-related — they point to
the other non-root.
Figure 1.10 (Sauer p.58) shows this failure.

2. Derivative becomes zero Fix: use bisection first to bracket, then switch to
If f′(xᵢ)=0 at any step, the Newton formula is undefined Newton once close.
(division by zero). The tangent line is horizontal — never meets
the x-axis.
Fix: choose a different starting guess.

3. Divergence to infinity
For some functions and starting guesses, xᵢ → ∞. The tangent
line at each step points further and further from the root.
See Sauer Exercise 1.4.6 for a specific example.
 When Newton's Method Fails Sauer §1.4.2, Ex. 1.15

Newton's method is powerful but not infallible. Knowing when it fails is as important as knowing when it succeeds.
Complete Newton implementation with safeguards Lab 4 convergence plot
Python Python
def newton(f, df, x0, tol=1e-8, max_iter=50): # Verify quadratic convergence: eᵢ₊₁/eᵢ² → M
"""Newton's Method with full diagnostics.
Sauer §1.4, Program 1.3 → Python.
r = 0.6823278038 # true root
f: function, df: derivative. errs = [abs(x-r) for x in hist[1:]]
Returns: (root, n_iter, iterates, errors) ratios = [errs[i+1]/errs[i]**2 for i in
"""
range(len(errs)-2) if errs[i]>1e-15]
x = x0
history = [x] print('Ratios eᵢ₊₁/eᵢ²:', [f'{r:.3f}' for r in ratios])
for i in range(max_iter):
fx = f(x)
dfx = df(x)
if abs(dfx) < 1e-14:
raise RuntimeError(f"f'(x)≈0 at step {i}")
x_new = x - fx / dfx
[Link](x_new)
if abs(x_new - x) < tol:
return x_new, i+1, history
x = x_new
raise RuntimeError(f"Failed to converge in {max_iter} steps")

# Example 1.11: x³ + x - 1 = 0, x₀ = -0.7

f = lambda x: x**3 + x - 1
df = lambda x: 3*x**2 + 1
root, n, hist = newton(f, df, x0=-0.7)
print(f"Root: {root:.10f} ({n} steps)")
# Root: 0.6823278038 (6 steps)
 SECTION 2 — §1.5.1

The Secant Method

Newton without the derivative — superlinear convergence

Motivation: when f′ is unavailable or expensive Superlinear convergence — the golden ratio

Method of False Position and Inverse Quadratic

Derivation from the Newton formula
Interpolation

Worked Example 1.16: x³+x−1=0, two starting points

The Secant Method Sauer §1.5.1, p.61

The Secant Method replaces the tangent line (slope = f′) with a secant line (slope = finite difference). This avoids computing
derivatives entirely.
Derivation — one substitution away from Newton

Newton requires f′(xᵢ) — approximate it Secant Method (Sauer p.61):

1 The derivative at xᵢ can be approximated by the finite xᵢ₊₁ = xᵢ − f(xᵢ)(xᵢ−xᵢ₋₁) / [f(xᵢ)−f(xᵢ₋₁)]
difference using the PREVIOUS iterate xᵢ₋₁:
f′(xᵢ) ≈ [f(xᵢ) − f(xᵢ₋₁)] / (xᵢ − xᵢ₋₁)
Requires two initial guesses x₀, x₁. Each new step uses only f(xᵢ) and
f(xᵢ₋₁) — no derivative!
Substitute into Newton's formula
2 Newton: xᵢ₊₁ = xᵢ − f(xᵢ)/f′(xᵢ)
Cost per step: ONE function evaluation
Substitute approximation:
xᵢ₊₁ = xᵢ − f(xᵢ) · (xᵢ − xᵢ₋₁) / [f(xᵢ) − f(xᵢ₋₁)]
Newton needs f(xᵢ) and f′(xᵢ) — two evaluations per step.
Secant needs only f(xᵢ) (f(xᵢ₋₁) was stored from the previous
step). For expensive functions, this is significant.
This is the Secant Method formula
3 Two starting guesses x₀, x₁ needed (unlike Newton which
only needs x₀). Each step uses the two most recent
iterates.
 The Secant Method Sauer §1.5.1, p.61

The Secant Method replaces the tangent line (slope = f′) with a secant line (slope = finite difference). This avoids computing
derivatives entirely.
Geometric picture: secant line vs tangent line

Newton uses the TANGENT line at xᵢ — requires f′(xᵢ).

Why the golden ratio?
The Secant recurrence eᵢ₊₁ ≈ C·eᵢ·eᵢ₋₁ leads to an error exponent α
Secant uses the SECANT line through (xᵢ₋₁,f(xᵢ₋₁)) and (xᵢ,f(xᵢ)) — satisfying α²=α+1 (Fibonacci!), giving α=(1+√5)/2≈1.618. See Sauer
same slope approximation as forward difference. Exercise 1.5.6.

Both lines are intersected with the x-axis to get xᵢ₊₁.

Convergence order — superlinear

If the Secant Method converges to r and f′(r) ≠ 0:

Method Order α Steps for 10⁻⁸ f evals/step
eᵢ₊₁ ≈ |f″(r)/2f′(r)|^(α−1) · eᵢ^α Newton 2.0 ~5 2 (f and f′)
Secant ≈ 1.618 ~9 1 only!
where α = (1 + √5)/2 ≈ 1.618 (the GOLDEN RATIO!)
Bisection 1.0 ~27 1 only
This is SUPERLINEAR convergence: between linear (α=1)
and quadratic (α=2).
Worked Example — Secant Method on f(x) = x³ + x − 1 Sauer §1.5.1, Ex. 1.16

Starting with x₀ = 0 and x₁ = 1, we trace the Secant Method step by step. Compare with Newton's Example.
First two steps — by hand (Sauer p.62) Full table — Sauer p.62
f(x) = x³ + x − 1 i xᵢ
x₀ = 0, x₁ = 1
f(x₀) = f(0) = −1 0 0.00000000000000
f(x₁) = f(1) = 1 + 1 − 1 = 1 1 1.00000000000000
STEP 1: x₂ = x₁ − f(x₁)·(x₁−x₀)/(f(x₁)−f(x₀)) 2 0.50000000000000
= 1 − f(1)·(1−0)/(f(1)−f(0))
= 1 − (1)(1)/(1−(−1)) 3 0.63636363636364
= 1 − 1/2 = 1/2 = 0.5 4 0.69005235602094

STEP 2: x₃ = x₂ − f(x₂)·(x₂−x₁)/(f(x₂)−f(x₁)) 5 0.68202041964819

f(x₂) = f(0.5) = 0.125+0.5−1 = −0.375 6 0.68232578140989
x₃ = 0.5 − (−0.375)(0.5−1)/(−0.375−1)
= 0.5 − (0.1875)/(−1.375) 7 0.68232780435903
= 0.5 + 0.1364 = 7/11 ≈ 0.6364 8 0.68232780382802
9 0.68232780382802 ✓
Note: no derivative needed at any step!
Only function values f(xᵢ) and f(xᵢ₋₁) are used. This makes the
✓ Converges in 9 steps to machine precision. Compare: Newton
Secant method ideal when f′ is hard to compute analytically. needed 6 steps — slightly fewer, but Newton needed f′ at each step.
Variants — Method of False Position and Inverse Quadratic Sauer §1.5.1, p.62–64
Interpolation
Two generalisations of the Secant Method: False Position keeps a bracket (guaranteed but can be slow); IQI uses a parabola
(faster than Secant).
Method of False Position (Regula Falsi) Example 1.17 — slow False Position
Like Bisection but uses the Secant formula for the new point
f(x) = x³ − 2x² + (3/2)x on [−1,1]. Root r=0.
instead of the midpoint.

c = b·f(a) − a·f(b)) / (f(a) − f(b)) Step 1: c = 1·f(−1) − (−1)·f(1) / (f(−1)−f(1)) = 4/5 = 0.8
Bracket becomes [−1, 0.8] (width = 1.8, wider than bisection's
1.0!).
Choose [a,c] or [c,b] based on sign change, just like bisection. Root is
always bracketed.
The right endpoint stays fixed at −1 for many steps because f is
much steeper there. Extremely slow convergence — bisection
Advantages over Secant: would be better here.
• Guaranteed bracket → root always in interval
• Never misses the root

Disadvantage:
• Can converge VERY slowly (see Example 1.17)
• If f is highly curved on one side, one endpoint stays fixed and
the interval shrinks very slowly.
 Variants — Method of False Position and Inverse Quadratic Sauer §1.5.1, p.62–64
Interpolation
Two generalisations of the Secant Method: False Position keeps a bracket (guaranteed but can be slow); IQI uses a parabola
(faster than Secant).
Inverse Quadratic Interpolation (IQI) Unlike Muller's Method (y=p(x)), IQI uses x=p(y):
• Always gives a unique real intersection with x-axis
IQI fits a parabola x = P(y) through three previous points, then • No ambiguity about which root of the quadratic to take
evaluates at y=0. • Slightly more complex formula but more stable

Given xᵢ,xᵢ₊₁,xᵢ₊₂ and values A,B,C = f at each: Sauer Equation 1.37: the IQI formula uses
q = f(xᵢ)/f(xᵢ₊₁), r = f(xᵢ₊₂)/f(xᵢ₊₁), s = f(xᵢ₊₂)/f(xᵢ)
Lagrange interpolation: xᵢ₊₃ = P(0) where P(y) passes through IQI converges faster than Secant due to the higher-order
(A,xᵢ),(B,xᵢ₊₁),(C,xᵢ₊₂)
(parabolic) interpolation.
Method Uses Starting Interpolation Order
bracket? pts
False Position YES 2 Linear Between 1
(bracket) and 2
Secant No 2 Linear ≈ 1.618
IQI No 3 Quadratic ≈ 1.839
Brent's YES 2 IQI/Secant/Bise Guaranteed +
ct fast
 SECTION 3 — §1.5.2

Brent's Method
The production-grade solver — guaranteed convergence at near-Newton speed

The hybrid idea: combine bisection with fast methods

The decision logic: IQI → Secant → Bisection

[Link] — the Python production solver

Brent's Method — The Best of All Worlds Sauer §1.5.2, p.64

Brent's Method (1973) combines the guaranteed convergence of bisection with the speed of IQI and Secant. It is the
algorithm behind [Link].
The hybrid strategy — three-layer priority Sauer's fzero trace (p.65) — same function x³+x−1

1st Try — Inverse Quadratic Interpolation Matlab fzero / [Link] output

Fit parabola x=P(y) through 3 last points → fast. Step x f(x) Procedure
1 0.000000 -1.000000 initial
ACCEPT if: (a) better backward error than before, AND (b)
2 1.000000 1.000000 initial
bracket cut by at least half. 3 0.500000 -0.375000 bisection
4 0.636364 -0.105935 interpolation
2nd Try — Secant Method 5 0.684910 0.006202 interpolation
6 0.682225 -0.000247 interpolation
Use linear interpolation if IQI step fails.
7 0.682328 -5.43e-07 interpolation
ACCEPT if: same two conditions — improves and halves 8 0.682328 1.50e-13 interpolation
bracket. 9 0.682328 0.000000 interpolation

3rd Try — Bisection (ALWAYS succeeds) Root: 0.68232780382802

If both IQI and Secant fail the acceptance test:
take the bisection step unconditionally.
Brent: 9 function evaluations total (same as Secant but
This GUARANTEES bracket halves every step.
GUARANTEED).
Acceptance test (both conditions must hold): Note: step 3 is bisection (fallback), steps 4–9 are all interpolation
(1) new point has better backward error |f(new)| < |f(old)| (fast!) — showing Brent exploiting the smooth function. For well-
AND (2) new bracket ≤ half the old bracket. behaved functions, Brent is as fast as Secant.
Brent's Method in Python — [Link] Sauer §1.5.2

[Link] is the production implementation of Brent's Method. Students should know both how to USE it and
what it does internally.
Using [Link]
Python Python-cont’d
from [Link] import brentq # Example 3: with full diagnostics
import numpy as np root3, result = brentq(f, 0, 1,
full_output=True,
# Example 1: x³ + x − 1 = 0 on [0, 1] xtol=1e-12, # tolerance
f = lambda x: x**3 + x - 1 rtol=4.4e-16) # relative tolerance
root = brentq(f, 0, 1) print(f"Converged: {[Link]}")
print(f"Root: {root:.15f}") print(f"Iterations: {[Link]}")
# Root: 0.682327803828019 print(f"Function calls: {result.function_calls}")

# Example 2: cos(x) − x = 0 (fixed point of # Example 4: use when Newton diverges

cosine) # f(x) = 4x⁴ − 6x² − 11/4 from Example 1.15
g = lambda x: [Link](x) - x h = lambda x: 4*x**4 - 6*x**2 - 11/4
root2 = brentq(g, 0, 1) root4 = brentq(h, 1.5, 3.0) # bracket safely
print(f"Root: {root2:.15f}") print(f"Brent finds root: {root4:.8f}")
# Root: 0.739085133215161 # Newton with x0=0.5 would FAIL; Brent finds it!
 Brent's Method in Python — [Link] Sauer §1.5.2

[Link] is the production implementation of Brent's Method. Students should know both how to USE it and
what it does internally.
When to use each method

Use Brent's (brentq) Use Secant Method

• ALWAYS when you have a bracket [a,b] • f′ is unavailable or expensive
• Production code / safety-critical • Good starting guesses known for both x₀ and x₁
• Unknown or complex functions • Need faster than bisection but no derivative
• When you can't guarantee starting near root → Middle ground between Brent and Newton
→ Default choice for well-behaved problems

Use Newton's Method Use Bisection only

• f′ is available and cheap to compute • Simplest case, need guaranteed bound on error
• Good starting guess is known (e.g., near known solution) • Exploring: finding rough location of root
• Need maximum speed • Multiple roots in interval (scan for sign changes)
• Not safety-critical (or combine with bisection) → Fallback when other methods are problematic
→ Choose when derivative is free/easy
Complete Comparison — All Module 2 Root-Finding Methods Sauer Ch. 1

The definitive reference: every method from Module 2, compared across all important dimensions.

Complete comparison table

Property Bisection FPI Newton Secant Brent's

Guaranteed? YES Locally Locally Locally YES (with bracket)
Order 1 (linear) 1 (linear) 2 (quadratic) 1.618 (suplin) ~1.6–2 (guaran)
Steps for 10⁻⁸ ~27 ~40–100 ~5 ~9 ~9 (guaranteed)
Needs Bracket |g′(r)| < 1 f′(x) x₀, x₁ close Bracket [a,b]
f evals/step 1 1 2 (f + f′) 1 1
Fails at Even-mult roots |g′(r)| ≥ 1 f′(r)=0 or bad No bracket Never (given valid bracket)
x₀
Sauer ref §1.1 §1.2 §1.4 §1.5.1 §1.5.2
Python — — custom custom [Link]
Complete Comparison — All Module 2 Root-Finding Methods Sauer Ch. 1

The definitive reference: every method from Module 2, compared across all important dimensions.

Module 2 — Connecting Everything to Taylor's Theorem (Module 1)

Bisection error FPI convergence Newton convergence Secant order

(b−a)/2ⁿ⁺¹ eᵢ₊₁≈g′(cᵢ)·eᵢ → S·eᵢ eᵢ₊₁≈M·eᵢ² α=(1+√5)/2
exponential in n — from IVT, no from MVT: g(xᵢ)−g(r)=g′(cᵢ)(xᵢ−r) from Taylor: from eᵢ₊₁≈C·eᵢ·eᵢ₋₁ → α²=α+1
Taylor needed [Module 1 Taylor] f(r)=f(xᵢ)+f′(xᵢ)(r−xᵢ)+f″(c)/2·(r−xᵢ)² (golden ratio equation)
Module 2 Week 2 — Practice Exercises Sauer §§1.4–1.5

Attempt each problem before checking the answer. Answers to starred exercises appear in Sauer pp. 621–622.

Section A — Newton's Method (§1.4) Section B — Secant Method & Brent's (§1.5)

A1 ★ Apply two Newton steps to x³+x−2=0 with B1 ★ Apply two Secant steps to x³+x−2=0 with
x₀=0. (Sauer §1.4 Ex.1a) x₀=0, x₁=1. (Sauer §1.5 Ex.1a)

f(x)=x³+x−2, f′(x)=3x²+1. x₁=x₀−f(x₀)/f′(x₀). x₂=x₁−f(x₁)(x₁−x₀)/(f(x₁)−f(x₀)). f(0)=−2, f(1)=0.

A2 ★★ For f(x)=x²−sin(x)−0.5, apply Newton B2 ★★ Apply two Secant steps to eˣ+x−7=0 with
starting at x₀=1. What is M = |f″(r)/2f′(r)|? x₀=1, x₁=2.
f′(x)=2x−cos(x), f″(x)=2+sin(x). Find r first (≈1.067), then compute
f(x)=eˣ+x−7. Compute f(1)=e+1−7≈−3.28, f(2)=e²+2−7≈2.39.
M.

A3 ★★★ f(x)=(x−1)³(x+2) has roots r=1 (mult 3) and B3 ★★★ Explain why the Method of False Position
r=−2 (simple). Predict Newton's can converge very slowly, even though it
convergence rate S at r=1. How many maintains a bracket. Give a concrete
steps to 6-place accuracy from x₀=1.5? condition on f that causes this slow
convergence.
Theorem Linear convergence at multiple roots: S=(m−1)/m. Step
count from (2/3)ⁿ < 5×10⁻⁷. Think about concavity of f. When does one endpoint of [a,b] stay
fixed for many steps?