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

Question

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

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

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

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

Answer 1

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

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