Quickly find the first point at which the function is 0 using scipy.optimize

Question

In principle, if a function is specified that produces such output for different parameters:

I want to quickly find the first x in which the function is 0. So, with the parameters that create the blue curve over x, I want to find x = 134. For the green curve, I want to find x = 56, etc.

I think that the function will always decrease monotonously until it reaches zero, but I'm not quite sure.

Function is not necessarily monotonously reduced.

I am sure that it will hit only once and then remain zero.

I am currently rudely forcing it by iterating over the x values ​​until it reaches zero, but I need something that is better for getting educated guesses (based on the slope?) And iterating.

Ideally, I want to use something already baked ( since 90% of programmers can't even write binary search correctly ), for example something from scipy.optimize , but it seems like everyone wants to find either a global minimum or a zero intersection.

(This function is a kind of distance to the RGB cube for a given color in the Lch color space (thus, basically creating the "reliable clip for RGB" function), but since the display between IRGB and LCh may vary depending on the library and with such parameters , as a light source, etc. I think it’s best to just try a few values ​​until the correct one is found, and not try to reprogram the value directly?)

Answer 1

Here is some code to retrieve @ExP bisection / binary search response:

def find_first_zero(func, min, max, tol=1e-3): min, max = float(min), float(max) assert (max + tol) > max while (max - min) > tol: mid = (min + max) / 2 if func(mid) == 0: max = mid else: min = mid return max 

Answer 2

Try bisection : check if it is 0 in the middle of your interval; if so, continue on the left, otherwise, on the right. Do the same with the reduced interval recursively until you are close enough. This method has O (log n) complexity compared to yours, which is O (n).

Answer 3

If it were not for the fact that the right-hand side of curve 0 is everywhere, the Newton method ( https://en.wikipedia.org/wiki/Newton 's_method ) will work just fine. But I think the option will still work fine:

1) Select a point.

2) If we are on a slope, take the gradient of the slope locally and trace the line from there to intercept x and take it as a new point (go to 1)).

3) If we are on a flat plain (x = 0, derivative = 0), then if the bit to the left is a slope (you would need to configure this to find out how much to check), then do a local search (probably a binary search with tolerance) to find the point at which the function is initially zero. If not, then take the point that is the middle between this point and the last point on the slope we tried (go to 1 with this new point).

To evaluate the derivative (to determine whether you are on a slope or not), you can try the point left and right, far enough so that you are sure that you will get a smooth approximation of the derivative.