Here is Prob. 24, Chap. 5 in the book Principles of Mathematical Analysis by Walter Rudin, 3rd edition:

The process described in part (c) of Exercise 22 can of course also be applied to functions that map $(0, \infty)$ to $(0, \infty)$.

Fix some $\alpha > 1$, and put $$ f(x) = \frac{1}{2} \left( x + \frac{\alpha}{x} \right), \qquad g(x) = \frac{\alpha+x}{1+x}. $$ Both $f$ and $g$ have $\sqrt{\alpha}$ as their only fixed point in $(0, \infty)$. Try to explain, on the basis of properties of $f$ and $g$, why the convergence in Exercise 16, Chap. 3, is so much more rapid than it is in Exercise 17. (Compare $f^\prime$ and $g^\prime$, draw the zig-zags suggested in Exercise 22.)

Do the same when $0 < \alpha < 1$.

Here are the links to my posts here at Math SE on Prob. 22, Chap. 5, Prob. 16, Chap. 3, and Prob. 17, Chap. 3, in Baby Rudin, 3rd edition:

Prob. 22, Chap. 5 in Baby Rudin: Fixed Points of Real Functions

Prob. 16, Chap. 3 in Baby Rudin: $x_{n+1} = (x_n + \alpha/x_n)/2$, with $x_1 > \sqrt{\alpha}$, $\alpha > 0$

Prob. 17, Chap. 3 in Baby Rudin: For $\alpha > 1$, how to obtain these inequalities from this recurrence relation?

My Attempt:

We note that, for $0 < x < \infty$,
$$ g(x) = 1 + \frac{\alpha-1}{x+1},$$ and so $$f^\prime(x) = \frac{1}{2} \left( 1 - \frac{\alpha}{x^2} \right), \qquad g^\prime(x) = - \frac{\alpha-1}{(x+1)^2},$$ and for $\alpha > 1$, we see that, if $x > \sqrt{\alpha}$, then $x^2 > \alpha$, and so $$0 < f^\prime(x) < \frac{1}{2}. $$ which implies (by part (c) of Prob. 22, Chap. 5, in Baby Rudin, 3rd edition) that the sequence $x_0 > \sqrt{\alpha}$, $x_{n+1} = f \left( x_n \right)$, for $n = 0, 1, 2, 3, \ldots$, does converge to the only fixed point of $f$, which is $\sqrt{\alpha}$. In fact, for all $n$, we have $$ \left| x_{n+1} - x_n \right| \leq \frac{1}{2} \left| x_n - x_{n-1} \right| \leq \cdots \leq \frac{1}{2^n} \left| x_1 - x_0 \right|, $$ and so for any $m < n$, we have $$ \begin{align} \left| x_n - x_m \right| &\leq \left| x_n - x_{n-1} \right| + \cdots+ \left| x_{m+1} - x_m \right| \\ &\leq \left( \frac{1}{2^{n-1}} + \cdots + \frac{1}{2^m} \right) \left| x_1 - x_0 \right| \\ &= \frac{1}{2^m} \left( 1 + \cdots + \frac{1}{2^{n-m-1}} \right) \left| x_1 - x_0 \right| \\ &= \frac{1}{2^m} \frac{ 1 - \frac{1}{2^{n-m}} }{ 1 - \frac{1}{2} } \left| x_1 - x_0 \right| \\ &= \left( \frac{1}{2^{m-1}} - \frac{1}{2^{n-1}} \right) \left| x_1 - x_0 \right|, \end{align} $$ and upon letting $n \to \infty$, while keeping $m$ fixed, we obtain $$ \left| x_m - x \right| \leq \frac{1}{2^{m-1}} \left| x_1 - x_0 \right| = \frac{1}{2^{m-1}} \left| \frac{1}{2} \left(x_0 + \frac{\alpha}{x_0} \right) - x_0 \right| = \frac{1}{2^m } \left( x_0 - \frac{\alpha}{x_0} \right), $$ for $m = 1, 2, 3, \ldots$, which gives the rate of convergence of this recursive algorithm.

And, the similar situation occurs for $0 < \alpha < 1$ as well, provided we choose $x_0 > \sqrt{\alpha}$.

Is my analysis correct? Or, have I erred anywhere or missed something of substance?

And, what about $g$? How to analyze it? How to show what Rudin has demanded to be shown?

  • $\begingroup$ f(x) goes back about 19 or 20 centuries to Hero (Heron) of Alexandria. $\endgroup$ Jun 3 '17 at 22:07
  • $\begingroup$ This looks right. You have the functions and their derivatives, so use L'hopital's rule to find some intermediate function in an interval $ [0,1] $. $\endgroup$
    – McTaffy
    Jun 4 '17 at 17:05

For $f:$

Suppose $x_0>0$ and $a>0$.Let $x_{n+1}=(x_n+a/x_n)/2.$ Assume $x_0\ne \sqrt a \;$( because if $x_0=\sqrt a$ then $x_n=\sqrt a$ for all $n,$ which is a trivial case). Then we have:

(I). $x_1^2>a$ so $x_1>\sqrt a.$

(II). If $x_n^2>a$ then $x_n>x_{n+1}>\sqrt a.$ So by (I), $n\geq 1\implies x_n>x_{n+1}>\sqrt a.$

(III). If $n\geq 1$ and $x_n=k\sqrt a$ with $k\geq 2$ then $x_{n+1}=\sqrt a\;(k+1/k)/2<\sqrt a\;(k+1)/2$, so for some $m>n$ we will have $1<x_m/\sqrt a\;<2.$

(IV). If $1<x_m/\sqrt a<2$ then let $x_n=(1+d_n)\sqrt a$ for each $n$. Then $0<d_m<1.$ We have $$2ad_{m+1}<2ad_{m+1}+ad_{m+1}^2=x_{m+1}^2-a=$$ $$=\frac {1}{4}\left(x_m+\frac {a}{x_m}\right)^2-a=\frac {1}{4}\left(x_m-\frac {a}{x_m}\right)^2=$$ $$=\frac{(x_m^2-a)^2}{4x_m^2}=\frac {(2ad_m+ad_m^2)^2}{4a(1+d_m)^2}<\frac{(2ad_m+2ad_m^2)^2}{4a(1+d_m)^2}=ad_m^2,$$ $$\text {so we have }\quad 0<d_{m+1}<d_m^2<1.$$ By induction on $n,$ for all $n\geq m$ we have $0<d_{n+1}<d_n^2<1.$

Another way to do this: With $x_1>\sqrt a\;,$ let $x_n/\sqrt a\;=\coth T_n$ for $n\geq 1.$ Then when $n\geq 1$ we have $T_{n+1}=2T_n$, so $T_n=2^{n-1}T_1.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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