Source: Rudin's "Principles of Mathematical Analysis" 3.17(d)
Problem: Compare the rapidity of convergence of the process
$$x_{n+1}=\frac{\alpha+x_n}{1+x_n}=x_n+\frac{\alpha-x_n^2}{1+x_n}$$
with $\alpha>1$ and $x_1>\sqrt{\alpha}$ with the process
$$x_{n+1}=\frac{1}{2}\left(x_n+\frac{\alpha}{x_n}\right).$$
In 16b, Rudin lets $\epsilon_n = x_n-\sqrt{\alpha}$ and we show that with $\beta=2\sqrt{\alpha}$,
$$\epsilon_{n+1}<\beta\left(\frac{\epsilon_1}{\beta}\right)^{2^n}.$$
My work:
For finding the rate of convergence in 16, we must find the $$\alpha\geq 1: \lim\limits_{n\rightarrow\infty} \frac{|\epsilon_{n+1}|}{|\epsilon_n|^\alpha}<\infty.$$ After 16b, we can deduce that with $\alpha=2$, the limit converges and so the rate of convergence is quadratic. For the latter, we just go through the same process as in 16b,c. I think $\beta=\frac{(\sqrt{\alpha}-1)x_1-1+\sqrt{\alpha})}{2x_1+1+\alpha}$ gives us a similar inequality as in 16b. Then from here,
$$\lim\limits_{n\rightarrow\infty}\frac{\left|\beta\left(\frac{\epsilon_1}{\beta}\right)^n\right|}{\left|\beta\left(\frac{\epsilon_1}{\beta}\right)^{n-1}\right|^\alpha}<\infty\iff \lim\limits_{n\rightarrow\infty}n-(n-1)\alpha<\infty\iff \alpha=1.$$
Hence it's rate of convergence is linear at best.
My Question: I was hoping to get some feedback on if my work is sufficient/good.
Best Answer
For the first one,
$\begin{array}\\ x_{n+1} &=\dfrac{a+x_n}{1+x_n}\\ \text{so}\\ x_{n+1}-\sqrt{a} &=\dfrac{a+x_n}{1+x_n}-\sqrt{a}\\ &=\dfrac{a+x_n-\sqrt{a}(1+x_n)}{1+x_n}\\ &=\dfrac{a+x_n-\sqrt{a}-\sqrt{a}x_n}{1+x_n}\\ &=\dfrac{a-\sqrt{a}+x_n-\sqrt{a}x_n}{1+x_n}\\ &=\dfrac{\sqrt{a}(\sqrt{a}-1)-x_n(\sqrt{a}-1)}{1+x_n}\\ &=\dfrac{(\sqrt{a}-1)(\sqrt{a}-x_n)}{1+x_n}\\ \text{so}\\ \dfrac{x_{n+1}-\sqrt{a}}{\sqrt{a}-x_n} &=\dfrac{\sqrt{a}-1}{1+x_n}\\ \text{or}\\ \dfrac{x_{n+1}-\sqrt{a}}{x_n-\sqrt{a}} &=\dfrac{1-\sqrt{a}}{1+x_n}\\ \end{array} $
so the convergence is linear.
For Newton,
$\begin{array}\\ x_{n+1} &=\dfrac{1}{2}\left(x_n+\dfrac{a}{x_n}\right)\\ \text{so}\\ x_{n+1}-\sqrt{a} &=\dfrac{1}{2}\left(x_n+\dfrac{a}{x_n}\right)-\sqrt{a}\\ &=\dfrac{1}{2}\left(x_n-2\sqrt{a}+\dfrac{a}{x_n}\right)\\ &=\dfrac{1}{2}\left(\dfrac{x_n^2-2x_n\sqrt{a}+a}{x_n}\right)\\ &=\dfrac{1}{2}\left(\dfrac{(x_n-\sqrt{a})^2}{x_n}\right)\\ \end{array} $
so the convergence is quadratic.