Heads up for a hot new root seeking algorithm!!

[Claudio L.]

(01-10-2017 06:30 PM)Namir Wrote:  The famous Russian mathematician Ostrowski, who taught for many years at the University of Basil, Switzerland, proposedf an enhancement to Newton’s root seeking algorithm. Ostrowski suggested that each iteration offers two refinements for the root—one of them being intermediate per each iteration. The Ostrowski algorithm matches Halley’s root seeking algorithm in its third order rate of convergence. Recently, the Ostrowski algorithm inspired many mathematicians to device root-seeking algorithms with two or more refinements to the root per iteration.

I recently applied Ostrowski’s approach to the Illinois algorithm (an improved version of the False Position algorithm) and was able to obtain better rates of convergence than with the Illinois algorithm. I posted the pseudo-code for this algorithm on this web site. I was a little baffled as to why Ostrowski improved only the Newton’s method and did not become more ambitious to enhance Halley’s method!

A few days ago, I decided to experiment with applying Ostrowski’s approach to Halley’s algorithm. Since the latter method is a bit more advanced than Newton’s method (requiring the calculations of approximations for the first AND second derivatives), applying the Ostrowski approach was NOT trivial. I decided, nevertheless, to give it a go. I started with a simple improvement to Halley’s method, but that did not yield better calculations. After two or three incarnations, I was able to find a satisfactory marriage between Ostrowski and Halley. I plan to publish a report on my website and include a comparison between the methods of Newton, Halley, Ostrowski, and my new Ostrowski-Halley method. The results will include testing these algorithms with two dozen functions and reporting the number of function calls AND iterations.

I am happy to report that the new Ostrowski-Halley method competes well with Halley’s method and its cousin the Ostrowski method. The competition is stiff between these three algorithms., but the Ostrowski-Halley method shows good promise. Stay tuned for my announcement of posting a paper on this subject in my personal web site.

Namir

Keep them coming. I hope you don't mind if one or more of your algorithms end up implemented in newRPL (proper credit will be given, of course!). Always interesting to discover something new in a subject that seemed closed already.