2
$\begingroup$

I know that generally the bisection method is used given a certain function and an interval where we know a root exists within it. What if we don't know the interval? Is there a way of "guessing" the interval to use?

$\endgroup$
3
$\begingroup$

If you know nothing about the properties of your function, then there isn't much you can do. For example, you function could have regions where it's not defined, it could have poles and so on.

But let's focus now on the domain on which the function is continuous. If it's odd, then taking a huge numerical range will be fine: bisection takes only $\log_2 (max-min)$ to reduce the interval so it won't take long. However, the biggest problem here is if the function has many zeroes and it's hard to find an interval with opposite signs of the function (to bracket the zero). Random sampling could work as a last resort - sample the domain according to some distribution (even distributions that reach to infinity) and find a pair of values where the function has opposite signs.

It's also quite common to "grow" the interval (see numerical recipes). You can double the width of your interval until you bracket a root.

However, none of this will be used in a sane application... you usually know at least something about your function. There are many root finding algorithms that don't require an interval (and most of them converge much faster). For polynomials, you can compute estimates on the magnitude of the largest root. And so on. Nobody does "blind" root finding, you either specify an initial condition or an initial bracket according to what you know. It's also rare that you need all roots - you need a specific root and if you don't know where to start, you will probably find the wrong one.

Global minimizers sort of attempt to do this - but it doesn't work very well. In this application, stochastic algorithms really are used (simulated annealing for instance). But this is different story.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

If you know that your function is continuous: Just, randomly sample the function until you find two points one positive and one negative, they define the first interval

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.