We define the recurrent sequences $(x_n)$ and $(z_n)$ : $$ x_{n+1} = z_{n+1} - \frac{f(z_{n+1})}{f'(x_n)} $$ $$ z_{n+1} = x_{n} - \frac{f(x_{n})}{f'(x_n)} $$
Show that the order of convergence of $(x_n)$ to the root $\alpha$ of the equation $f(x) = 0$ is at least $3$, where $f \in C^3[a,b]. $
To prove this I must show that there is a real number $c$ such that for every positive $n$ : $$ |x_{n+1} - \alpha| \leq c|x_n - \alpha|^3 $$
I have tried :
$$ |\alpha - x_{n+1} | \leq |\alpha - x_{n+1} | + |x_{n+1} - x_{n} | = |\alpha - x_{n+1} | - \frac{f(x_n) -f(z_{n+1})}{f'(x_n)} $$ How to approach this kind of problem? I don't know how to get to the third power right there.
The first step is a Newton step, so that $$ z_{n+1}-r\approx \frac{f''(r)}{f'(r)}(x_n-r)^2. $$ The second step is a simplified Newton step, inserting expansions at the root $r$ gives \begin{align} x_{n+1}-r&=z_{n+1}-r-\frac{f'(r)(z_{n+1}-r)+\frac12f''(r)(z_{n+1}-r)^2+...}{f'(r)+f''(r)(x_n-r)+...} \\ &\approx \frac{f''(r)(z_{n+1}-r)(x_n-z_{n+1})}{f'(r)}\approx\frac{f''(r)^2(x_n-r)^3}{f'(r)^2} \end{align} so that you get indeed an order 3 reduction in the error in one combined step using 3 (or more realistically $2+2=4$) function evaluations (counting the derivative evaluation as 1 or 2 additional function evaluations). This is an order of $\sqrt[3]3=1.442$ or $\sqrt[4]3=1.3161$ per function evaluation compared to $\sqrt[2]2=1.414$ or $\sqrt[3]2=1.259$ for the Newton method.