我有非平凡次数（4+）的多项式，需要稳健有效地确定它们是否在区间 [0,T] 中有根。根的精确位置或数量与我无关，我只需要知道是否至少有一个。
现在我正在使用区间算术作为快速检查，看看我是否可以证明不存在根。如果不能，我将使用 Jenkins-Traub 来求解所有多项式根。这显然是低效的，因为它正在检查所有真正的根并找到它们的确切位置，而我最终不需要的信息。
我应该使用标准算法吗？如果没有，在对所有根进行完整的 Jenkins-Traub 求解之前，我还能做其他有效的检查吗？
例如，我可以做的一种优化是检查我的多项式 f(t) 在 0 和 T 处是否具有相同的符号。如果不是，则区间中显然有一个根。如果是这样，我可以求解 f'(t) 的根，并在区间 [0,T] 内计算 f' 的所有根处的 f。当且仅当所有这些评估与 f(0) 和 f(T) 具有相同的符号时，f(t) 在该区间中没有根。这将我必须求根的多项式的次数减少了一个。不是一个巨大的优化，但也许总比没有好。
Sturm 定理可让您计算范围内的实根数(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 (Sturm's Theorem) 在 (a, b) 中具有实系数的多项式 f(x) 的不同实零的数量等于序列 f0(a), ... ., fk-1(a), fk 超过序列 f0(b), ..., fk-1(b), fk 中符号变化的次数。
您当然可以对区间算术进行二进制搜索。从 [0,T] 开始并将其代入您的多项式。如果结果区间不包含 0，那么您就完成了。如果是这样，则将间隔除以 2 并在每一半上递归。该方案将很快找到每个根的大致位置。
如果你最终得到 4 个独立的间隔，你就知道你已经完成了。否则，我认为您需要到达区间 [x,y]，其中 f'([x,y]) 不包含零，这意味着该函数单调递增或递减，因此最多包含一个零。双根可能会出现问题，我不得不考虑更多。
编辑：如果您怀疑有多个根，请使用相同的过程查找 f' 的根。
使用笛卡尔符号规则收集一些信息。只需计算系数中符号变化的数量即可。这为您提供了正实根数的上限。考虑多项式 P。
P = 131.1 - 73.1*x + 52.425*x^2 - 62.875*x^3 - 69.225*x^4 + 11.225*x^5 + 9.45*x^6 + x^7
事实上，我已经将 P 构造成一个简单的根列表。他们是...
{-6, -4.75, -2, 1, 2.3, -i, +i}
我们能确定区间[0,3]中是否有根吗？请注意，端点处的 P 值没有符号变化。
P(0) = 131.1
P(3) = 4882.5
P的系数有多少个符号变化？有 4 个符号变化，因此可能有多达 4 个正根。
但是，现在用 x+3 代替 x 到 P 中。因此
Q(x) = P(x+3) = ...
4882.5 + 14494.75*x + 15363.9*x^2 + 8054.675*x^3 + 2319.9*x^4 + 370.325*x^5 + 30.45*x^6 + x^7
看到 Q(x) 的系数没有符号变化。所有系数均为正值。因此，不可能有大于 3 的根。
所以区间 [0,3] 中可能有 2 个或 4 个根。
至少这告诉你是否要费心去看。当然，如果函数在区间的每一端都有相反的符号，我们知道该区间有奇数个根。
如果该值f(0)*f(t)<=0，则保证您有根。否则，您可以开始将域分成两部分（二等分）并检查末端的值，直到您确信该段中没有根。
如果f(0)*f(t)>0您没有，两个，四个，.. 根。您的限制是多项式顺序。如果f(0)*f(t)<0你可能有一个、三个、五个、.. 根。