Need help finishing my proof about this complex recursive limit

Question

Let $a \in \mathbb C$ be a given non zero complex number. An exercise in my book is asking me to determine for which complex $z_0$ the the sequence

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

makes sense and has a limit.

Here is what I have so far:

I believe the sequence always makes sense when $z_0 \neq 0$ and it's only a question whether the limit exists or not.

I conjectured that if $\sqrt{a} = \sqrt{r}e^{i 2 \varphi}$ has positive real part then the limit of the sequence exists if $z_0$ has positive real part (and similarly for negative real parts.

To prove this I assumed that $\varphi \in (-{\pi \over 2}, {\pi \over 2})$ and that the argument of $z_0$ is also in this interval. Then it's easy to see that all $z_n$ also have positive real part and by taking the limit on both sides we can prove that the limit is $\sqrt{a}$.

(1) (At this point it's not clear to me how to determine to which of the two square roots it converges to. Any help is appreciated.)

Next I wanted to show that if $\varphi \in (-{\pi \over 2}, {\pi \over 2})$ but the argument of $z_0$ is not in this interval so that $z_0$ has negative real part then the sequence does not converge. This is where I got stuck.

(2) Can someone please help me prove that if $\varphi \in (-{\pi \over 2}, {\pi \over 2})$ but $z_0$ has negative real part then the sequence does not converge?

Answer 1

I. The argument using normal families: $\DeclareMathOperator{\re}{Re}$

We let $b$ denote one of the two square roots of $a$. Now we note that for $z\in \mathbb{C}\setminus \{0\}$ we have

$$\re z \gtrless 0 \iff \re \frac{1}{z} \gtrless 0,$$

and hence $$f(z) = \frac{1}{2}\left(z + \frac{a}{z}\right)$$ maps the half-planes $H^+ := \{ z : \re (z/b) > 0\}$ and $H^- := \{ z : \re (z/b) < 0\}$ to themselves, as well as the (extended) line $L := \{ z : \re (z/b) = 0\} \cup \{\infty\}$. So we can consider the families of iterates of $g = f\lvert_{H^+}$, the restriction of $f$ to $H^+$, and $h = f\lvert_{H^-}$, the restriction of $f$ to $H^-$. Let $\mathscr{G} = \bigl\{ g^n : n \in \mathbb{N}\setminus \{0\} \bigr\}$ and $\mathscr{H} = \bigl\{ h^n : n \in \mathbb{N}\setminus \{0\} \bigr\}$. Then $\mathscr{G}$ is a family of holomorphic functions with values in $H^+$, and $\mathscr{H}$ is a family of holomorphic functions with values in $H^-$.

Since half-planes are biholomorphically equivalent to the unit disk, the families $\mathscr{G}$ and $\mathscr{H}$ are normal. [Note: the two families are in fact locally bounded, so the little Montel theorem asserts the normality without the detour via the unit disk, but showing that directly is non-obvious.]

Next we note that $f$ has the two fixed points $b$ and $-b$ in $\mathbb{C}$ (in the Riemann sphere, $\infty$ is a third fixed point), and since

$$f'(z) = \frac{1}{2}\left(1 - \frac{a}{z^2}\right),$$

we have $f'(\pm b) = 0$, so $b$ and $-b$ are attractive fixed points. Hence the sequence of iterates $(f^n)$ converges uniformly to the constant $b$ on some neighbourhood of $b$, and it converges uniformly to the constant $-b$ on some neighbourhood of $-b$. By the identity theorem, it follows that every subsequence $(g^{n_k})$ of $(g^n)$ that converges locally uniformly on $H^+$ converges to the constant $b$, and ditto every subsequence $(h^{n_k})$ of $(h^n)$ that converges locally uniformly on $H^-$ converges to the constant $-b$. By the normality of $\mathscr{G}$ and $\mathscr{H}$, it then follows that $g^n \to b$ locally uniformly on $H^+$ and $h^n \to -b$ locally uniformly on $H^-$.

So we see that the sequence $(z_n)$ converges to $b$ when $z_0 \in H^+$, and it converges to $-b$ when $z_0 \in H^-$. For $z_0\in L$, the sequence either converges to $\infty$ - when $z_0$ is one of countably many points on $L$ such that $z_n = 0$ for some $n\in \mathbb{N}$ - or not at all.

Remark: For this specific example, the argument by normality is not the best, we can obtain a more precise view with simpler means, as illustrated below, or in user21820's answer. However, in geometrically more complicated situations, such an argument can be very powerful while still remaining (comparatively) simple.

II. The argument by the normal form:

As above, we let $b$ denote one of the square roots of $a$. The rational function $f$ from above has two special points, the attractive fixed points $b$ and $-b$. In such a situation, it is often illuminating to move the special points to $0$ and $\infty$ by conjugating the function with a Möbius transformation. The simplest Möbius transformation mapping $b\mapsto 0$ and $-b \mapsto \infty$ is $$S(z) = \frac{z-b}{z+b}.$$

The inverse is $$S^{-1}(w) = b\frac{1+w}{1-w},$$ and we compute

$$(f\circ S^{-1})(w) = \frac{1}{2}\left( b\frac{1+w}{1-w} + b\frac{1-w}{1+w}\right) = \frac{b}{2} \frac{(1+w)^2 + (1-w)^2}{1-w^2} = b\frac{1+w^2}{1-w^2}$$ and finally

$$(S\circ f \circ S^{-1})(w) = \frac{b\frac{1+w^2}{1-w^2}-b}{b\frac{1+w^2}{1-w^2}+b} = \frac{b(1+w^2)-b(1-w^2)}{b(1+w^2)+b(1-w^2)} = \frac{2bw^2}{2b} = w^2.$$

The behaviour of the iterates of $g = S\circ f \circ S^{-1}$ is now very easy to understand. It is immediately obvious that $g^n(w_0) \to 0$ for $\lvert w_0\rvert < 1$ and $g^n(w_0) \to \infty$ for $\lvert w_0\rvert > 1$, and even the behaviour on the unit circle is better understandable. We see that $g^n(w_0)$ stabilises at $1$ if and only if there are $m\in \mathbb{Z}$ and $k\in \mathbb{N}$ such that

$$w_0 = \exp \left(2\pi i \frac{m}{2^k}\right),$$

for all other $w_0$ on the unit circle the sequence is not convergent, it becomes periodic if $w_0 = \exp (2\pi i r)$ with a rational $r$, and does not repeat for other starting values on the unit circle.

Now we can use that $f^n = S^{-1}\circ g^n \circ S$ to obtain the explicit formula

$$f^n(z) = b\frac{1 +\left(\frac{z-b}{z+b}\right)^{2^n}}{1 - \left(\frac{z-b}{z+b}\right)^{2^n}},$$

which is essentially the same as in user21820's answer.

Answer 2

[I will solve the problem in the extended complex plane $\hat{\mathbb{C}} = \mathbb{C} \cup \{\infty\}$ for convenience.]

Solution

Take $z_0 \in \hat{\mathbb{C}}$ and $z_{n+1} = \frac{1}{2} ( z_n + \frac{a}{z_n} )$ for all $n \in \mathbb{N}$.

[Note that if $a = 0$ then $z_n \to 0$ or $z_n = \infty$ depending on whether $z_0 \ne \infty$, but the question assumes $a \ne 0$ anyway.]

Let $w_n = \sqrt{a} z_n$ for all $n \in \mathbb{N}$. [Then all we need to find is the behaviour of $w$ since $z_n = \frac{w_n}{\sqrt{a}}$.]

Then $w_{n+1} = \frac{1}{2} ( w_n + \frac{1}{w_n} )$ for all $n \in \mathbb{N}$.

[Now the idea is to express $w_n = \frac{p_n}{q_n}$ and convert the recurrence into simpler ones.]

Let $(p_0,q_0) = (w_0,1)$ and $(p_{n+1},q_{n+1}) = (p_n^2+q_n^2,2p_nq_n)$ for all $n \in \mathbb{N}$.

Then $w_{n} = \frac{p_n}{q_n}$ for all $n \in \mathbb{N}$.

Also $p_{n+1}+q_{n+1} = (p_n+q_n)^2$ and hence $p_n+q_n = (p_0+q_0)^{2^n} = (w_0+1)^{2^n}$ for all $n \in \mathbb{N}$.

And $p_{n+1}-q_{n+1} = (p_n-q_n)^2$ and hence $p_n-q_n = (p_0-q_0)^{2^n} = (w_0-1)^{2^n}$ for all $n \in \mathbb{N}$.

Thus $w_n = \dfrac{(w_0+1)^{2^n}+(w_0-1)^{2^n}}{(w_0+1)^{2^n}-(w_0-1)^{2^n}} = \dfrac{c^{2^n}+1}{c^{2^n}-1}$ for all $n \in \mathbb{N}$, where $c = \dfrac{w_0+1}{w_0-1}$.

If $|c| > 1$:

  $w_n \to 1$ as $n \to \infty$.

If $|c| < 1$:

  $w_n \to -1$ as $n \to \infty$.

If $|c| = 1$ and $c^{2^m} = 1$ for some $m \in \mathbb{N}$:

  $w_n = \infty$ for all $n \in \mathbb{N}_{\ge m}$.

If $|c| = 1$ and $c^{2^n} \ne 1$ for all $n \in \mathbb{N}$:

  $w_0 \ne \infty$ and $|w_0-1| = |w_0-(-1)|$

  Thus $w_0 \in i\mathbb{R}$ and hence $w_n \in i\mathbb{R}$ since $w_n \ne \infty$ for all $n \in \mathbb{N}$.

  If $w_n \to b$ as $n \to \infty$ for some $b \in \hat{\mathbb{C}}$:

    $b \in i\mathbb{R} \cup \{\infty\}$ because $i\mathbb{R} \cup \{\infty\}$ is closed in $\hat{\mathbb{C}}$.

    If $b = \infty$:

      Let $m \in \mathbb{N}$ such that $|w_n| \ge 2$ for all $n \in \mathbb{N}_{\ge m}$.

      Then $|c^{2^n}-1| \le 1$ for all $n \in \mathbb{N}_{\ge m}$.

      Let $t \in [-π/2,π/2] \backslash \{0\}$ such that $c^{2^m} = e^{it}$.

      Then $c^{2^{m+n}} = e^{it2^n}$ for all $n \in \mathbb{N}$ and hence $Arg(c^{2^{m+k}}) \notin [-π/2,π/2]$ for some $k \in \mathbb{N}$.

      Thus $|c^{2^{m+k}}-1| > 1$ and hence a contradiction.

    Therefore $b \ne \infty$.

    Thus $0 = \lim_{n\to\infty} ( z_{n+1} - \frac{1}{2} ( z_n + \frac{1}{z_n} ) ) = b - \frac{1}{2} ( b + \frac{1}{b} )$ and hence $b \in \{1,-1\}$.

    Contradiction.

  Therefore $w$ does not converge.

[I leave it to you to find the corresponding $w_0$ for each case above.]

Notes

For those values of $w_0$ that make $w$ non-convergent, some make $w$ a cyclic sequence while others never cycle. See if you can distinguish the two cases as well.

Notice also that the iteration we have studied is exactly the Newton-Raphson iteration to find a root of $z \mapsto z^2-a$. Our analysis shows exactly when it converges to which root. Such iteration is actually an efficient method to compute the square-root of a complex number in arbitrary precision arithmetic, since the precision doubles at each step (which follows from the exponent of $2^n$ in the closed form for $w_n$), and hence each step is computed with about double the precision of the previous step, making the total time no more than a constant times that taken by the last step.