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

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然而,根收敛到-3,直到它超时.

当我跑步时,binarySearchIter(f, 0, 3, eps = 1e-10)我得到了正确答案1.4142135623842478.

我显然缺少使函数中断的东西,具体取决于它是否得到(-3,0)或(3,0).

谢谢您的帮助.

Answer 1

你们看到的是,你的功能只可在增加功能,这是真正x**2 - 2之间0和3,但但递减函数,这对于你之间的功能是真正的不工作-3和0.

有几种方法可以修复您的功能.一种方法是交换start和endif 的值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.'