I need to find all the roots of a scalar function in a given interval. The function may have discontinuities. The algorithm can have a precision of ε (e.g. it is ok if the algorithm doesn't find two distinct roots that are closer than ε).
Does such algorithm exists? Could you point me papers about that?
Actually, I have a function to find a zero in a given interval using Brent's algorithm, and a function to find a minimum in a given interval. Using those two functions, I built my own algorithm, but I was wondering if a better algorithm exists. My algorithm is like that:
I start with an interval
[a,b] and a function
sign(f(a+ε)) ≠ sign(f(b-ε)), I know there is at least one zero between
b, and I find
z = zero(]a,b[). I test if
z really is a zero (it could be a discontinuity), by looking a the value of
z+ε. If it is, I add it to the list of found zeros. If
f(b-ε) both are positive, I search
m = min(]a, b[). If
f(m) still is positive, I search
m = max(]a,b[) because there could be a discontinuity between
b. I do the opposite if
f(b-ε) were negatives.
Now, from the point I found (
m) I build a stack containing the zeros, discontinuities, and inflection points of my function. After the first iteration, the stack now looks like
[a, z, b]. I start again the algorithm from intervals
]z,b[. When, between two points
b, the extrema have the same sign than both interval ends, and there is no discontinuities at both extrema, I remove the interval from the stack. The algorithm ends when there is no more intervals.