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…
Best Answer
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)$.