Talk:Halley's method

This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Low‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Low This article has been rated as Low-priority on the project's priority scale.

The article declares that "The function ƒ has to be a function of one real variable". Where does the method use the condition, that the imaginary part of the argument is zero? dima (talk) 08:56, 15 January 2009 (UTC)Reply

A real function does not have some "imaginary part" that could be set to zero. That is something that could only be said about complex functions. But you are right that one can generalsize Halley's method to complex functions and even to multidimensional real and complex functions. All operations are purely arithmetic. The real version is simply the most popular one. One could even say that "real function" is just a shorthand for "(real-valued) scalar function in one (real) variable", that is, denoting the one-dimensional nature of the function.--LutzL (talk) 10:23, 15 January 2009 (UTC)Reply

I'm intrigued by the statement about the multidimensional version and wondering how that would actually look like - I can guess as much that there would be a third order tensor (of all third derivatives) involved, but the precise details of notation and computation elude me for the moment. Could anyone provide a specific link or even better the appropriate formula? --Summsumm2 (talk) 10:44, 29 June 2009 (UTC)Reply

See for instance the german version. The derivation goes via the hyperbolic approximation of the function, but as you observed, there are tensors and noncommutativity involved.

1. perform a Newton step:

   solve ${\displaystyle F'(x_{k})t_{k}=-F(x_{k})}$

2. compute the second order correction of the Newton step:

   solve ${\displaystyle \left(F'(x_{k})+{\tfrac {1}{2}}F''(x_{k})(t_{k},\cdot )\right)s_{k}=-F(x_{k})}$

   where ${\displaystyle \,F''(x_{k})}$ is a symmetric bilinear vector-valued form that gets evaluated in the first argument only.

3. Set ${\displaystyle x_{k+1}=x_{k}+s_{k}}$ as the next iterate.

Or in one formula, where one can see the connection to the one-dimensional case

${\displaystyle x_{k+1}=x_{k}-\left(F'(x_{k})-{\tfrac {1}{2}}F''(x_{k})\left(F'(x_{k})^{-1}F(x_{k}),\cdot \right)\right)^{-1}F(x_{k})}$

--LutzL (talk) 11:30, 29 June 2009 (UTC)Reply

As I see, there is no mention of the hyperbolic approximation in the article. Up to now I believed I first read here about it. Instead of the linear approximation as in the Newtons's method or the quadratic approximation as in Halley's original approach, one may try to find an approximation of the type

${\displaystyle f(x+h)\approx {\frac {a+bh}{1+ch}}+O(h^{3})}$

Multiplying out the denominator and comparing the lower order coefficients for the Taylor expansions, one arrives at f(x)=a, f '(x)+cf(x)=b and f "(x)+2cf '(x)=0, from where one obtains the next Halley-iterate as x+h=x-a/b. Similarly, from the ansatz

${\displaystyle F(x+h)=(I+C(h))^{-1}(A+Bh)+O(h^{3})}$

where C(h) is a matrix with components that are linear in h, one can derive the multidimensional formula.--LutzL (talk) 11:56, 29 June 2009 (UTC)Reply

Thanks! Makes some sense to me. --Summsumm2 (talk) 21:43, 30 June 2009 (UTC)Reply

I don't get it. When I solve the equation you provided for F(x+h)==0 I get A=-B*h which is Newton's method as far as I understand. I'm also curious in any case how to derive the multidimensional case. Or could somebody point me to the necessary mathematics for this? Can Householder's methods be used for even higher order than two for the multidimensional case? Does this always mean, one more matrix factorization/inversion for every order?

2601:647:4100:E061:E1FE:EF00:4CFA:D051 (talk) 23:46, 11 December 2016 (UTC)Reply

Please add the multidimensional formula you provided into the general part of this wiki page. I need to look it up all the time again, since I cannot derive it (yet hopefully).2601:647:4100:E061:E1FE:EF00:4CFA:D051 (talk) —Preceding undated comment added 23:56, 11 December 2016 (UTC)Reply

Thank you for the start on Halley's irrational method. I'd like to see more and am hoping people have the knowledge and citations: How is it derived? (For example, one way to derive the rational method is to apply Newton's method to $f(x)/{\sqrt {f'(x)}}$; does something similar work for the irrational method?) When is it the case that the irrational method has about half the error of the rational method? Does the irrational method generalize from cubic convergences to higher-order convergence in the way that the rational method generalizes to Householder's method(s)? Does the irrational method generalize to functions ${\displaystyle f(\mathbf {x} )}$ where ${\displaystyle \mathbf {x} }$ is a vector, similar to the way that the rational method does? By "irrational method" we appear to mean what is sometimes called the "quadratic irrational method"; can we also say something about the "cubic irrational method" and other higher-order irrational methods? —Quantling (talk | contribs) 14:55, 28 August 2024 (UTC)Reply

