math - 有效地确定多项式在区间 [0,T] 中是否有根

Question

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

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

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

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

Answer 1

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 = 0 时 fk−1)被称为多项式 f 的 Sturm 序列。

定理 1(Sturm 定理)多项式 f(x) 的不同实零点数
(a, b) 中的实系数等于序列 f0(a), ..., fk−1(a), fk 中符号变化次数超过序列中符号变化次数的余量f0(b), ..., fk−1(b), fk。