EulerPad

Practice / Calculus

Newton's method for roots and minima

Ten problems on Newton's method: the update read off the tangent line, square roots and cube roots by iteration, a reciprocal computed without dividing, the exact error identity that makes the digits double, the slow convergence at a double root and its fix, a starting point that cycles, an iteration that runs away, Newton's method for a minimum, a system of two equations with its Jacobian, and a normal quantile found by inverting the distribution function, with worked solutions and the mistakes of adding the step instead of subtracting it, finding a root of the function when its minimum is wanted, expecting quadratic convergence at a double root, seeding the reciprocal iteration too high and transposing the Jacobian.

Before you start

Newton's method finds a root of an equation f(x)=0f(x) = 0 by replacing ff with its tangent line, solving the line instead, and repeating from the new point. Near a simple root it is remarkably fast, because the error at each step is roughly the square of the error before it, so the number of correct digits about doubles. It is how calculators take square roots, how hardware computes reciprocals, how statistical software inverts a distribution function, and, applied to f′f' instead of ff, how second-order optimizers find a minimum. These ten problems derive the update, run it on square roots, cube roots and reciprocals, prove the doubling of digits, and then look at what goes wrong: a double root, a starting point that cycles, an iteration that runs away. They end with a minimum, a system of two equations and a normal quantile. The five mistakes at the end are the ones that still produce numbers: a step added instead of subtracted, the root of the function found when its minimum was wanted, quadratic convergence expected at a double root, a reciprocal iteration started too far out, and a Jacobian used transposed.

  • The update. For a differentiable ff and a current guess xnx_n with f′(xn)≠0f'(x_n) \ne 0, Newton's method sets xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}.
  • Error. If rr is the root, en=xn−re_n = x_n - r is the error of the nn-th guess. A root is simple when f(r)=0f(r) = 0 and f′(r)≠0f'(r) \ne 0, and has multiplicity mm when f(x)=(x−r)mg(x)f(x) = (x - r)^m g(x) with g(r)≠0g(r) \ne 0.
  • Quadratic convergence. Near a simple root, with f′′f'' continuous, en+1≈f′′(r)2f′(r) en2e_{n+1} \approx \dfrac{f''(r)}{2f'(r)}\,e_n^2. Linear convergence means en+1≈c ene_{n+1} \approx c\,e_n with a constant 0<∣c∣<10 < |c| < 1.
  • Minimization. To find a minimum of ff, apply the method to f′f': xn+1=xn−f′(xn)f′′(xn)x_{n+1} = x_n - \dfrac{f'(x_n)}{f''(x_n)}. It finds a point with f′=0f' = 0, which is a minimum when f′′>0f'' > 0 there.
  • Systems. For F:Rn→RnF: \mathbb{R}^n \to \mathbb{R}^n with Jacobian JJ, Jij=∂Fi/∂xjJ_{ij} = \partial F_i/\partial x_j (row ii is equation ii, column jj is variable jj), the step dd solves J(xn) d=−F(xn)J(x_n)\,d = -F(x_n) and xn+1=xn+dx_{n+1} = x_n + d.
  • Φ\Phi is the standard normal distribution function and φ(z)=e−z2/2/2π\varphi(z) = e^{-z^2/2}/\sqrt{2\pi} its density, with Φ′=φ\Phi' = \varphi.

Builds on: Taylor series and linear approximation

