Solving nonlinear equations · Lecture 9

The Newton–Raphson Method

Replace the curve by its tangent line and jump to where the tangent crosses the axis. Near a simple root the number of correct digits doubles every step; far from it, anything can happen.

Md Mahbub E Noor · Assistant Professor
CSE-3107 Numerical Methods · B.Sc. 3rd Year 1st Semester
Department of CSE, University of Barishal

Why this lecture

The problem: divide without dividing

Division is the slowest arithmetic operation in hardware. Can a chip compute 1/71/7 using only multiplication and subtraction?

  • We want x=1/7x = 1/7: the root of f(x)=1x−7f(x) = \dfrac{1}{x} - 7
  • Some rule xn+1=(something)x_{n+1} = (\text{something}) that improves a guess using only ×\times and −-
  • Bisection would need 20 steps for 6 digits; fixed-point iteration needs the right gg
  • Today's method gives the rule xn+1=xn(2−7xn)x_{n+1} = x_n(2 - 7x_n), and the digits double every step
nnxnx_ncorrect digits
00.10
10.131
20.14172
30.142847775
40.1428571410+
Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
2 / 21

Today's goals

  • Derive the Newton–Raphson formula geometrically and from Taylor series
  • Carry out Newton's method by hand to a required accuracy (iteration tables)
  • Explain quadratic convergence: errors square, digits double
  • Recognise the failure cases: f′(x)≈0f'(x) \approx 0, cycles, divergence, multiple roots
  • Implement Newton in Python and C with proper safeguards
  • Know its best and worst cases, and when to choose it over the other methods
Last time

Fixed-point iteration converges linearly with rate ∣g′(r)∣|g'(r)|; if g′(r)=0g'(r) = 0 it is much faster.

Today

Newton's method is the fixed-point iteration whose g′(r)=0g'(r) = 0, built from the tangent line.

Solving nonlinear equations · you are here
L6 · Root Finding and the Bisection Method→L7 · False Position Method→L8 · Fixed-Point Iteration→L9 · Newton–Raphson Method→L10 · Secant Method and Nonlinear Systems
Builds on: L3, L8
Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
3 / 21
Start here

The idea in one picture

xf(x)x₀x₁x₂tangent: the curve seen up closeroot 1.419
We want the x where the curve crosses the axis.Start at a guess x₀ and go up to the curve.Slide down the tangent line until it hits the axis.That point is the new guess x₁. Go up to the curve again.Slide down the new tangent.x₂ = 1.619 is already close.Two steps: 3 → 2.106 → 1.619. The next gives 1.444, then 1.419. Very fast.
In plain words
  • Up close, a curve looks like its tangent line
  • A line is easy: find where the tangent crosses the axis
  • Use that as the new guess and repeat: very fast near the root
New words today
tangent
the line that just touches the curve at a point
derivative f′(x)
the slope of the tangent
Newton step
x − f(x)/f′(x)
quadratic convergence
correct digits double each step
Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
4 / 21

Deriving the formula

Tangent line at x_ny=f(xn)+f′(xn)(x−xn)y = f(x_n) + f'(x_n)(x - x_n)
Set y = 0xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}
Same thing from Taylor (Lecture 3)0=f(r)≈f(xn)+f′(xn)(r−xn)  ⇒  r≈xn−f(xn)f′(xn)0 = f(r) \approx f(x_n) + f'(x_n)(r - x_n) \;\Rightarrow\; r \approx x_n - \frac{f(x_n)}{f'(x_n)}
  • Geometric: follow the tangent down to the axis
  • Analytic: keep the first two Taylor terms, solve the linear equation
  • Needs f′(x)f'(x) and one starting value x0x_0; no bracket
  • Fixed-point view: g(x)=x−f/f′g(x) = x - f/f' has g′(r)=f(r)f′′(r)f′(r)2=0g'(r) = \dfrac{f(r)f''(r)}{f'(r)^2} = 0
Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
5 / 21
The method, step by step

The Newton–Raphson algorithm

  1. Find f′(x)f'(x); choose x0x_0 near the root (from a sketch or a sign change)
  2. Compute xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}
  3. If f′(xn)=0f'(x_n) = 0 (flat tangent), stop and choose another x0x_0
  4. Repeat until ∣xn+1−xn∣<ε|x_{n+1} - x_n| < \varepsilon (the required digits stop changing)
  5. Answer: the last xn+1x_{n+1}; check that f(xn+1)≈0f(x_{n+1}) \approx 0
