0
$\begingroup$

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...

$\endgroup$
3
  • $\begingroup$ 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/… $\endgroup$ Commented Jan 3 at 11:57
  • $\begingroup$ @LutzLehmann I looked up Halley's method on Wikipedia but I fail to see how it's related to the problem. $\endgroup$ Commented Jan 3 at 12:20
  • $\begingroup$ 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. $\endgroup$ Commented Jan 3 at 12:27

1 Answer 1

1
$\begingroup$

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)$.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Commented Jan 3 at 12:43
  • $\begingroup$ 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)$. $\endgroup$ Commented Jan 3 at 13:11
  • $\begingroup$ 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? $\endgroup$ Commented Jan 3 at 13:15
  • $\begingroup$ 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. $\endgroup$ Commented Jan 3 at 13:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .