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

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.

[KSSV]

fzero needs one initial point...read the documentation once.

[Blue Bird]

I understand the setting that you mentioned; however, it finds a root and exists.

I need a method that searches the entire range. The MATLAB has a global optimization toolbox. Will is it helpful?

[Matt J]

You also need to know a lower bound on the distance between the roots.

[Blue Bird]

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.

Answer 1

[Torsten]

- 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

[Blue Bird]

Testing it one by one can be a method.

I think I am a little hyper-critical, but this software calls Mathematical laboratory (The MATLAB means matrix laboratory, actually). The reference of function fzero was published in 1973. Are there any mathematical ways that have been tested in these years?

[Torsten]

This is the most reliable way to check for all roots of a continuous function of one variable in a specified interval.

Answer 2

[Walter Roberson]

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.

[Bruno Luong]

Now it's new to me : What Runge-Kutta has to do with finding zero(s) of function?

[John D'Errico]

Bruno - actually, you CAN use an ODE solver to find roots of a function, using homotopy continuation methods. Garcia and Zangwill wrote a book on the topic.

https://archive.org/details/PathwaysToSolutionsFixedPointsAndEquilibria/page/n17

[Bruno Luong]

Thanks, look like pretty exotic method to solve a big problem when one have a continuous family of simpler problem to solve by tracking.

FZERO uses however much standard technique

"Algorithms

The fzero command is a function file. The algorithm, created by T. Dekker, uses a combination of bisection, secant, and inverse quadratic interpolation methods. An Algol 60 version, with some improvements, is given in [1]. A Fortran version, upon which fzero is based, is in [2].

References

[1] Brent, R., Algorithms for Minimization Without Derivatives, Prentice-Hall, 1973.

[2] Forsythe, G. E., M. A. Malcolm, and C. B. Moler, Computer Methods for Mathematical Computations, Prentice-Hall, 1976. "

[Walter Roberson]

Runge Kutta methods are a family of ways of estimating derivatives with control of error bounds. Estimating derivatives can be used to find zeros by looking for the extrema of f(x)^2 by way of solving for a derivative of 0, which is sometimes easier than finding a zero of the original function.

[Bruno Luong]

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....

Answer 3

[John D'Errico]

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.

[Bruno Luong]

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.