Newton and Halley's methods with enhanced derivatives estimation

[Dieter]

(10-06-2017 10:52 AM)Namir Wrote:  I did not claim the enhanced derivative accuracy were more efficient in the number of function call. In fact, if one is ever to use this approach, then Halley's method is preferable over Newton's method.

OK, but if the enhanced method is significantly less efficient that the classic 2-point method, why should it be used at all? Maybe I overlooked something here, that's why I'm asking for the benefit of this method. Or, more precisely: what was your motivation here? There must be a reason: people usually do things for a reason. ;-)

Re. the Halley method: I tried the usual 3-point-method for the second derivative and compared this with the results of the enhanced method and those based on the exact first and second derivative. The results are the same as for Newton: The enhanced method nicely matches the results based on exact derivatives, and here and there these two converge in one approximation step less than the standard 3-point method. But since the enhanced derivative requires 5 function calls per iteration vs. just 3 with the standard method, it would have to converge much, much faster (e.g. in only 6 steps where the standard method requires 10). But it doesn't, the number of saved iterations is marginal. So again I do not see any advantage here. But maybe I didn't get the essential point, that's why I'm asking.

BTW, regarding the total number of function calls the standard Newton and Halley methods are very similar (OK, unless you're starting close to a function max/min, here Halley performs better). Comparing the two versions with enhanced derivatives the Halley method has a significant advantage, just as you said. But it's still less efficient than a standard Newton or Halley approach.

Here are some figures for f(x) = exp(x) – 3 x² and tolerance=1E–10, based on exact, enhanced and "standard" evaluation of the derivatives.

Code:

     Total number of function calls
-----------------------------------
     Newton method    Halley method
x0   exact enh std    exact enh std
-----------------------------------
-3     14   35  14      15   25  15
-1     12   30  12      12   20  12
 0     14   35  14      15   25  15
 1      8   20  10       9   15   9
 3     20   50  20      15   25  15
 5     14   35  14      15   25  15

The line for x0=3 shows that the Newton method first leads away from the root at x=3,733 while the Halley method directly approaches the solution.

Dieter