You are here

Newton’s method

20 January, 2016 - 10:05

In the 1958 science fiction novel Have Space Suit - Will Travel, by Robert Heinlein, Kip is a high school student who wants to be an engineer, and his father is trying to convince him to stretch himself more if he wants to get any- thing out of his education:

“Why did Van Buren fail of re- election? How do you extract the cube root of eighty-seven?”
Van Buren had been a president; that was all I remembered. But I could answer the other one. “If you want a cube root, you look in a table in the back of the book.”

Dad sighed. “Kip, do you think that table was brought down from on high by an archangel?”

We no longer use tables to compute roots, but how does a pocket calculator do it? A technique called Newton’s method allows us to calculate the inverse of any function efficiently, including cases that aren’t preprogrammed into a calculator. In the example from the novel, we know how to calculate the function y=x^3 fairly accurately and quickly for any given value of x, but we want to turn the equation around and find x when y=87. We start with a rough mental guess: since 4^3=64 is a little too small, and 5^3=125 is much too big, we guess x\approx 4.3. Testing our guess, we have 4.3^3=79.5. We want y to get bigger by 7.5, and we can use calculus to find approximately how much bigger x needs to get in order to accomplish that:

\begin{align*} \Delta x &= \frac{\Delta x}{\Delta y}\Delta y\\ &\approx \frac{dx}{dy}\Delta y \\ &=\frac{\Delta y}{dy/dx} \\ &= \frac{\Delta y}{3x^2}\\ &= \frac{\Delta y}{3x^2}\\ &= 0.14 \end{align*}

Increasing our value of x to 4.3 +0.14 = 4.44, we find that 4.44^3 =87.5 is a pretty good approximation to 87. If we need higher precision, we can go through the process again with \Delta y=-0.5, giving

\begin{align*} \Delta x &\approx \frac{\Delta y}{3x^2} \\ &=0.14 \\ x&=4.43 \\ x^3&=86.9 \end{align*}

This second iteration gives an excellent approximation.

Example

media/image1.png
Figure 5.1  

Figure 5.1 shows the astronomer Johannes Kepler’s analysis of the motion of the planets. The ellipse is the orbit of the planet around the sun. At t=0, the planet is at its closest approach to the sun, A. At some later time, the planet is at point B. The angle x (measured in radians) is defined with reference to the imaginary circle encompassing the orbit. Kepler found the equation

2\pi \frac{t}{T}=x-e \textrm{ sin }x

where the period, T , is the time required for the planet to complete a full orbit, and the eccentricity of the ellipse, e, is a number that measures how much it differs from a circle. The relationship is complicated because the planet speeds up as it falls inward toward the sun, and slows down again as it swings back away from it.

The planet Mercury has e=0.206. Find the angle x when Mercury has completed 1/4 of a period.

We have

y=x-(0.206)\textrm{ sin }x

and we want to find x when y=2\pi/4=1.57. As a first guess, we try x=\pi/2 (90 degrees), since the eccentricity of Mercury’s orbit is actually much smaller than the example shown in the figure, and therefore the planet’s speed doesn’t vary all that much as it goes around the sun. For this value of x we have y=1.36, which is too small by 0.21.

\begin{align*} \Delta x &\approx \frac{\Delta y}{dy/dx} \\ &= \frac{0.21}{1-(0.206)\textrm{cos }x}\\ &= 0.21 \end{align*}

(The derivative dy/dx happens to be 1 at x=\pi/2.) This gives a new value of x , 1.57+.21=1.78. Testing it, we have y=1.58, which is correct to within rounding errors after only one iteration. (We were only supplied with a value of e accurate to three significant figures, so we can’t get a result with precision better than about that level.)