3
$\begingroup$

Let $x_1=c$ and $x_{n+1}=\frac{x_n^2 + \frac{a}{b}}{2x_n}$. How prove $\lim x_n = \sqrt{\frac{a}{b}}$ if $b \neq 0$ ?

$\endgroup$
  • 3
    $\begingroup$ If it exists, it will satisfy $L=\frac{L^2+\frac{a}{b}}{2L}$. (Take the limit of both sides of the recurrence relation). $\endgroup$ – Michael Burr Jul 13 '15 at 5:41
  • $\begingroup$ yes, but how prove $\lim x_n = \sqrt{\frac{a}{b}}$? $\endgroup$ – piteer Jul 13 '15 at 5:44
  • 2
    $\begingroup$ Try and show that $x_n$ is eventually monotone, and bounded (depending on the value of $c$). Hence, the existence of the limit will follow from monotone convergence. $\endgroup$ – r9m Jul 13 '15 at 5:56
  • $\begingroup$ @MichaelBurr just said how to compute the limit, if it exists. What remains is to prove that it exists. $\endgroup$ – Yves Daoust Jul 13 '15 at 5:58
  • $\begingroup$ This is well-known Newton (or Babylonian) method $\endgroup$ – Michael Galuza Jul 13 '15 at 6:00
4
$\begingroup$

Let $v=\sqrt{\frac{a}{b}},b\gt0,x_1=c\gt 0$ Now we first show that $x_n^2\ge v$ for $n\ge2$,

since $x_n$ satisfied the quadratic equation $$x_n^2-2x_nx_{n+1}+v=0$$ this equation has a real root. Hence the discriminant $$4x_{n+1}^2-4v$$ must be non-negative, that is ,$x_{n+1}^2\ge v$ for $n\ge 1$

Now, $$x_n-x_{n+1}=x_n-\frac{1}{2}\left(x_n+\frac{v}{x_n}\right)=\frac{(x_n^2-v)}{2x_n}\ge0$$ $\implies x_{n+1}\le x_n$ for all $n\ge2$,
and as $x_{n}$ is both monotonically decreasing and bounded below, by Monotone-convergence-Theorem limit of the given sequence $x_n$ exists.

Take $\lim_{n\to \infty}x_n=l$, then $\lim_{n\to \infty}x_{n+1}=l$ and taking limit on both sides of the given expression, we have

$$l=\frac{l^2+\frac{a}{b}}{2l}$$ which gives ,

$$l^2=\frac{a}{b}$$ can you finish from here?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ He wants proof of existence of the limit... $\endgroup$ – pre-kidney Jul 13 '15 at 5:52
  • $\begingroup$ @ pre-kidney: See ;) $\endgroup$ – Chiranjeev_Kumar Jul 13 '15 at 6:35
3
$\begingroup$

For convenience, let $s:=\sqrt{\dfrac ab}$.

Then,

$$\frac{x_{n+1}-s}{x_{n+1}+s}=\frac{\dfrac{x_n^2+s^2}{2x_n}-s}{\dfrac{x_n^2+s^2}{2x_n}+s}=\left(\frac{x_n-s}{x_n+s}\right)^2,$$

and by recurrence $$\frac{x_n-s}{x_n+s}=\left(\frac{c-s}{c+s}\right)^{2^n}.$$

This gives us the explicit formula

$$\color{green}{x_n=s\frac{1+r^{2^n}}{1-r^{2^n}}},$$

where $$r:=\frac{c-s}{c+s}.$$

It (quickly) converges to $s$ when $$|r|=\left|\frac{c-s}{c+s}\right|<1,$$ which is true for any $$c>0.$$


Addendum for numericians:

Choose the integer $k$ such that $2^k\le s^2<2^{k+1}$ ($k$ is the rank of the most significant bit in $s^2$) and let $$c=\frac1{\sqrt[4]2}\cdot2^{k/2}\text{ or }c=\sqrt[4]2\cdot2^{(k-1)/2}$$ depending on the parity of $k$. Then $$\frac 1{\sqrt[4]2}\le\frac cs<\sqrt[4]2.$$

