Chapter 5. Techniques
5.1 Newton's method
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 anything 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=x3 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 43=64 is a little too small, and 53=125 is much too big, we guess x≈ 4.3. Testing our guess, we have 4.33=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:
Increasing our value of x to 4.3+0.14=4.44, we find that 4.443=87.5 is a pretty good approximation to 87. If we need higher precision, we can go through the process again with Δ y=-0.5, giving
This second iteration gives an excellent approximation.
Example 1◊ Figure 63 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
The planet Mercury has e=0.206. Find the angle x when Mercury has completed 1/4 of a period.
◊ We have
and we want to find x when y=2π/4=1.57. As a first guess, we try x=π/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.
(The derivative dy/dx happens to be 1 at x=π/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.)