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?

  • 2
    $\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
  • $\begingroup$ Just out of curiosity, what happens is you run Newton method starting at 0 (or close). $\endgroup$ – nicoguaro Jun 1 '18 at 15:01
  • 3
    $\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
  • 2
    $\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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.