Talk:Halley's method

Real??

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)

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)

Multidimensional version

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)

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 $F'(x_{k})t_{k}=-F(x_{k})$

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

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

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

3. Set $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

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

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

$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

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

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

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)

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)

Irrational method

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 $f(\mathbf {x} )$ where $\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)

The derivation is just wrong like what?

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

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)

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)

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)

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)

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)

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:

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

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

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

$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 $(x-x_{n})$

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

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

$x=x_{n}-{\frac {f(x_{n})}{f'(x_{n})+{1 \over 2}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 \over 2}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 \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 $2f'(x_{n})$ and therefore:

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

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)

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

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)

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

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

to compute

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

Similarly for Halley's method, a proof starts with

$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

$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

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

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)

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)