All roots of a non-polynomial function

Question

Say I have a function $f(x)$ which crosses the zero several times. Suppose I want to find all the $x$ in a range $[a,b]$ where the function $f(x)$ would be zero. I have got quite some methods like Newton Raphson and bisection but those enables us to find only one root.

P.S.: I am facing few problems, which I came across while I was trying to code this out:

Suppose my function has same sign for $f(a)$ and $f(b)$. Then it possible that either the function does not cross zero or the function has even no of roots.
I would like to know the algorithm, I do not want an answer like 'Check out this code'.
I have looked at these two questions, but they do not seem to help much.
- Finding all roots of polynomial system (numerically)
- Finding all complex zeros of a high-degree polynomial

I suspect you're out of luck without more information about the structure of your function. Even brute force evaluation at many points could miss zeroes if there are many close together. — Ethan Bolker, Jun 03 '17 at 19:13
If you know the number of zeros, apply a numerical method using all test points $a+k(b-a)/n$ $k=0,1,...,n$. Didn't find them all? Increment $n$. — David P, Jun 03 '17 at 19:16
You may consider the function as a sinusoid. I am trying to predict the roots out of that. It is having infinite number of crossing in range (-infinity,+infinity). However, I am interested in only [a,b]. — Mitradip Das, Jun 03 '17 at 19:25
There is no completely general algorithm for finding the roots of any function in an interval given no additional information. For example, a function could have infinitely many zeroes in a finite interval. Meanwhile, if the function is actually a sinusoid, it is very easy to get the zeros using the special properties of sinusoids. You have to be more specific about the kinds of functions you are interested in in order to figure out the most appropriate method (unless you are literally just interested in sinusoids, then use the special trig properties to get the zeros). — idontseethepoint, Jun 03 '17 at 20:20

score 2 · Answer 1 · answered Jun 04 '17 at 13:21

2

This is solved in Interval Analysis.

[1] Tucker Warwick, "Validated Numerics: A Short Introduction to Rigorous Computations", 2011

[2] C++ Toolbox for Verified Computing (C-XSC)

answered Jun 04 '17 at 13:21

rych

4,205

1

Provided that there exists an interval extension of the given $f$... I would also add the references: Ratschek and Rokne, "Computer Methods for the Range of Functions" and Moore, "Introduction to Interval Analysis" – Michael Burr Jun 04 '17 at 13:25

All roots of a non-polynomial function

1 Answers1