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?

  • 3
    $\begingroup$ 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. $\endgroup$ – Kirill Jun 1 '18 at 14:07
  • $\begingroup$ 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. $\endgroup$ – Endulum Jun 1 '18 at 14:54
  • 4
    $\begingroup$ 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. $\endgroup$ – Kirill Jun 1 '18 at 15:02
  • 3
    $\begingroup$ 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. $\endgroup$ – miracle173 Jun 1 '18 at 19:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Endulum Jun 4 '18 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.