A Closely Related Algorithm


Here's a more general algorithm than the one we've been considering. Begin with two positive numbers, and , and, for , define

Then, and converge (quadratically) to the common limit .

Notice that is the arithmetic mean (average) of and , while is the harmonic mean of and . [To see that this is truly a generalization of the Babylonian algorithm, set = /.]

To see that the algorithm converges, first convince yourself, using induction, that

for > 1. That is, the 's decrease while the 's increase. Thus, both sequences converge. The only issue here is finding the limit.

Next, we use nearly the same computation as for our first algorithm:

As before, and are half as far apart as and .

By induction, and hence and have the same limit . To compute this limit, notice that

and hence ; that is, and .

As with the Babylonian algorithm, now that we know the limit we can discuss the rate of convergence. In this setting we have

Thus, the sequence converges quadratically. A similar computation shows that is likewise quadratically convergent.

Iterative algorithms of this type are actually quite common and, in recent years, have been used to good advantage in constructing fast, effective algorithms for computing various transcendental functions and, in particular, for computing to millions of places. Another such algorithm is described in connection with our discussion of Archimedes' method.

-30-


Neal Carothers - carother@bgnet.bgsu.edu