Results of new rootseeking methods  Printable Version + HP Forums (https://archived.hpcalc.org/museumforum) + Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum1.html) + Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum2.html) + Thread: Results of new rootseeking methods (/thread191462.html) 
Results of new rootseeking methods  Namir  08222011 Hi All, Fellow forum members Hugh Steer and Lyuka have opened an interesting door. Hugh mentioned the Ostrowski algorithm for finding nonlinear function roots. I went on a little online crusade to find more on the Ostrowski algorithm. I found several improvements (some just a few years old) on Newton's method and Ostrowski's methods, and a few improvements on Halley's methods. I came out with about 30 algorithms/variants starting with Newton, Halley, Ostrowski, and so on. I included the version of Ostrowski algorithm that Luyka mentioned in his web site. I tested all these methods with many nonlinear functions. The results??? 1. The simple Ostrowski algorithm ranked the best in the battery fo tests. Its simplicity (compared to the sophisticated enhancements given by various mathematicians) kept the number of function calls and iterations low. 2. The Ostrowski 4th Order (by Grau and DiazBarrero) was ranked second best. 3. The Ostrowski algorithm as implemented on Lyuka's web site came third. A special mention to the way the Ostrowski algorithm is implemented since it had only one function call per iteration!!! Very clever!! Here is the basic scheme used by the simple Ostrowski algorithm:
y = x  f(x) / f'(x) Here is the basic scheme used by he Ostrowski 4th Order (by Grau and DiazBarrero):
y = x  f(x) / f'(x) Check Lyuka's web site algorithm version and implementation here
Edited: 22 Aug 2011, 11:11 p.m. after one or more responses were posted
Re: Results of new rootseeking methods  Marcus von Cube, Germany  08222011 I would rank the methods based on different criteria: 1. How many function evaluations are necessary for a given accuracy? The reasoning behind this is that the evaluation of f is more expensive than the operations that the algorithm does with the values. If algorithm (a) uses twice as many function evaluations as algorithm (b) it's ranked better only if the number of iterations is less then half of that of algorithm (b).
2. How stable is the algorithm for some nasty functions or with bad initial guesses? Is it able to solve more problems then some other algorithm? E. g. Newton will fail if started at or near an extremum.
Re: Results of new rootseeking methods  Namir  08222011 Marcus, I have ranked the various algorithms based on the number of function calls. Some of the sophisticated enhancements on Newton or Ostrowski require 4 or 5 function calls!! Several of these methods will give a refined root value (within the specified accuracy) in two or three iterations.
As far as stability, again some of the sophisticated enhancements become unstable depending on the combination of test function and the initial values.
Re: Results of new rootseeking methods  C.Ret  08222011 Thank you Namir for pointing me out this stable and fast rootfinding method. I ‘m now using it instead of a more classic but slow search by dichotomy algorithm.
The code for HP42S (ref. OST ‐ Rev 2.8: Mar. 22 2011 ‐ Copyright(c) 19982011 Takayuki HOSODA, All rights reserved.) is great as it returns root, value,status and give the oportuniti to select with register to solve for. Before a search can start, the two registers R04 and R05 have to be initialized respectively with expected accuracy eps (i.e. 1E6 is a good enough) and the name of the function (i.e. “FCT1” as following exemple). The function have to be programmed in the calculator as taking its only argument from the stack x register and return the value of the function at this point into the same x stackregister. The function code may use other stack registers (convenient for complicated function lucubrations) as the code always consider that at each call of the function, all content of the stack as well as LastX are lost, except the x register returning f(x).
  PROGRAM   STACK REGISTER 
Registers to be initialized :
  PROGRAM 
Edited: 22 Aug 2011, 3:38 p.m.
