Archimedes numerical roots
How did Archimedes calculate the lengths of the sides of the polygons which needed him to be able to calculate square roots?
Problem
Archimedes estimated the value of $\pi$ by finding the perimeters of regular polygons inscribed in a circle and circumscribed around the circle. He managed to establish that $3\frac{10}{71} < \pi < 3\frac{1}{7}$.
Before he could find the perimeters of polygons he need to be able to calculate square roots. How did he calculate square roots? He didn't have a calculator but needed to work to an appropriate degree of accuracy. To do this he used what we now call numerical roots.
How might he have calculated $\sqrt{3}$?
This must be somewhere between $1$ and $2$. How do I know this? Now calculate the average of $\frac{3}{2}$ and 2 (which is 1.75) - this is a second approximation to $\sqrt 3$. i.e. we are saying that a better approximation to $\sqrt 3$ is $$x_{n+1} = \frac{(\frac{3}{x_n} + x_n)}{2}$$ where $x_n$ is an approximation to $\sqrt 3$ .
We then repeat the process to find the new (third) approximation to $\sqrt{3}$ $$\sqrt{3} \approx {(3 / 1.75 + 1.75) \over {2}} = 1.73214... $$ to find a fourth approximation repeat this process using 1.73214 and so on...
How many approximations do I have to make before I can find $\sqrt{3}$ correct to five decimal places?
Why do you think it works?
Will it always work no matter what I take as my first approximation and does the same apply to finding other roots?
Did you know ... ?
BBC News on 6 January 2010 reported that a computer scientist Fabrice Bellard claimed to have computed the mathematical constant pi to nearly 2.7 trillion digits, some 123 billion more than the previous record. He used a desktop computer to perform the calculation, taking a total of 131 days to complete and check the result. This version of pi takes over a terabyte of hard disk space to store.
Previous records were established using supercomputers, but Mr Bellard claims his method is 20 times more efficient. The prior record of about 2.6 trillion digits, set in August 2009 by Daisuke Takahashi at the University of Tsukuba in Japan, took just 29 hours.
Getting Started
A sequence of numbers $x_1, x_2, x_3, ... ,$ starts with $x_1 = 2$, and, if you know any term $x_n$, you can find the next term $x_{n+1}$ using the formula $x_{n+1} = \frac{1}{2} \left( x_n + \frac{3}{x_n} \right)$.
Student Solutions
A sequence of numbers $x_1, x_2, x_3, ... ,$ starts with $x_1 = 2$, and, if you know any term $x_n$, you can find the next term $x_n+1$ using the formula $x_{n=1} = \frac{1}{2} \left( x_n + \frac{3}{x_n} \right)$.
Solution by Andaleeb of Woodhouse Sixthform College, London.
For the iteration $$x_{n+1} = \frac{1}{2} \left( x_n + \frac{3}{x_n} \right)$$ \begin{eqnarray} \\ x_1 &=& 2,\; x_2 = 1.75,\; x_2 = 1.732142857,\; x_4 = 1.73205081 \\ x_5 &=& 1.732050808,\; x_6 = 1.732050808,\; x_7 = 1.732050808 \\ x_8 &=& 1.732050808;\end{eqnarray} We notice that when $x_n = 1.732050808$, so is $x_{n+1}$. Squaring these terms we get $x_1^2 = 4, x_2^2 = 3.0625, ... , x_5^2 = 3$ and the rest of the other terms are the same!! This implies that when $x_n \approx \sqrt{3}$ so is $x_{n+1}$ and the values of $x_n$ tend to the limit $\sqrt{3}$. This special property can easily be proven. Assume that the limit exists, so $x_{n+1} = x_n = x$, then solve the equation $$X = \frac{1}{2}\left(X + \frac{3}{X} \right)$$. Rearranging, we can see that $X^2=3$. We can also adapt the formula to find cube roots as follows: $$x_{n+1} = \frac{1}{2} \left( x_n + \frac{N}{x_n^2} \right)$$ If we test it for $N = 3$, we see that $x_{29} = 1.44224957$, which is what the calculator gives for the cube root of 3. Testing it for $N = 8$, we get $x_1 = 2$, which is the right answer. By experimentation you can soon discover for yourself that it is not safe to assume that the same method works finding fourth roots using the iteration formula. $$x_{n+1} = \frac{1}{2} \left( x_n + \frac{N}{x_n^3} \right)$$ There is work to do to show that the iteration $x_{n+1} = F(x_n)$ converges to a limit $L$ if and only if $-1 < F'(L) < 1$.
There was also a correct solution from Andrei Lazanu (School 205, Bucharest). The first part is very clear but I have tried to simplify his solution to the second part for inclusion here. Perhaps someone could improve on this for us. Thank you for your hard work Andrei.
First, I approximated 3 using the method given in the problem. I know that $\sqrt 3$ is between $1$ and $2$ because $1^2 < (\sqrt 3) ^2 < 2^ 2 $ or $1 < 3 < 4$. I know that the approximation of $\sqrt 3$ correct to five decimal places is: $$\sqrt 3 \approx 1.73205$$.
Now I show each of the approximation steps: First approximation: $$\sqrt{3} \approx {2}$$.
Second approximation: $$\sqrt{3}\approx {{{3\over{2}} + 2} \over {2}} ={1.75}.$$
Third approximation: $$\sqrt{3} \approx {{{3\over{1.75}} + 1.75} \over {2}} = {1.732142857}.$$ Fourth approximation: $$\sqrt{3} \approx {{{3\over{1.732142857}} + 1.732142857} \over {2}} = {1.73205081}$$
So, four approximations are sufficient to approximate $\sqrt{3}$ correct to 5 decimal places.
You could think of the above as $$ \sqrt{a^2}\approx {{{a^2\over{n}} + n} \over {2}} ={m}$$ Where $n$ is the approximation to the square root of $a^2$ (that is "$a$") and $m$ the next approximation. The first approximation $n$ differs from $a$ by $k$. I can therefore write $n$ as $a + k$ where $k$ is numerically less than $a$ ($k$ could be negative). So I have the next approximation $$\quad = {{{a^2\over{a+k}} + a+k} \over {2}}$$
The next approximation = $${{{a^2\over{a+k}} + a+k} \over {2}}$$
But $${{{a^2\over{a+k}} + a+k} \over {2}} = {{2a^2 + 2ak + k^2} \over{2(a+k)}}$$ and $${{2a^2 + 2ak + k^2} \over{2(a+k)}} = {{2a(a+k)+ k^2} \over{2(a+k)}}= {{2a(a+k)} \over{2(a+k)}} + {{k^2} \over{2(a+k)}} = a + {{k^2} \over{2(a+k)}}$$
While $a$ is positive, $${{k^2} \over{2(a+k)}}$$must be positive as $k$ is numerically less than $a$.
So $$a< {{{a^2\over{a+k}} + a+k} \over {2}}$$
But the same equation could be written as: $${{2a^2 + 2ak + k^2} \over{2(a+k)}} = {{a^2+ (a+k)^2} \over{2(a+k)}}= {{(a+k)^2} \over{2(a+k)}} + {{a^2} \over{2(a+k)}} = {{a+k} \over{2}} + {{a^2}\over {2(a+k)}}$$
The following number is equal to a+k: $${{a+k} \over{2}} + {{a^2}\over {2(a+k)}} + {{2ak+k^2}\over{2(a+k)}} = {{(a+k)^2 + a^2 + 2ak + k^2}\over{2(a+k)}} = {{a^2 + k^2 + 2ak + a^2 + 2ak + k^2}\over{2(a+k)}} = {{2(a^2 + 2ak + k^2)}\over{2(a+k)}}={{(a+k)^2}\over{(a+k)}} = (a+k)$$
This means that $${{{a^2\over{a+k}} + a+k} \over {2}}< {a+k}.$$ From the two inequalities I obtain that: $$a< {{{a^2\over{a+k}} + a+k} \over {2}}< {a+k}.$$ This means that the solution obtained goes closer and closer at each step to the real value of $a$ whether $k$ is positive or negative.
Teachers' Resources
Why do this problem?
This problem involves a historically significant example of iteration. It gives students the opportunity to think about how iterative processes work and what their limitations are. Students can use a spreadsheet to speed up multiple calculations, but should use algebra and reasoning to explain their numerical results.
Possible approach
Students could read through the introductory explanation given first or they could start with the iteration given as a formula, a worded explanation or a flow chart. If students start with the iteration without any context, they could be asked to experiment with different starting values and try to work out what the iteration does. The historical context could then follow.
Alongside experimenting with changes to the iterative formula, students should be asked to consider how the iterative process works. They may already have an idea after seeing how the given formula gives approximations to $\sqrt3$ or they may prefer to try adapting the formula to find the square roots of other values before they can explain the iteration in words. Once they have a good idea of how the formula works and can adapt it to find other square roots, they should try to adapt it to find other roots such as cube roots and beyond. Students should be able to demonstrate algebraically why their formulae approach the limit that they do if such a limit exists.
Possible extension
Students who have encountered fixed point iteration and the Newton-Raphson method could consider how the iterative formula used in this problem could be seen as an example of either of those two methods. They could use the graphical interpretations of those methods to explain why different adaptations of the iteration and different starting points do or do not work.