Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer
    
Thanks! There was also a follow-up question: what happens if x_0 < 0? I'm not sure about this, other than just to say there are no real roots. I don't think that's the expected answer. I think that means, it violates some assumptions of banachs fixed point theorem? Perhaps that it's monotonic and/or bounded? Really not sure. –  nsw Feb 18 '13 at 11:21
    
no than it just konverges to $-\sqrt{A}$ –  Dominic Michaelis Feb 18 '13 at 11:23

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)}$$

share|improve this answer
    
as the newton raphson is only a local convergent iteration method you need something for the global convergence (here it is the convexity of $x^2$ –  Dominic Michaelis Feb 18 '13 at 10:45
    
Correct. Thanks for clarifying. –  Gautam Shenoy Feb 18 '13 at 10:49

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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