algorithm - 多项式求根二分法

Question

如果我使用二分法求多项式的根，在某些情况下，根据多项式的不同，根可能为负，也可能为正。

我知道我可以根据多项式的计算结果确定根是负数还是正数...但是我不确定我将使用什么作为 x。

谁能在这里提供任何见解？

Answer 1

根可以是负的也可以是正的，这与二分法无关。可以使用 intermediate value theorem 证明根的存在来自微积分。

因此，您所要做的就是找到点 x1 和 x2 使得 y(x1) 为负且 y( x2) 为正。然后你从 IVT 知道 x1 和 x2 之间有一个根。您可以通过对该时间间隔进行二分搜索来做到这一点。如果 y(x3) = y((x1+x2)/2) 为负，则您在区间 [x3,x2] 上重复二分搜索。否则，如果它是正数，则在区间 [x1,x3] 上搜索。

根是负的还是正的并不重要。我不确定这是否能回答您的问题，但我希望这能帮助您理解该算法。