I am reading the standard (Numerical Recipes and GSL C versions are identical) implementation of Brent root finding algorithm, and cannot understand the meaning of variable "e". The usage suggests that "e" is supposed to be the previous distance between the brackets. But then, why is it set to "xm" (half the distance) when we use bisection?
views:
417answers:
3Yes, I can see that "e" is related to the loop conditional, because it is read in the "if" statement... The point is, "b" and "a" in the Wikipedia conditional statement are the current best guess and the opposite point (where the function has different sign), while in GSL and Netlib codes, "b" is the best guess and "a" is the previous best guess, "c" being the opposite point.
quant_dev
2009-12-29 23:14:24
See updates above.
Seth
2009-12-30 04:09:57
Thanks. I could have thought about searching for the original paper via Google Books...
quant_dev
2009-12-30 07:50:36
It was an accident :P. I wanted to learn a bit more about the algorithm. The original book just happens to be the first result when searching for "algol 60 procedure zero given in richard brent, algorithms" (from one of the comments in the Fortran source).
Seth
2009-12-30 09:21:48
+1
A:
E is the "epsilon" variable, which is basically a measure of how close is close enough. Your particular application may not require 20 digits of precision, so epsilon lets you balance how many iterations it requires ( i.e., how long it runs ) versus how accurate you need it.
With floating point numbers you may not be able to be exact, so epsilon should be some small non-zero number. The actual value depends on your application... it's basically the largest acceptable error.
Chris Arguin
2009-12-29 22:52:48
I don't think so, because "e" is a) a variable, which is changing between iterations, b) is checked only when deciding whether to do inverse quadratic interpolation or fall back to bisection, and c) there is already an "elastic" tolerance variable "tol", which responsible for what you claim "e" does. No cookie.
quant_dev
2009-12-29 23:13:25
I think he's basically right, he's not saying it is the constant which specifies the desired precision, rather he's saying it is the value which you compare to the constant which specifies the desired precision. Matches up well with the other answer.It could also be used to determine which algorithm(inverse quadratic vs bisection) to use based on their convergence characteristics?
Tim Lovell-Smith
2009-12-30 16:58:56
A:
During a bisection step, the interval is exactly halved. Thus, e, holding the current width of the interval, is halved as well.
Drew Hall
2009-12-30 04:47:09