0
$\begingroup$

When you use the bisection method to find the roots of a function $f(x)$, you have to start with values $a$ and $b$ such that $f(a)$ and $f(b)$ have different signs- so (by the intermediate value theorem) you can find a root between $a$ and $b$. Only thing is... I'm automating the process with some code, and the code is supposed to be very general- so any combinations of regular algebraic arithmetic, trigonometry, logarithms, and hyperbolic functions.

This makes it pretty hard to estimate $a$ and $b$ on the spot such that they have opposite signs. Is there any way I can do this (without randomizing $a$ and $b$ and then running values through the same function to hone them down until they have separate signs)?

Thanks

Edit: I'm using an algorithm called Lehmer-Schur which is generalized to complex values using disks rather than a specific interval. I realize that it would be a lot simpler to pick really big bounds or try using some kind of randomizer, but this seems really crude and I was hoping there'd be a better solution. This is a big ask since (within the restrictions on composition mentioned above) there are no limits on the complexity of the function- so I understand that this may not be possible at all. I'm just keen to know what other people are doing or if there are any smart solutions.

$\endgroup$
13
  • $\begingroup$ This is pretty standard. If you search you will find this algorithm written in many languages. $\endgroup$
    – John Douma
    Commented Nov 16, 2020 at 7:18
  • $\begingroup$ Technically it's not the true bisection method- it's a variant called Lehmer-Schur (for complex values- so it works quite a bit differently to simple bisection), of which I can't find many sources, let alone code, let alone one that actually uses a smart technique. Most pick numbers with a big range or do the randomizer thing. I've updated the post to reflect this. $\endgroup$
    – MukundKS
    Commented Nov 16, 2020 at 7:35
  • $\begingroup$ Consider this: If you can find two values with opposite signs very easily, why do you need the bisection anymore? The point of this method is that you no nearly nothing and do crude operations. $\endgroup$
    – Nurator
    Commented Nov 17, 2020 at 10:58
  • $\begingroup$ @Nurator Your statement that "The point of this method is that you no nearly nothing and do crude operations" is unclear to me. The Lehmer-Schur algorithm relies on root-counting, so a root-finding method which does not depend on the values of the output is needed. $\endgroup$
    – Simply Beautiful Art
    Commented Nov 17, 2020 at 14:17
  • 2
    $\begingroup$ You mention the Lehmer-Schur method, which is made for polynomials, though you did not say this in your question. It makes a big difference. $\endgroup$
    – user65203
    Commented Nov 17, 2020 at 14:23

1 Answer 1

Reset to default
1
$\begingroup$

There is no issue with choosing very large brackets for a function, because the bracket will close in on the root very rapidly. To accelerate initial convergence to find the order of magnitude of the root, see here and here. The given routines will guarantee convergence in roughly 70 iterations over the largest finite bracket using doubles (somewhat useless if you don't care about relative accuracy).

If the values at infinity give the same sign (i.e. $f(\infty)=f(-\infty)=\pm\infty$), then you can try using optimization methods on that bracket to attempt to find how close it gets to the opposing infinity (i.e. $f(x)\to\mp\infty$). If there is a sign change, then you have two brackets (from the relative extrema to each infinity), and if there is no sign change then you really have no guarantee on the existence of a root. You may also wish to consider the case when $|f(x_\text{relative-extrema})|$ is very small as a double (or higher) root.

If the root is expected to be simple, then superlinear convergence may be obtained by using better bracketing methods, such as Chandrupatla's method. Feel free to look into the source code on GitHub and take out the portions that fit your needs.

$\endgroup$
6
  • $\begingroup$ When the are several roots, choosing very large brackets is just out of question. $\endgroup$
    – user65203
    Commented Nov 17, 2020 at 14:15
  • $\begingroup$ @YvesDaoust I am not sure what you mean. $\endgroup$
    – Simply Beautiful Art
    Commented Nov 17, 2020 at 14:18
  • $\begingroup$ With large brackets you can (will) miss all roots, obviously $\endgroup$
    – user65203
    Commented Nov 17, 2020 at 14:21
  • $\begingroup$ Yes, this is only for finding one root of a function. If several roots are desired then you will need to use several separated brackets. As far as the OP's purposes however, these brackets will come naturally on their own. $\endgroup$
    – Simply Beautiful Art
    Commented Nov 17, 2020 at 14:24
  • $\begingroup$ No you don't understand. If the function has several roots, large bracketing can fail to find any. Not one. Zero. Nada. $\endgroup$
    – user65203
    Commented Nov 17, 2020 at 14:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .