Fast root finding for strictly decreasing function

Question

What is a fast algorithm to find the root of a strictly decreasing function? If the root is not exact I want to find a root such that the function value is positive to an error.

Answer 1

This is an attempt to make precise the statement that bisection is the fastest method. Consider the problem of approximating the solution of $f(x) = 0$, $x \in [0,1]$, where $f$ is known to be a continuous decreasing function on $[0,1]$ with $f(0) > 0$ and $f(1) < 0$. An algorithm is allowed to evaluate $f$ at $N$ points $x_1, \ldots x_N \in [0,1]$, where each $x_j$ is allowed to depend on the values $f(x_1), \ldots, f(x_{j-1})$, and must then produce an interval that contains the solution. The bisection method would start with the interval $[0,1]$, at each step $i$ would take $x_i$ to be the midpoint of the current interval, and the interval for the next step would be the left or right half of the current interval depending on whether $f(x_i) \le 0$ or $f(x_i) > 0$. Thus after evaluation at $N$ points the resulting interval has length $2^{-N}$. The claim is that this is best possible in the following sense: for any algorithm and any $N$ we can construct a continuous decreasing function $f$ such that the result of this algorithm after evaluation at $N$ points is an interval of length $\ge 2^{-N}$.

It is easy to prove the claim. Note that after evaluating at points $x_1, \ldots, x_k$ the only useful information we have is that the solution is in the interval $(a,b)$ between the greatest sampled point (or 0) where $f > 0$ and the least sampled point (or 1) where $f < 0$. If $x_{k+1}$ is not in that interval, it provides no useful information. If $x_{k+1}$ is in the interval, choose $f$ so $f(x_{k+1})$ is either negative or positive according to which of $x_{k+1} - a$ and $b - x_{k+1}$ is greater.

Answer 2

In the absence of any other information, you'd need to use bisection as described above (let's avoid the issue, for the moment, that your guesses need to bracket the root.) The {\bf order of convergence} of bisection is linear. Indeed, if you already have a good set of such guesses, and know the function is decreasing, take a couple of steps of the Secant method.

However, if you have knowledge that the function is differentiable AND you know initial guesses to bracket the root, I'd use the Regula Falsi method. This couples the Secant method with bisection. Since you have a strictly decreasing function, the usual problems with rounding may be ameliorated, since you know the sign of the derivative. The order of convergence should be around 1.67.

Finally, if you have the derivative handy, I'd start off with Newton's method. This converges quadratically, you don't need a bracketing guess, and you'll find out within a few iterations if gradient-based methods are going to fail.

In other words: use the information you have, and build in safe-guards to default to the bisection method if needed.

Answer 3

If we don't have more information about the function then we really just have the case that an unknown point has been selected in $[0,1]$ and we try to confine it to a small interval by guessing points and getting an answer of less or more. In this case it depends on the criteria for fastest. As observed by Robert, bisection has better worst case behavior than any other method. It also has worse best case behavior than any other method.

Suppose that we play a game where you try to find the unknown point. You get 20 guesses. After guess $k$, if you have confined it to an interval of length less $w(k)=\frac{0.8}{2^k}$ you win a dollar, otherwise you lose 3 dollars. If I am not mistaken, this game favors you.