Heads up for a hot new root seeking algorithm!!

[Namir]

(01-19-2017 10:44 AM)emece67 Wrote:  

(01-19-2017 05:26 AM)Namir Wrote:  Yes the paper states, on page 78, that Ostrowski's convergence is of order 4. The author is mistaken!!

http://folk.uib.no/ssu029/Pdf_file/Varona02.pdf states that the order of convergence of Newton's is 2, Halley's 3 and Ostrowsky's 4.

http://www.sciencedirect.com/science/art...2706006716 states that the basic Ostrowsky's method has order of convergence 4.

http://www.sciencedirect.com/science/art...2111008078 states again that the order of convergence of Ostrowsky method is 4. It also says that the Ostrowsky's method is optimal in the sense that it satisfies the Kung-Traub conjecture (which states that the maximum attainable order of convergence for an algorithm with \(n\) function evaluations is \(2^{n-1}\), neither Halley's nor Newton's are optimal in such sense.

I'm not sure about the first reference, but the other two are peer reviewed publications, so I assume them to be safe sources.

I cannot find now your algorithms description (didn't they were in this thread or in another one?) so, how many function evaluations do they need on each iteration?

Obtaining the computational order of convergence COC of your algorithm seems not to be a hard task (only 3 iterations are needed for some test function/root combinations). Such COC combined with the number of function evaluations needed on each iteration will give us all a much better indication of your algorithm performance.

Regards.

Edit: I located your algorithm in the other thread (sorry I forgot it). It needs four function evaluations on each iteration. Supposing its order of convergence is 4, its efficiency index is \(\sqrt[4]{4}=1.4142...\). As Ostrowsky's algorithm only requires 3 function evaluations on each iteration and it has an order of convergence of 4, its efficiency index is \(\sqrt[3]{4}=1.5874...\), which is better. If the order of convergence of your algorithm is not 4, but 3, then the situation is even worse. To compete with the Ostrowsky's algorithm (in terms of the efficiency index) we need your algorithm to be of order 6-7. For comparison, the efficiency index of Newton's is also 1.4142... and that for Halley is 1.44225...

Thank you for the interesting information. I will look at the various articles you mentioned in your links.

I have a question for you. Given a function f(x) with an initial guess x0 and a specified tolerance. If I apply root-seeking algorithm AL1, which has an efficient index EI1, and it takes N1 iterations to refine the root. Can I predict the number of iterations N2 for another algorithm AL2 with an efficiency index EI2? If we can do that, then we can estimate the efficiency index EI3 of algorithm AL3, compared with algorithm AL1, given the number of iterations N1 and N3 for both methods (which the initial guess and tolerance being the same) and an Efficiency Index EF1 for AL1.

Namir