Problems

  1. ·

    Derive the Newton update from the tangent line at xnx_n. Then apply it to f(x)=x2−2f(x) = x^2 - 2 from x0=1x_0 = 1: show the update is xn+1=12(xn+2/xn)x_{n+1} = \tfrac12\big(x_n + 2/x_n\big) and find x1x_1, x2x_2 and x3x_3 as fractions.

  2. ·

    Write the Newton update for the cube root of a>0a > 0, using f(x)=x3−af(x) = x^3 - a. Take a=10a = 10 and x0=2x_0 = 2, and find x1x_1 and x2x_2.

  3. ··

    To compute 1/a1/a without dividing, apply Newton's method to f(x)=1x−af(x) = \dfrac1x - a. Show that the update is xn+1=xn(2−axn)x_{n+1} = x_n(2 - ax_n) and that 1−axn+1=(1−axn)21 - ax_{n+1} = (1 - ax_n)^2. Find x1x_1, x2x_2 and x3x_3 for a=7a = 7 from x0=0.1x_0 = 0.1, and say for which x0x_0 the iteration converges.

  4. ··

    For the square-root iteration of Problem 1 with a=2a = 2, show that the errors satisfy en+1=en22xne_{n+1} = \dfrac{e_n^2}{2x_n} exactly. Compute e0e_0 to e4e_4 from x0=1x_0 = 1, and compare the limit of en+1/en2e_{n+1}/e_n^2 with f′′(r)2f′(r)\dfrac{f''(r)}{2f'(r)}.

  5. ··

    f(x)=x3−3x+2=(x−1)2(x+2)f(x) = x^3 - 3x + 2 = (x - 1)^2(x + 2) has a double root at x=1x = 1. Starting from x0=2x_0 = 2, find x1x_1 and x2x_2 and the ratios en+1/ene_{n+1}/e_n. Show that near 11 the ratio tends to 12\tfrac12. Then run the modified step xn+1=xn−2f(xn)/f′(xn)x_{n+1} = x_n - 2f(x_n)/f'(x_n) from the same start.

  6. ··

    Apply Newton's method to f(x)=x3−2x+2f(x) = x^3 - 2x + 2 from x0=0x_0 = 0, and then from x0=−2x_0 = -2. What happens in each case?

  7. ···

    Show that for f(x)=x1/3f(x) = x^{1/3} (the real cube root) the Newton update is xn+1=−2xnx_{n+1} = -2x_n, whatever x0≠0x_0 \ne 0. Then apply the method to f(x)=arctan⁡xf(x) = \arctan x from x0=1x_0 = 1 and from x0=1.5x_0 = 1.5, and compute two steps of each.

  8. ··

    Find the minimum of f(x)=ex−2xf(x) = e^x - 2x with Newton's method from x0=0x_0 = 0: write the update, compute x1x_1 to x3x_3, and compare with the exact minimizer.

  9. ···

    Solve the system x2+y2=4x^2 + y^2 = 4, xy=1xy = 1 with Newton's method from (x0,y0)=(2,0.5)(x_0, y_0) = (2, 0.5): write FF and its Jacobian, take one step, and compare with the exact solution near the start.

  10. ···

    The 97.5%97.5\% point of the standard normal is the root of f(z)=Φ(z)−0.975f(z) = \Phi(z) - 0.975. With Φ(2)≈0.977250\Phi(2) \approx 0.977250 and φ(2)≈0.053991\varphi(2) \approx 0.053991, take one Newton step from z0=2z_0 = 2. Why does the method suit this equation?

Answers

  1. x1=32x_1 = \tfrac32, x2=1712≈1.41667x_2 = \tfrac{17}{12} \approx 1.41667, x3=577408≈1.4142157x_3 = \tfrac{577}{408} \approx 1.4142157
  2. xn+1=13(2xn+a/xn2)x_{n+1} = \tfrac13\big(2x_n + a/x_n^2\big); x1=136≈2.16667x_1 = \tfrac{13}6 \approx 2.16667, x2≈2.154504x_2 \approx 2.154504
  3. xn+1=xn(2−axn)x_{n+1} = x_n(2 - ax_n); x1=0.13x_1 = 0.13, x2=0.1417x_2 = 0.1417, x3=0.14284777x_3 = 0.14284777; it converges exactly when 0<x0<2/a0 < x_0 < 2/a
  4. en+1=en2/(2xn)e_{n+1} = e_n^2/(2x_n); the errors are about 0.08580.0858, 0.002450.00245, 2.1×10−62.1 \times 10^{-6}, 1.6×10−121.6 \times 10^{-12}; the ratio tends to 1/(22)1/(2\sqrt2), the general constant
  5. Plain Newton: x1=149x_1 = \tfrac{14}9, x2≈1.298x_2 \approx 1.298, ratio →12\to \tfrac12 (linear); modified: errors 0.1110.111, 0.00190.0019, 6.3×10−76.3 \times 10^{-7} (quadratic again)
  6. From 00 the guesses cycle 0,1,0,1,…0, 1, 0, 1, \dots forever; from −2-2 they converge to the only real root, r≈−1.7692924r \approx -1.7692924
  7. x1/3x^{1/3}: xn+1=−2xnx_{n+1} = -2x_n, diverging from every start; arctan⁡\arctan: from 11 the iterates go to 00, from 1.51.5 they alternate in sign and grow
  8. xn+1=xn−1+2e−xnx_{n+1} = x_n - 1 + 2e^{-x_n}; x1=1x_1 = 1, x2≈0.7358x_2 \approx 0.7358, x3≈0.6940x_3 \approx 0.6940; the minimizer is ln⁡2≈0.6931\ln 2 \approx 0.6931
  9. (x1,y1)=(2915,3160)≈(1.93333,0.51667)(x_1, y_1) = \big(\tfrac{29}{15}, \tfrac{31}{60}\big) \approx (1.93333, 0.51667); the solution is (6+22,6−22)≈(1.93185,0.51764)\big(\tfrac{\sqrt6 + \sqrt2}{2}, \tfrac{\sqrt6 - \sqrt2}{2}\big) \approx (1.93185, 0.51764)
  10. z1≈1.9583z_1 \approx 1.9583; the iterates converge to 1.9599641.959964, the 1.961.96 of a 95%95\% confidence interval

Worked solutions

Problem 1

Derive the Newton update from the tangent line at xnx_n. Then apply it to f(x)=x2−2f(x) = x^2 - 2 from x0=1x_0 = 1: show the update is xn+1=12(xn+2/xn)x_{n+1} = \tfrac12\big(x_n + 2/x_n\big) and find x1x_1, x2x_2 and x3x_3 as fractions.

  1. Tangent at xnx_n: y=f(xn)+f′(xn)(x−xn)y = f(x_n) + f'(x_n)(x - x_n)The line through (xn,f(xn))(x_n, f(x_n)) with slope f′(xn)f'(x_n).
  2. Set y=0y = 0: x=xn−f(xn)/f′(xn)x = x_n - f(x_n)/f'(x_n)Solve for xx, which needs f′(xn)≠0f'(x_n) \ne 0. This is xn+1x_{n+1}.
  3. xn+1=xn−xn2−22xnx_{n+1} = x_n - \dfrac{x_n^2 - 2}{2x_n}f′(x)=2xf'(x) = 2x.
  4. =2xn2−xn2+22xn=12(xn+2xn)= \dfrac{2x_n^2 - x_n^2 + 2}{2x_n} = \dfrac12\Big(x_n + \dfrac2{x_n}\Big)Common denominator, then split.
  5. x1=12(1+2)=32x_1 = \tfrac12(1 + 2) = \tfrac32, x2=12(32+43)=1712x_2 = \tfrac12\big(\tfrac32 + \tfrac43\big) = \tfrac{17}{12}Each guess is the average of xnx_n and 2/xn2/x_n.
  6. x3=12(1712+2417)=577408x_3 = \tfrac12\big(\tfrac{17}{12} + \tfrac{24}{17}\big) = \tfrac{577}{408}Common denominator 204204, then halve.
  7. x1=32x_1 = \tfrac32, x2=1712≈1.41667x_2 = \tfrac{17}{12} \approx 1.41667, x3=577408≈1.4142157x_3 = \tfrac{577}{408} \approx 1.41421572≈1.4142136\sqrt2 \approx 1.4142136, so x3x_3 is already right to six figures. If xnx_n is too big, 2/xn2/x_n is too small, and their average is closer than either: the Babylonian method for square roots.

Problem 2

Write the Newton update for the cube root of a>0a > 0, using f(x)=x3−af(x) = x^3 - a. Take a=10a = 10 and x0=2x_0 = 2, and find x1x_1 and x2x_2.

  1. xn+1=xn−xn3−a3xn2x_{n+1} = x_n - \dfrac{x_n^3 - a}{3x_n^2}f′(x)=3x2f'(x) = 3x^2.
  2. =3xn3−xn3+a3xn2=13(2xn+axn2)= \dfrac{3x_n^3 - x_n^3 + a}{3x_n^2} = \dfrac13\Big(2x_n + \dfrac{a}{x_n^2}\Big)Common denominator, then split.
  3. x1=13(4+104)=136≈2.16667x_1 = \tfrac13\big(4 + \tfrac{10}4\big) = \tfrac{13}6 \approx 2.16667a=10a = 10, x0=2x_0 = 2.
  4. x2=13(133+10⋅36169)≈2.154504x_2 = \tfrac13\big(\tfrac{13}3 + 10 \cdot \tfrac{36}{169}\big) \approx 2.1545041/x12=36/1691/x_1^2 = 36/169.
  5. xn+1=13(2xn+a/xn2)x_{n+1} = \tfrac13\big(2x_n + a/x_n^2\big); x1=136≈2.16667x_1 = \tfrac{13}6 \approx 2.16667, x2≈2.154504x_2 \approx 2.154504103≈2.154435\sqrt[3]{10} \approx 2.154435, so the errors are about 0.01220.0122 and then 0.0000690.000069. The next step, x3≈2.1544347x_3 \approx 2.1544347, is off by about 2×10−92 \times 10^{-9}.

Problem 3

To compute 1/a1/a without dividing, apply Newton's method to f(x)=1x−af(x) = \dfrac1x - a. Show that the update is xn+1=xn(2−axn)x_{n+1} = x_n(2 - ax_n) and that 1−axn+1=(1−axn)21 - ax_{n+1} = (1 - ax_n)^2. Find x1x_1, x2x_2 and x3x_3 for a=7a = 7 from x0=0.1x_0 = 0.1, and say for which x0x_0 the iteration converges.

  1. f′(x)=−1/x2f'(x) = -1/x^2Power rule.
  2. xn+1=xn−1/xn−a−1/xn2x_{n+1} = x_n - \dfrac{1/x_n - a}{-1/x_n^2}The update.
  3. =xn+xn2(1/xn−a)=xn(2−axn)= x_n + x_n^2\big(1/x_n - a\big) = x_n(2 - ax_n)Dividing by −1/xn2-1/x_n^2 is multiplying by −xn2-x_n^2. Only multiplications and a subtraction are left.
  4. 1−axn+1=1−2axn+a2xn2=(1−axn)21 - ax_{n+1} = 1 - 2ax_n + a^2x_n^2 = (1 - ax_n)^2Expand axn(2−axn)ax_n(2 - ax_n).
  5. x1=0.1(2−0.7)=0.13x_1 = 0.1(2 - 0.7) = 0.13, x2=0.13(2−0.91)=0.1417x_2 = 0.13(2 - 0.91) = 0.1417a=7a = 7.
  6. x3=0.1417(2−0.9919)=0.14284777x_3 = 0.1417(2 - 0.9919) = 0.14284777Exact in decimals.
  7. xn+1=xn(2−axn)x_{n+1} = x_n(2 - ax_n); x1=0.13x_1 = 0.13, x2=0.1417x_2 = 0.1417, x3=0.14284777x_3 = 0.14284777; it converges exactly when 0<x0<2/a0 < x_0 < 2/aWith εn=1−axn\varepsilon_n = 1 - ax_n, step 4 gives εn=ε02n\varepsilon_n = \varepsilon_0^{2^n}: here 0.30.3, 0.090.09, 0.00810.0081, 0.00006560.0000656, against 1/7≈0.142857141/7 \approx 0.14285714. That tends to 00 exactly when ∣ε0∣<1|\varepsilon_0| < 1, that is 0<ax0<20 < ax_0 < 2 (Mistake 4).

Problem 4

For the square-root iteration of Problem 1 with a=2a = 2, show that the errors satisfy en+1=en22xne_{n+1} = \dfrac{e_n^2}{2x_n} exactly. Compute e0e_0 to e4e_4 from x0=1x_0 = 1, and compare the limit of en+1/en2e_{n+1}/e_n^2 with f′′(r)2f′(r)\dfrac{f''(r)}{2f'(r)}.

  1. xn+1−2=xn2+22xn−2x_{n+1} - \sqrt2 = \dfrac{x_n^2 + 2}{2x_n} - \sqrt2Problem 1's update, written over one denominator.
  2. =xn2−22 xn+22xn=(xn−2)22xn= \dfrac{x_n^2 - 2\sqrt2\,x_n + 2}{2x_n} = \dfrac{(x_n - \sqrt2)^2}{2x_n}Common denominator; the numerator is a perfect square.
  3. e0≈−0.414e_0 \approx -0.414, e1≈0.0858e_1 \approx 0.0858, e2≈0.00245e_2 \approx 0.00245x0=1x_0 = 1, x1=1.5x_1 = 1.5, x2=17/12x_2 = 17/12.
  4. e3≈2.12×10−6e_3 \approx 2.12 \times 10^{-6}, e4≈1.59×10−12e_4 \approx 1.59 \times 10^{-12}x3=577/408x_3 = 577/408, and x4=665857/470832x_4 = 665857/470832.
  5. en+1/en2=1/(2xn)→1/(22)≈0.354e_{n+1}/e_n^2 = 1/(2x_n) \to 1/(2\sqrt2) \approx 0.354Step 2, with xn→2x_n \to \sqrt2.
  6. f′′(r)2f′(r)=22⋅22=122\dfrac{f''(r)}{2f'(r)} = \dfrac{2}{2 \cdot 2\sqrt2} = \dfrac1{2\sqrt2}f′′=2f'' = 2 and f′(2)=22f'(\sqrt2) = 2\sqrt2.
  7. en+1=en2/(2xn)e_{n+1} = e_n^2/(2x_n); the errors are about 0.08580.0858, 0.002450.00245, 2.1×10−62.1 \times 10^{-6}, 1.6×10−121.6 \times 10^{-12}; the ratio tends to 1/(22)1/(2\sqrt2), the general constantThe number of correct digits goes about 1,2,5,111, 2, 5, 11, roughly doubling each step. Every error after the first is positive, so from x1x_1 on the guesses come down to 2\sqrt2 from above.

Problem 5

f(x)=x3−3x+2=(x−1)2(x+2)f(x) = x^3 - 3x + 2 = (x - 1)^2(x + 2) has a double root at x=1x = 1. Starting from x0=2x_0 = 2, find x1x_1 and x2x_2 and the ratios en+1/ene_{n+1}/e_n. Show that near 11 the ratio tends to 12\tfrac12. Then run the modified step xn+1=xn−2f(xn)/f′(xn)x_{n+1} = x_n - 2f(x_n)/f'(x_n) from the same start.

  1. f′(x)=3x2−3f'(x) = 3x^2 - 3; x1=2−49=149≈1.5556x_1 = 2 - \tfrac{4}{9} = \tfrac{14}9 \approx 1.5556f(2)=4f(2) = 4, f′(2)=9f'(2) = 9.
  2. x2≈1.2979x_2 \approx 1.2979; errors 11, 0.5560.556, 0.2980.298One more step; the ratios are 0.5560.556 and 0.5360.536.
  3. ff′=(x−1)2(x+2)(x−1)(3x+3)=(x−1)(x+2)3(x+1)\dfrac{f}{f'} = \dfrac{(x - 1)^2(x + 2)}{(x - 1)(3x + 3)} = \dfrac{(x - 1)(x + 2)}{3(x + 1)}f′=3(x−1)(x+1)f' = 3(x - 1)(x + 1); one factor x−1x - 1 cancels.
  4. en+1=en(1−xn+23(xn+1))→en(1−36)e_{n+1} = e_n\Big(1 - \dfrac{x_n + 2}{3(x_n + 1)}\Big) \to e_n\big(1 - \tfrac36\big)Subtract step 3 from xn−1x_n - 1; at xn=1x_n = 1 the bracket is 12\tfrac12.
  5. Modified: x1=2−89=109x_1 = 2 - \tfrac89 = \tfrac{10}9, then x2≈1.00195x_2 \approx 1.00195, x3≈1.00000063x_3 \approx 1.00000063Twice the Newton step from each point.
  6. Plain Newton: x1=149x_1 = \tfrac{14}9, x2≈1.298x_2 \approx 1.298, ratio →12\to \tfrac12 (linear); modified: errors 0.1110.111, 0.00190.0019, 6.3×10−76.3 \times 10^{-7} (quadratic again)At a root of multiplicity mm, f/f′≈e/mf/f' \approx e/m, so a plain step removes only 1/m1/m of the error and the ratio is (m−1)/m(m - 1)/m. Multiplying the step by mm restores the fast convergence, when mm is known.

Problem 6

Apply Newton's method to f(x)=x3−2x+2f(x) = x^3 - 2x + 2 from x0=0x_0 = 0, and then from x0=−2x_0 = -2. What happens in each case?

  1. f′(x)=3x2−2f'(x) = 3x^2 - 2, so xn+1=xn−xn3−2xn+23xn2−2x_{n+1} = x_n - \dfrac{x_n^3 - 2x_n + 2}{3x_n^2 - 2}The update.
  2. x1=0−2−2=1x_1 = 0 - \tfrac{2}{-2} = 1f(0)=2f(0) = 2, f′(0)=−2f'(0) = -2.
  3. x2=1−11=0x_2 = 1 - \tfrac11 = 0f(1)=1f(1) = 1, f′(1)=1f'(1) = 1.
  4. From −2-2: x1=−2−−210=−1.8x_1 = -2 - \tfrac{-2}{10} = -1.8, then x2≈−1.76995x_2 \approx -1.76995f(−2)=−2f(-2) = -2, f′(−2)=10f'(-2) = 10.
  5. x3≈−1.769293x_3 \approx -1.769293, x4≈−1.7692924x_4 \approx -1.7692924Two more steps; the iterates stop changing in the seventh figure.
  6. From 00 the guesses cycle 0,1,0,1,…0, 1, 0, 1, \dots forever; from −2-2 they converge to the only real root, r≈−1.7692924r \approx -1.7692924The tangent at 00 crosses the axis at 11, and the tangent at 11 crosses it at 00. Newton's method only promises convergence from a start close enough to a root. Here ff has a local maximum and a local minimum at x=±2/3≈±0.816x = \pm\sqrt{2/3} \approx \pm 0.816, where f′=0f' = 0 and the update is not even defined, and the starts 00 and 11 sit on either side of the local minimum, far from the root.

Problem 7

Show that for f(x)=x1/3f(x) = x^{1/3} (the real cube root) the Newton update is xn+1=−2xnx_{n+1} = -2x_n, whatever x0≠0x_0 \ne 0. Then apply the method to f(x)=arctan⁡xf(x) = \arctan x from x0=1x_0 = 1 and from x0=1.5x_0 = 1.5, and compute two steps of each.

  1. f′(x)=13x−2/3f'(x) = \tfrac13 x^{-2/3} for x≠0x \ne 0Power rule; it holds for negative xx too, with the real cube root.
  2. f(x)f′(x)=x1/313x−2/3=3x\dfrac{f(x)}{f'(x)} = \dfrac{x^{1/3}}{\tfrac13 x^{-2/3}} = 3xx1/3⋅x2/3=xx^{1/3} \cdot x^{2/3} = x.
  3. xn+1=xn−3xn=−2xnx_{n+1} = x_n - 3x_n = -2x_nSo from x0=1x_0 = 1: −2-2, 44, −8-8, …\dots, doubling away from the root 00.
  4. For arctan⁡\arctan: xn+1=xn−(1+xn2)arctan⁡xnx_{n+1} = x_n - (1 + x_n^2)\arctan x_nf′(x)=1/(1+x2)f'(x) = 1/(1 + x^2).
  5. From 11: x1=1−2⋅π4≈−0.5708x_1 = 1 - 2 \cdot \tfrac\pi4 \approx -0.5708, x2≈0.1169x_2 \approx 0.1169Then x3≈−0.0011x_3 \approx -0.0011, closing in on 00.
  6. From 1.51.5: x1≈1.5−3.25⋅0.98279≈−1.6941x_1 \approx 1.5 - 3.25 \cdot 0.98279 \approx -1.6941, x2≈2.3211x_2 \approx 2.3211arctan⁡1.5≈0.98279\arctan 1.5 \approx 0.98279; then x3≈−5.114x_3 \approx -5.114.
  7. x1/3x^{1/3}: xn+1=−2xnx_{n+1} = -2x_n, diverging from every start; arctan⁡\arctan: from 11 the iterates go to 00, from 1.51.5 they alternate in sign and growAt the root of x1/3x^{1/3} the derivative is infinite, so the theory's assumption f′(r)≠0f'(r) \ne 0 finite fails, and f/f′f/f' is three times the distance to the root. arctan⁡\arctan has a perfectly good simple root, but it flattens out, so a tangent from far away overshoots; the starts that converge are those with ∣x0∣<1.3917|x_0| < 1.3917 about.

Problem 8

Find the minimum of f(x)=ex−2xf(x) = e^x - 2x with Newton's method from x0=0x_0 = 0: write the update, compute x1x_1 to x3x_3, and compare with the exact minimizer.

  1. f′(x)=ex−2f'(x) = e^x - 2, f′′(x)=exf''(x) = e^xThe step uses the first two derivatives.
  2. xn+1=xn−exn−2exn=xn−1+2e−xnx_{n+1} = x_n - \dfrac{e^{x_n} - 2}{e^{x_n}} = x_n - 1 + 2e^{-x_n}Newton's method on f′f'.
  3. x1=0−1+2=1x_1 = 0 - 1 + 2 = 1e0=1e^0 = 1.
  4. x2=1−1+2/e≈0.735759x_2 = 1 - 1 + 2/e \approx 0.7357592e−12e^{-1}.
  5. x3=x2−1+2e−x2≈0.694042x_3 = x_2 - 1 + 2e^{-x_2} \approx 0.694042e−0.735759≈0.479142e^{-0.735759} \approx 0.479142.
  6. Exact: ex=2e^x = 2, so x∗=ln⁡2≈0.693147x^* = \ln 2 \approx 0.693147f′′=ex>0f'' = e^x > 0 everywhere, so this is the global minimum.
  7. xn+1=xn−1+2e−xnx_{n+1} = x_n - 1 + 2e^{-x_n}; x1=1x_1 = 1, x2≈0.7358x_2 \approx 0.7358, x3≈0.6940x_3 \approx 0.6940; the minimizer is ln⁡2≈0.6931\ln 2 \approx 0.6931The errors are 0.3070.307, 0.0430.043, 0.00090.0009 and then 4×10−74 \times 10^{-7}: quadratic again, now for f′f'. Each step jumps to the minimum of the quadratic Taylor model at xnx_n. The minimum value is 2−2ln⁡2≈0.614>02 - 2\ln 2 \approx 0.614 > 0, so ff itself has no root (Mistake 2).

Problem 9

Solve the system x2+y2=4x^2 + y^2 = 4, xy=1xy = 1 with Newton's method from (x0,y0)=(2,0.5)(x_0, y_0) = (2, 0.5): write FF and its Jacobian, take one step, and compare with the exact solution near the start.

  1. F(x,y)=(x2+y2−4, xy−1)F(x, y) = \big(x^2 + y^2 - 4,\ xy - 1\big)Both equations moved to the form F=0F = 0.
  2. J=[2x2yyx]J = \begin{bmatrix} 2x & 2y \\ y & x \end{bmatrix}Row ii holds the partial derivatives of FiF_i in xx and then yy.
  3. F(2,0.5)=(0.25,0)F(2, 0.5) = (0.25, 0), J=[410.52]J = \begin{bmatrix} 4 & 1 \\ 0.5 & 2 \end{bmatrix}At the start.
  4. 4d1+d2=−0.254d_1 + d_2 = -0.25 and 0.5d1+2d2=00.5d_1 + 2d_2 = 0J d=−FJ\,d = -F.
  5. d1=−4d2d_1 = -4d_2, so −15d2=−0.25-15d_2 = -0.25The second equation, substituted into the first.
  6. d2=160d_2 = \tfrac1{60}, d1=−115d_1 = -\tfrac1{15}So (x1,y1)=(2−115, 0.5+160)(x_1, y_1) = (2 - \tfrac1{15},\ 0.5 + \tfrac1{60}).
  7. Exact: (x+y)2=6(x + y)^2 = 6, (x−y)2=2(x - y)^2 = 2x2+y2±2xy=4±2x^2 + y^2 \pm 2xy = 4 \pm 2.
  8. (x1,y1)=(2915,3160)≈(1.93333,0.51667)(x_1, y_1) = \big(\tfrac{29}{15}, \tfrac{31}{60}\big) \approx (1.93333, 0.51667); the solution is (6+22,6−22)≈(1.93185,0.51764)\big(\tfrac{\sqrt6 + \sqrt2}{2}, \tfrac{\sqrt6 - \sqrt2}{2}\big) \approx (1.93185, 0.51764)The errors fall from about 0.070.07 to 0.00150.0015 in one step and to 1.1×10−61.1 \times 10^{-6} in the next. The step solves the linearized system, so a 2×22 \times 2 solve takes the place of the division by f′f'.

Problem 10

The 97.5%97.5\% point of the standard normal is the root of f(z)=Φ(z)−0.975f(z) = \Phi(z) - 0.975. With Φ(2)≈0.977250\Phi(2) \approx 0.977250 and φ(2)≈0.053991\varphi(2) \approx 0.053991, take one Newton step from z0=2z_0 = 2. Why does the method suit this equation?

  1. f′(z)=φ(z)f'(z) = \varphi(z)Φ′=φ\Phi' = \varphi, and the constant drops out.
  2. z1=2−0.0022500.053991z_1 = 2 - \dfrac{0.002250}{0.053991}f(2)=0.977250−0.975f(2) = 0.977250 - 0.975.
  3. z1≈2−0.04167=1.95833z_1 \approx 2 - 0.04167 = 1.95833The step is negative because Φ(2)\Phi(2) is already above 0.9750.975.
  4. z2≈1.959961z_2 \approx 1.959961, z3≈1.9599640z_3 \approx 1.9599640Repeat with Φ\Phi and φ\varphi at the new point.
  5. z1≈1.9583z_1 \approx 1.9583; the iterates converge to 1.9599641.959964, the 1.961.96 of a 95%95\% confidence intervalThe derivative of a distribution function is its density, which is cheap to evaluate and positive, so every step is defined, and the root is simple. The errors are about 0.00160.0016, then 2.6×10−62.6 \times 10^{-6}, then about 7×10−127 \times 10^{-12}: the digits double each step.

Where this goes wrong

1. Adding the step instead of subtracting it

The update is remembered as “xx plus a correction”, and the sign of the correction is easy to flip.

  1. f(x)=x2−2f(x) = x^2 - 2, x0=1x_0 = 1, f(1)=−1f(1) = -1, f′(1)=2f'(1) = 2Right so far: Problem 1.
  2. “x1=x0+f(x0)/f′(x0)x_1 = x_0 + f(x_0)/f'(x_0).”The tangent line crosses zero at x0−f(x0)/f′(x0)x_0 - f(x_0)/f'(x_0): below the axis with a positive slope, the crossing is to the right.
  3. x1=1+−12=0.5x_1 = 1 + \tfrac{-1}{2} = 0.5The guess moves away from 2\sqrt2, and the next wrong step jumps to −1.25-1.25, on the far side of 00. The right step gives x1=1−−12=1.5x_1 = 1 - \tfrac{-1}2 = 1.5. A quick check: ∣f(x1)∣|f(x_1)| should be smaller than ∣f(x0)∣|f(x_0)|, and f(0.5)=−1.75f(0.5) = -1.75.

2. Finding a root of f when its minimum is wanted

The same formula finds roots and minima, and it is easy to feed it the function instead of its derivative.

  1. Minimize f(x)=ex−2xf(x) = e^x - 2x from x0=0x_0 = 0Right so far: Problem 8.
  2. “Newton's step is x−f/f′x - f/f'.”That finds where f=0f = 0. A minimum is where f′=0f' = 0, so the step is x−f′/f′′x - f'/f''.
  3. x1=0−1−1=1x_1 = 0 - \tfrac{1}{-1} = 1, x2=1−e−2e−2=0x_2 = 1 - \tfrac{e - 2}{e - 2} = 0The first step happens to agree with Problem 8, which hides the slip; then the guesses cycle 0,1,0,10, 1, 0, 1. They cannot settle anywhere, because f≥2−2ln⁡2≈0.614f \ge 2 - 2\ln 2 \approx 0.614 has no root. The minimizer is ln⁡2≈0.693\ln 2 \approx 0.693.

3. Expecting quadratic convergence at a double root

Newton's method is famous for doubling the digits, and the promise is quoted without its condition f′(r)≠0f'(r) \ne 0.

  1. f(x)=(x−1)2(x+2)f(x) = (x - 1)^2(x + 2), x0=2x_0 = 2Right so far: Problem 5.
  2. “Ten steps of Newton's method are plenty for ten digits.”That holds at a simple root. Here f′(1)=0f'(1) = 0, and each step only halves the error.
  3. After ten steps, x10x_{10} is 11 to about ten digitsIt is about 1.00131.0013: the error is 1.3×10−31.3 \times 10^{-3}, and twenty steps reach only about 1.2×10−61.2 \times 10^{-6}. The ratio en+1/en→12e_{n+1}/e_n \to \tfrac12 is the sign of a double root; the step x−2f/f′x - 2f/f' of Problem 5 gets six digits in three steps.

4. Seeding the reciprocal iteration too high

Any rough guess near 1/a1/a looks good enough, and 0.30.3 seems a fair guess for 1/71/7.

  1. xn+1=xn(2−7xn)x_{n+1} = x_n(2 - 7x_n)Right so far: Problem 3 with a=7a = 7.
  2. “Start from x0=0.3x_0 = 0.3.”Convergence needs ∣1−7x0∣<1|1 - 7x_0| < 1, that is 0<x0<2/7≈0.28570 < x_0 < 2/7 \approx 0.2857; here 1−7x0=−1.11 - 7x_0 = -1.1.
  3. x1=0.3(2−2.1)=−0.03x_1 = 0.3(2 - 2.1) = -0.03, x2=−0.03(2+0.21)=−0.0663x_2 = -0.03(2 + 0.21) = -0.0663The quantity 1−7xn1 - 7x_n is squared at each step, from −1.1-1.1 to 1.211.21, then 1.46411.4641, and the guesses run off to −∞-\infty. Hardware first reads a guess from a table, which keeps ∣1−ax0∣|1 - ax_0| well below 11.

5. Using the Jacobian transposed

In two variables the step needs a matrix, and the rows and columns of JJ are easy to swap.

  1. F(2,0.5)=(0.25,0)F(2, 0.5) = (0.25, 0)Right so far: Problem 9, step 3.
  2. “J=[2xy2yx]J = \begin{bmatrix} 2x & y \\ 2y & x \end{bmatrix}, with each column one equation.”Row ii of the Jacobian is equation ii: the first row is (2x,2y)(2x, 2y).
  3. (x1,y1)≈(1.93333,0.53333)(x_1, y_1) \approx (1.93333, 0.53333)The transposed system gives d2=130d_2 = \tfrac1{30} instead of 160\tfrac1{60}, so yy overshoots: its error only shrinks from 0.0180.018 to 0.0160.016, where the right step brings it to 0.0010.001, and the first equation is off by 0.0220.022 instead of 0.0050.005. Here the transposed steps still converge, but only linearly: after five of them the error is about 2×10−52 \times 10^{-5}, where Newton's own steps reach 8×10−138 \times 10^{-13} in three.

Print this set: newtons-method.pdf (problems, answers, and worked solutions on separate pages).

Read the guide: Newton's method: x − f(x)/f′(x), digits that double, and the starts that run away

More practice sets

All practice sets

More at eulerpad.app. This is one of 82 free practice sets with worked solutions at eulerpad.app/practice, alongside guides to the topics behind them.

EulerPad, the app, reads your handwritten math on iPad, iPhone and Android and checks it line by line. It's free to start.

This set is also Chapter 10 of Calculus I & II, a 250-problem workbook with worked solutions: eulerpad.app/workbooks

eulerpad.app/practice/newtons-method