有效确定多项式是否在区间 [0,T] 内有根

我有非平凡次数 (4+) 的多项式，需要稳健有效地确定它们是否在区间 [0,T] 中具有根。根的精确位置或数量与我无关，我只需要知道是否至少有一个。

现在我正在使用区间算术作为快速检查，看看是否可以证明不存在根。如果我不能，我使用 Jenkins-Traub 来解决all的多项式根。这显然效率低下，因为它会检查所有真实的根并找到它们的确切位置，而这些信息是我最终不需要的。

我应该使用标准算法吗？如果没有，在对所有根进行完整的 Jenkins-Traub 求解之前，我可以做任何其他有效的检查吗？

例如，我可以做的一项优化是检查多项式 f(t) 在 0 和 T 处是否具有相同的符号。如果不是，则区间中显然存在根。如果是这样，我可以求解 f'(t) 的根，并在区间 [0,T] 内的 f' 的所有根处评估 f。当且仅当所有这些评估具有与 f(0) 和 f(T) 相同的符号时，f(t) 在该区间内没有根。这将我必须求根的多项式的次数减少了 1。虽然不是一个巨大的优化，但也许总比没有好。

斯特姆定理 http://en.wikipedia.org/wiki/Sturm's_theorem让您计算范围内的实根数(a, b)。给定根的数量，您就知道是否至少有一个。从本文第 4 页的下半部分开始：

设 f(x) 为实多项式。用 f0(x) 表示它，用 f1(x) 表示它的导数 f′(x)。按照欧几里得算法进行求解

f0(x) = q1(x) · f1(x) − f2(x),
f1(x) = q2(x) · f2(x) − f3(x),
.
.
.
fk−2(x) = qk−1(x) · fk−1(x) − fk,

其中 fk 是常数，对于 1 ≤ i ≤ k，fi(x) 的次数低于 fi−1(x) 的次数。余数的符号与欧几里得算法中的符号相反。

请注意，最后一个非零余数 fk（或当 fk = 0 时为 fk−1）是最常见的 f(x) 和 f′(x) 的除数。序列f0，f1，。 。 ., fk （或 fk−1，当 fk = 0 时）被称为多项式 f 的 Sturm 序列。

定理 1（斯图姆定理）多项式 f(x) 的不同实零点的数量 (a, b) 中的实系数等于序列 f0(a), ..., fk−1(a), fk 中符号变化次数除以序列中符号变化次数之差f0(b), ..., fk−1(b), fk。