如何在Python中实现二分法

Question

我想制作一个Python程序，它将运行一个等分方法来确定：

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

二分法是一种估计多项式f（x）根的数值方法。

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

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

Answer 2

我的实现比其他解决方案更通用，也更简单：（和公共域）

def solve(func, x = 0.0, step = 1e3, prec = 1e-10):
    """Find a root of func(x) using the bisection method.

    The function may be rising or falling, or a boolean expression, as long as
    the end points have differing signs or boolean values.

    Examples:
        solve(lambda x: x**3 > 1000) to calculate the cubic root of 1000.
        solve(math.sin, x=6, step=1) to solve sin(x)=0 with x=[6,7).
    """
    test = lambda x: func(x) > 0  # Convert into bool function
    begin, end = test(x), test(x + step)
    assert begin is not end  # func(x) and func(x+step) must be on opposite sides
    while abs(step) > prec:
        step *= 0.5
        if test(x + step) is not end: x += step
    return x

Answer 3

您可以在前面使用scipy.optimize.bisect的堆栈溢出问题here中看到解决方案。或者，如果您的目的是学习，Wikipedia entry on the bisection method中的伪代码是在Python中进行自己实现的一个很好的指南，正如前面问题的注释者所建议的那样。