17
$\begingroup$

There is a problem in my textbook that goes like this

$$ a_n = \frac {a_{n-1} + \frac {2}{a_{n-1}}}{2}$$

and

$$a_0 =1$$

for all $n\ge1$.

It is monotonically decreasing sequence of rational numbers and bounded below. However, it cannot converge to a rational number.

Then the task is to find the limit. The problem itself is easy but I don't understand how the author judged the limit to be irrational even before solving the question? Is there any property or did they just know the answer beforehand?

$\endgroup$
  • 11
    $\begingroup$ I'm sure the author worked out the limit before setting the question.... $\endgroup$ – Lord Shark the Unknown Aug 8 '17 at 6:26
  • 2
    $\begingroup$ Assume $a_n=a_{n-1}=p/q$, and you'll find $p^2/q^2=2$. This tells you that the limit isn't rational even without recognising Newton's algorithm. $\endgroup$ – Toffomat Aug 8 '17 at 9:29
28
$\begingroup$

Yep, the author knew the answer beforehand, I would say much longer before.

Because this is just an instance of the Babylonian method of computing square roots, later discovered to be a particular case of Newton's iterative method for the resolution of nonlinear equations.

So with closed eyes, this sequence converges to $\sqrt2$. You can easily verify it be assuming convergence, so that $a_{n-1}$ and $a_n$ become indiscernible, and

$$a=\frac{a+\dfrac2a}{2}$$ or $$a^2=2.$$ As the initial value is $1$, all terms are positive and convergence is to the positive root (if there is convergence, though).


There is a simple way to explain that method, also known as Heron's formula.

Let $s$ be the number of which you want to extract the root, and let $a$ be an approximation by default. Then $$a<\sqrt s\implies a':=\frac sa>\sqrt s$$ so that $\dfrac sa$ is another approximation, by excess. Now if we take the arithmetic mean, we get a new approximation which is closer than the worse of the two,

$$a''=\frac{a+a'}2=\frac{a+\dfrac sa}{2}.$$

As can be shown, when you are close to the root, the sequence converges extremely rapidly.

For example,

$$a=\color{green}{1.41}\implies a'=\color{green}{1.41}84397163121\cdots\implies a''=\color{green}{1.41421}9858156\cdots$$ while the true value is $$\sqrt2=1.4142135623731\cdots$$

The next iteration gives $11$ exact digits.


A note on convergence, for the skepticals (the method has been in use for at least two millenia).

Let $$x_n:=\frac{a_n}{\sqrt s}.$$

We have

$$\frac{x_{n+1}-1}{x_{n+1}+1}=\frac{x_n+\dfrac1{x_n}-2}{x_n+\dfrac1{x_n}+2}=\frac{(x_n-1)^2}{(x_n+1)^2}$$ and by induction

$$\frac{x_n-1}{x_n+1}=\left(\frac{x_0-1}{x_0+1}\right)^{2^n}.$$

This is an exact formula for the $n^{th}$ iterate, which proves convergence from any $x_0$ such that

$$\left|\frac{x_0-1}{x_0+1}\right|<1.$$

This holds for all positive $x_0$.

In passing, this also proves quadratic convergence, i.e. the relative error is squared on every iteration.

$\endgroup$
  • $\begingroup$ This is very nice but it doesn't seem obvious that the approximations converge. While the average is better than the worse of the two approximations it might be much worse than the better of the two approximations so you might actually be diverging if you choose the average as your new approximation. Or am I missing something? $\endgroup$ – DRF Aug 8 '17 at 8:06
  • 3
    $\begingroup$ @DRF: the OP claimed convergence, so I didn't address this issue. But as the average is better than the worse estimate, the worse estimate always improves and divergence is not possible. $\endgroup$ – Yves Daoust Aug 8 '17 at 8:11
  • $\begingroup$ @YvesDaoust You only have one estimate when approaching the problem as the OP does. More over in your case you start with one estimate and get two. How do you continue from there? Choose the one you didn't choose last? Then you might be choosing the worse of the two and end up with three. I suppose this isn't really pertinent to the OP's question but the way you wrote the post seems confusing. $\endgroup$ – DRF Aug 8 '17 at 8:17
  • 1
    $\begingroup$ @YvesDaoust I apologize I didn't intend to provide comments in bad faith. I sincerely didn't see why the algorithm should have to converge always when given as the OP described it, and I have never seen this specific algorithm. (I suppose it might not anyway the initial approximation needs to be good enough). Thank you for the extra explanation which I think works very nicely. (oh and a +1) $\endgroup$ – DRF Aug 8 '17 at 9:24
  • $\begingroup$ @DRF: I discarded my harsh comment :) $\endgroup$ – Yves Daoust Aug 8 '17 at 9:55
5
$\begingroup$

Suppose $f(x)=x^2-2$ so roots are $\pm \sqrt2$ now use Newton method $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$$ so you will have $$x_{n+1}=x_n-\frac{x_n^2-2}{2x_n}\\=\frac{\frac{2x_n^2-x_n^2+2}{x_n}}{2}\\=\frac{x_n+\frac{2}{x_n}}{2}$$ now take $x_n \to a_n$ so $$a_n = \frac {a_{n-1} + \frac {2}{a_{n-1}}}{2}$$ and note $a_n $ tends to $\sqrt 2 ,if \space a_1>0$ , tends to $-\sqrt 2 ,if \space a_1<0 $ by iteration.
$\bf remark:$ there are some equation like this which work with rational numbers and finally get irrational ... for example :$\sum _{n=1}^{\infty}\frac{1}{n^2}=\frac{\pi^2}{6}\\\text{sum of rationals = irrational}$

$\endgroup$
5
$\begingroup$

Rewrite $$a_n = \frac {a_{n-1} + \frac {2}{a_{n-1}}}{2}$$ as $$a_n=a_{n-1}-\frac 12a_{n-1}+\frac 1{a_{n-1}}=a_{n-1}-\frac{a^2_{n-1}-2 }{2a_{n-1}}$$ and recognize the Newton formula for the solution of $x^2-2=0$.

$\endgroup$
2
$\begingroup$

Because if $a$ is the limit then $a^2=2$, which gives $a=\sqrt2$, which is an irrational number.

$$a_{n}-\sqrt2=\frac{(a_{n-1}-\sqrt2)^2}{2a_{n-1}}>0$$ and $$a_n-a_{n-1}=\frac{1}{a_{n-1}}-\frac{a_{n-1}}{2}=\frac{2-a_{n-1}^2}{2a_{n-1}}<0,$$ which gives that our sequence converges.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.