如何在 Python 中执行二分法

Question

我想制作一个 Python 程序，它将运行二分法来确定以下项的根：

 f(x) = -26 + 85x - 91x2 +44x3 -8x4 + x5

二分法是一种用于估计多项式 f(x) 的根的数值方法。

是否有任何可用的伪代码、算法或库可以用来告诉我答案？

原文由 Scrubatpython 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

基本技术

这是一些显示基本技术的代码：

 >>> def samesign(a, b):
        return a * b > 0

>>> def bisect(func, low, high):
    'Find root of continuous function where f(low) and f(high) have opposite signs'

    assert not samesign(func(low), func(high))

    for i in range(54):
        midpoint = (low + high) / 2.0
        if samesign(func(low), func(midpoint)):
            low = midpoint
        else:
            high = midpoint

    return midpoint

>>> def f(x):
        return -26 + 85*x - 91*x**2 +44*x**3 -8*x**4 + x**5

>>> x = bisect(f, 0, 1)
>>> print(x, f(x))
0.557025516287 3.74700270811e-16

宽容

要在达到给定的公差时提前退出，请在循环末尾添加一个测试：

 def bisect(func, low, high, tolerance=None):
    assert not samesign(func(low), func(high))
    for i in range(54):
        midpoint = (low + high) / 2.0
        if samesign(func(low), func(midpoint)):
            low = midpoint
        else:
            high = midpoint
        if tolerance is not None and abs(high - low) < tolerance:
            break
    return midpoint

原文由 Raymond Hettinger 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

您可以在 此处 使用 scipy.optimize.bisect 的早期 Stack Overflow 问题中看到解决方案。或者，如果您的目的是学习， 维基百科条目中关于二分法 的伪代码是一个很好的指南，可以帮助您在 Python 中实现您自己的实现，正如之前问题的评论者所建议的那样。

原文由 Simon 发布，翻译遵循 CC BY-SA 4.0 许可协议