|
|
The Babylonian Algorithm finds the square-root of a positive number Q by iterations starting with a guess x0,
the (n+1)-th approximation being
xn+1 = (xn + Q/xn)/2.
As n ® ¥, xn ® √Q. We show below why this is so.
Consider a number Q that is not the square of an integer. Then
Q = A2 + b, where A is the largest integer whose square is less than Q.
Since A < √Q,
1< √Q/A so that √Q < Q/A.
Thus A < √Q < Q/A.
We have the following picture:
A----- √Q ------ Q/A
Let A = x0.
For n > 0, we now produce a sequence of intervals [Q/xn, xn], each containing √Q and [Q/xn+1, xn+1] inside [Q/xn, xn].
It suffices to prove the following:
Q/xn < Q/xn+1 < √Q < xn+1 < xn ---- Inequality (1)
Claim: Q/xn < √Q < xn, for all n > 0.
Proof of Claim:
From xn+1 = (xn + Q/xn)/2, we get (xn+1 - Q/xn+1) = (xn - Q/xn)2/(4xn+1) ≥ 0, for n ≥ 0.
If xn+1 - Q/xn+1 = 0, it would imply xn - Q/xn = 0 and, descending to successively lower values of n, we would have x0 - Q/x0 = A - Q/A = 0; a contradiction.
So xn+1 - Q/xn+1 >0, for n ≥ 0. In other words, xn > Q/xn, for all n > 0.
But xn > Q/xn implies xn2 > Q so that xn > √Q.
However, xn > √Q implies √Q/xn < 1. So Q/xn = (√Q . √Q)/ xn = √Q (√Q/ xn) < √Q . 1 = √Q.
Combining this with √Q < xn, we get Q/xn < √Q < xn, proving the claim.
From the claim,
Q/xn+1 < √Q < xn+1 --------- Inequality (2)
and also Q/xn < xn.
But Q/xn < xn gives
Q/xn + xn < 2xn
(Q/xn + xn)/2 < xn
xn+1 < xn ------------------- Inequality (3)
But then, 1/xn < 1/xn+1, and so
Q/xn < Q/xn+1 -------------- Inequality (4)
Combining Inequalities (2), (3), and (4), we get Inequality (1).
We now have an infinite sequence of nested intervals [Q/xn, xn], each containing √Q.
Now, there is a property called the Nested Interval Property of real numbers. It says that an infinite sequence of nested closed intervals on the real line converges to a point on the line when the length of the intervals approaches zero.
It is easy to show that each subinterval is strictly less than half the length of the interval just enclosing it. This means that the (n+1)-th interval is 1/(2n) of the length of the first interval which is the one from A to Q/A. Then, for any small number e > 0, (Q/A - A)/(2n) < e for all n > log((Q/A - A)/e)/log 2. This proves that, as n ® ¥, the length of the subintervals goes to zero.
Therefore, by the Nested Interval Property, our nested intervals will converge to a unique point. This point must be √Q since each of the nested intervals contains √Q. Thus our successive approximations xn approach √Q closer and closer with each iteration.
This is why the Babylonian Algorithm works!
Observe that the method requires neither Q nor A to be an integer, nor A2 to be less than Q. Our derivation would have worked if A2 > Q.
In that case we would have A > √Q > Q/A and the rest of the nested intervals will be as described above.
Ü BACK
MathPath - "BRIGHT AND EARLY"
Send suggestions to webmaster@mathpath.org
Copyright © 2001- MathPath
Last updated - December 20, 2003
|
