施图姆定理

在数学中，单变量多项式 p 的斯特姆序列是与 p 及其导数相关的多项式序列，由欧几里德多项式算法的变体得出。 施图姆定理用Sturm序列值在区间边界处符号变化的次数来表示位于区间内的p的不同实根的个数。 应用于所有实数的区间，它给出了 p 的实根总数。

虽然代数基本定理很容易得出复数根的总数，但它没有提供计算它们的程序。 施图姆定理计算不同实根的数量并将它们定位在区间内。 通过细分包含一些根的区间，它可以将根隔离成任意小的区间，每个区间只包含一个根。 这产生了最古老的实根隔离算法和单变量多项式的任意精度寻根算法。

对于实数计算，施图姆定理的效率低于其他基于笛卡尔符号规则的方法。 然而，它适用于每个实数封闭域，因此，对于实数一阶理论中可判定性和量词消去的计算复杂性的理论研究来说，它仍然是基础。

Sturm 序列和施图姆定理以 1829 年发现该定理的 Jacques Charles François Sturm 的名字命名。

具有实系数的单变量多项式 P(x) 的斯特姆链或斯特姆序列是多项式 P 0 , P 1 , … ,

P 的 Sturm 序列的 ξ 处的符号变化数是实数序列中符号变化的数量——忽略零

这个符号变化的数量在这里表示为 V(ξ)。

施图姆定理指出，如果 P 是无平方多项式，则 P 在半开区间 (a, b] 中的不同实根的数目是 V(a) − V(b)（这里，a 和 b是实数使得a＜b)。

通过将多项式 +∞ 处的符号定义为其首项系数（即最高阶项的系数）的符号，该定理扩展到无界区间。 在 –∞ 处，多项式的符号是偶数次多项式的前导系数的符号，奇数次多项式的符号相反。

在非无平方多项式的情况下，如果 a 和 b 都不是 p 的重根，则 V(a) − V(b) 是 P 的不同实根的数量。

接下来将 p1 除以 p2 并将余数乘以 -1

现在将 p2 除以 p3 并将余数乘以 -1

由于这是一个常量，这就完成了 Sturm 序列的计算。

要找到 p 0 {displaystyle p_{0}} 的实根数，必须计算这些多项式在 −∞ 和 ∞ 处的符号序列。