Order of convergence of this (fixed point) iterative method

This is a a previously asked question in my university.

Find the order of convergence for the iterative method $$x_{n+1}=g(x_n)$$ to solve $$f(x)=0$$ where, $$g(x)=x-\frac{f(x)}{f'(x)}-\frac{f''(x)}{2f'(x)}\left(\frac{f(x)}{f'(x)}\right)^2$$

In general, I know how to determine the rate of convergence of the fixed point iteration method.

Given a function $$\phi(x)$$, we attempt to find a fixed point $$x=\alpha$$ at which $$\phi(\alpha)=\alpha$$. We begin with an initial guess $$x_0$$ and generate the sequence $$x_{k+1}=\phi(x_k)$$ iteratively.

Using Lagrange's mean value theorem, it can be shown that we have a sufficient criterion for convergence of this sequence: $$|\phi'(x)|<1$$ for all $$x$$ lying between $$\alpha$$ and $$x_0$$.

Let $$\varepsilon_k= \alpha-x_k$$ be the error at the $$k$$-th iteration.

By Taylor-series expansion at $$\alpha$$, we have: \begin{align}\phi(x_k)&=\phi(\varepsilon_k + \alpha)\\ &=\underbrace{\phi(\alpha)}_{=\alpha}+\frac{\varepsilon_k\phi'(\alpha)}{1!}+\frac{\varepsilon_k^2\phi''(\alpha)}{2!}+\ldots\tag{1}\end{align}

Also, $$\phi(x_k)=x_{k+1}=\varepsilon_{k+1} +\alpha\tag{2}$$.

We assume that each $$|\varepsilon_k|$$ is much smaller than $$1$$. Thus, by setting (1) and (2) equal, we have:

$$\varepsilon_{k+1}=\frac{\varepsilon_k^n}{n!}\phi^{(n)}(\alpha)+O(\varepsilon_k^{n+1})$$

where $$n$$ is the least positive integer such that the $$n$$-th derivative $$\phi^{(n)}(x)$$ is non-zero at the point $$x=\alpha$$. Hence, $$\lim_{k\to\infty}\left| \frac{\varepsilon_{k+1}}{\varepsilon_k^n}\right|=\left|\frac{\phi^{(n)}(\alpha)}{n!}\right|$$

Thus, by definition, the order of convergence is $$n$$ i.e., the least positive integer for which $$\phi^{(n)}(\alpha)\neq 0$$.

In the particular question, $$g$$ is the iterative function, if I let $$\alpha$$ to be the actual solution, I need to find the least $$n\in\mathbb Z^+$$ such that $$g^{(n)}(\alpha)\neq 0$$. I am not sure how to approach the problem, the given function looks too complicated to differentiate.

I can't use any computational aid. I need to compute $$g'(\alpha)$$, $$g''(\alpha)$$, $$g'''(\alpha)$$ and so on until I get a non-zero value. All I know is that $$g(\alpha)=\alpha$$ and $$f(\alpha)=0$$.

I am not aware if there's any other approach to find the order of convergence...

• This is the Euler-Chebyshev method, a variant of the Halley method, both of 3rd order. It is perhaps easier to argue via $f(x_{n+1})$, as at simple roots that is approximately $f'(\alpha)(x_{n+1}-\alpha)$. math.stackexchange.com/questions/5746/…, math.stackexchange.com/questions/2709283/… Commented Jan 3 at 11:57
• @LutzLehmann I looked up Halley's method on Wikipedia but I fail to see how it's related to the problem. Commented Jan 3 at 12:20
• Your iteration is $x-s(1+bs)$, $s=f(x)/f'(x)$ small, Halley's iteration is $x-s(1-bs)^{-1}$, which has a difference of $O(s^3)$, that is, modifying the third-order residual by another third-order term. Commented Jan 3 at 12:27

You can compute derivatives of products systematically using the logarithmic derivative. Thus you get $$g'(x)=1-f'(x)^{-1}f(x)\left(-\frac{f''(x)}{f'(x)}+\frac{f'(x)}{f(x)}\right) -\frac12f''(x)f'(x)^{-3}f(x)^2\left(\frac{f'''(x)}{f''(x)}-3\frac{f''(x)}{f'(x)}+2\frac{f'(x)}{f(x)}\right) \\=-\frac12f'''(x)f'(x)^{-3}f(x)^2+\frac32f''(x)^2f'(x)^{-4}f(x)^2$$ Now one could continue or directly read off $$g'(x)=O(f(x)^2)=O((x-\alpha)^2)$$.
• Please fix the missing dollar sign... Does $g'(x)=O(f(x)^2)$ imply $g''(x)=O(f(x))$? Can you explain a bit more? Commented Jan 3 at 12:43
• Yes, as $g'(x)=C(x)f(x)^2$, you get $g''(x)=C'(x)f(x)^2+2C(x)f'(x)f(x)=O(f(x))$. But for the task one is interested in the other direction, that this implies $g(x)=O((x-\alpha)^3)$. Commented Jan 3 at 13:11
• I got it now... $\alpha$ is a triple root of the equation $g(x)=x$ because we already found that it is a double root of the equation $g'(\alpha)=\alpha$ and it was at least single root of $g(x)=x$. Is that right? Commented Jan 3 at 13:15
• I wrote wrong, it has to be $g(x)-\alpha=O((x-\alpha)^3)$. Or $f(g(x))=O(f(x)^3)$. For the fixed-point version you get $g(x)-x=\alpha-x+O((x-\alpha)^3)$, which is not what you describe. Commented Jan 3 at 13:47