Burden & Faires, 9th Ed. - §2.3–2.5

Chapter 4: Newton's Method & Its Extensions

Tangent-line derivation · Quadratic convergence · Secant & False Position · Multiple roots · When Newton's Method fails

Bisection is slow but unconditionally reliable. Newton's Method is the opposite trade: when it works, it is spectacularly fast - the number of correct digits can roughly double with every single iteration - but "when it works" is doing a lot of quiet work in that sentence. This chapter derives that speed from Taylor's Theorem, proves exactly when it's guaranteed, and then spends equal time on the ways it can go wrong, because a method this fast is also this easy to trust past the point it deserves.

Section 4.1

Newton's Method

Derivation from Taylor's Theorem

Derivation
Let $p_0$ approximate a root $p$ of $f$, with $f''$ continuous and $p_0$ close to $p$. Taylor-expand $f$ about $p_0$ and evaluate at $x=p$: $$0 = f(p) = f(p_0) + (p-p_0)f'(p_0) + \frac{(p-p_0)^2}{2}f''(\xi)$$ Dropping the (quadratically small) remainder term and solving for $p$ gives an approximation $p_1$: $$0 \approx f(p_0) + (p_1-p_0)f'(p_0) \;\Rightarrow\; p_1 = p_0 - \frac{f(p_0)}{f'(p_0)}$$ Repeating gives Newton's Method: $$p_n = p_{n-1} - \frac{f(p_{n-1})}{f'(p_{n-1})}, \qquad n\ge1$$ Geometrically, $p_n$ is where the tangent line to $f$ at $p_{n-1}$ crosses the $x$-axis - which is exactly the visualization below.
n = 0 · p₀ = 1.500000
Newton's Method on $f(x)=x^3-x-2$ (root $p\approx1.521380$, the same function used in Chapter 2's Bisection demo - compare how few clicks this takes). Each step draws the tangent line at the current point and drops to where it crosses the axis.

Quadratic Convergence

Theorem 4.1 - Convergence of Newton's Method
Let $f\in C^2[a,b]$. If $p\in(a,b)$ is a simple root ($f(p)=0$, $f'(p)\neq0$), then there exists $\delta>0$ such that Newton's Method converges to $p$ for any starting point $p_0\in[p-\delta,p+\delta]$, and $$|p_{n+1}-p| \le M|p_n-p|^2, \qquad M = \frac{\max|f''|}{2\min|f'|}$$ so convergence is (at least) quadratic - order $\alpha=2$ (Chapter 1, Definition).

Why. Newton's Method is fixed-point iteration with $g(x)=x-f(x)/f'(x)$. Differentiating using the quotient rule and simplifying with $f(p)=0$ gives $g'(p) = \dfrac{f(p)f''(p)}{f'(p)^2} = 0$. A fixed-point iteration whose $g'(p)=0$ converges quadratically rather than merely linearly - this is the entire mechanism behind Newton's speed, and it is also exactly why it breaks down at a multiple root, where $f'(p)=0$ too (§4.3).

📘 Example 4.1 - Digits Doubling in Real Time
Apply Newton's Method to $f(x)=\cos x - x$ (root $p=0.7390851332\ldots$) from $p_0=0.5$. Solution $f'(x)=-\sin x - 1$.
$n$$p_n$$f(p_n)$correct digits
10.7552224171$-2.71\times10^{-2}$1
20.7391416661$-9.46\times10^{-5}$4
30.7390851339$-1.18\times10^{-9}$9
40.7390851332$\approx0$16 (machine precision)
Look at the error column: roughly 1, 4, 9, 16 correct digits - each step is roughly doubling the number of correct digits, the visible signature of quadratic convergence. Four iterations reach machine precision; recall Bisection needed 27 iterations just for $10^{-8}$ on a comparable problem (Chapter 2, Example 2.2).
Section 4.2

Secant Method & Method of False Position

The Secant Method

Motivation and Formula
Newton's Method needs $f'$ analytically - not always available or cheap. The Secant Method replaces $f'(p_{n-1})$ with a finite-difference approximation using the two most recent iterates: $$f'(p_{n-1}) \approx \frac{f(p_{n-1})-f(p_{n-2})}{p_{n-1}-p_{n-2}} \quad\Rightarrow\quad p_n = p_{n-1} - \frac{f(p_{n-1})(p_{n-1}-p_{n-2})}{f(p_{n-1})-f(p_{n-2})}$$ Geometrically, $p_n$ is where the line through $(p_{n-2},f(p_{n-2}))$ and $(p_{n-1},f(p_{n-1}))$ crosses the axis - a secant line standing in for the tangent line. It needs two starting points $p_0,p_1$ and only one new function evaluation per step (vs. Newton's one function and one derivative evaluation).
Superlinear Convergence
The Secant Method converges with order $\alpha = \dfrac{1+\sqrt5}{2} \approx 1.618$ - the golden ratio - strictly between Bisection's linear ($\alpha=1$) and Newton's quadratic ($\alpha=2$). It is usually the better engineering choice when $f'$ is expensive or unavailable: two secant steps cost roughly what one Newton step costs, yet $1.618^2\approx2.618 > 2$, so two secant steps typically gain more accuracy than one Newton step for the same work.

Method of False Position (Regula Falsi)

Definition - False Position
Identical to the Secant Method's formula, but with Bisection's safety net: it maintains a bracket $[p_{n-2},p_{n-1}]$ with $f$ opposite in sign at the endpoints, always replacing whichever endpoint has the same sign as the new point - never both, the way Secant does. This guarantees a root stays bracketed at every step, at the cost of sometimes converging only linearly when one endpoint gets "stuck" while the other creeps toward the root.
n = 1 · p₀ = 0.000000 · p₁ = 1.000000
Secant Method on $f(x)=\cos x - x$: each step draws the line through the two most recent points and drops to its $x$-intercept - no derivative used anywhere.
📘 Example 4.2 - Secant vs. Newton, Head to Head
Apply the Secant Method to $f(x)=\cos x - x$ from $p_0=0,\,p_1=1$ and compare iteration count with Newton's Method (Example 4.1) for reaching $|f(p_n)|<10^{-8}$. Solution
$n$$p_n$$f(p_n)$
20.6850733573$8.93\times10^{-2}$
30.7362989976$4.66\times10^{-3}$
40.7391193619$-5.73\times10^{-5}$
50.7390851121$3.53\times10^{-8}$
60.7390851332$2.67\times10^{-13}$
Secant needs 5 steps (6 function evaluations total, including $p_0,p_1$) to pass $10^{-8}$; Newton needed 3 steps but 3 evaluations of $f$ and 3 of $f'$ - 6 evaluations either way if $f'$ costs about the same as $f$. When $f'$ is expensive to compute, Secant wins outright.
Section 4.3

Multiple Roots

Multiplicity Degrades Convergence

Definition - Multiplicity
$p$ is a root of multiplicity $m$ if $f(x)=(x-p)^m q(x)$ with $q(p)\neq0$. Equivalently, $f(p)=f'(p)=\cdots=f^{(m-1)}(p)=0$ but $f^{(m)}(p)\neq0$. Theorem 4.1 required $f'(p)\neq0$ - which fails whenever $m\ge2$.
Newton's Method Degrades to Linear Convergence
At a root of multiplicity $m\ge2$, ordinary Newton's Method still converges, but only linearly, with asymptotic error constant $\lambda = \dfrac{m-1}{m}$ - for $m=3$, that's $\lambda=\tfrac23\approx0.667$, barely better than Bisection's $0.5$.
📘 Example 4.3 - Newton's Method Crawling at a Triple Root
$f(x)=(x-1)^3(x-2)$ has a root of multiplicity $m=3$ at $p=1$. Apply Newton's Method from $p_0=1.3$. Solution $$f'(x)=3(x-1)^2(x-2)+(x-1)^3$$
$n$$p_n$$e_n=|p_n-1|$$e_n/e_{n-1}$
11.1833330.1833330.611
21.1172790.1172790.640
31.0763750.0763750.651
41.0501950.0501950.657
71.0145990.0145990.664
91.0064620.0064620.666
The ratio $e_n/e_{n-1}$ is visibly settling toward $\frac{m-1}{m}=\frac23\approx0.6667$, exactly as the theory predicts - this is linear convergence disguised inside a method built for quadratic speed, and it is easy to mistake for a bug rather than expected behavior at a multiple root.

Modified Newton's Method

Restoring Quadratic Convergence
Define $\mu(x) = \dfrac{f(x)}{f'(x)}$. Since $f(x)=(x-p)^mq(x)$, it turns out $\mu(x)$ has a root of multiplicity exactly $1$ at $p$, no matter what $m$ was - so ordinary Newton's Method applied to $\mu$ instead of $f$ converges quadratically again: $$p_n = p_{n-1} - \frac{\mu(p_{n-1})}{\mu'(p_{n-1})} = p_{n-1} - \frac{f(p_{n-1})f'(p_{n-1})}{[f'(p_{n-1})]^2 - f(p_{n-1})f''(p_{n-1})}$$ The cost: this needs $f''$, and it is more sensitive to round-off since it subtracts two similar-sized quantities in the denominator (recall Chapter 1's cancellation warning) - a real trade, not a free upgrade.
📘 Example 4.4 - Modified Newton Recovers Quadratic Speed
Repeat Example 4.3 using Modified Newton's Method. Solution $f''(x) = 6(x-1)(x-2)+6(x-1)^2$.
$n$$p_n$$e_n=|p_n-1|$
11.057692$5.77\times10^{-2}$
21.001248$1.25\times10^{-3}$
31.0000005$5.20\times10^{-7}$
41.0000000$9.04\times10^{-14}$
Four iterations reach machine precision - matching the simple-root speed of Example 4.1 - versus 9+ iterations still crawling with ordinary Newton in Example 4.3, on the exact same problem.
Log-scale error vs. iteration for the triple-root example: plain Newton (orange, linear slope) vs. Modified Newton (purple, steepening quadratic slope) - same function, same starting point, wildly different trajectories.
Section 4.4

When Newton's Method Fails

Failure Mode 1 - Oscillation from a Bad Starting Point
Theorem 4.1's convergence guarantee is local - it only promises a $\delta$-neighborhood of $p$ exists, never how big $\delta$ is, and never that an arbitrary $p_0$ lands inside it. A classic pathology: $f(x)=x^3-2x+2$ (root near $p\approx-1.7693$) started from $p_0=0$.
📘 Example 4.5 - Newton's Method Stuck in an Infinite Loop
Apply Newton's Method to $f(x)=x^3-2x+2$ from $p_0=0$. Solution $f'(x)=3x^2-2$. $f(0)=2$, $f'(0)=-2 \Rightarrow p_1 = 0-2/(-2)=1$. Then $f(1)=1$, $f'(1)=1 \Rightarrow p_2 = 1-1/1=0$.
$n$0123456
$p_n$0101010
The iteration cycles between $0$ and $1$ forever and never approaches the real root near $-1.7693$ - a tangent line at each point happens to land exactly on the other point. No error message, no crash: an unmonitored implementation would simply loop, which is why every practical Newton implementation needs a maximum-iteration cap and a residual check, never blind trust in convergence.
Other Failure Modes to Watch For
  • $f'(p_n)\approx0$: the tangent line is nearly horizontal and the next iterate can fly arbitrarily far away - numerically this is the same cancellation-adjacent instability as dividing by a near-zero number.
  • Inflection points near $p_0$: the tangent can send the iteration in the wrong direction entirely, especially for functions with nearby local extrema.
  • No real root exists nearby: Newton's Method has no way to detect this - it will simply wander (or, for complex-valued extensions, converge to a complex root) rather than report failure.
A cheap, common safeguard: bracket the root first with a few Bisection steps (Chapter 2), then switch to Newton once close - combining Bisection's guaranteed convergence with Newton's speed once safely inside the basin of quadratic convergence.
Practice

Practice Problem

Try this problem yourself before expanding the solution below.

✏️ Practice Problem 4.1 - Newton's Method and Quadratic Convergence
Apply Newton's Method to $f(x)=x^3+3x^2-1$ starting from $p_0=0.5$. Compute $p_1$, $p_2$, $p_3$, and verify that the error roughly squares at each step. Solution $f'(x)=3x^2+6x$. Newton's formula $p_{n+1}=p_n-\dfrac{f(p_n)}{f'(p_n)}$ gives: $$p_1 = 0.5 - \frac{-0.125}{3.75} = 0.533333, \qquad p_2 = 0.532091, \qquad p_3 = 0.532089.$$ The iteration has converged (to six decimals) to the root $p\approx0.532089$. Tracking the true error $e_n=|p_n-p|$:
$n$$p_n$$e_n=|p_n-p|$$e_n/e_{n-1}^2$
10.533333$1.24\times10^{-3}$-
20.532091$1.76\times10^{-6}$1.13
30.532089$3.51\times10^{-12}$1.14
The ratio $e_n/e_{n-1}^2$ stays close to a constant ($\approx1.14$), the signature of quadratic ($\alpha=2$) convergence - each step roughly doubles the number of correct decimal digits. $p_3=0.532089$ to six decimals; error shrinks like $e_n\propto e_{n-1}^2$, confirming order-2 convergence.
Connections Across the Course
  • Newton's Method is literally the special case $g(x)=x-f(x)/f'(x)$ of Chapter 3's fixed-point framework - its quadratic speed is a direct consequence of $g'(p)=0$ there.
  • The same tangent-line idea, applied to a system of nonlinear equations using the Jacobian matrix, is Newton's Method for nonlinear systems - the natural sequel once Chapter 13's matrix norms are available.
  • Multiple-root detection reuses the derivative machinery of Chapter 8 when $f'$ and $f''$ aren't available in closed form.
Scroll to Top