Pseudocode
input f, df, x0, tol, N
x ← x0
repeat up to N times:
    d ← df(x)
    if d = 0: stop (flat tangent)
    x_new ← x − f(x) / d
    if |x_new − x| < tol:
        return x_new
    x ← x_new
stop: no convergence

One function value and one derivative value per step. No bracket, so nothing guarantees convergence: the cap NN matters.

Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
6 / 21

Explore: tangent after tangent

  • The dashed orange line is the tangent at xnx_n
  • Its crossing gives xn+1x_{n+1}
  • Look at the ∣xn+1−xn∣|x_{n+1} - x_n| column: 2×10−22\times10^{-2}, 4×10−44\times10^{-4}, 10−710^{-7}, 10−1410^{-14}
  • Compare: bisection needed 14 steps for 10−410^{-4}; Newton needs 3
Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
7 / 21

Problem 1: f(x)=2x3−2x−5f(x) = 2x^3 - 2x - 5

Problem 1"Find out the root of the following equation using the Newton–Raphson method: f(x)=2x3−2x−5f(x) = 2x^3 - 2x - 5." Here f′(x)=6x2−2f'(x) = 6x^2 - 2; f(1)=−5f(1) = -5, f(2)=7f(2) = 7, so start at x0=1.5x_0 = 1.5.
nnxnx_nf(xn)f(x_n)f′(xn)f'(x_n)xn+1=xn−f/f′x_{n+1} = x_n - f/f'∣xn+1−xn∣|x_{n+1} - x_n|
01.500000−1.25000011.5000001.6086960.108696
11.6086960.10890113.5274101.6006450.008050
21.6006450.00062513.3723911.6005990.000047
31.6005990.00000013.3714941.6005990.000000

Root ≈ 1.600599 (correct to 6 decimals after 3 iterations). Check: f(1.600599)=2(4.100667)−3.201198−5≈0f(1.600599) = 2(4.100667) - 3.201198 - 5 \approx 0.

Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
8 / 21

Problem 2: 3x+sin⁡x=ex3x + \sin x = e^{x} to 5 decimal places

Problem 2"Use Newton–Raphson method to find a real root of the equation 3x+sin⁡x=ex3x + \sin x = e^{x} correct up to 5 decimal places."
1
f(x)=3x+sin⁡x−exf(x) = 3x + \sin x - e^{x},   f′(x)=3+cos⁡x−ex\;f'(x) = 3 + \cos x - e^{x}; f(0)=−1f(0) = -1, f(1)=1.123189f(1) = 1.123189: root in (0,1)(0, 1); take x0=0x_0 = 0
2
x1=0−−13=0.333333x_1 = 0 - \dfrac{-1}{3} = 0.333333
3
x2=0.333333−−0.0684182.549345=0.360171x_2 = 0.333333 - \dfrac{-0.068418}{2.549345} = 0.360171
4
x3=0.360171−−0.0006282.502263=0.360422x_3 = 0.360171 - \dfrac{-0.000628}{2.502263} = 0.360422;   x4=0.360422\;x_4 = 0.360422 (change <10−6< 10^{-6})
x=0.36042x = 0.36042 (to 5 decimal places). Radians! A calculator in degree mode gives nonsense.
Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
9 / 21
Classical vs numerical

Same problem, two approaches: x3−x−2=0x^3 - x - 2 = 0

