Finding all roots in a given interval in 1d

Question

In order to complement the question raised here, I would like to ask how I can find all roots in a certain interval, up to some granularity. Right now I use the poor man's approach and find roots by

import numpy as np
x = np.linspace(0,10,1000)
data = np.sin(x)
roots = (np.abs(data) < 0.1)
# Cluster the data using some other poor man's approach

What does `roots = (np.abs(data) < granularity)` do? What is the meaning of "granularity"? That is, what does it represent? OK, now from the last edit it is clear. Thanks! — AGN Gazer, Jul 18 '17 at 18:16
Can you evalueate the function when looking for the roots or do you only have sampled data? — MB-F, Jul 19 '17 at 06:12
Do you know that all roots are real only? If the come in complex conjugate pairs you will miss many of them. — Jon Custer, Jul 19 '17 at 13:38
@kazemakase: I have a well behaved function, which can be sampled over arbitrary intervals. — varantir, Jul 19 '17 at 14:35

score 1 · Answer 1 · answered Jul 19 '17 at 08:15

It should be obvious that without any information on the function at hand, the poor man's approach is optimal (in some probabilistic sense).

Because the roots of general functions a spread uniformly and independently of each other, so that unequal steps, possibly based on the function values, would be a waste of time.

You are in a better position when you can exploit some property of the function. For instance, if you have a bound on the derivative in an interval, for suitable values of the function at the endpoints you can show that no root can be present.

score 0 · Answer 2 · answered Jul 18 '17 at 18:29

I do not think there is a magical method that would find all roots of a general equation. Your "poor man's approach" is not too bad to start with. I would use product instead of |data|<eps. For example,

dp = data[1:] * data[:-1]
indices = np.where(dp <= 0)

would provide the location of the "suspicious" intervals. Then you can run a better method providing as initial guess every such suspicious interval's center coordinate. A more sophisticated method maybe could adapt to the slope and adjust function sampling instead of having a constant one like you get with linspace().

Finding all roots in a given interval in 1d

2 Answers2