Newton and Halley's methods with enhanced derivatives estimation

[Dieter]

(09-30-2017 08:39 PM)Namir Wrote:  I present versions of Newton's method and Halley's method that use enhanced estimations for the first and second derivatives
(...)
You are welcome to add iteration counters to also view the number of iterations needed.

What? Still no answers after six days ?-) Then let me add a first comment.

First of all, thank you very much for your suggestion of enhanced methods with more accurate derivatives. I tried the Newton method in Excel VBA, and here is what I got:

Indeed the derivative is much more accurate than the classic method based on two points at x and x+h. The approximation sequence actually matches very nicely the one based on the exact derivative. This way often one iteration less is required, there may be even cases where two or more are saved.

But... the number of function calls is much higher than with the classic two-point approach.
Here is an example with your f(x) = exp(x) – 3 · x², based on a tolerance of 1 E–10.

Code:

               Newton method with x0 = -2 and
exact derivative  5-point derivative  2-point derivative
--------------------------------------------------------
-1,0223043336      -1,0223043336       -1,0223090585
-0,5948746572      -0,5948746572       -0,5948783091
-0,4711156755      -0,4711156755       -0,4711167598
-0,4590772551      -0,4590772551       -0,4590773196
-0,4589622780      -0,4589622780       -0,4589622784
-0,4589622675      -0,4589622675       -0,4589622675
-0,4589622675      -0,4589622675       -0,4589622675
--------------------------------------------------------
 14 fn calls        35 fn calls         14 fn calls

               Newton method with x0 = +2 and
exact derivative  5-point derivative  2-point derivative
--------------------------------------------------------
 1,0000000000       1,0000000000        0,9999969874
 0,9141552818       0,9141552818        0,9141554524
 0,9100176658       0,9100176658        0,9100176888
 0,9100075725       0,9100075725        0,9100075726
 0,9100075725       0,9100075725        0,9100075725
                                        0,9100075725
--------------------------------------------------------
 10 fn calls        25 fn calls         12 fn calls

The 2-point derivative was based on an IMHO more suitable definition of h = x/10000 (or 0,00001 for x=0).

You can see that the first two columns agree very nicely, i.e. the 5-point derivative essentially delivers the same results as the exact derivative. So yes, the number of iterations can be slightly improved with a more accurate derivative, but (and this is a big BUT) the number of function calls and thus the required execution time will significantly increase! Since the function has to be called 2,5x more often compared to a classic 2-point derivative (and the calculation of the derivative itself also requires a bit more effort) the gain of one or two less iterations does not outweigh the much longer time it takes for each approximation step. In the above example the simple 2-point method is more than twice as fast.

So... where's the benefit of a more exact derivative?

Dieter