Algebra

Classical (exact formula)

  • Cardano (1545): x=1+26/273+1−26/273x = \sqrt[3]{1 + \sqrt{26/27}} + \sqrt[3]{1 - \sqrt{26/27}}
  • =1.2559834+0.2653963=1.5213797= 1.2559834 + 0.2653963 = 1.5213797
  • Needs square and cube roots (computed by Newton inside the calculator!), and 1−26/27=0.01871 - \sqrt{26/27} = 0.0187 is a cancellation that loses about 2 digits
vs
Algorithm

Numerical (Newton)

  • xn+1=xn−xn3−xn−23xn2−1x_{n+1} = x_n - \dfrac{x_n^3 - x_n - 2}{3x_n^2 - 1} from 1.5
  • 3 iterations: 1.5217391.521739, 1.5213801.521380, 1.52137971.5213797
  • Same answer, simpler, and the same code works for any cubic
When the classical approach cannot work

The quintic x5−x−1=0x^5 - x - 1 = 0

Abel–Ruffini theorem (1824): there is no formula in radicals for general degree-5 equations, and this one is a standard example. Newton from x0=1x_0 = 1: x=1.167304x = 1.167304 in 5 iterations.

Even where a formula exists, numerical methods are often simpler and more accurate; beyond degree 4 they are the only general option.

Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
10 / 21

Why so fast? Quadratic convergence

