|Re: Reverse Engineering HP Solve [long]|
Message #16 Posted by Patrick on 15 Oct 2003, 3:13 p.m.,
in response to message #15 by Valentin Albillo
To see the effect of the bent secant characteristic of HP Solve, try the following experiment. Using an HP-34C or an HP-15C (other calculators may use the same algorithm, I have not verified any others yet), key in a program which consists of a single instruction, R/S, sandwiched between a label and a RTN:
This program forms my lab bench upon which I perform experiments on Solve. If you run "Solve A" the program will stop each time it calls your "function". The program simply waits for you to look at the x value in the display and type in the y value you want to correspond to it. You then press R/S to continue the Solve algorithm.
Using this technique, you can present the algorithm with any sort of situation you like, without having to craft some sort of mathematical function that does it for you.
With this setup, start Solve running with initial guesses x1=1 and x2=-1 (1, ENTER, CHS, SOLVE A). When your program stops to get y values, suppy the values y1=1 and y2=-1 (i.e., just press R/S each time). Of course the secant line between these two points lands you smack dab at the origin, so the next x point you'll be asked about is x3=0. Well, not quite. There is a certain amount of what can only be described as randomization inserted by HP Solve, so what you get is an x3 value near zero. For this x value, whatever it is, supply the y value y3=-0.8.
So far, you've given the algorithm three points to consider: (1,1), (-1,-1), and (0, -0.8). Note that the first two x values already bracket the root, since the corresponding y values are of opposite signs. The brackets become tighter once you know that the value of the function at zero is negative. Now the root should lie between 0 and 1. However, if you try to draw the secant line between the second and third points, the resulting x value is x4=4, outside of the brackets. This is where the bending of secant should take place, so as to guarantee x4 stays between the brackets: 0 < x4 < 1.
My spreadsheet uses the following algorithm: If the secant method lands you outside the brackets, pick the midpoint of the brackets for the next trial. In this case, my spreadsheet would choose x4=0.5. The HP Solve algorithm on my HP-15C doesn't do this. It selects x4=0.6997201114.
My question is, how is that strange number selected?
In fact, after an initial period of experimentation, I believe that the HP Solve algorithm has computed:
x4 = base + randomizer
where base=0.7 and the randomizer is on the order of (5e-4 * base). I have an inkling as to why the randomization is included, but it is still pretty foggy to me.
Anyhow, why 0.7? That is my question.
Using this technique, one can generate any number of examples of when the bent secant algorithm is needed. Using a series of experiments, I have determined that:
- The x4 value scales linearly in x1 and x2 (i.e., replace x1 by c*x1 and x2 by c*x2 and the x4 value changes to c*x4)
- The x4 value scales linearly in y1 and y2.
- The x4 value does not depend on a value of x and y previous to (x1,y1).
I have computed the value of x4 for a host of values of y3 and have plotted the results, but don't have a functional relationship there yet. Still trying...