1

Consider the recursive sequence

$$ z_{n+1} = {1 \over 2}\left ( z_n + {1 \over z_n} \right )$$

where we start at some point $z_0 = x_0 + i y_0 \in \mathbb C$. This is Newton's formula to find the roots of $p(x) = x^2 -1$. By taking the limit on both sides we see that if the sequence converges then the limit must be either $1$ or $-1$. But:

How do you prove this sequence converges? Of course this is the very first thing we must show, even before calculating the limit!

Normally I would show it's a Cauchy sequence but I don't see how to do that here.

Anna
  • 1,757
  • 2
    Don't ask randomly same question...If you have any question about your problem then ask it it the comment of that question...Ask in your question – Empty Apr 06 '15 at 04:42
  • Here is the same question, only for the roots of $z^2 +1$ instead of $z^2 -1$: http://math.stackexchange.com/questions/33330/convergence-of-a-recursive-sequence-z-n1-frac12-z-n-frac1z-n?rq=1. – Martin R Apr 06 '15 at 10:12
  • @MartinR None of the answers there give a proof of convergence. Only in the case where the starting value is purely imaginary. But if I encounter this question I don't know in advance for what starting values it converges. So first I would try to prove convergence for a given (arbitrary) complex number. This is what I am asking about here. – Anna Apr 07 '15 at 04:52
  • In fact, the sequence might not converge. If $z_0=i$, then $z_1=0$ and $z_2=\infty$. If $z_0=i/\sqrt{3}$, then $z_1=-i/\sqrt{3}$, $z_2=i/\sqrt{3}$, and we have a periodic sequence. All kinds of awful behavior is possible on the imaginary axis. So you need some assumption on $z_0$ to obtain convergence. Specifically, we need $Im(z_0)\neq0$. – Mark McClure Apr 07 '15 at 05:46

2 Answers2

3

First of all, the sequence doesn't converge if $\newcommand{\real}{\operatorname{Re}}\real z_0 = 0$. You can check that if $z_0$ is purely imaginary, then so is $z_1$, and inductively all $z_n$.

On the other hand, it's also easy to check that if $\real z_0 > 0$, then $\real z_1 > 0$, so sequences that start in the left half-plane stays there. Similarly, sequences that start in the right half-plane stay in the right half-plane.

Now, assume that $\real z_0 > 0$. The analysis will be easier if we work on the unit disc instead of the half-plane. The mapping $$ f(z) = \frac{i+z}{i-z} $$ maps the unit disc conformally onto the right half-plane. Define a new sequence of points: $w_n = f^{-1}(z_n)$. Then (after some algebra) $$ w_{n+1} = f^{-1}(z_{n+1}) = f^{-1}(N(f(w_n)) = -iw_n^2 $$ where $N(z) = \frac12(z+\frac1z)$ is the Newton iteration.

Here it is clear that $w_n$ tends to $0$ if we start inside the unit disc, so $z_n$ tends to $f(0) = 1$.

The case where $z_0$ is in the left half-plane can be handled in a similar way. This corresponds to a starting point $w_0$ outside the unit disc, and $w_n \to \infty$. I.e. $z_n \to f(\infty) = -1$.

Note: the convergence here is deceptively simple. For higher degree polynomials, the basins of attraction for the various solutions is very complicated. See Newton fractals for some nice pictures!

mrf
  • 43,639
  • I was just about to write a similar answer :) I chose $w \to (1+w)/(1-w) $ as mapping from the unit disk to the right half-plane, then $w_{n+1} = w_n^2$. The inverse mapping is $z \to (z-1)/(z+1)$. – Martin R Apr 07 '15 at 07:40
  • Thank you for your answer! So, showing that it is a Cauchy sequence is not an option? And what about the other answer? Does it mean the other answer is invalid? – Anna Apr 18 '15 at 03:12
  • 1
    The other answer is only valid for real staring points. It might be possible to directly prove that the sequence is Cauchy, but the above was the first that came to mind. – mrf Apr 18 '15 at 07:02
  • I have one last question about your answer: Where you write unit disk you mean as a subset of the Riemann sphere, right? So that $f$ maps the right half plane into the Riemann sphere. And I guess that it maps the other half plane to the other half of the Riemann sphere (which corresponds to the outside of the unit disk)? – Anna Apr 19 '15 at 04:33
2

Assume $z_1 > 0$, first you prove that $z_n \geq 1, \forall n \geq 2$, and this is easily done by apply AM-GM inequality to the right side of the equation. Next, $0\leq z_{n+1} - 1 = \dfrac{(z_n-1)^2}{2z_n}=(z_n-1)\dfrac{z_n-1}{2z_n}< \dfrac{z_n-1}{2}<...< \dfrac{z_1-1}{2^n}$. Thus by squeeze theorem, $z_n \to 1$.

DeepSea
  • 77,651
  • Thank you for your answer. Please, could you elaborate a little on why it is okay to assume that $z_1$ is real? – Anna Apr 06 '15 at 04:47
  • No, see it has the tag complex-analysis. I will edit and make it more explicit. – Anna Apr 06 '15 at 04:51
  • Fine, you can consider the real and imaginary parts of the sequence $z_n = a_n+ib_n$ – DeepSea Apr 06 '15 at 04:53
  • Thank you for your comment. Say we let $z_n = x + iy$ then I calculated the real part as $$ {x^3 + xy^2 + x \over x^2 + y^2}$$

    Now I tried to apply AM-GM inequality like so

    $$ {1 \over x^2 + y^2}\cdot {x^3 + xy^2 + x \over 3} \ge {1 \over x^2 + y^2} \cdot \sqrt[3]{x^2 + xy^2 + x}$$

    But I don't know how to go on from there...

     – Anna Apr 07 '15 at 04:45