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)