问多项式求根二分法

EN

根可以是负的也可以是正的这一事实与二分法无关。根的存在可以用微积分中的intermediate value theorem来证明。

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

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

许多寻根器允许用户提供一个或多个起始点来开始搜索。这允许用户尝试“摆弄”结果以找到不同的根，或者允许查找器收敛到根。

如果允许用户提供起始值没有任何意义，您可以从几个点开始：

• -1，0，1
• -10，0，10
• -100，0,100
• etc.

如果输入是一个奇数多项式，这最终会发现一个适合二等分的范围。如果输入是偶数多项式，您可能永远不会捕捉到符号的变化(考虑f(x)=x^2 --它永远不会是负的)，所以在遇到某个(可配置的？)探测量。

我建议在这里将范围扩大10的幂；由于二等分方法每次将范围减半，可能这太保守了。(需要两次到三次二等分迭代才能将范围缩小到下一个“更紧”的括号。)也许更好的是更大的跳跃：

1000

• -100000，

-10，0，1

• -10，0，1
• -1000，0，英特尔0，#en0#0，英特尔

这将执行较少的探测，但需要更多的二等分。尝试几个多项式，并跟踪执行时间以找到这两个建议的根。

为了使用二分法，首先需要找到一个包含根的区间。此操作的标准算法在Sturm's Theorem中给出。

但是，标准的二等分算法期望端点中函数值的符号不同。这可能是个问题。最简单的例子是x^2，它有一个2阶的根0。由于x^2对于所有非零的x都是正的，所以您找不到适合用于二等分算法的包含根的区间。