I would like to find all roots of a nonlinear equation in one variable, e.g., f(x) = 0.

26 views (last 30 days)
I would like to find all roots of a nonlinear equation in one variable, e.g., f(x) = 0.
The maximum possible number of solutions can be determined theoretically.
The unknown variable x is an angle, so it changes in the range [0, 2pi).
The function f(x) is continuous.
There needs an algorithm that can automatically find all the solutions for this nonlinear equation.
I know there is a function called fzero in MATLAB; however, one needs to give parameters x0 and x1 which make f(x0) and f(x1) have opposite signs. I do not know how to find the parameters for the fzero using an algorithm.
  4 Comments
Blue Bird
Blue Bird on 4 Nov 2018
I think it is possible to know the lower bound on the distance between the roots. I am not sure I can do this for now, and I will try. To prevent wasting your enthusiasm, I will come back for the next move if I successfully find the lower bound.

Sign in to comment.

Answers (3)

Torsten
Torsten on 30 Oct 2018
Edited: Torsten on 30 Oct 2018
- Select number of subintervals N of [0:2*pi)
- Set x(i)=2*pi*(i-1)/N (i=1,...,N+1)
- Evaluate f(x)
Begin Loop from i=1:N
- Check whether f(x(i))*f(x(i+1))<=0 (i=1,...,N)
- If yes: call fzero in the interval [x(i) x(i+1)] and store the root.
End Loop
  2 Comments
Torsten
Torsten on 30 Oct 2018
Edited: Torsten on 30 Oct 2018
This is the most reliable way to check for all roots of a continuous function of one variable in a specified interval.

Sign in to comment.


Walter Roberson
Walter Roberson on 4 Nov 2018
In the general case, there exist functions for which it has been shown that there is no theoretical way to know the number of zeros, and where no amount of information about the value of the function at other locations can predict whether the function is zero at a particular location.
fzero treats the function as a "black box", something that it just calls upon to get a result without knowing anything about how the function computes the results. The pure mathematics of finding zeros of a continuous black box function has not progressed much since Runge Kutta methods, when it was shown that there is a hierarchy of increasingly complicated methods of increasing acceleration: methods that require more and more continuity assumptions and which become less and less practical to implement.
In the case where the function is available as an analytic expression, such as with the symbolic toolbox, there has been progress in calculation of roots of specialized functions, including elliptic curves. Those are topics better addressed through dedicated advanced packages, or packages such as Mathematica or Maple. MATLAB's symbolic toolbox team does not have nearly the resources of those kinds of products, to keep on the forefront of analysis.
  5 Comments
Bruno Luong
Bruno Luong on 5 Nov 2018
Edited: Bruno Luong on 5 Nov 2018
reference please
I think in one sentence you get a nimble mix between root of real uni-variate function (fzero), multivaririate least-square (fsolve) that bases indeed on optimization technique, and finally ode solver (runge-kutta).
Not talking about just balancing the elliptic curve through the bunch....

Sign in to comment.


John D'Errico
John D'Errico on 4 Nov 2018
Edited: John D'Errico on 4 Nov 2018
As has been said, unless you can limit the nastiness of your function, one can construct functions whee you cannot know the number of zeros. But if you are willing to restrict the function so that you "know" that no too roots lie within some delta of each other, then the answer is simple. Just sample the function at a set of points with a higher resolution than delta. dx = delta/2-eps(delta/2) should suffice. If you see a sign change between any such sample points, then you have a bracketed root. Just call fzero with that bracket.
Is there something more sophisticated? No, if your function can be completely general.
So, if you want to search for all roots of
fun = @(x) sin(1./x).*x
in the half open interval (0,1]? It is a simple function to write, but finding all such roots numerically using the function as a black box will be impossible, since the derivatives of fun get pretty crazy, and the roots get arbitrarily close together.
Of course, if you restrict the interval of interest to be [0.125,0.25], then the problem will be solvable, since then the roots can be bracketed.
As far as fzero going back 40 years or more, so what? fzero is still pretty much state of the art in this respect, and there is no mathemagics that have been invented since to change that fact.
  1 Comment
Bruno Luong
Bruno Luong on 4 Nov 2018
Edited: Bruno Luong on 4 Nov 2018
There is even a more nasty example Weierstrass function, a strange beast. I believe whenever there is a root, there are an infinity other next to it. Therefore there is no way a bracket can help to isolate a root.
The function is continuous everywhere, before anyone asks.

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by