Halley's method

Halley's method is a numerical algorithm for solving the nonlinear equation {{nobr| {{math|f (x) {{=}} 0}} .}} In this case, the function {{mvar|f}} has to be a function of one real variable. The method consists of a sequence of iterations:

:$x\_\{n+1\}\; =\; x\_n\; -\; \backslash frac\{\backslash \; f(x\_n)\backslash \; f\text{'}(x\_n)\backslash \; \}\{\backslash \; \backslash left[\backslash \; f\text{'}(x\_n)\backslash \; \backslash right]^2\; -\; \backslash tfrac\{1\}\{2\}\backslash \; f(x\_n)\backslash \; f\text{'}\text{'}(x\_n)\backslash \; \}$

beginning with an initial guess {{math|x₀}}.{{cite journal |last1=Scavo|first1=T.R. |last2=Thoo |first2=J.B. |year=1995 |title=On the geometry of Halley's method |journal=American Mathematical Monthly |volume=102 |issue=5 |pages=417–426 |doi=10.2307/2975033 |jstor=2975033 }}

If {{mvar|f}} is a three times continuously differentiable function and {{mvar|a}} is a zero of {{mvar|f}} but not of its derivative, then, in a neighborhood of {{mvar|a}}, the iterates {{math|x_n}} satisfy:

:$|\; x\_\{n+1\}\; -\; a\; |\; \backslash le\; K\; \backslash cdot$

x_n - a

^3, \quad \text{ for some }\quad K > 0 ~.

This means that the iterates converge to the zero if the initial guess is sufficiently close, and that the convergence is cubic.{{cite journal |last=Alefeld |first=G. |year=1981 |title=On the convergence of Halley's method |jstor=2321760 |journal=American Mathematical Monthly |volume=88 |issue=7 |pages=530–536 |doi=10.2307/2321760 }}

The following alternative formulation shows the similarity between Halley's method and Newton's method. The ratio $\backslash \; f(x\_n)/f\text{'}(x\_n)\backslash$ only needs to be computed once, and this form is particularly useful when the other ratio, $\backslash \; f\text{'}\text{'}(x\_n)/f\text{'}(x\_n)\backslash \; ,$ can be reduced to a simpler form:

:$x\_\{n+1\}\backslash \; =\backslash \; x\_n\; -\backslash frac\{\; f(x\_n)\; \}\{\backslash \; f\text{'}(x\_n)\; -\; \backslash frac\{\; f(x\_n)\; \}\{\backslash \; f\text{'}(x\_n)\backslash \; \}\backslash frac\{\backslash \; f$(x_n)\ }{2}\ }\ =\ x_n - \frac{ f(x_n) }{\ f'(x_n)\ } \left[\ 1\ -\ \frac{1}{2} \cdot \frac{f(x_n)}{\ f'(x_n)\ } \cdot \frac{\ f(x_n)\ }{ f'(x_n) }\ \right]^{-1} ~.

When the second derivative, $\backslash \; f\text{'}\text{'}(x\_n)\backslash \; ,$ is very close to zero, the Halley's method iteration is almost the same as the Newton's method iteration.

When deriving Newton's method, a proof starts with the approximation

$$0\; =\; f(x\_\{n+1\})\; \backslash approx\; f(x\_n)\; +\; f\text{'}(x\_n)\; (x\_\{n+1\}\; -\; x\_n)$$

to compute

$$x\_\{n+1\}-x\_n\; =\; -\backslash frac\{f(x\_n)\}\{f\text{'}(x\_n)\}\backslash ,.$$

Similarly for Halley's method, a proof starts with

$$0\; =\; f(x\_\{n+1\})\; \backslash approx\; f(x\_n)\; +\; f\text{'}(x\_n)\; (x\_\{n+1\}\; -\; x\_n)\; +\; \backslash frac\{f\text{'}\text{'}(x\_n)\}2\; (x\_\{n+1\}\; -\; x\_n)^2\backslash ,.$$

For Halley's rational method, this is rearranged to give

$$x\_\{n+1\}-x\_n\; =\; -\backslash frac\{f(x\_n)\}\{f\text{'}(x\_n)\; +\; \backslash frac\{f\text{'}\text{'}(x\_n)\}2\; (x\_\{n+1\}-x\_n)\}\backslash ,$$

where {{math|x{{sub|n+1}} − x{{sub|n}}}} appears on both sides of the equation. Substituting in the Newtwon's method value for {{math|x{{sub|n+1}} − x{{sub|n}}}} into the right-hand side of this last formula gives the formula for Halley's method,

$$x\_\{n+1\}\; =\; x\_n\; -\; \backslash frac\{f(x\_n)\}\{f\text{'}(x\_n)\; -\; \backslash frac\{f\text{'}\text{'}(x\_n)f(x\_n)\}\{2f\text{'}(x\_n)\}\}\backslash ,.$$

Also see the motivation and proofs for the more general class of Householder's methods.

Suppose a is a root of f but not of its derivative. And suppose that the third derivative of f exists and is continuous in a neighborhood of a and {{math|x_n}} is in that neighborhood. Then Taylor's theorem implies:

:$0\; =\; f(a)\; =\; f(x\_n)\; +\; f\text{'}(x\_n)\; (a\; -\; x\_n)\; +\; \backslash frac\{f$(x_n)}{2} (a - x_n)^2 + \frac{f'(\xi)}{6} (a - x_n)^3

and also

:$0\; =\; f(a)\; =\; f(x\_n)\; +\; f\text{'}(x\_n)\; (a\; -\; x\_n)\; +\; \backslash frac\{f\text{'}\text{'}(\backslash eta)\}\{2\}\; (a\; -\; x\_n)^2,$

where ξ and η are numbers lying between a and {{math|x_n}}. Multiply the first equation by $2f\text{'}(x\_n)$ and subtract from it the second equation times $f\text{'}\text{'}(x\_n)(a\; -\; x\_n)$ to give:

:$\backslash begin\{align\}$

0 &= 2 f(x_n) f'(x_n) + 2 [f'(x_n)]^2 (a - x_n) + f'(x_n) f(x_n) (a - x_n)^2 + \frac{f'(x_n) f'(\xi)}{3} (a - x_n)^3 \\

&\qquad- f(x_n) f(x_n) (a - x_n) - f'(x_n) f(x_n) (a - x_n)^2 - \frac{f(x_n) f(\eta)}{2} (a - x_n)^3.

\end{align}

Canceling $f\text{'}(x\_n)\; f\text{'}\text{'}(x\_n)\; (a\; -\; x\_n)^2$ and re-organizing terms yields:

:$0\; =\; 2\; f(x\_n)\; f\text{'}(x\_n)\; +\; \backslash left(2\; [f\text{'}(x\_n)]^2\; -\; f(x\_n)\; f$(x_n) \right) (a - x_n) + \left(\frac{f'(x_n) f'(\xi)}{3} - \frac{f(x_n) f(\eta)}{2} \right) (a - x_n)^3.

Put the second term on the left side and divide through by

:$2\; [f\text{'}(x\_n)]^2\; -\; f(x\_n)\; f\text{'}\text{'}(x\_n)$

to get:

:$a\; -\; x\_n\; =\; \backslash frac\{-2f(x\_n)\; f\text{'}(x\_n)\}\{2[f\text{'}(x\_n)]^2\; -\; f(x\_n)\; f$(x_n)} - \frac{2f'(x_n) f'(\xi) - 3 f(x_n) f(\eta)}{6(2 [f'(x_n)]^2 - f(x_n) f''(x_n))} (a - x_n)^3.

Thus:

:$a\; -\; x\_\{n+1\}\; =\; -\; \backslash frac\{2\; f\text{'}(x\_n)\; f$'(\xi) - 3 f(x_n) f(\eta)}{12[f'(x_n)]^2 - 6 f(x_n) f(x_n)} (a - x_n)^3.

The limit of the coefficient on the right side as {{math|x_n → a}} is:

:$-\backslash frac\{2\; f\text{'}(a)\; f$'(a) - 3 f(a) f(a)}{12 [f'(a)]^2 - 6 f(a) f(a)}.

If we take K to be a little larger than the absolute value of this, we can take absolute values of both sides of the formula and replace the absolute value of coefficient by its upper bound near a to get:

:$|a\; -\; x\_\{n+1\}|\; \backslash leq\; K\; |a\; -\; x\_n|^3$

which is what was to be proved.

To summarize,

:$\backslash Delta\; x\_\{i+1\}\; =\backslash frac\{3(f$)^2 - 2f' f'}{12(f')^2} (\Delta x_i)^3 + O[\Delta x_i]^4, \qquad \Delta x_i \triangleq x_i - a.{{Cite journal|last1=Proinov|first1=Petko D.|last2=Ivanov|first2=Stoil I.|year=2015|title=On the convergence of Halley's method for simultaneous computation of polynomial zeros|journal=J. Numer. Math.|volume=23|issue=4|pages=379–394|doi=10.1515/jnma-2015-0026|s2cid=10356202 }}

Halley actually developed two third-order root-finding methods. The above, using only a division, is referred to as Halley's rational method. A second, "irrational" method uses a square root as well.{{cite journal

|first=Harry |last=Bateman |author-link=Harry Bateman

|title=Halley's methods for solving equations

|journal=The American Mathematical Monthly

|volume=45 |issue=1 |date=January 1938 |pages=11–17

|doi=10.2307/2303467

|jstor=2303467 }}{{cite journal

|title=Methodus nova accurata & facilis inveniendi radices æqnationum quarumcumque generaliter, sine praviæ reductione

|first=Edmond |last=Halley |author-link=Edmond Halley

|journal=Philosophical Transactions of the Royal Society

|volume=18 |issue=210 |date=May 1694 |pages=136–148

|lang=la

|doi=10.1098/rstl.1694.0029 |doi-access=free

}} An English translation was published as {{cite book

|chapter=A new, exact, and easy Method of finding the Roots of any Equations generally, and that without any previous Reduction

|first=Edmond |last=Halley |author-link=Edmond Halley

|title=The Philosophical Transactions of the Royal Society of London, from their commencement, in 1665, to the year 1800

|editor1=C. Hutton |editor2=G. Shaw |editor3=R. Pearson

|volume=III from 1683 to 1694

|year=1809 |orig-date=May 1694 |pages=640–649

|url=https://archive.org/details/s3id13654280

}}{{cite tech report

|title=A correctly rounded binary64 cube root

|first=Robin |last=Leroy

|date=2021-06-21

|url=https://raw.githubusercontent.com/mockingbirdnest/Principia/master/documentation/cbrt.pdf?raw=true

}}

It starts with

:$f(x\_\{n+1\})\; \backslash approx\; f(x\_n)\; +\; f\text{'}(x\_n)(x\_\{n+1\}\; -\; x\_\{n\})\; +\; \backslash frac\{f\text{'}\text{'}(x\_n)\}\{2\}(x\_\{n+1\}\; -\; x\_\{n\})^2$

and solves $f(x\_\{n+1\})\; \backslash approx\; 0$ for the value $(x\_\{n+1\}\; -\; x\_\{n\})$ using one of two forms of the quadratic formula. The quadratic formula solution either has the radical in the numerator:

:$x\_\{n+1\}\; =\; x\_n\; -\; \backslash frac\{f\text{'}(x\_n)\; -\; \backslash operatorname\{sign\}(f\text{'}(x\_n))\backslash sqrt\{[f\text{'}(x\_n)]^2\; -\; 2f(x\_n)f$(x_n)}}{f(x_n)} = x_n - \frac{f'(x_n) \left(1 - \sqrt{1 - \frac{2f(x_n)f(x_n)}{f'(x_n)^2}}\right)}{f(x_n)}

or it has the radical in the denominator, yielding an update step that often gives better results:

:$x\_\{n+1\}\; =\; x\_n\; -\; \backslash frac\{2f(x\_n)\}\{f\text{'}(x\_n)\; +\; \backslash operatorname\{sign\}(f\text{'}(x\_n))\backslash sqrt\{[f\text{'}(x\_n)]^2\; -\; 2f(x\_n)f$(x_n)}} = x_n - \frac{2f(x_n)}{f'(x_n) \left( 1 + \sqrt{1 - \frac{2f(x_n)f(x_n)}{f'(x_n)^2}}\right)}

This iteration was "deservedly preferred" to the rational method by Halley{{r|Halley1694}} on the grounds that the denominator is smaller, making the division easier. A second advantage is that it tends to have about half of the error of the rational method, a benefit which multiplies as it is iterated. On a computer, it would appear to be slower as it has two slow operations (division and square root) instead of one, but on modern computers the reciprocal of the denominator can be computed at the same time as the square root via instruction pipelining, so the latency of each iteration differs very little.{{r|eggrobin|p=24}}

The formulation with the radical in the denominator reduces to Halley's rational method under the approximation that {{tmath|\sqrt{1-z} \approx 1 - z/2}}.

Muller's method could be considered as modification of this method. So, this method can be used to find the complex roots.

• {{MathWorld|urlname=HalleysMethod|title=Halley’s method}}
• [http://numbers.computation.free.fr/Constants/Algorithms/newton.html Newton's method and high order iterations], Pascal Sebah and Xavier Gourdon, 2001 (the site has a link to a Postscript version for better formula display)

{{Root-finding algorithms}}

{{DEFAULTSORT:Halley's Method}}

Category:Root-finding algorithms