Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
How fast? Is the derivative available? What is wrong with bisection? –  Dirk Oct 7 '11 at 11:17
    
Faster than the iterative dumb method would be fine :-) Bisection is ok. –  user16416 Oct 7 '11 at 11:30
1  
The Newton method has quadratic convergence provided e.g. the function $C^2$ and convex. In you only know that your function is continuous and monotone, I think one can't do better than bisection. –  Pietro Majer Oct 7 '11 at 11:59
2  
This is not mathematics research, is too vague, and I am voting to close it. –  Igor Rivin Oct 7 '11 at 14:10
5  
Maybe the question is naively expressed, but I don't think it is trivial at all. I think that clarifying a non-trivial question, and putting it in the right setting is within the scope of this site, as well as giving an answer. Can anybody give a precise meaning to the statement: "in order to approximate the root of a continuous decreasing function the faster algorithm is the bisection method". –  Pietro Majer Oct 7 '11 at 16:34
show 4 more comments

3 Answers 3

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
I put up a question mathoverflow.net/questions/77520 inspired by this one. –  Aaron Meyerowitz Oct 8 '11 at 6:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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