2

Chebyshev method $$ (1)\space\space p_{n+1}=p_n-\frac{f(p_n)}{f'(p_n)}-\frac{1}{2}\frac{[f(p_n)]^2f''(p_n)}{[f'(p_n)]^3} $$ Halley method $$ (2)\space\space p_{n+1}=p_n-\frac{f(p_n)}{f'(p_n)-\frac{f(p_n)f''(p_n)}{2f'(p_n)}} $$

First we know that Newton method is $$ (3)\space\space p_{n+1}=p_n-\frac{f(p_n)}{f'(p_n)}\to{p_{n+1}-p_n=\frac{-f(p_n)}{f'(p_n)}} $$ And the second order Taylor series expanded about $p_n$ says $$ (4)\space\space f(p_{n+1})=f(p_n)+f'(p_n)(p_{n+1}-p_n)+\frac{1}{2}f''(p_n)(p_{n+1}-p_n)^2=0 $$ We write $(4)$ as $$ (5)\space\space p_{n+1}=p_n-\frac{f(p_n)}{f'(p_n)}-\frac{1}{2}\frac{f''(p_n)}{f'(p_n)}(p_{n+1}-p_n)^2 $$ Substituting the value of $p_{n+1}–p_n$ from $(3)$ by $\frac{-f(p_n)}{f'(p_n)}$ on the right side of $(5)$ we get Chebyshev method. Also we can write $(4)$ as $$ (6)\space\space p_{n+1}=p_n-\frac{f(p_n)}{f'(p_n)+\frac{1}{2}f''(p_n)(p_{n+1}-p_n)} $$ Again we use $(3)$ to obtain Halley method. Is there any difference or I am so stupid?!

Dante
  • 1,908
  • I think because both of them are based on fixed point iteration scheme, and every root-finding problem can be transformed into any number of fixed point problems with different behavior, then they are different. But I am not sure. – Dante Sep 29 '13 at 05:54

1 Answers1

2

Halley's method and Chebyshev's method are both of the same order of accuracy. Chebyshev's method is in the form of a Taylor expansion of the inverse function, and Halley's method is in the form of a rational approximation known as the Padé approximant.

Define $g:= -f/f'$ and $h:= f''/f'$. Remember that $g$ is linear in the residual error.

Then Chebyshev is $$ p_{n+1}-p_n = g\cdot(1-g\cdot h/2) = g/(1+g\cdot h/2) + O(g^3) $$ and Halley is $$ p_{n+1}-p_n = g/(1+g\cdot h/2) = g\cdot(1-g\cdot h/2) + O(g^3) $$

In other words, within their respective order of accuracy, they are the same (and you are not stupid). One is a purely polynomial approximation of order 2 [of the inverse function], and the other is a rational approximation of order (1,1) [of the inverse function]. Because they are of the same order and it is thus not easy to choose which is to be preferred, people have even blended them into what is called the "Chebyshev-Halley" method, see, for instance, M.A. Hernandez and M.A. Salanova, A family of Chebyshev-Halley type methods, Internat. J. Comput. Math. 47(1993), 59-63.

I recommend reading up on rational function approximation, or just the chapter on Padé approximants in Numerical Recipes in C or similar (which contains some delectable phrases).

If it's any comfort, even experienced practitioners in applied numerical analysis get confused about this.

user107773
  • 21