8

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?

miracle173
  • 109
  • 6
Endulum
  • 735
  • 3
  • 9
  • 3
    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. – Kirill Jun 01 '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. – Endulum Jun 01 '18 at 14:54
  • Just out of curiosity, what happens is you run Newton method starting at 0 (or close). – nicoguaro Jun 01 '18 at 15:01
  • 4
    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. – Kirill Jun 01 '18 at 15:02
  • @nicoguaro $f$ often has (multiple) stationary points between $0$ and the smallest root, so Newton starting at $0$ is a no-go. – Endulum Jun 01 '18 at 16:42
  • And what about brent's method? – nicoguaro Jun 01 '18 at 16:46
  • Brent and other classic rootfinders based on an initial search interval will certainly find some root of $f$, but it will not necessarily be the smallest. – Endulum Jun 01 '18 at 17:03
  • 3
    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. – miracle173 Jun 01 '18 at 19:54
  • There are methods called the Durand-Kerner methods and Aberth methods that simultaneously find all the roots using newtons methods, there are accelerated methods using FFTs. –  Jun 04 '18 at 18:47
  • 1
    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. – Endulum Jun 04 '18 at 19:18

0 Answers0