# Finding the smallest root of a function on $[0, \infty)$

I would like to find the smallest real root of a 1-D real-valued function $f(x)$ on the domain $x\in [0,\infty)$. In this problem, I can make the following guarantees on $f$:

1. $f$ does have a root at some finite, positive $x$.
2. $f$ is differentiable at all finite, positive $x$ and $f'(x)$ is either known or can be approximated accurately.
3. $f$ may have multiple roots (and usually does).
4. At its smallest root, $f$ changes sign from positive to negative.

Further, I can estimate

• an approximate lower bound on the spacing between roots, call it $\Delta$.
• an upper bound on the location of the smallest root, call it $x_{\max}$. If the root is beyond this point, I can compute its approximate location analytically.

My current algorithm for this problem is to bracket the root via a naive linear search. Starting from $x=0$, I march along in increments of $\Delta$ until $f(x)$ and $f(x+\Delta)$ differ in sign. With the root bracketed, I defer to a standard root-finding algorithm.

With the knowledge I have of $f$ and the estimates I am willing to make about its root structure, can I bracket the smallest root more quickly than a simple linear search?

• If your function is well-behaved and $x_{\mathrm{max}}$ is not too large, this is the sort of problem that chebfun typically handles without difficulty. Jun 1 '18 at 14:07
• I expect that chebfun is too heavy for this application. There are two external parameters in the problem, and each combination gives a different $f(x)$. I need to canvass this parameter space, so the overhead of repeatedly building the Chebyshev interpolant seems prohibitive. Jun 1 '18 at 14:54
• You know $f$ better than me of course. If something off-the-shelf like chebfun is too heavy, it could also be that what you're already doing is hard to beat. Also: I want to point out that the six facts about $f$ are actually very weak, they guarantee a solution exists and that linear search+bracketing works, but they really don't constrain $f$ much at all. (Compare with a case where you know $f$'s asymptotics, for example.) It can be quite tricky to give just the right amount of information about $f$ in a question like this. Jun 1 '18 at 15:02
• The problem is if you have an interval $(a,b)$ (e.g. $(0,x_{\max})$ or a subinterval, how can you decide there is no zero in this interval. I think if you only know $f(a),f(b), f'(a), f'(b)$ then you haven't enough knowledge to decide this and only the approach you use is possible. So additional information is necessary. Jun 1 '18 at 19:54
• Do I understand correctly that Durand-Kerner and Aberth are specific to polynomials? My $f$ is not a polynomial, though it looks like one locally. Jun 4 '18 at 19:18