python - 使用递归的函数的二进制搜索根

Question

我正在尝试编写一个二进制搜索函数，以在区间 [𝑠𝑡𝑎𝑟𝑡,𝑒𝑛𝑑] 中找到函数 fun 的根:

这是我所拥有的接近但缺少标记的内容:

def binarySearchIter(fun, start, end,  eps=1e-10):
    '''
    fun: funtion to fund the root
    start, end: the starting and ending of the interval
    eps: the machine-precision, should be a very small number like 1e-10

    return the root of fun between the interval [start, end]
    '''

    root = (start + end)/2
    print(root)

    answer=fun(root)

    if abs(answer) <= eps:
        print(root)
        return root
    elif answer - eps > 0:
        binarySearchIter(fun, start, root, eps=1e-10)
    else:
        binarySearchIter(fun, root, end,  eps=1e-10)

这是我用来测试的函数:

def f(x):
return x ** 2 - 2

当我运行:binarySearchIter(f, -3, 0, eps = 1e-10) 我期望答案为:-1.4142135623842478，然而，root 收敛到-3 直到超时。

当我运行 binarySearchIter(f, 0, 3, eps = 1e-10) 时，我得到了 1.4142135623842478 的正确答案。

我显然遗漏了一些导致函数中断的东西，具体取决于它是 (-3, 0) 还是 (3,0)。

感谢您的帮助。

Answer 1

您看到的是您的函数仅适用于递增函数，对于 x**2 - 2 也是如此。在 0 之间和 3 , 但不适用于递减函数，这对于 -3 之间的函数是正确的和 0 .

修复函数的方法有多种。一种方法是交换 start 的值和 end如果fun(start) > fun(end) .换句话说，改变你的行 root = (start + end)/2到三行

if fun(start) > fun(end):
    start, end = end, start
root = (start + end)/2

这确实会减慢您的日常事件，因此有更好的方法来完成您的日常事件。特别是，使用迭代而不是递归。与迭代相比，Python 执行递归的速度相当慢。

但是，您的函数并不健壮。您应该首先检查 fun(start)和 fun(end)有不同的标志。然后您的例程将继续重新定义 start和 end使他们的图像继续具有相反的符号。如果符号相同，那么你的函数在那个区间内可能没有根，你的例程肯定没有好的方法来决定继续搜索哪一半区间。一种方法是在我已经插入的行之前添加这两行:

if fun(start) * fun(end) > 0:
    raise 'Endpoints in binarySearchIter should yield opposite signs.'