Appendix B. Newton's Method

To review Newton's method very briefly, we are given a differentiable function f of a real variable x and we wish to solve the equation f(x) = 0 for x. Given a current estimate x_n of a root of f, Newton's method gives us a better estimate x_{n + 1}, under suitable conditions, according to the formula

Here, f'(x_n) is the derivative of f at x = x_n. The derivation of this formula can be read off the figure below (solve for x_{n + 1}).

The method works very well for simple, well-behaved functions such as polynomials, provided the first estimate is quite close. Once an estimate is sufficiently close, the method converges quadratically. That is, if r is the exact value of the root, and x_n is a sufficiently close estimate, then

Thus, the number of digits of accuracy doubles with each iteration (e.g., if

If the first estimate is way off, then the iterations may converge very slowly, may diverge to infinity, may converge to a root other than the one closest to the first estimate, or may loop among certain values indefinitely.

This discussion has been quite vague because of phrases like "suitable conditions," "well-behaved," and "sufficiently close." For a more precise discussion, consult almost any first-year calculus textbook.

In spite of the caveats surrounding this method, it is occasionally useful in the domain of integers. To see whether or not the method applies to a particular function, you have to work it out, such as is done in Section 11-1, "Integer Square Root," on page 203.

Table B-1 gives a few iterative formulas derived from Newton's method, for computing certain numbers. The first column shows the number it is desired to compute. The second column shows a function that has that number as a root. The third column shows the right-hand side of Newton's formula corresponding to that function.

It is not always easy, incidentally, to find a good function to use. There are, of course, many functions that have the desired quantity as a root, and only a few of them lead to a useful iterative formula. Usually, the function to use is a sort of inverse of the desired computation. For example, to find use f(x) = x² - a; to find log₂a use f(x) = 2^x - a, and so on. ^[1]

^[1] Newton's method for the special case of the square root function was known to Babylonians about 4,000 years ago.

Table B-1.. Newton's Method for Computing Certain Numbers
Quantity to Be Computed	Function	Iterative Formula
	x^2 - a
	x^3 - a
	x^-2 - a
	x^-1 - a	xn(2 - axn)
log2a	2^x - a

The iterative formula for log₂ a converges (to log₂ a) even if the multiplier 1/ln2 is altered somewhat (for example, to 1, or to 2). However, it then converges more slowly. A value of 3/2 or 23/16 might be useful in some applications (1/ln2 1.4427).