Prove the sequence $x_n = \frac{x_{n-1}}{2}+\frac{A}{2x_{n-1}} \rightarrow \sqrt{A}$ as $n \to \infty$

Question

Show that if A is any positive number, then the sequence defined by:

$$x_n = \frac{x_{n-1}}{2}+\frac{A}{2x_{n-1}}$$

for any $n \geq 1$ converges to $\sqrt{A}$ whenever $x_0 > 0$.

Answer 1

Ok you can make this in two different ways, banachs fix point theorem, this ones says: $f:M\rightarrow M$ be a strict contraction (lipschitz constant $<1$) and $M$ be complete. Than there exits exactly one solution of $f(x)=x$

An alternative way is to show, that the sequence is monotone and bounded (both for the convergence). Afterwards use $$\lim_{n\rightarrow \infty} a_{n+1} = \lim_{n\rightarrow \infty} a_n$$ After you have shown, hat $x_n$ converges you know it has a limit $x$. So $$x=\frac{x}{2}+\frac{A}{2x}\iff (2-1)x^2=A$$ The $\iff$ comes from the assumption $x_0>0$

There is even another one over the newton iteration. (the convergence is guaranted, because $x^2$ is convex.)

Answer 2

As the above answer suggests, use Newton Raphson method on $f(x) = x^2 -A$.

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

Answer 3

Let $A > 0$ and $x_0 > 0$. Set $$f(x) = \frac{x}{2} + \frac{A}{2x},$$

then $x_n = f(x_{n-1})$ for $n > 0$. Observe that $\left(x-\sqrt{A}\right)^2 \geq 0$ forces $f(x) \geq \sqrt{A} > 0$. Moreover, $x \geq \sqrt{A}$ implies $\frac{A}{x}\leq x$, hence $f(x) \leq x$, i.e. sequence $(x_n)$ is non-increasing for $n > 1$. Thus, we know that a finite limit $\lambda < \infty$ exist and that $\lambda \geq \sqrt{A}$. However, if your sequence $x_{n+1} = f(x_n)$ has a finite limit $\lim_{n\to\infty}x_n = \lambda$, then it has to be a fixed point of $f$ (it is continuous), i.e. $f(\lambda) = \lambda$, but

$$\lambda = \frac{\lambda}{2} + \frac{A}{2\lambda}$$

implies that $(\lambda - \sqrt{A})^2 = 0$ (note that $\lambda \geq \sqrt{A} > 0$) and this concludes the proof. $\blacksquare$

I hope this helps ;-)