用二分法求多项式的根

Question

我是python的新手，我很难用二等分法来找到多项式的根。到目前为止，我有两种方法。在x值处求多项式的一个

 def eval(x, poly):
 """
Evaluate the polynomial at the value x.
poly is a list of coefficients from lowest to highest.

:param x:     Argument at which to evaluate
:param poly:  The polynomial coefficients, lowest order to highest
:return:      The result of evaluating the polynomial at x
"""

result = poly[0]
for i in range(1, len(poly)):
  result = result + poly[i] * x**i

return result

下一种方法是用二分法求多项式的根

^{pr2}$

用二等分法求根呢？我得到了一个测试脚本来测试这些。在

编辑：我跟踪了伪代码，最后得出了这样的结论：

def bisection(a, b, poly, tolerance):
#poly(a) <= 0
#poly(b) >= 0
difference = abs(a-b)
xmid = (a-b)/2
n = 1
nmax = 60




while n <= nmax:
 mid = (a-b) / 2
 if poly(mid) == 0 or (b - a)/2 < tolerance:
       print(mid)

 n = n + 1
 if sign(poly(mid)) == sign(poly(a)):
     a = mid
 else:
     b = mid


return xmid

这是对的吗？由于返回xmid语句的缩进错误，我无法对其进行测试。在

Answer 1

除了xmid和{}的混乱之外，您的代码看起来还不错。mid = (a + b) / 2而不是mid = (a - b) / 2，而且您不需要difference变量。在

清理了一下：

def sign(x):
  return -1 if x < 0 else (1 if x > 0 else 0)

def bisection(a, b, poly, tolerance):
  mid = a # will be overwritten
  for i in range(60):
    mid = (a+b) / 2
    if poly(mid) == 0 or (b - a)/2 < tolerance:
      return mid
    if sign(poly(mid)) == sign(poly(a)):
      a = mid
    else:
      b = mid
  return mid

print(bisection(-10**10, 10**10, lambda x: x**5 - x**4 - x**3 - x**2 - x + 9271, 0.00001))