Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am looking for an algorithm to do the following.

Given:

  • An interval $[a,b]$.
  • A black box function $n(x)$ which returns the number of roots (zeros) of a function that lie to the left of $x$. That is, for some function $f(y)$, $n(x)$ returns a count of all $y$ such that $f(y)=0$ and $y<x$.

Find: Approximations to all of the roots of the function in $[a,b]$ using few invocations of $n(x)$.

It would be nice if there was a tunable parameter to trade off accuracy of approximations and the number of invocations. Also, it is sufficient to indicate a cluster of nearby roots without resolving all of them.

Quick edit: I know about algorithms like bisection, which work for single roots. I'm wondering if wanting all the roots at once might save on function invocations.

share|improve this question
1  
Just use bisection: divide and conquer. –  user16697 Dec 29 '11 at 10:57
    
Just to clarify: $f$ is a continuous function with a finite number of roots in $[a,b]$, right? As to QED's comment, I think he meant bisection on $n(x)$ (not on $f(x)$), which involves finding $y \neq x$ with $n(y) \neq n(x)$. –  Pedro Milet Dec 29 '11 at 11:11

1 Answer 1

up vote 6 down vote accepted

An obvious algorithm is to look at $n(a)$ and $n(b)$. If the difference is positive then go ahead as the interval is "in play".

Look at $n\left(\frac{a+b}{2}\right)$. If this is equal to either $n(a)$ and $n(b)$ then half the interval is no longer in play; otherwise both halves are in play.

Continue subdividing the subintervals which are in play until your appoximations are close enough.

share|improve this answer

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.