Advanced root extraction, II
This is a translation of an article that appeared in the November 2005 issue of Pythagoras.
Last time we showed why ∛2 exists. This time we see how we can approximate ∛2 efficiently.
An approximating sequence for √2
To find a sequence of approximations of √2 you start with x0=2 and, successively, once you have xi calculate a new approximation xi+1, as follows.
So, x1=3/2, x2=½(3/2+4/3)=17/12, and so on. The sequence that we get in this way is decreasing and every term is larger than √2. To see this we need the AGM-inequality, first for two distinct numbers a and b:
We have x0>√2 to begin with and whenever xi>√2 we have xi>2/xi and so
(the average is smaller than the larger number) and by the AGM-inequality we get xi+1>√2. These approximations converge quite rapidly to √2; if you rewrite xi+1-√2 then you ge
(just expand the square). And because xi>1 we find that
This means that the number of correct decimals roughly doubles each time. To begin x0-√2<0.6 and so x1-√2<0.62/2=0.18, x2-√2<0.182/2=0.0162, and then x3-√2<000013122, and so on.
In general, to create a sequence of approximations of √a start with x0=a and repeat the step
In a similar fashion as above we can create a sequence of approximations for ∛2. We star with x0=2 and each time we create a new approximation from xi as follows
Again we find a decreasing sequence with xi>∛2 for all i. You can show this using the three-number version of the AGM-inequality:
Put a=b=xi and c=2/(xi)2. The product of the numbers is equal to 2 and the average is smaller than the largest number, which is xi.
Just like in the case of √2 this sequence converges quite rapidly, with a bit of work you can verify that
Because every xi lies between 1 and 2 you derive that
This means that also here the number of correct decimals will, roughly, double in each step.
For other n-th roots you can create similar sequences. Star with x0=2 and keep repeating
The resulting sequence will converge to the n-th root of 2.
