Order of convergence of a two-step iteration method

Question

Find the order of the iteration is given by

$$y_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \quad x_{n+1} = y_{n+1} - \frac{f(y_{n+1})}{f'(x_n)}$$

Assuming $f(r) = 0$, $f'(r) \neq 0$ and the initial guess is close to r.

I know the iteration is a third order method because if I let $Y(x) = x - \frac{f(x)}{f'(x)}$ and $I(x) = Y(x) - \frac{f(Y(x))}{f'(x)}$. We end up with $$\frac{dI(x)}{dx}|_r = 0$$ $$\frac{d^2I(x)}{dx^2}|_r = 0$$ $$\frac{d^3I(x)}{dx^3}|_r \neq 0$$

This way however is very messy when evaluating all of the derivatives. I was wondering if there is another way to prove that the above methods order of convergence?

Answer 1

Let $L$ be a Lipschitz constant of $f'$ on the domain under consideration. Then we know that $$ |f(x+v)-f(x)-f'(x)v|\le\int_0^1|f'(x+sv)-f'(x)|\,|v|\,ds\le L\,|v|\,\int_0^1|sv|\,ds=\frac{L}2|v|^2, $$ so that especially $$ |f(y_{n+1})|\le\frac{L}2\frac{|f(x_n)|^2}{|f'(x_n)|^2} $$ Further, $$ f(x_{n+1})=f(y_{n+1})-f'(y_{n+1})\frac{f(y_{n+1})}{f'(x_n)}+R~~\text{with}~~ |R|\le\frac{L}2\frac{|f(y_{n+1})|^2}{|f'(x_n)|^2} $$ so that $$ |f(x_{n+1})| \le L\,|x_{n}-y_{n+1}|\,\frac{|f(y_{n+1})|}{|f'(x_n)|}+\frac{L^3}{8}\frac{|f(x_{n+1})|^4}{|f'(x_n)|^6} \le \frac{L^2}{2}\frac{|f(x_n)|^3}{|f'(x_n)|^4}+\frac{L^3}{8}\frac{|f(x_{n+1})|^4}{|f'(x_n)|^6} $$ As the function value stands as proxy for the distance to the root, this shows the third order convergence.

---

Note however that in terms of effort, or the Ostrowski index, only for polynomial $f$ you get an order convergence of $\sqrt[3]{3}=1.442$ per function or derivative evaluation. In the non-polynomial case this is only $\sqrt[4]3=1.316$ as one derivative costs as much as 2 function evaluations.

To compare, the Newton method has $\sqrt2=1.414$ resp. $\sqrt[3]2=1.260$ and the secant method $\frac{1+\sqrt5}2=1.618$ (if it converges).

So this method is slightly better than the Newton method. To put it in integer terms, in the polynomial case within the effort of $6$ function evaluations one can perform

• 3 Newton steps with error reduction from $\epsilon$ to $ϵ^8$ or
• 2 cycles of this two-step method with an error reduction to $ϵ^9$.

In the non-polynomial case, in the time of $12$ evaluations of $f$ one can perform

• $4$ Newton steps to $ϵ^{16}$ or
• $3$ two-step cycles to $ϵ^{27}$.