有效地确定多项式是否在区间[0，T]中具有根 [英] efficiently determining if a polynomial has a root in the interval [0,T]

问题描述

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

I have polynomials of nontrivial degree (4+) and need to robustly and efficiently determine whether or not they have a root in the interval [0,T]. The precise location or number of roots don't concern me, I just need to know if there is at least one.

现在，我正在使用区间算术作为快速检查，以查看是否可以证明不存在任何根.如果不能，我正在使用詹金斯-特劳布(Jenkins-Traub)来求解多项式根的 all .这显然是低效的，因为它要检查所有真实的根源并找到它们的确切位置，而这些信息我最终都不需要.

Right now I'm using interval arithmetic as a quick check to see if I can prove that no roots can exist. If I can't, I'm using Jenkins-Traub to solve for all of the polynomial roots. This is obviously inefficient since it's checking for all real roots and finding their exact positions, information I don't end up needing.

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

Is there a standard algorithm I should be using? If not, are there any other efficient checks I could do before doing a full Jenkins-Traub solve for all roots?

例如，我可以做的一种优化是检查我的多项式f(t)在0和T处是否具有相同的符号.如果是这样，我可以求出f'(t)的根，并在区间[0，T]中对f'的所有根求f.当且仅当所有这些评估均具有与f(0)和f(T)相同的符号时，f(t)才在该间隔中没有根.这样可以将我必须求根的多项式的阶数减少1.不是一个巨大的优化，但总比没有好.

For example, one optimization I could do is to check if my polynomial f(t) has the same sign at 0 and T. If not, there is obviously a root in the interval. If so, I can solve for the roots of f'(t) and evaluate f at all roots of f' in the interval [0,T]. f(t) has no root in that interval if and only if all of these evaluations have the same sign as f(0) and f(T). This reduces the degree of the polynomial I have to root-find by one. Not a huge optimization, but perhaps better than nothing.

推荐答案

Sturm定理使您可以计算(a, b)范围内的实根数.给定根数，您知道是否至少有一个.从本文第4页的下半部分开始:

Sturm's theorem lets you calculate the number of real roots in the range (a, b). Given the number of roots, you know if there is at least one. From the bottom half of page 4 of this paper:

让f(x)是一个实多项式.用f0(x)表示它，并用f1(x)表示它的导数f'(x).按照Euclid算法中的步骤进行查找

Let f(x) be a real polynomial. Denote it by f0(x) and its derivative f′(x) by f1(x). Proceed as in Euclid's algorithm to find

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)的度数.其余符号与Euclid算法中的符号相反.

where fk is a constant, and for 1 ≤ i ≤ k, fi(x) is of degree lower than that of fi−1(x). The signs of the remainders are negated from those in the Euclid algorithm.

请注意，最后一个不消失的余数fk(或当fk = 0时为fk-1)是最大的共同点 f(x)和f'(x)的除数.序列f0，f1.... . .，fk(或当fk = 0时为fk-1)被称为多项式f的Sturm序列.

Note that the last non-vanishing remainder fk (or fk−1 when fk = 0) is a greatest common divisor of f(x) and f′(x). The sequence f0, f1,. . ., fk (or fk−1 when fk = 0) is called a Sturm sequence for the polynomial f.

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

Theorem 1 (Sturm's Theorem) The number of distinct real zeros of a polynomial f(x) with real coefficients in (a, b) is equal to the excess of the number of changes of sign in the sequence f0(a), ..., fk−1(a), fk over the number of changes of sign in the sequence f0(b), ..., fk−1(b), fk.

这篇关于有效地确定多项式是否在区间[0，T]中具有根的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！