6

基本上，给定一个针对不同参数产生类似输出的函数：

在此处输入图像描述

我想快速找到函数等于 0 的第一个 x。因此，对于在 x 上产生蓝色曲线的参数，我想找到 x=134。对于绿色曲线，我想找到 x=56 等。

我认为该函数将始终单调递减，直到达到零，但我不完全确定。

该函数不一定是单调递减的。

我确信它只会命中 0 一次，然后保持为零。

目前我通过迭代 x 值直到我达到零来强制它，但我想要一些能更好地做出有根据的猜测（基于斜率？）和迭代的东西。

理想情况下，我想使用一些已经成熟的东西（因为 90% 的程序员甚至无法正确编写二进制搜索），比如scipy.optimize中的东西，但似乎那些人都想找到一个全局最小值或零-穿越。

（这个函数有点像 Lch 颜色空间中给定色度的 RGB 立方体的 distance_to_the_wall （所以基本上是构建一个“合理地剪辑到 RGB”函数），但是由于 IRGB 和 LCh 之间的映射可能因库和参数而异发光体等。我认为最好只尝试几个值，直到找到正确的值，而不是尝试直接反向计算值？）

4

3 回答 3

2

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

于 2013-04-11T23:54:48.910 回答
2

这是一些充实@ExP的二分/二分搜索答案的代码：

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
于 2013-04-12T00:44:45.467 回答
0

如果不是因为曲线的右手处处处为 0，牛顿的方法（https://en.wikipedia.org/wiki/Newton's_method）会很好用。但我认为一个变体仍然可以正常工作：

1）选择一个点。

2）如果我们在斜坡上，则在本地获取斜坡的梯度并从那里追踪一条线到 x 截距并将其作为您的新点（转到 1））。

3）如果我们在平坦的平原上（x = 0，导数 = 0），那么如果左边一点是斜坡（必须调整它以找出剩下多少要检查），然后进行局部搜索（可能是带公差的二分搜索）找到函数首先等于零的点。如果不是，则取该点和我们尝试过的斜坡上最后一个点之间的中间点（使用这个新点转到 1）。

要估计导数（以确定您是否在斜坡上），您可以在左侧和右侧采样一个点，距离足够远，您确信您将获得导数的平滑近似值。

于 2013-04-11T23:50:15.717 回答