Proof: $x_{n+1} = \frac{x_n(x_n^2 + 3R)}{3x_n^2 + R}$ converges cubically to $\sqrt{R}$ I have the following problem:
Prove that iterative method:$$x_{n+1} = \frac{x_n(x_n^2 + 3R)}{3x_n^2 + R}$$ converges cubically to $\sqrt{R}$.
So, as I understand, I have to show two things:


*

*the method converges to $\sqrt{R}$

*$\lim_{n\rightarrow\infty} |\frac{x_{n+1} - \sqrt{R}}{(x_n - \sqrt{R})^3}| > 0$


but I have no idea how to do it.
 A: There is a general theorem about function iteration:

If $a$ is a fixed point of $\phi$ and $\phi^{(k)}(a)=0$ for $k=1,\dots,q-1$ but $\phi^{(q)}(a)\ne0$, then the iteration of $\phi$ converges to $a$ with order $q$ if it starts sufficiently close to $a$.

Cubic convergence for your sequence follows from this theorem because the Taylor series of $\phi(x)=\dfrac{x(x^2 + 3R)}{3x^2 + R}$ at $x=\sqrt R$ is 
$
\sqrt R + \dfrac{(x-\sqrt R)^3}{4 R} + \cdots
$
The same explanation works for the quadratic convergence of Newton's method for finding $\sqrt R$.
A: [1]. Convergence.The case $x_1\ne 0=R$ is easy, as $x_{n+1}=\frac {x_n}{3}.$ The case $x_1=\sqrt R\ne 0$ is also easy as $x_n=\sqrt R$ for all $n$.  For $R\ne 0$ and $0<x_1\ne \sqrt R,$ let $x_n^2=R+e_n.$ By direct calculation we have $$(\bullet ) \quad e_{n+1}=\frac {e_n^3}{(3x_n^2+R)^2}=\frac {e_n^3}{(4R+3e_n)^2}.$$ (i). $x_n>\sqrt R \implies e_n>0 \implies  0<\frac {e_{n+1}}{e_n}=\frac {e_n^2}{(4R+3e_n)^2}<\frac {e_n^2}{(3e_n)^2}=\frac {1}{9}.$ So if $x_1>\sqrt R$ then $e_n$ decreases to $0$ and $x_n$ converges to $\sqrt R.$
(ii). If $x_n<\sqrt R$ and $x_n>0$ then  $-R<e_n<0$ so $0<e_{n+1}/e_n<R^2/(4R-3R)^2=1. $   So if $0<x_1<\sqrt R$ then $(x_n)_n$ is an increasing sequence bounded above by $\sqrt R,$ so it has a  positive limit $X\leq \sqrt R.$ If $X<\sqrt R$ then $e_n$ converges to a negative limit $E$ with $|E|= R-X^2<R.$  But then $$ 0> E=\lim_{n\to \infty}e_{n+1}=\lim_{n\to \infty}\frac {e_n^3}{(4R+3e_n)^2}=\frac {E^3}{(4R+E)^2}$$ which implies $E=-R,$ which contadicts $|E|<R.$ Therefore $E=0$ and $X=\sqrt R$ and  $x_n$ converges to $\sqrt R.$
[2]. Rate of convergence. For $0<x_1\ne \sqrt R:\; $ Let $x_n=\sqrt R+d_n.$ We have $e_n=x_n^2-R=(x_n-\sqrt R)(x_n+\sqrt R)=d_n(d_n+2\sqrt R).$ So by $(\bullet)$ we have $$\frac {1}{(4R+3e_n)^2}=\frac {e_{n+1}}{e_n^3}=\frac {d_{n+1}}{d_n^3} \cdot \frac { d_{n+1}+2\sqrt R}{(d_n+2\sqrt R)^3}.$$ Compare the far left and far right terms above .Since $d_n\to 0$ and $e_n\to 0$ as $n\to \infty,$ and $ R\ne 0,$ we have $\lim_{n\to \infty}\frac {d_{n+1}}{d_n^3}=\frac {1}{4R}.$             
