Determine the rate of convergence

If a recursion of the form $x_{n+1} = g(x_n)$ is convergent to $z$ (with regular enough $g$) and $$ g'(z)=\cdots = g^{(p-1)}(z) =0, g^{(p)}(z) \ne 0 $$

then $(x_n)$ converges with order $p$.

In this case, since the only possible values for $z$ are $\pm 4$, and noting that $g'(\pm 4)=0, g''(\mp 4) \ne 0$, we conclude that when $x_0$ is chosen in a way that $x_n$ converges, the convergence is quadratic.

In this case, it is possible to establish that when $x_0>0$ the sequence converges quadratically to 4 and, when $x_0<0$, the sequence converges quadratically to $-4$.

Convergence when $x_0>0$.

In this case, since $g(x_0) > 4$ when $x_0 < 4$, we can assume without loss of generality that $x_0 \ge 4$. Applying the fixed point theorem to $g$ on the set $[4, +\infty[$, we get convergence for any $x_0 >0$.

First of all, let us assume without loss of generality that $x_0>0$ (implying that all further $x_n$ are themselves $>0$). Indeed if $x_0<0$, we have completely symmetrical results.

In fact, this sequence can be "casted" into a Newton's method convergence:

$$x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}=x_n-\dfrac{x_n^2-16}{2x_n}$$

with $f$ defined by $f(x)=x^2-16$ (roots of $f(x)=0$ are precisely $\pm 4$).

One of the essential properties of Newton's method is that it has a quadratic convergence. It means that

$$e_{n+1}=Ke_n^2 \ \ \text{where} \ \ e_n=|x_{n+1}-4| \ \ \text{and} \ \ K=\dfrac{f''(L)}{2f'(L)}=\dfrac18.$$

(where $L$ is the limit, with $L=4$ here).

for a certain $K$, which gives a fantastic speed of convergence (under the condition to be in a good vicinity of the root).

Therefore, the computation of $\lim_{n \to \infty} \frac{e_{n+1}}{e_{n}}$ i.e.

$$\lim_{n \to \infty} \frac{|x_{n+1}-4|}{{|x_{n}-4|}}$$

will give $0$ but gives no information, plainly because the convergence isn't linear as is the case for example for a fixed point method.