3
$\begingroup$

For any $a > 0$, I have to show the sequence $x_{n+1}$ $=$ $ \frac 12$($x_n+ $ $ \frac {a} {x_n}$)

converges to the square root of $a$ for any $x_1>0$.

If I assume the limit exists ( denoted by $x$) then,

$x$ $=$ $ \frac 12$($x+ $ $ \frac {a} {x}$) can be solved to $x^2 = a$

How could I show that it does exist?

$\endgroup$
  • $\begingroup$ Try to show that the sequence is monotonic and bounded, then you can conclude that the limit exists. $\endgroup$ – Mustafa Said Mar 21 '14 at 20:36
  • $\begingroup$ It seemed that whether or not it increased/decreased depended on the value of $x_n$ compared to $a$ and to 1. I assumed this would mean I would have to break it into multiple cases. Is there something I missed? $\endgroup$ – user110503 Mar 21 '14 at 20:41
  • $\begingroup$ we have that $x_n \geq a$ by the arithmetic-geometric mean inequality for $n \geq 2$ so you may assume that $x_n > a$. $\endgroup$ – Mustafa Said Mar 21 '14 at 20:55
  • $\begingroup$ Possible duplicate of Proof of Convergence: Babylonian Method $x_{n+1}=\frac{1}{2}(x_n + \frac{a}{x_n})$ $\endgroup$ – Arnaud D. Apr 18 at 12:14
2
$\begingroup$

As mentioned in the comments, we need to show that the sequence is monotonic and bounded.

First, we observe that $$ x_n-x_{n+1}=x_n-\frac12\Bigl(x_n+\frac a{x_n}\Bigr)=\frac1{2x_n}(x_n^2-a). $$ Secondly, we obtain that \begin{align*} x_n^2-a &=\frac14\Bigl(x_{n-1}+\frac a{x_{n-1}}\Bigr)^2-a\\ &=\frac{x_{n-1}^2}4-\frac a2+\frac{a^2}{4x_{n-1}^2}\\ &=\frac14\Bigl(x_{n-1}^2-2a+\frac{a^2}{x_{n-1}^2}\Bigr)\\ &=\frac{1}{4}\Bigl(x_{n-1}-\frac a{x_{n-1}}\Bigr)^2\\ &\ge0. \end{align*} Hence, $x_n\ge x_{n+1}$ and $x_n$ is bounded from below since $x_n^2\ge a$ for each $n\ge2$.

Monotonic and bounded sequence converges. Denote the limit of the sequence $x=\lim_{n\to\infty}x_n$. Then we have that $$ x=\frac12\Bigl(x+\frac ax\Bigr)\quad\iff\quad x=\sqrt a. $$

$\endgroup$
  • $\begingroup$ This argument shows that a limit exists, but how does is show that the limit is $\sqrt{a}$? $\endgroup$ – Fly by Night Mar 21 '14 at 23:22
  • $\begingroup$ @FlybyNight The OP stated that he/she already knows that the limit is $\sqrt a$ if it exists. $\endgroup$ – Tunococ Mar 22 '14 at 0:08
  • $\begingroup$ @FlybyNight I added the fact that the limit is $\sqrt a$ to my answer. $\endgroup$ – Cm7F7Bb Mar 22 '14 at 7:22
2
$\begingroup$

That looks a lot like the well known method for computing square roots. It is derived by using Newton's on

$$ x^2 - a = 0 $$

$$ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} $$

$$=x_n-\frac{x_n^2-a}{2x_n}$$

$$=\frac{1}{2}\left(x_n+\frac{a}{x_n}\right) $$

If it converges it will converge to the $$ \sqrt{a} $$

$\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.