2.4.3 Newton's method with derivatives

Any slope, from the rules

Lesson 1.3.3 ran Newton's method on a few borrowed slopes: those of $x^2$ and $x^3$ , and the fact that adding $mx$ adds $m$ . Module 2.3 now gives the slope of any function built from powers, products, quotients, exponentials and logs. So Newton's method works for all of them.

The step is the same. The tangent at the guess $x_n$ is the line $y = f(x_n) + f'(x_n)(x - x_n)$ of lesson 2.2.1, and the next guess is where it crosses zero.

Rule: Newton's method

x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

$f(x_n)$ is a height and $f'(x_n)$ a slope, so their ratio is in input units: the distance to step sideways. The slope must not be 0.

Solving $xe^x = 1$

No formula gives $x$ . So take $f(x) = xe^x - 1$ and look for its root. The product rule (lesson 2.3.2), with $e^x$ as its own slope (lesson 2.3.4), gives

f'(x) = e^x + xe^x = e^x(1 + x)

Start at $x_0 = 1$ . There $f(1) = e - 1 \approx 1.718$ and $f'(1) = 2e \approx 5.437$ , so $x_1 = 1 - \frac{1.718}{5.437} \approx 0.684$ .

step $n$	guess $x_n$	$f(x_n)$
1	0.6839397205857212	0.355
2	0.5774544771544498	0.0287
3	0.5672297377301171	0.000239
4	0.5671432965302959	0.0000000169
5	0.567143290409784	$2 \times 10^{-16}$

The root is $x \approx 0.567143$ . The last value of $f$ is zero up to rounding: the computer keeps about 16 digits (lesson 2.1.1).

f

import math def f(x): return x * math.exp(x) - 1 def slope(x): return math.exp(x) * (1 + x) x = 1.0 for step in range(1, 6): x = x - f(x) / slope(x) print(step, x, f(x))

⌘/Ctrl + Enter runs the cell

How fast: the error squares

Write $r$ for the root and $e_n = x_n - r$ for the error of guess $n$ . Here are the errors for $xe^x - 1$ from $x_0 = 1$ , with the number of correct digits, $-\log_{10} e_n$ (lesson 1.4.3).

step $n$	error $e_n$	correct digits	$e_n \div e_{n-1}^2$
0	0.433	0.4
1	0.117	0.9	0.62
2	0.0103	2.0	0.76
3	0.0000864	4.1	0.81
4	0.00000000612	8.2	0.82

The correct digits go 1, 2, 4, 8: they double. The last column settles near 0.82, so each error is about 0.82 times the square of the one before. An error that squares each step is called quadratic convergence.

Rule: Quadratic convergence

