Convergence of the sequence from Heron's method.

[Coffee_]

$a_1=1$

$a_{n+1}=\frac{1}{2} ( a_{n} + \frac{b}{a_n} )$

This should converge to $\sqrt{b}$ but I seem not to be able to prove this. Could someone give me a hint.

 

[micromass]

First prove that a limit exists. Show this by proving (by induction) that the sequence (starting from $a_2$) is nonincreasing and bounded below.

 

[jostpuur]

One can define a new sequence \delta_1,\delta_2,\delta_3,\ldots by setting \delta_n=a_n-\sqrt{b}, and then solve an equivalent recursion formula for \delta_{n+1}. Proving \delta_n\to 0 can turn out more natural than proving the original claim directly.

 

[Coffee_]

First we prove that any term that is given by the recursion formula is either larger or equal to $\sqrt{b}$.

$\frac{1}{2}(a_n + \frac{b}{a_n}) \ge \sqrt{b}$
This can be rewritten as :

$(a_n-\sqrt{b})^{2} \ge 0$

Which is obviously always the case. To conclude, any term starting from $a_2$ is larger or equal to $\sqrt{b}$

Next we will look at when the succeeding term is non increasing:

$a_{n+1}=\frac{1}{2}(a_n + \frac{b}{a_n}) \le a_n$ ?

$a_n + \frac{b}{a_n} \le 2 a_n$

$b \le a_n^{2}$

This means that as long as the previous term was above $\sqrt{b}$ the next one will be smaller. However I proved that from $a_2$ all the terms are above $\sqrt{b}$ which means that from $a_2$ on it is non decreasing and bounded from below by $\sqrt{b}$.

 

[micromass]

That is correct. So now you've shown that $(a_n)_n$ is decreasing and bounded below, which means that it converges. Now we use a dirty trick to find the actual limit of $(a_n)_n$. We have

\lim_{n\rightarrow +\infty} a_n = \lim_{n\rightarrow +\infty} a_{n+1} = \lim_{n\rightarrow +\infty} \frac{1}{2}\left(a_n + \frac{b}{a_n}\right)

I'll let you do the rest.

 

[Coffee_]

Wow that is indeed a dirty trick! However it clearly does follow from it, thanks a lot.

 

[jostpuur]

It seems my advice wasn't useful for the precise requested task, but I insist that it can be useful for other purposes. For example here the sequence converges towards \sqrt{b} at a rate that is faster than exponential, and that can be relevant for numerical purposes, but it wasn't yet proven by the used tricks.