Brent Worden wrote:
In the chi-square patch, I created a root finding utility class. I used the
bisection method to provide a default mechanism for computing inverse CDFs.
It's driven by a simple Function interface. Check it out and see if it's
something you can use or improve.
Here's my take on root finding. Note that BrentSolver uses only inverse quadratic interpolation rather than the full Brent algorithm.
Can you provide a math reference desribing this? I have been referring to Atkinson and I am having a hard time following the implementation. What exactly do you mean by "only inverse quadratic interpolation"? Am I correct in assuming that what you mean by this is that you *never* use Secant or Bisection? Looks to me like this is the case, but I am having a little difficulty following the code. If it is the case, what impact does this have on convergence/stability?
THere are a few issues with accuracy, there should really be a relative accuracy too, as well as some plausiblity checks.
What do you have in mind re: plausibility?
I guess I like your rootfinding framework better than Brent's (Here I mean Brent Worden, the famous commons-math contributor, not the numerical analyst). I suggest that we agree to use your interfaces and UnivariateRealSolverImpl base,include Brent's bisection implementation strategy and modify his CDF inversion to use the new rootfinding framework.
I do have a few small questions/comments on the framework:
1. Having solve() *require* brackets makes it impossible (or at least, un-natural) to add Newton's method or any other method that just starts with one initial value. Brent W. includes a method that will try to find a bracket from initial values. I suppose that we could add a solve() with only one initial value and if necessary push it out to a bracket. Personally, given the multiple good implementations available now, I am OK with dropping Newton altogether, so this could be a moot point at least for the initial release.
2. I am curious as to why the "result" property is there. How exactly do we expect clients to make use of this?
3. What were you thinking about putting into the base solve() implementation as diagnostics? Do you mean things like checking to make sure the bracket is good?
4. Thinking of the developers who will use this stuff, I feel like we need a way to insulate them from having to think about rootfinding strategy choice. As Al has pointed out, we are not (at least yet ;-)) in the AI business, so we can't automagically make the best choice for them; but it might be a good idea to somehow specify a default strategy. Unfortunately, the "safe" choice would likely be bisection. We could obviously annoint bisection as the "default" by naming it something like "Solver", but there might be simpler/better ways to do this.
<flame-invitation> I bet that in most real world applications the difference in convergence speed is not a big deal and guaranteed convergence/domain of application is more important than expected speed of convergence. Consider, for example, our own use in CDF inversion to get critical values for stat tests. </flame-invitation>.
Phil
J.Pietschmann
------------------------------------------------------------------------
--------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
--------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
