On Convergence Rates of Root-Seeking Methods

[Claudio L.]

(03-14-2018 09:57 PM)emece67 Wrote:  For non-bracketed methods, you my find this paper interesting. It compares up to 13 different non-bracketed methods (not high order, high complexity ones, the highest order method in the comparison is Ostrowsky-Traub, 4rd order), being Newton, Halley & Steffensen among them. On this paper, Steffensen method failed to converge many, many times (although the author works in the complex plane, not in the real line).

Also, the fractal pictures on the paper are nice :-)

Regards.

Took me a while to digest the paper. There's a lot of information there. From the tables it seems that regardless of the theoretical convergence rates, only one method is consistently faster than Newton: Ostrowski-Traub and not by much (usually 10 to 30% faster only, not what you'd expect with a 4th order method).
And a few surprises: The author worked with complex roots, and here I thought only a few methods were good to find complex roots. It seems any method can work, but some do a horrible job (Steffensen, Figure 9 - the black area means no solution found). And I said before I was going to research this method... now it's discarded (thanks!).
It seems the simplest methods are really hard to beat. All that complexity to get a 10% speedup only some times? Even Halley was faster than Newton on only one table.
A very enlightening paper, thanks for the link.