I have since edited the page, so this is mostly moot. —Quantling (talk | contribs) 20:55, 8 July 2025 (UTC)Reply

I have derived this mistakenly myself, when I was looking for a higher order method to Newton's method. So for Newton's method, at a point ${\displaystyle x_{n}}$ we guess the ${\displaystyle x_{n+1}}$ as the solution of the tangent that passes from ${\displaystyle (x_{n},f(x_{n}))}$. For this irrational method, it is the closer root of the parabola tangent (and same second derivative) at ${\displaystyle (x_{n},f(x_{n}))}$. Panthades (talk) 13:37, 20 August 2025 (UTC)Reply

not only incomplete and unclear but wrong, that's not how you get halley's method Whateverowo (talk) 23:00, 10 April 2025 (UTC)Reply

here's the actual derivation

\documentclass{article}

\usepackage{amsmath}

\usepackage{graphicx} % Required for inserting images

\title{Halley's method}

\author{whatever owo}

\date{April 2025}

\begin{document}

\maketitle

\section{Explanation}

$$f(x)=f(x_n)+f'(x_n)(x-x_n)+{1\over2}f' '(x_n)(x-x_n)^2+...$$

This is just the Taylor series. If we take only up to the second Taylor term, then we set it to 0, just like in Newton-Raphson, we get the following.

$$f(x_n)+f'(x_n)(x-x_n)+{1\over2}f' '(x_n)(x-x_n)^2=0$$

we notice that there's a common factor of $(x-x_n)$

$$(x-x_n)[f'(x_n)+{1\over2}f' '(x_n)(x-x_n)]=-f(x_n)$$

$$x-x_n=-\frac{f(x_n)}{f'(x_n)+{1\over2}f' '(x_n)(x-x_n)}$$

$$x=x_n-\frac{f(x_n)}{f'(x_n)+{1\over2}f' '(x_n)(x-x_n)}$$

now $x \text{ is } x_{n+1}$

$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)+{1\over2}f' '(x_n)(x_{n+1}-x_n)}$$

Now, from the Newton-Raphson method, we know that

$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} \Longrightarrow x_{n+1}-x_n=-\frac{f(x_n)}{f'(x_n)}$$

We can plug this into our previous equation

$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)+{1\over2}f' '(x_n)\left(-\frac{f(x_n)}{f'(x_n)}\right)}$$

We simplify this by multiplying on the denominator and numerator by $2f'(x_n)$

$$x_{n+1}=x_n-\frac{2f'(x_n)f(x_n)}{2[f'(x_n)]^2-f(x_n)f' '(x_n)}$$

\end{document}

paste it into your favorite latex document editor Whateverowo (talk) 23:04, 10 April 2025 (UTC)Reply

I agree that the article's derivation is lacking. If you want, you might boldly edit the article to improve it. FWIW, I don't know how I feel about your derivation here because it is in LaTeX rather than something I can easily read. —Quantling (talk | contribs) 14:01, 11 April 2025 (UTC)Reply

I recommend using overleaf to view it, It's the best like that and you don't have to go through the trouble of setting up LaTeX locally Whateverowo (talk) 14:37, 11 April 2025 (UTC)Reply

Likely, I won't be the only one who wants to read it, and it seems inefficient to ask each reader to go to Overleaf... O(n). Instead, it would be great if you could supply a readable version here... O(1). —Quantling (talk | contribs) 16:51, 11 April 2025 (UTC)Reply

Ahaha, I don't know how to write math in the talk section, sorry, can you point me to which article explains it? I'll write it for you then (: Whateverowo (talk) 17:11, 11 April 2025 (UTC)Reply

There may be issues with one dialect of LaTeχ vs. another, but a good first step would be to convert strings that look like "$$stuff$$" to "<math>stuff</math>". For example,

<math>f(x)=f(x_n)+f'(x_n)(x-x_n)+{1\over2}f''(x_n)(x-x_n)^2+...</math>

displays as:

${\displaystyle f(x)=f(x_{n})+f'(x_{n})(x-x_{n})+{1 \over 2}f''(x_{n})(x-x_{n})^{2}+...}$

Or use "<math display=block>stuff</math>" so that the math cannot be inline with a sentence. With any luck, there won't be any LaTeχ dialect issues and that is all you will need to do. —Quantling (talk | contribs) 18:08, 11 April 2025 (UTC)Reply

ok here's the derivation, thanks for explaining :) :

${\displaystyle f(x)=f(x_{n})+f'(x_{n})(x-x_{n})+{1 \over 2}f''(x_{n})(x-x_{n})^{2}+...}$

This is just the Taylor series. If we take only up to the second Taylor term, then we set it to 0, just like in Newton-Raphson, we get the following.

${\displaystyle f(x_{n})+f'(x_{n})(x-x_{n})+{1 \over 2}f''(x_{n})(x-x_{n})^{2}=0}$

we notice that there's a common factor of ${\displaystyle (x-x_{n})}$

${\displaystyle (x-x_{n})\left[f'(x_{n})+{1 \over 2}f''(x_{n})(x-x_{n})\right]=-f(x_{n})}$

${\displaystyle x-x_{n}=-{\frac {f(x_{n})}{f'(x_{n})+{1 \over 2}f''(x_{n})(x-x_{n})}}}$

${\displaystyle x=x_{n}-{\frac {f(x_{n})}{f'(x_{n})+{1 \over 2}f''(x_{n})(x-x_{n})}}}$

now ${\displaystyle x{\text{ is }}x_{n+1}}$

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})+{1 \over 2}f''(x_{n})(x_{n+1}-x_{n})}}}$

Now, from the Newton-Raphson method, we know that

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\Longrightarrow x_{n+1}-x_{n}=-{\frac {f(x_{n})}{f'(x_{n})}}}$

We can plug this into our previous equation

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})+{1 \over 2}f''(x_{n})\left(-{\frac {f(x_{n})}{f'(x_{n})}}\right)}}}$

We simplify this by multiplying on the denominator and numerator by ${\displaystyle 2f'(x_{n})}$ and therefore:

${\displaystyle x_{n+1}=x_{n}-{\frac {2f'(x_{n})f(x_{n})}{2[f'(x_{n})]^{2}-f''(x_{n})f(x_{n})}}}$ Whateverowo (talk) 18:54, 11 April 2025 (UTC)Reply

there's a typo here I don't know why but f'' disapears on the denominator sorry so in the denominator the 1/2 term is the second derivative Whateverowo (talk) 18:58, 11 April 2025 (UTC)Reply

Yes, using the Newton's update step inside the Halley's update step is a common way to state this. If it's to go in the article, I would want to fix that we are giving two inconsistent definitions for ${\displaystyle x_{n+1}-x_{n}}$, one for Newton's update step and one for Halley's update step. I see what you are aiming for, and hope that the notation can openly represent that distinction. —Quantling (talk | contribs) 19:25, 11 April 2025 (UTC)Reply

hmm, yeah I see so maybe we could give two different letters for halley and newton so its understood? is that what you mean? Whateverowo (talk) 20:17, 12 April 2025 (UTC)Reply

Hmm. Different letters could be confusing too. How about calling out the distinction prominently in the text, along the lines of this?:

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

${\displaystyle 0=f(x_{n+1})\approx f(x_{n})+f'(x_{n})(x_{n+1}-x_{n})}$

to compute

${\displaystyle x_{n+1}-x_{n}=-{\frac {f(x_{n})}{f'(x_{n})}}\,.}$

Similarly for Halley's method, a proof starts with

${\displaystyle 0=f(x_{n+1})\approx f(x_{n})+f'(x_{n})(x_{n+1}-x_{n})+{\frac {f''(x_{n})}{2}}(x_{n+1}-x_{n})^{2}\,.}$

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

${\displaystyle x_{n+1}-x_{n}=-{\frac {f(x_{n})}{f'(x_{n})+{\frac {f''(x_{n})}{2}}(x_{n+1}-x_{n})}}\,}$

where x_n+1 − x_n appears on both sides of the equation. Substituting in the Newtwon's method value for x_n+1 − x_n into the right-hand side of this last formula gives the formula for Halley's method

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})-{\frac {f''(x_{n})f(x_{n})}{2f'(x_{n})}}}}\,.}$

—Quantling (talk | contribs) 21:55, 12 April 2025 (UTC)Reply

The derivation section is unnecessary, because the "Cubic convergence" section provides a proof that Halley's formula is correct. JRSpriggs (talk) 23:44, 12 April 2025 (UTC)Reply

Good point. I think a shorter Motivation section will clarify where the formula came from. I will boldly edit the section to include the text above and a name change for the section. Please edit it further if you see ways to improve it, or undo it if you think I've stepped off in the wrong direction. Thanks —Quantling (talk | contribs) 18:39, 13 April 2025 (UTC)Reply

With Newton's method, a line consistent with x, f(x), f′(x) is fit and one gets the next iteration where the line crosses the x axis. With Halley's irrational method, it also uses f′′(x), a parabola is fit, and we look for where it crosses the x axis. My question is, what curve is fit for Halley's rational method? Is it a different parabola ... or something else. If this is documented somewhere (or is simple enough to be WP:CALC), let's mention it in the article. —Quantling (talk | contribs) 20:18, 28 August 2025 (UTC)Reply