Order of convergence of a two-step iteration method

Solution 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}$.