e_{n+1} \approx \frac{f''(r)}{2f'(r)}\, e_n^2

This holds near a root $r$ where $f'(r) \neq 0$ . The constant uses the second derivative of lesson 2.4.2; module 2.7 shows where it comes from.

For $xe^x - 1$ , $f''(x) = e^x(2 + x)$ , and the constant at $r$ is 0.819, the number the table settles on. For $x^2 - 2$ of lesson 1.3.3, $f'' = 2$ and $f'(\sqrt{2}) = 2\sqrt{2}$ , so the constant is $\frac{1}{2\sqrt{2}} \approx 0.354$ . That is the "about a third" lesson 1.3.3 saw.

At a double root $f'(r) = 0$ , so the rule fails. That is why lesson 1.3.3 saw the error of $(x - 1)^2$ only halve each step.

\frac{f''(r)}{2f'(r)}

import math def f(x): return x * math.exp(x) - 1 def slope(x): return math.exp(x) * (1 + x) guesses = [1.0] for step in range(8): x = guesses[-1] guesses.append(x - f(x) / slope(x)) root = guesses[-1] errors = [x - root for x in guesses[:5]] for n, e in enumerate(errors): ratio = "-" if n == 0 else round(e / errors[n - 1] ** 2, 2) print(n, f"{e:.2e}", round(-math.log10(e), 1), ratio) print(round(math.exp(root) * (2 + root) / (2 * slope(root)), 3))

⌘/Ctrl + Enter runs the cell

The explorer below starts on $x^3 - x - 1$ from 1.5, the cubic of lesson 1.3.3, whose slope is $3x^2 - 1$ by the power rule (lesson 2.3.1). Press Next step and watch the distance from the root in the readout: about 0.023, then 0.00048, then 0.00000022. Each error is roughly the square of the last, scaled by a constant.

Explore

Press Next step. Each step follows the tangent line at the current guess down to where it crosses zero, which is the next guess.

Steps: 0
Current guess: 1.5
f there: 0.875
Distance from the root 1.324718: 0.175282042755

Good starts and bad starts

From $x_0 = 1$ , every guess for $xe^x = 1$ landed right of the root: 0.684, then 0.577, then 0.5672. Concavity explains it. $f''(x) = e^x(2 + x)$ is positive for $x > -2$ , so the curve is concave up there and lies above each tangent (lesson 2.4.2).

Follow such a tangent down from $x_n$ to zero. There the curve, which lies above the tangent, is still above zero, so the root is further left. Each guess therefore lands between the root and the previous guess: it never overshoots.

From a start left of the root it overshoots once: $x_0 = 0$ gives $x_1 = 1$ , and the guesses then march back from the right.

A start that runs away

$g(x) = xe^{-x}$ has its root at 0. The product rule (lesson 2.3.2), with $-e^{-x}$ as the slope of $e^{-x}$ (lesson 2.3.4), gives $g'(x) = (1 - x)e^{-x}$ , as in lesson 2.4.1. From $x_0 = 2$ :

step $n$	1	2	3	4
guess $x_n$	4	5.3333	6.5641	7.7438
$g(x_n)$	0.0733	0.0257	0.0093	0.0034

The values of $g$ shrink towards 0, yet the guesses move away from the root. Past its peak at 1, the curve sinks towards the axis without reaching it, and the tangents get flatter.

Algebra shows it never stops. The step simplifies to $x - \frac{x}{1 - x} = \frac{x^2}{x - 1}$ , which is more than $x + 1$ whenever $x > 1$ .

At $x = 1$ the tangent is flat and the step divides by 0. From $x_0 = 0.5$ the guesses go $-0.5$ , $-0.1667$ , $-0.0238$ , $-0.0006$ : straight to the root.

Two starts. For $xe^x - 1$ the curve bends up, so each tangent lies below it and every guess lands between the root and the last guess. For $xe^{-x}$ from 2, each tangent is flatter than the last and the guesses run away from the root at 0.

Lesson 1.3.3 met the other failures: a flat tangent, a cycle, a double root, no root, and an unexpected root.

xe^{-x}

import math def g(x): return x * math.exp(-x) def g_slope(x): return (1 - x) * math.exp(-x) for x0 in [2.0, 0.5]: x = x0 row = [] for step in range(4): x = x - g(x) / g_slope(x) row.append((round(x, 4), round(g(x), 4))) print(x0, row)

⌘/Ctrl + Enter runs the cell

Newton or bisection?

Bisection (lesson 1.3.2) and Newton's method make opposite trades. Here both solve $xe^x = 1$ to $10^{-12}$ :

	bisection on $[0, 1]$	Newton from 1
needs	a sign change	a slope and a start
each step	halves the bracket	about doubles the digits
steps to $10^{-12}$	40	6
can fail?	no, once bracketed	yes

Newton's count includes a last tiny step that shows the guess has stopped moving, as in lesson 1.3.3. Bisection needs 40 steps because $2^{40}$ is the first power of 2 above $10^{12}$ .

Newton with a bracket

Careful code gets both: Newton's speed and bisection's guarantee. Keep a bracket $[a, b]$ with a sign change. After each guess, shrink the bracket to the half that still changes sign, as bisection does.

Rule: Newton with a bracket

\begin{gathered} \text{if } x - \frac{f(x)}{f'(x)} \text{ lies inside } [a, b], \\ \text{take that step;} \\ \text{otherwise take } \frac{a + b}{2} \end{gathered}

A Newton step that would leave the bracket, or a flat tangent, is replaced by a bisection step. The root never escapes, and near it the Newton steps take over.

x^3 - 2x + 2

import math def safe_newton(f, slope, a, b, tol=1e-12): x = (a + b) / 2 for step in range(1, 101): fx = f(x) if fx == 0: return x, step if (fx < 0) == (f(a) < 0): a = x else: b = x s = slope(x) new = x - fx / s if s != 0 else x if not a < new < b: new = (a + b) / 2 if abs(new - x) < tol: return new, step x = new print(safe_newton(lambda x: x**3 - 2 * x + 2, lambda x: 3 * x**2 - 2, -2, 0)) print(safe_newton(lambda x: x * math.exp(-x), lambda x: (1 - x) * math.exp(-x), -1, 4))

⌘/Ctrl + Enter runs the cell

SciPy's brentq (lesson 1.3.2) mixes safe and fast steps in a similar way, with chords instead of tangents. Practice set 2.4.4 asks you to write this solver, and case study 2.4.6 needs it for options whose price curve is almost flat.

Newton for a minimum

A local minimum is a root of $f'$ (lesson 2.4.1), and Newton's method finds roots. Its step then divides by the slope of $f'$ , which is $f''$ .

Rule: Newton for a critical point

x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)}

Newton's method applied to $f'$ instead of $f$ . It finds any critical point, so check the answer with $f''$ (lesson 2.4.2): positive means a minimum, negative a maximum.

Take $f(x) = x^4 - 3x^2 + x$ , with $f'(x) = 4x^3 - 6x + 1$ and $f''(x) = 12x^2 - 6$ . From $x_0 = 1$ the guesses are 1.166667, 1.132616, 1.130905 and 1.130901. There $f'' \approx 9.35 > 0$ , so it is a minimum, with value $-1.0702$ .

The start decides which critical point you get. From 0, Newton lands on 0.169938, where $f'' \approx -5.65$ : a maximum. From $-1$ it lands on $-1.30084$ , a second minimum with the lower value $-3.5139$ .

f''

from scipy.optimize import newton def d1(x): return 4 * x**3 - 6 * x + 1 def d2(x): return 12 * x**2 - 6 x = 1.0 for step in range(1, 6): x = x - d1(x) / d2(x) print(step, x) print(round(d2(x), 4), round(x**4 - 3 * x**2 + x, 4)) for x0 in [0.0, -1.0]: c = newton(d1, x0, fprime=d2) print(x0, round(c, 6), round(d2(c), 4), round(c**4 - 3 * c**2 + c, 4))

⌘/Ctrl + Enter runs the cell

Common mistakes

Use the slope from the rules at the current guess. A wrong derivative still moves the guess, but convergence slows or fails. A central difference (lesson 2.2.2) is a quick check.
A small $f(x_n)$ is not a small error. For $xe^{-x}$ from 2, $g$ falls to 0.0034 while the guess runs off past 7.
Quadratic convergence needs $f'(r) \neq 0$ . At a double root the error only halves.
The start matters. For $xe^{-x}$ , any start above 1 runs away, and a start at 1 has a flat tangent.
Fast is not safe. When you cannot pick a good start, keep a bracket and bisect whenever a step leaves it.
For a minimum, give Newton $f'$ and $f''$ , not $f$ and $f'$ , and check the sign of $f''$ at the answer.

Newton's method with derivatives

0 of 12 correct

1.
For $f(x) = xe^x - 1$ , with slope $e^x(1 + x)$ , take one Newton step from $x_0 = 0$
2.
For $f(x) = xe^x - 1$ , take one Newton step from $x_0 = 1$
3.
For $f(x) = e^x - 3$ , take one Newton step from $x_0 = 1$
4.
Near a root, each error is 0.8 times the square of the last. The error is 0.001. What is the next one?
5.
For $f(x) = x^2 - 9$ at its root 3, find the constant $\frac{f''(3)}{2f'(3)}$
6.
$f$ is rising and concave up, and $x_0$ is right of the root. Does $x_1$ land right of the root (type 1) or left (type 0)?
7.
For $xe^{-x}$ , Newton's step simplifies to $\frac{x^2}{x - 1}$ . Take one step from $x_0 = 3$
8.
At which $x$ is Newton's step for $xe^{-x}$ undefined?
9.
How many bisection steps shrink a bracket of width 1 below $10^{-12}$ ?
10.
$f(x) = x^3 - 2x + 2$ has bracket $[-2, 0]$ , with $f(-2) = -2$ . At $-1$ , $f = 3$ and the Newton step would land on $-4$ . Where does a bracketed step go instead?
11.
For $f'(x) = 4x^3 - 6x + 1$ and $f''(x) = 12x^2 - 6$ , take one Newton step from $x_0 = 1$
12.
Newton's method on $f'$ lands on a point where $f'' = -3$ . Is it a maximum (type 1) or a minimum (type 0)?

How to type answers

Powers with ^: x^7, 2^(1/3), a^-2.
Multiply with * or by writing side by side: 3x^2, 2(x+1).
ln(x) is the natural log, log(x, 2) is log base 2, e is Euler's number, sqrt(x) is a square root.
sin(x), cos(x) and tan(x) take radians; write pi for π and sin(x)^2 for sin²x.
Your first answer to each question is saved: it counts towards your score and brings the question back for review.
Exact answers like ln(20)/ln(3) are best. Decimals need about 4 significant figures.

x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

Newton's method with derivatives

Any slope, from the rules

Rule: Newton's method

Solving $xe^x = 1$

How fast: the error squares

Rule: Quadratic convergence

Good starts and bad starts

A start that runs away

Newton or bisection?

Newton with a bracket

Rule: Newton with a bracket

Newton for a minimum

Rule: Newton for a critical point

Common mistakes

Newton's method with derivatives

Summary card

Free further reading

Any slope, from the rules

Rule: Newton's method

Solving xex=1xe^x = 1xex=1

How fast: the error squares

Rule: Quadratic convergence

Good starts and bad starts

A start that runs away

Newton or bisection?

Newton with a bracket

Rule: Newton with a bracket

Newton for a minimum

Rule: Newton for a critical point

Common mistakes

Summary card

Free further reading

Solving $xe^x = 1$