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

fixed-point-theoremssequences-and-series

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

Best Answer

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.)

Related Question