New Root-Seeking Algorithms

[robve]

(04-15-2017 10:58 PM)Namir Wrote:  Hello All,

I have posted on my web site a ZIP file that contains the following:
[...]

Great work to tabulate the results. Hats off.

I ran a few extra tests with the first zip file, i.e. the sheet with the Newton, Halley, Ostrowski, Super Secant, and Hyper Secant methods.

The most difficult functions that I added to the tests are sign(x)*sqrt(abs(x)) and sqrt(abs(x)). The second of these two is impossible to handle with bisection and secant methods, because those methods (and methods such as Brent-Dekker) require bracketing the root by two points x0 and x1, such that f(x0)*f(x1) < 0 (i.e. have opposite signs). For other methods that do not require bracketing, starting at any nonzero guess for x, the methods typically do not converge but bounce around the root x=0 without getting any closer. I came up with these as the most extreme examples of the problem illustrated in Numerical Recipes 2nd ed Ch 9.4 Fig. 9.4.3. The second function is non-differentiable, which adds another twist.

I was surprised to find that Hyper Secant method actually converged for sign(x)*sqrt(abs(x)) starting with the initial guess x=1. This produces x=-0.005306656. The question is, is this result intended? The convergence check may not be accurate perhaps? I would expect the method to continue until x=0 within 1E-9.

A strange result for function sqrt(abs(x)) is produced when starting with the guess x=1. In this case both the Super Secant and Hyper Secant methods loop with the value x=65535 for which f(x) is also 65535. This happens after about 100 iterations. It is odd to see both the Super Secant and Hyper Secant methods lock onto 65535. Probably a VB bug.

Running Halley on a pocket computer (because it's BCD) does produce a series of x values that get successively closer to the root x=0, for both of these functions, when starting with a nonzero guess for x. Newton and Ostrowski completely fail to show any direction for x, but Ostrowski does successively get closer to the root of the function sign(x)*sqrt(abs(x)). Also a non-CAS calculator like the Casio fx-115ES PLUS 2nd ed produces a value close to x=0, but takes significant time to do so. But it did not crash.

I found a minor issue in the VB code of Halley. The loop does not terminate. Adding the check for R>1000 fixed this.

Thanks for posting this and keep up the good work.

EDIT: I neglected to mention that I'm using a smaller h value on my machines, which was also mentioned by previous replies as an improvement. I found that h=sqrt(MachEps)|x| works very well for |x|>1 and h=sqrt(MachEps) for |x|<1, with MachEps the machine epsilon, e.g. h=3E-5 for MachEps=1E-9. You can also fix h to this value before the loop, which is fine as long as x does not change by orders of magnitude in the loop, which should not happen for reasonable initial guesses of x. To prevent the next guess from flying off the scale, you might want to check that |f'(x)|<m|f(x)| for a large value if m, such as m=10^(log10(maxFloat)/2), e.g. m=1E50 or less for maxFloat=1E99. Note that the value of f'(x) is an approximation of the derivative (Quasi-Newton, Halley, etc) or the secant slope.

- Robert