Error relation (from Taylor about x_n)en+1≈f′′(r)2f′(r) en2,en=xn−re_{n+1} \approx \frac{f''(r)}{2f'(r)}\,e_n^{2}, \qquad e_n = x_n - r
  • Errors are squared each step: 10−2→10−4→10−8→10−1610^{-2} \to 10^{-4} \to 10^{-8} \to 10^{-16}
  • Correct digits roughly double each step
  • Measured ratio 0.768 matches theory 6r2(3r2−1)=0.768\dfrac{6r}{2(3r^2 - 1)} = 0.768 ✓
  • Only near a simple root (f′(r)≠0f'(r) \ne 0); far away, no promise
nnxnx_n for x3−x−2x^3 - x - 2∣en∣|e_n|∣en+1∣/en2|e_{n+1}|/e_n^2
01.52.1e−20.786
11.5217391303.6e−40.768
21.5213798069.9e−80.768
31.5213797077.6e−15—
Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
11 / 21

Newton inside your computer

Square root

f(x)=x2−Nf(x) = x^2 - N

Exactly the Babylonian method of Lecture 1. 10\sqrt{10} from x0=3x_0 = 3: 3.166667, 3.162281, 3.162278.

xn+1=xn−xn2−N2xn=12(xn+Nxn)x_{n+1} = x_n - \frac{x_n^2 - N}{2x_n} = \frac12\left(x_n + \frac{N}{x_n}\right)
Division without dividing

f(x)=1x−Nf(x) = \dfrac{1}{x} - N

Only multiplications! CPUs and GPUs compute 1/N1/N like this. 1/71/7 from x0=0.1x_0 = 0.1: 0.13, 0.1417, 0.142848, 0.14285714.

xn+1=xn(2−Nxn)x_{n+1} = x_n(2 - N x_n)
Cube root

f(x)=x3−Nf(x) = x^3 - N

173\sqrt[3]{17} from x0=2.5x_0 = 2.5: 2.573333, 2.571283, 2.571282.

xn+1=13(2xn+Nxn2)x_{n+1} = \frac{1}{3}\left(2x_n + \frac{N}{x_n^2}\right)
Graphics

Fast inverse square root

The famous Quake III code computes 1/x1/\sqrt{x} with a bit-trick guess followed by one Newton step y(1.5−0.5xy2)y(1.5 - 0.5xy^2).

Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
12 / 21

Newton–Raphson in Python and C

  • Supply both ff and f′f'
  • Stops when ∣xn+1−xn∣<tol|x_{n+1} - x_n| < \text{tol}
  • Guards: f′(x)=0f'(x) = 0 check and an iteration cap
  • Try x0=0.6x_0 = 0.6 (near the minimum of ff) and see the big first jump
Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
13 / 21
Practice

Practice problem

Problem 3"Newton–Raphson's method can fail to converge, or converge to an unintended root, for certain functions or starting points. Describe two distinct scenarios in which this happens, each with a brief illustrative example. Then explain how the Secant method removes the requirement of an analytical derivative and identify one drawback it introduces in exchange."
How to write a complete answer
  • Scenario 1, stationary point: f(x)=x2−1f(x) = x^2 - 1, x0=0x_0 = 0: f′(0)=0f'(0) = 0, the tangent never meets the axis
  • Scenario 2, cycle: f(x)=x3−2x+2f(x) = x^3 - 2x + 2, x0=0x_0 = 0: x1=1x_1 = 1, x2=0x_2 = 0, … forever (or divergence: tan⁡−1x\tan^{-1}x from 1.5)
  • Unintended root: starting near a local extremum throws x1x_1 far away, possibly into another root's basin
  • Secant: replace f′(xn)f'(x_n) by f(xn)−f(xn−1)xn−xn−1\dfrac{f(x_n) - f(x_{n-1})}{x_n - x_{n-1}} (Lecture 10)
  • Drawback: needs two starting values, order drops to 1.618, and can still diverge (no bracket)
Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
14 / 21

When Newton fails

  • Stationary point: f′(xn)=0f'(x_n) = 0, horizontal tangent, division by zero
  • Cycle: x3−2x+2x^3 - 2x + 2 from x0=0x_0 = 0 jumps 0→1→0→1…0 \to 1 \to 0 \to 1 \dots forever
  • Divergence: tan⁡−1x\tan^{-1}x from x0=1.5x_0 = 1.5: −1.69,2.32,−5.11,32.3…-1.69, 2.32, -5.11, 32.3 \dots
  • Double root (x−1)2(x-1)^2: only linear, the error halves each step
  • Same cubic from x0=−2x_0 = -2: converges in 4 steps to −1.769292-1.769292
Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
15 / 21
When to use it

Newton–Raphson: method profile

Best case
  • Simple root, good start, cheap f′f': digits double; x3−x−2x^3 - x - 2 from 1.5 in 3 steps, x2−4x−10x^2 - 4x - 10 from 5 in 4
  • Square roots, reciprocals and Kepler's equation: 3–6 steps to full precision
  • Extends directly to systems (L10) and optimisation (L25)
Worst case
  • Start near f′(x)=0f'(x) = 0: from x0=0.6x_0 = 0.6 the first step jumps to 30.4; 13 steps in total
  • Cycles (x3−2x+2x^3 - 2x + 2 from 0) or divergence (tan⁡−1x\tan^{-1}x from 1.5)
  • Double root (x−1)2(x - 1)^2: only linear, the error just halves
  • No formula for f′f', or ff is noisy
Best suited for
  • Smooth ff with an easy derivative, when a good starting value is known
  • Refining an estimate from bisection (hybrid methods)
  • Hardware: square root, division, inverse square root; ML: second-order optimisers
Avoid when
  • f′f' unavailable or expensive (use secant, L10)
  • No idea where the root is (bracket first)
  • Multiple roots, unless you use x−mf/f′x - m f/f' with known multiplicity mm

Rule of thumb: bracket first, then Newton. Safety from bisection, speed from the tangent.

Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
16 / 21
Comparison

Comparative analysis: x3−x−2=0x^3 - x - 2 = 0 (root 1.521380)

MethodStartIterations for 10−610^{-6}EvaluationsOrderGuaranteed?
Bisection[1,2][1, 2]20≈ 22 of ff1 (rate ½)yes
False position[1,2][1, 2]12≈ 14 of ff1yes
Fixed point, g=(x+2)1/3g = (x+2)^{1/3}1.577 of gg1 (rate 0.14)if ∣g′∣<1|g'| < 1
Newton1.533 of ff + 3 of f′f'2no
Newton from a poor start0.61313 + 132 (eventually)no

Kepler's equation, e=0.9e = 0.9: fixed point 11 iterations, Newton 6. Newton wins on iterations, but each iteration costs two evaluations, and it needs a good start.

Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
17 / 21
Roadmap

Limitations, and where we fix them

Newton is the fastest classical method near a simple root. Its weaknesses are exactly the topics that follow:

What it does well (keep this)
  • Quadratic convergence: digits double
  • One starting value, no bracket
  • Systematic: no guessing a gg
  • Generalises to systems and to optimisation
LimitationHow it is overcomeWhere
Needs the derivative f′f'
→
Replace the tangent by a secant through two recent points
Lecture 10 →
May diverge or cycle from a poor start
→
Hybrid: keep a bracket and fall back to bisection (Brent)
Lecture 10 →
Linear at multiple roots
→
Modified Newton x−m f/f′x - m\,f/f'
this lecture
Several equations, several unknowns
→
Jacobian matrix and a linear solve per step
Lecture 10 →
Finding a minimum instead of a root
→
Apply Newton to f′(x)=0f'(x) = 0 (Hessian in many dimensions)
Lecture 25 →
Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
18 / 21
Applications

Where this method runs in the real world

Click a card to see the exact Newton step inside each system.

Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
19 / 21

Checkpoint

Checkpoint · think, then discuss with your neighbourNewton's method for f(x)=x2−5f(x) = x^2 - 5 starting from x0=2x_0 = 2. What is x1x_1?
A2.5
B2.25
C2.2361
D1.75
B. x1=2−4−54=2+0.25=2.25x_1 = 2 - \dfrac{4 - 5}{4} = 2 + 0.25 = 2.25. Next: x2=2.236111x_2 = 2.236111, x3=2.236068=5x_3 = 2.236068 = \sqrt5.
Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
20 / 21

Summary

Key points
  • xn+1=xn−f(xn)/f′(xn)x_{n+1} = x_n - f(x_n)/f'(x_n): the tangent's crossing; from first-order Taylor
  • Quadratic convergence near a simple root: en+1≈f′′2f′en2e_{n+1} \approx \frac{f''}{2f'}e_n^2, digits double
  • Square root, reciprocal and cube root algorithms are Newton's method
  • Failures: f′≈0f' \approx 0, cycles, divergence from poor x0x_0; only linear at multiple roots
  • In practice: bracket first, then Newton, with safeguards
Opening problem: solved

Newton on f(x)=1/x−7f(x) = 1/x - 7 gives xn+1=xn−1/xn−7−1/xn2=xn(2−7xn)x_{n+1} = x_n - \dfrac{1/x_n - 7}{-1/x_n^2} = x_n(2 - 7x_n): only multiplication. From 0.1: 0.13, 0.1417, 0.14284777, 0.14285714.

Homework
  1. Find the root of xlog⁡10x=1.2x\log_{10}x = 1.2 by Newton's method starting at x0=2.5x_0 = 2.5, to 5 decimal places.
  2. Derive the Newton iteration for N3\sqrt[3]{N} and compute 173\sqrt[3]{17} from x0=2.5x_0 = 2.5.
  3. Find the positive root of cos⁡x=xex\cos x = xe^{x} by Newton's method, 4 decimal places.
  4. Lab: find a starting value for x3−2x+2x^3 - 2x + 2 that leads to the cycle, and one that converges. Explain using the graph.
Next lecture

Secant method and nonlinear systems. Newton without derivatives, a comparison of all five methods, and Newton for several equations at once.

Md Mahbub E Noor
Lecture 9: Newton–Raphson Method
University of Barishal
21 / 21