Newton's method
Most equations cannot be solved by algebra. If you can guess roughly where a root is, how can you sharpen the guess quickly?
Where you are 11 in Applications of derivatives
When you reach for it
Reach for Newton’s method when you need a root of f(x) = 0 to many decimal places, no formula gives it, f is differentiable, and a graph, a table of values or a few steps of bisection give a reasonable first guess. Typical cases are a cubic such as x^3 - 2x - 5 = 0, an equation such as e^x = 4x, and a square root. When it works it is far faster than bisection.
The procedure
One step, from the linearization. Suppose x_n is a guess near a root r and f'(x_n) \ne 0. Near x_n the graph is close to its tangent line, which written as a function is the linearization of f at x_n:
We cannot solve f(x) = 0, but we can solve L(x) = 0, because L is linear. Setting L(x) = 0 gives f'(x_n)(x - x_n) = -f(x_n). Dividing by f'(x_n), which is allowed because it is not zero, the solution is the next guess:
So x_{n+1} is where the tangent line at (x_n, f(x_n)) crosses the x-axis. From x_{n+1} we do the same again. A first guess x_0 produces a sequence x_0, x_1, x_2, \ldots in which every term comes from the one before by the same formula, an iteration.
How fast it closes in. Write e_n = x_n - r for the error. The following is stated here without proof. If f'(r) \ne 0, f'' is continuous near r, and x_0 is close enough to r, then the iterates converge to r, and there is a constant K with
Close to r the ratio |e_{n+1}|/e_n^2 approaches \left|\dfrac{f''(r)}{2f'(r)}\right|. The reason: the tangent line misses the graph by about a constant times the distance squared, as for linearizations. Once the error is small, the number of correct decimal places roughly doubles at every step: quadratic convergence. Bisection halves the error bound at each step, about 3.3 steps per decimal place (since 2^{10} \approx 10^3).
When to stop. We stop when two successive iterates agree to the places wanted and f is tiny at the last one. That is evidence, not proof. A proof is a sign change of f across a short interval around the answer, by the intermediate value theorem.
Worked examples
Newton’s own cubic
Approximate the real root of x^3 - 2x - 5 = 0 starting from x_0 = 2, and follow the error.
SolutionHere f(x) = x^3 - 2x - 5 and, by the power rule, f'(x) = 3x^2 - 2. Since f(2) = -1 < 0 and f(3) = 16 > 0, a root lies in [2, 3], and the small value f(2) = -1 suggests it is near 2. The first step is
Next, f(2.1) = 9.261 - 4.2 - 5 = 0.061 and f'(2.1) = 3(4.41) - 2 = 11.23, so
Carrying full precision through two more steps, and comparing with the root r \approx 2.0945514815423:
| n | x_n | f(x_n) | \lvert x_n - r \rvert |
|---|---|---|---|
| 0 | 2 | -1 | 9.5 \times 10^{-2} |
| 1 | 2.1 | 0.061 | 5.4 \times 10^{-3} |
| 2 | 2.0945681 | 1.9 \times 10^{-4} | 1.7 \times 10^{-5} |
| 3 | 2.094551481698 | 1.7 \times 10^{-9} | 1.6 \times 10^{-10} |
| 4 | 2.0945514815423 | 1.5 \times 10^{-19} | 1.4 \times 10^{-20} |
The exponents of the error run -2, -3, -5, -10, -20: from x_2 on, each error is about 0.56 times the square of the one before, and 0.56 is \left|\dfrac{f''(r)}{2f'(r)}\right| = \dfrac{6r}{2(3r^2 - 2)}. As a certificate, f(2.0945514815) < 0 and f(2.0945514816) > 0, so r \approx 2.0945514815 to ten places.
Newton showed his method on this equation, also from 2, in his manuscript De analysi (written 1669), though he wrote the arithmetic as corrections to a polynomial; the general formula is usually credited to Joseph Raphson (1690) and Thomas Simpson (1740).
Square roots by averaging
Approximate \displaystyle \sqrt{7} with Newton’s method, starting from x_0 = 3.
Solution\displaystyle \sqrt{7} is the positive root of f(x) = x^2 - 7, and f'(x) = 2x. The step simplifies to
This is the average of x_n and \displaystyle \frac{7}{x_n}. Their product is exactly 7, so when one is above \displaystyle \sqrt{7} the other is below, and their average lands between them. The rule is far older than calculus: it appears in the Metrica of Heron of Alexandria (usually dated to the first century), and it is often called Heron’s rule. In exact fractions,
In decimals these are 2.6667, 2.645833 and 2.6457513123. Since \displaystyle \sqrt{7} \approx 2.6457513111, the errors are about 3.5 \times 10^{-1}, 2.1 \times 10^{-2}, 8.2 \times 10^{-5} and 1.3 \times 10^{-9}: correct places 0, 1, 4, 8. In fact x_3^2 = 7 + \dfrac{1}{12{,}192^2}, so x_3^2 misses 7 by less than 7 \times 10^{-9}.
Two roots of an equation mixing a line and an exponential
Solve e^x = 4x.
SolutionLet f(x) = e^x - 4x, so f'(x) = e^x - 4. A few values place the roots: f(0) = 1 > 0, f(1) = e - 4 < 0, f(2) = e^2 - 8 \approx -0.61 < 0 and f(3) = e^3 - 12 \approx 8.09 > 0. So there is a root in [0, 1] and one in [2, 3]. The step is
From x_0 = 0 the first step is exact, \displaystyle x_1 = 0 - \frac{1}{-3} = \frac{1}{3}. Running both starts:
| n | from x_0 = 0 | from x_0 = 2 |
|---|---|---|
| 1 | 0.333333 | 2.180270 |
| 2 | 0.357246 | 2.153951 |
| 3 | 0.3574029494 | 2.1532928 |
| 4 | 0.357402956181 | 2.15329236411 |
The solutions are x \approx 0.3574030 and x \approx 2.1532924. The start decides which root is found. The tangent is horizontal at x = \ln 4 \approx 1.386, and a start near there is thrown far: from x_0 = 1.5, where f'(1.5) \approx 0.48, the nearly flat tangent gives x_1 \approx 4.652, and the iterates take several steps to crawl back.
Against bisection, on the same root
The bisection lesson trapped the root of x^3 + x - 3 = 0 in [1.2109375,\ 1.21875] after seven halvings of [1, 2]. Run Newton’s method from x_0 = 1 and compare.
SolutionHere f'(x) = 3x^2 + 1. The numbers stay exact fractions:
Then \displaystyle f\!\left(\frac{5}{4}\right) = \frac{125}{64} + \frac{5}{4} - 3 = \frac{13}{64} and \displaystyle f'\!\left(\frac{5}{4}\right) = \frac{91}{16}, so \displaystyle x_2 = \frac{5}{4} - \frac{13}{64} \cdot \frac{16}{91}, which is \displaystyle \frac{5}{4} - \frac{1}{28} = \frac{17}{14}. Next \displaystyle f\!\left(\frac{17}{14}\right) = \frac{13}{2744} and \displaystyle f'\!\left(\frac{17}{14}\right) = \frac{1063}{196}, so
The root is r \approx 1.2134117, so after three steps the error is about 5.1 \times 10^{-7}. Seven halvings only guarantee a midpoint within \displaystyle \frac{1}{256} \approx 0.0039. To guarantee 5.1 \times 10^{-7}, bisection needs \displaystyle \frac{1}{2^{n+1}} < 5.1 \times 10^{-7}, that is n = 20 halvings, since 2^{21} = 2{,}097{,}152. The price is that Newton’s method needs a derivative and promises nothing in advance, while bisection is slow but certain.
Kertu’s tank
Kertu’s water tank is a sphere of radius 1 meter. Water standing to depth h meters fills V = \dfrac{\pi h^2 (3 - h)}{3} cubic meters (the volume of a spherical cap, taken as given here). Tiiu wants to mark the dipstick at the depth where the tank holds 1 cubic meter. Find that depth.
SolutionSetting V = 1 and multiplying by \displaystyle \frac{3}{\pi} gives \displaystyle 3h^2 - h^3 = \frac{3}{\pi}, so we want the root of
with 0 \le h \le 2, and f'(h) = 3h^2 - 6h. Half full, at h = 1, the tank holds \displaystyle \frac{2\pi}{3} \approx 2.09 cubic meters, more than 1, so the mark is below h = 1; start at h_0 = 1. There \displaystyle f(1) = -2 + \frac{3}{\pi} \approx -1.04507 and f'(1) = -3, so
Two more steps give h_2 \approx 0.635606 and h_3 \approx 0.6355008, and h_4 agrees with h_3 to eight places. Since f(0.635) > 0 > f(0.636), the root is between them: Tiiu’s mark goes at h \approx 0.6355 meters, about 63.6 centimeters. The cubic’s other roots, about -0.521 and 2.885, lie outside [0, 2].
Three ways to fail
Run Newton’s method on (a) f(x) = x^3 - 3x + 3 from x_0 = 0; (b) f(x) = x^3 - 5x from x_0 = 1; (c) \displaystyle f(x) = \sqrt[3]{x} from x_0 = 1.
Solution(a) f'(x) = 3x^2 - 3, so \displaystyle x_1 = 0 - \frac{3}{-3} = 1. But f'(1) = 0 and f(1) = 1: the tangent at (1, 1) is the horizontal line y = 1, which never meets the axis, and x_2 does not exist. The real root is near -2.1038, and from x_0 = -2 the method reaches it quickly: -2.1111, -2.103836, -2.1038034.
(b) f'(x) = 3x^2 - 5. Then \displaystyle x_1 = 1 - \frac{-4}{-2} = -1 and \displaystyle x_2 = -1 - \frac{4}{-2} = 1. The guesses alternate between 1 and -1 forever, although f has roots at 0 and \displaystyle \pm\sqrt{5}.
(c) \displaystyle f'(x) = \frac{1}{3}x^{-2/3} for x \ne 0, so \dfrac{f(x)}{f'(x)} = x^{1/3} \cdot 3x^{2/3} = 3x and x_{n+1} = x_n - 3x_n = -2x_n. The guesses are 1, -2, 4, -8, \ldots, each twice as far from the only root, 0, as the one before. At the root the tangent line is vertical and f'(0) does not exist, so the hypothesis f'(r) \ne 0 of the convergence statement is not met.
A double root slows it down
Run Newton’s method on f(x) = x^3 - 3x + 2 from x_0 = 2 and explain the rate.
SolutionThe function factors as f(x) = (x - 1)^2(x + 2), and f'(x) = 3x^2 - 3 = 3(x - 1)(x + 1), which is 0 at the root x = 1 itself. The first step is \displaystyle x_1 = 2 - \frac{4}{9} = \frac{14}{9} \approx 1.5556, and the next ones are 1.2979, 1.1554, 1.0796, 1.0403, 1.0203. The errors 0.556, 0.298, 0.155, 0.080, 0.040, 0.020 halve at every step, the same rate as bisection, not squaring. Cancelling the common factor shows why:
As x_n \to 1 the factor \displaystyle \frac{2x_n + 1}{3(x_n + 1)} tends to \displaystyle \frac{3}{6} = \frac{1}{2}, so each step only halves the error.
Boundaries
- Each step needs f differentiable at x_n and f'(x_n) \ne 0. Where f'(x_n) = 0 the next guess does not exist; where f'(x_n) is small, it lands far away.
- Nothing guarantees convergence. The guesses may cycle, run away, or settle on an unwanted root; no interval keeps the root trapped.
- Quadratic convergence needs a simple root, f'(r) \ne 0, with f'' continuous near r. At a root where f'(r) = 0 the error shrinks only by a roughly fixed factor each step (one half for a double root). Where f' does not exist at the root, as for \displaystyle \sqrt[3]{x}, the method can fail entirely.
- Started at a real number, the method produces only real numbers, so it cannot find a root that is not real; with no real root it wanders.
Where this goes next
Finding maxima and minima and solving optimization problems means solving f'(x) = 0; when that has no algebraic solution, Newton’s method applied to f' finds the critical points. The chain rule and the trigonometric derivatives widen its reach to equations such as \cos x = x. The bound K e_n^2 is made exact by Taylor polynomials, and concavity decides from which side the guesses approach.
Exercises
Carrying out the steps
- Write Newton’s formula for f(x) = x^3 - 7 in simplified form. Starting from x_0 = 2, find x_1 and x_2 and compare with \displaystyle \sqrt[3]{7}.
- Start Newton’s cubic x^3 - 2x - 5 = 0 at x_0 = 3, as in the first figure. Find x_1, x_2 and x_3.
- Use Newton’s method on x^4 - x - 10 = 0 from x_0 = 2 to find x_1, x_2 and x_3.
- Use Heron’s rule for \displaystyle \sqrt{20} from x_0 = 4. Give x_1 and x_2 as fractions and decimals, and the error of x_2.
- Show that Newton’s method for f(x) = \dfrac{1}{x} - 7 gives x_{n+1} = x_n(2 - 7x_n), a way to find \displaystyle \frac{1}{7} without dividing. From x_0 = 0.1, find x_1, x_2 and x_3.
- Solve x e^x = 1 by Newton’s method from x_0 = 0.5, giving x_1, x_2 and x_3.
- Use Newton’s method on \dfrac{x}{x^2 + 1} = \dfrac{2}{5} from x_0 = 0 to find x_1, x_2 and x_3. Then solve the equation exactly and compare.
In context
- Aare deposits 1000 dollars at the start of each of three years. Each year the account is multiplied by a growth factor g, and at the end of the third year it holds 3300 dollars, so g^3 + g^2 + g = 3.3. Take two Newton steps from g_0 = 1.05 and give the yearly interest rate to the nearest hundredth of a percent.
- Tiiu designs a closed cylindrical can holding 355 cubic centimeters with 300 square centimeters of metal. Show that the radius r satisfies 2\pi r^2 + \dfrac{710}{r} = 300. Use Newton’s method from r_0 = 3 and from r_0 = 6 to find two possible radii, and give the height of each can.
- Find the depth at which Kertu’s tank holds 3 cubic meters, starting from h_0 = 1.
When it stalls or fails
- Run Newton’s method on f(x) = x^2 - 4x + 5 from x_0 = 3. What happens, and why can no start succeed for this function?
- Find the number c > 0 for which Newton’s method on f(x) = x^3 - x from x_0 = c gives x_1 = -c, so that the guesses cycle.
- For f(x) = x e^{-x}, show that the step is x_{n+1} = \dfrac{x_n^2}{x_n - 1}. From x_0 = 2, find x_1, x_2 and x_3. The values f(x_n) shrink toward 0; explain why the method still finds no root.
- For f(x) = x^3, show that \displaystyle x_{n+1} = \frac{2}{3}x_n. Starting from x_0 = 1, how many steps are needed before |x_n| < 10^{-6}?
- How many halvings of [2, 3] does bisection need to trap the root of x^3 - 2x - 5 in an interval of length below 10^{-9}? Compare with the first worked example.
Reasoning
- Show that if f(x) = mx + b with m \ne 0, then x_1 is the exact root for every x_0. Explain why in terms of tangent lines.
- For Heron’s rule \displaystyle x_{n+1} = \frac{1}{2}\left(x_n + \frac{a}{x_n}\right) with a > 0, show that \displaystyle x_{n+1} - \sqrt{a} = \dfrac{(x_n - \sqrt{a})^2}{2x_n}. Deduce that from any x_0 > 0 every later guess is at least \displaystyle \sqrt{a}, and explain what the formula says about correct digits.
- Suppose the Newton iterates converge to a number r, where f and f' are continuous and f'(r) \ne 0. Prove that f(r) = 0.
- Explain why Newton’s method for Kertu’s tank cannot start at h_0 = 0 or h_0 = 2, both from the formula and from the shape of the tank.
- Explain what bisection and Newton’s method each contribute when a few halvings are followed by Newton steps, using the fourth and sixth worked examples.
Answers
- x_{n+1} = \dfrac{2x_n^3 + 7}{3x_n^2}; \displaystyle x_1 = \frac{23}{12} \approx 1.916667, x_2 \approx 1.912938, against \displaystyle \sqrt[3]{7} \approx 1.912931. From \displaystyle x_n - \frac{x_n^3 - 7}{3x_n^2} over a common denominator; x_2 is already within 10^{-5}.
- x_1 = 2.36, x_2 \approx 2.127197, x_3 \approx 2.095136. With f(3) = 16 and f'(3) = 25, x_1 = 3 - 0.64; then f(2.36) \approx 3.424256 and f'(2.36) = 14.7088.
- \displaystyle x_1 = \frac{58}{31} \approx 1.870968, x_2 \approx 1.855781, x_3 \approx 1.855585. Here f'(x) = 4x^3 - 1, f(2) = 4 and f'(2) = 31.
- \displaystyle x_1 = \frac{9}{2} = 4.5, \displaystyle x_2 = \frac{161}{36} \approx 4.472222; since \displaystyle \sqrt{20} \approx 4.472136, the error of x_2 is about 8.6 \times 10^{-5}. \displaystyle x_2 = \frac{1}{2}\left(\frac{9}{2} + \frac{40}{9}\right).
- f'(x) = -\dfrac{1}{x^2}, so \displaystyle x_{n+1} = x_n + x_n^2\left(\frac{1}{x_n} - 7\right), which is 2x_n - 7x_n^2 = x_n(2 - 7x_n). Then x_1 = 0.13, x_2 = 0.1417, x_3 = 0.14284777, against \displaystyle \frac{1}{7} = 0.142857\ldots
- x_1 \approx 0.571020, x_2 \approx 0.567156, x_3 \approx 0.567143. By the product rule f'(x) = (x + 1)e^x for f(x) = x e^x - 1.
- x_1 = 0.4, x_2 \approx 0.488381, x_3 \approx 0.499807. By the quotient rule f'(x) = \dfrac{1 - x^2}{(x^2 + 1)^2}. Exactly, 5x = 2x^2 + 2 gives (2x - 1)(x - 2) = 0, so \displaystyle x = \frac{1}{2} or x = 2; the guesses approach \displaystyle \frac{1}{2}.
- g_1 \approx 1.048420, g_2 \approx 1.048418, so the rate is about 4.84\%. With f(g) = g^3 + g^2 + g - 3.3, f(1.05) = 0.010125 and f'(1.05) = 6.4075.
- Radius about 2.8531 cm with height about 13.88 cm, or radius about 5.0265 cm with height about 4.47 cm. With \displaystyle h = \frac{355}{\pi r^2}, the area 2\pi r^2 + 2\pi r h is \displaystyle 2\pi r^2 + \frac{710}{r}. From r_0 = 3: 2.835283, 2.852845, 2.853068. From r_0 = 6: 5.200230, 5.035372, 5.026513, 5.026487.
- h \approx 1.2970 meters. Now \displaystyle f(h) = h^3 - 3h^2 + \frac{9}{\pi}, and the guesses are 1.288263, 1.296971, 1.296995.
- \displaystyle x_1 = 3 - \frac{2}{2} = 2, and f'(2) = 0 with f(2) = 1, so the tangent is horizontal and the method stops. The discriminant is 16 - 20 = -4 < 0, so f has no real root and no real start can converge to one.
- \displaystyle c = \dfrac{1}{\sqrt{5}} \approx 0.4472. We need \displaystyle \frac{c^3 - c}{3c^2 - 1} = 2c, so c^2 - 1 = 6c^2 - 2 and \displaystyle c^2 = \frac{1}{5}. Since f is odd, the step from -c returns to c.
- x_1 = 4, \displaystyle x_2 = \frac{16}{3}, \displaystyle x_3 = \frac{256}{39} \approx 6.5641. Here f'(x) = (1 - x)e^{-x}, so \displaystyle x - \frac{x}{1 - x} = \frac{x^2}{x - 1}. For x > 1 this exceeds x by \displaystyle \frac{x}{x - 1} > 1, so the guesses grow without bound. f(x_n) \to 0 because of the horizontal asymptote y = 0, not a nearby root; the only root is 0.
- 35 steps. The step is \displaystyle x - \frac{x^3}{3x^2} = \frac{2}{3}x, so \displaystyle x_n = \left(\frac{2}{3}\right)^n, and \displaystyle \left(\frac{2}{3}\right)^{34} \approx 1.03 \times 10^{-6} while \displaystyle \left(\frac{2}{3}\right)^{35} \approx 6.9 \times 10^{-7}. A triple root has f'(r) = 0, so the rate is linear.
- 30 halvings, since 2^{29} < 10^9 < 2^{30} = 1{,}073{,}741{,}824. Newton’s method from x_0 = 2 was within 1.6 \times 10^{-10} after three steps.
- \displaystyle x_1 = x_0 - \frac{m x_0 + b}{m} = -\frac{b}{m}, the root, whatever x_0 is. The tangent line to a line is the line itself, so its crossing is the true crossing.
- \displaystyle \frac{x_n^2 + a}{2x_n} - \sqrt{a} is \displaystyle \frac{x_n^2 - 2x_n\sqrt{a} + a}{2x_n}, which is \displaystyle \frac{(x_n - \sqrt{a})^2}{2x_n}. For x_n > 0 this is at least 0, so \displaystyle x_{n+1} \ge \sqrt{a}, and every later guess stays positive and at least \displaystyle \sqrt{a}. Near \displaystyle \sqrt{a} the new error is the old one squared over about \displaystyle 2\sqrt{a}, so an error near 10^{-k} becomes one near 10^{-2k}: the correct digits roughly double.
- Since x_n \to r and x_{n+1} \to r, the difference \displaystyle x_{n+1} - x_n = -\frac{f(x_n)}{f'(x_n)} tends to 0. By continuity, and because f'(r) \ne 0, the same quantity tends to \displaystyle -\frac{f(r)}{f'(r)}. So \displaystyle \frac{f(r)}{f'(r)} = 0, and f(r) = 0.
- f'(h) = 3h(h - 2) is 0 at h = 0 and h = 2, so the step divides by zero. Since \displaystyle f(h) = \frac{3}{\pi}\big(1 - V(h)\big), f' is a multiple of \displaystyle \frac{dV}{dh} = \pi h(2 - h), the area of the water’s surface. At the bottom and top of the sphere that surface is a single point, so the volume momentarily stops changing with depth: the tangent is horizontal.
- Bisection supplies certainty: the root stays trapped, so a few halvings give a start known to be close, away from the cycle and runaway of the sixth example. Newton’s method supplies speed: in the fourth example it gained about six places in three steps, where bisection needed about twenty halvings.