Newton's method
Tonight's idea
You want a solution of \(f(x) = 0\) and no formula gives it. Start with a guess \(x_0\). Stand on the curve at \((x_0, f(x_0))\) and slide down the tangent to the \(x\)-axis. Where you land is the next guess, \(x_1\). Repeat.
The tangent has slope \(f'(x_0)\), the derivative from The slope of a curve. To lose a height of \(f(x_0)\) at that slope you move sideways by \(f(x_0) / f'(x_0)\).
Newton's step. \(x_{\text{new}} = x - \dfrac{f(x)}{f'(x)}\).
The slopes needed tonight: \(x^2\) has slope \(2x\), \(x^3\) has slope \(3x^2\), \(kx\) has slope \(k\), a constant has slope 0, and slopes add.
Take \(f(x) = x^2 - 2\), whose positive root is \(\sqrt2\). The slope is \(2x\), so the step is
\[x - \frac{x^2 - 2}{2x} = \frac12\left(x + \frac{2}{x}\right).\]
Average your guess with 2 divided by your guess. That is the Babylonian rule for square roots, far older than Newton.
Watch one: \(\sqrt2\) from \(x_0 = 2\)
| step | guess | decimal | correct digits |
|---|---|---|---|
| 1 | \(\tfrac32\) | 1.5 | 1 |
| 2 | \(\tfrac{17}{12}\) | 1.41666… | 3 |
| 3 | \(\tfrac{577}{408}\) | 1.4142156… | 6 |
| 4 | \(\tfrac{665857}{470832}\) | 1.41421356237469… | 12 |
Average the last guess with 2 divided by it. For example \(x_2 = \tfrac12\left(\tfrac32 + \tfrac43\right) = \tfrac{17}{12}\).
The true value is \(1.41421356237310\ldots\) The correct digits go 1, 3, 6, 12, roughly doubling at every step.
See it move: mathdetours.com/demos/newton.html. Slopes of tangents: mathdetours.com/demos/tangent.html.
Your turn
- The averaging rule for \(\sqrt{10}\) is \(\tfrac12\left(x + \tfrac{10}{x}\right)\). Start at \(x_0 = 3\) and take two steps, as fractions and as decimals. Compare with your calculator's \(\sqrt{10}\).
- For the cube root of 2 use \(f(x) = x^3 - 2\). Write down Newton's step. Take two steps from \(x_0 = 1\).
- \(x^3 - 2x + 2\) has slope \(3x^2 - 2\). (a) From \(x_0 = 0\) find \(x_1, x_2, x_3\). (b) From \(x_0 = -2\) find \(x_1, x_2\).
- (a) For \(x^2 - 2\), what goes wrong if \(x_0 = 0\)? Describe the tangent. (b) Which two starting values break the very first step for \(x^3 - 2x + 2\)? (c) Where do the guesses for \(x^2 - 2\) go from \(x_0 = -2\), and why?
Stretch: why the digits double
Show that \(\tfrac12\left(x + \tfrac{2}{x}\right) - \sqrt2 = \dfrac{(x - \sqrt2)^2}{2x}\). The left side is the error after a step. If a guess is 0.001 too big, about how far off is the next one? Why does that double the number of correct digits?
Answers
- \(x_1 = \tfrac12\left(3 + \tfrac{10}{3}\right) = \tfrac{19}{6} \approx 3.16667\). \(x_2 = \tfrac12\left(\tfrac{19}{6} + \tfrac{60}{19}\right) = \tfrac{721}{228} \approx 3.162281\). The calculator gives \(\sqrt{10} = 3.162278\ldots\), so after two steps the error is only about \(0.000003\).
- The slope is \(3x^2\), so the step is \(x - \dfrac{x^3 - 2}{3x^2}\). \(x_1 = 1 - \tfrac{-1}{3} = \tfrac43\). \(x_2 = \tfrac43 - \dfrac{64/27 - 2}{16/3} = \tfrac43 - \tfrac{5}{72} = \tfrac{91}{72} \approx 1.2639\). The true value is \(1.2599\ldots\)
- (a) \(f(0) = 2\) and the slope is \(-2\), so \(x_1 = 0 - \tfrac{2}{-2} = 1\). \(f(1) = 1\) and the slope is 1, so \(x_2 = 1 - 1 = 0\). Then \(x_3 = 1\) again: a cycle. (b) \(f(-2) = -2\) and the slope is 10, so \(x_1 = -2 + 0.2 = -1.8\). \(f(-1.8) = -0.232\) and the slope is 7.72, so \(x_2 = -1.8 + \tfrac{0.232}{7.72} \approx -1.7699\). The root is \(-1.7693\) to four places, so this start works.
- (a) The slope at 0 is 0. The tangent is horizontal, at height \(-2\), and never reaches the axis. The step asks you to divide by zero. (b) The slope \(3x^2 - 2\) is zero when \(x^2 = \tfrac23\): \(x_0 = \pm\sqrt{2/3} \approx \pm 0.816\). (c) They go \(-2, -\tfrac32, -\tfrac{17}{12}, \dots\) towards \(-\sqrt2\), the other root. The curve is symmetric about the \(y\)-axis, so every guess is the mirror image of the one in the example.
Stretch. \(\tfrac12\left(x + \tfrac2x\right) - \sqrt2 = \dfrac{x^2 + 2 - 2\sqrt2\,x}{2x} = \dfrac{(x - \sqrt2)^2}{2x}\). The new error is the old error squared, divided by \(2x \approx 2.83\). An error of \(0.001\) becomes about \(0.000\,000\,35\). Squaring a number like \(10^{-3}\) gives \(10^{-6}\): twice as many zeros after the decimal point, so twice as many correct digits.