This makes an excellent starting approximation, as at worse $r=0.086427\cdots=2^{-3.5323\cdots}$ and the iterates give at least $3.5,7,28,56\cdots$ exact bits, which are enough for the single and double precision floating-point representations.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Let $r=\frac{a}{b}$ and assume that $r>0$ and $c>0$. To prove existence of the limit, rewrite the equation as follows: $$ 2x_{n+1}=x_n + \frac{r}{x_n}\quad (\star) $$ Since $x_1=c>0$ and $r>0$, it follows by induction that all $x_n$ are positive. Applying the AM-GM Inequality, we see that $x_{n+1}\geq \sqrt{r}$ (for $n\geq 1$). Squaring both sides of $(\star)$ yields $$ \begin{align*} 4x_{n+1}^2&=x_n^2 + 2r + \frac{r^2}{x_n^2}\\ \implies 4x_{n+1}^2-4r&=\left(x_n-\frac{r}{x_n}\right)^2\\ \implies \left|\frac{x_{n+1}^2-r}{x_n^2-r}\right|&=\frac{\left|1-\frac{r}{x_n^2}\right|}{4}. \end{align*} $$

Since $x_n\geq \sqrt{r}$ for $n\geq 2$, it follows that $\left|1-\frac{r}{x_n^2}\right|\leq 1$ for $n\geq 2$. Consequently $$ \left|x_{n+1}^2-r\right|\leq \left(\frac{1}{4}\right)\cdots \left(\frac{1}{4}\right)\left(\frac{\left|1-\frac{r}{c^2}\right|}{4}\right)\left|c^2-r\right|=\frac{C}{4^n}, $$ for some positive constant $C$.

Taking the limit as $n\to\infty$, it follows that $\lim_{n\to\infty} x_{n+1}^2=r$, and therefore $\lim_{n\to\infty}x_n=\sqrt{r}$ as desired.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ How do you know that $|1-r/x^2_n| < 1$? $x_n$ might be very small compared to $r$, so $1-r/x^2_n < 0$ and large in absolute value. $\endgroup$ – marty cohen Jul 13 '15 at 6:13
  • $\begingroup$ In fact, $x_n^2 \geq r$ by AM-GM, which ensures that $1-r/x_n^2\geq 0$. I will include this argument, good catch! $\endgroup$ – pre-kidney Jul 13 '15 at 6:16
  • 1
    $\begingroup$ What if $x_1 = r/1000$? $\endgroup$ – marty cohen Jul 13 '15 at 6:20
  • $\begingroup$ No problem; simply start telescoping from $n=2$. See the edits... $\endgroup$ – pre-kidney Jul 13 '15 at 6:27
  • $\begingroup$ OK. btw, $x+r/x = x-2\sqrt{r}+r/x + 2\sqrt{r} = (\sqrt{x}-\sqrt{r/x})^2+2\sqrt{r} \ge 2\sqrt{r}$, so you don't need to invoke am-gm. $\endgroup$ – marty cohen Jul 13 '15 at 6:53
1
$\begingroup$

Let $L =\sqrt{\dfrac{a}{b}}$, then $x_{n+1}-x_n = \dfrac{x_n^2+L^2}{2x_n}-x_n=\dfrac{L^2-x_n^2}{2Lx_n}\leq 0$ because $L \leq x_n$ is true by AM-GM inequality: $x_n^2+L^2 \geq 2Lx_n\to x_{n+1} = \dfrac{x_n^2+L^2}{2x_n} \geq L, \forall n \geq 1$, and $x_n \geq L$ so it is decreasing and bounded below by $L$, hence converges also to $L$. The "also" part needs some more clarification: $l = \displaystyle \lim_{n\to \infty} x_n$, then $l = \dfrac{l^2+L^2}{2l}\to l^2=L^2 \to l = L$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This argument proves that the limit exists and that the limit is greater than or equal to $L$, but does not rule out the possibility that it is strictly larger than $L$. $\endgroup$ – pre-kidney Jul 13 '15 at 6:05
  • $\begingroup$ For example, the sequence $\frac{n+1}{n}$ is decreasing and bounded below by $0$, but converges to $1$. $\endgroup$ – pre-kidney Jul 13 '15 at 6:06

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.