Convergence of Halley's method at a Root $x = p$ of $f(x)$

223 Views Asked by At

Define an iterative method for finding the roots of a function $f(x)$ by

$$p_{n+1} = p_n − \frac{f(p_n)f'(p_n)}{f'(p_n)^2 - \frac{1}{2}f(p_n)f''(p_n)}$$

where $f(x)$ is at least twice differentiable.

I would like to show that, if f(x) has a simple root at $x = p$ and $f$ is sufficiently differentiable, then the method is convergent for a starting value sufficiently close to p, but I'm not sure how to begin. I would appreciate some indication on how to begin

1

There are 1 best solutions below

0
On BEST ANSWER

Consider the example $f(x)=c_1x+c_2x^2+c_3x^3+...$ and use Halley's method to "find" the root $x=0$, that is, explore the progress of the method close to $x=0$.

\begin{align} H(x)&=x-\frac{f(x)f'(x)}{f'(x)^2-\frac12f(x)f''(x)} \\ &=x-\frac{x(c_1+c_2x+c_3x^2+...)(c_1+2c_2x+3c_3x^2+...)}{(c_1+2c_2x+3c_3x^2+...)^2-\frac12x(c_1+c_2x+c_3x^2+...)(2c_2+6c_3x+...)} \\ &=x-x\frac{c_1^2+3c_1c_2x+(2c_2^2+4c_1c_3)x^2+...}{c_1^2+3c_1c_2x+(3c_2^2+3c_1c_3)x^2+...} \\ &= \frac{(c_2^2-c_1c_3)x^3+...}{c_1^2+3c_1c_2x+...} \end{align} This immediately tells that the method is third order. One gets convergence like $|Cx_{n+1}|\approx |Cx_n|^3$ if the iteration is started within some interval that is close to the interval of the condition $|Cx_0|<1$ where $$ C^2=\left|\frac{c_2^2-c_1c_3}{c_1^2}\right| =\left|\frac{3f''(0)^2-2f'(0)f'''(0)}{12f'(0)^2}\right|. $$ With some attention to the details one can also read off if the convergence is monotone or alternating around the root.