有理多项式的实根隔离

一个小数 $1.324718$ 可以很好地近似 $x^3-x-1$ 的实根，但它没有说误差多大，也没有证明根是唯一的。实根隔离交付另一种答案：一个有理端点区间，里面恰好一个根；所有这样的区间合在一起，覆盖全部实根。近似值随后可以取区间中点，误差由区间宽度保证。

它与普通二分求根的差别在“恰好一个”。例如 $x^2-1$ 在 $-2$ 和 $2$ 都为正，却在里面有两个根；只靠端点是否异号，会把这两个根一起漏掉。这里每次分割之前，先调用Sturm计数确认区间中到底有多少根。

形式陈述

明确输入和交付物

输入是非零的 $F\in\mathbb Q[x]$ ，系数以精确分数给出。输出是一列开区间

I_j=(a_j,b_j),\qquad a_j,b_j\in\mathbb Q,

满足四条条件：

两个端点都不是 $F$ 的根
每个 $I_j$ 恰好含一个不同实根
各区间两两不相交
$F$ 的每个实根都在某个 $I_j$ 中

还可以要求 $b_j-a_j\le\varepsilon$ ，其中 $\varepsilon>0$ 是指定的有理精度。这个附加要求使中点 $m_j=(a_j+b_j)/2$ 满足 $|m_j-\alpha_j|<\varepsilon/2$ 。重数另附在对应区间上，不通过复制区间来表示。

非零常数没有根，直接返回空列表。零多项式在每个实数处都为零，不存在这种有限隔离列表，必须作为不符合输入条件的情形报告。

去重不等于丢掉重数

先求平方自由部分

f=F/\gcd(F,F').

它与 $F$ 的不同根相同，且每个根都简单。若还要恢复重数，同时保存平方自由分解

F=c\prod_{k\ge1}F_k^k,

其中非恒定 $F_k$ 两两互素且平方自由。

接着为 $f$ 建立一条Sturm链，并用根界找整数 $B>0$ ，保证全部实根在 $(-B,B)$ 中。链只建一次，以后在不同端点重复求值即可。记 $N(a,b)=V(a)-V(b)$ 。

三种区间，三种动作

把 $(-B,B)$ 放入待处理列表。每次拿出一个区间 $(a,b)$ ：

若 $N(a,b)=0$ ，丢弃它
若 $N(a,b)=1$ ，且精度已经满足，将它加入输出
若 $N(a,b)>1$ ，或还需要更窄的区间，选择一个非根有理数 $m\in(a,b)$ ，改为处理 $(a,m)$ 与 $(m,b)$

由于 $m$ 不是根，计数满足

N(a,b)=N(a,m)+N(m,b).

因此分割不会在切口丢失根，也不会重复计算它。

最自然的候选是中点。若 $f((a+b)/2)=0$ ，已经发现一个精确有理根，但不能继续把这个根当作“非根端点”。可以专门输出单点并调整邻区间；本页选择更统一的做法：改选附近的非根切口，仍让所有输出都采用开区间。

具体地，若 $n=\deg f$ ，检查中间一半内的 $n+1$ 个有理数

m_j=a+\left(\frac14+\frac{j}{2(n+2)}\right)(b-a), \qquad j=1,\ldots,n+1.

非零 $n$ 次多项式最多有 $n$ 个不同根，所以至少一个候选不是根。它在区间的四分之一与四分之三之间，两个子区间的长度都不超过原长的 $3/4$ 。这个选择同时保证“找得到切口”和“确实缩短区间”。

直觉

为什么没有漏根，也为什么最终会停

在任意一步，每个实根都恰好属于一个已输出区间或一个待处理区间。初始时由根界成立。丢弃计数零的区间不会删掉根；保存计数一的区间不会混入第二个根；非根切口将原区间的根不重不漏地分到两边。因此这个不变量一直成立。

再看终止。 $f$ 只有有限多个不同实根。如果至少有两个，令 $\delta>0$ 为任意两个根之间距离的最小值；若只有一个，分离要求自动满足。沿任何不断细分的分支，第 $d$ 层区间长度至多为

2B(3/4)^d.

当它小于 $\delta$ ，其中不可能再含两个根；若还要求精度，继续缩到不超过 $\varepsilon$ 即可。计数为零的分支立即删除，所以经过有限层，待处理列表必为空。

这个证明并不要求预先知道 $\delta$ 。算法通过计数决定是否继续； $\delta$ 只用来证明它不可能永远继续。若要从输入位数推导显式运行时间，还需要额外的根分离下界。

例子与边界

把一份七次输入算完

考虑展开输入

F=x^7-2x^6-2x^5+5x^4+x^3-3x^2-2x+2.

精确乘法可核验

F=(x-1)^2(x^2-2)(x^3-x-1).

它的首一GCD为 $\gcd(F,F')=x-1$ ，所以平方自由部分是

f=(x-1)(x^2-2)(x^3-x-1),

由根界可取 $B=4$ 。这是一个可读性良好的隔离证书：

区间	来自哪个因子	该因子在两端的值	不同根数	$F$ 中重数
$(-3/2,-11/8)$	$x^2-2$	$1/4,-7/64$	1	1
$(3/4,5/4)$	$x-1$	$-1/4,1/4$	1	2
$(5/4,4/3)$	$x^3-x-1$	$-19/64,1/27$	1	1
$(11/8,3/2)$	$x^2-2$	$-7/64,1/4$	1	1

这些开区间两两不相交；第二和第三个虽然共享端点 $5/4$ ，端点不属于任何一个区间，也不是根。

单看表中的异号还不够，唯一性和完整性需要另外核对。二次因子 $x^2-2$ 的Sturm链为 $(x^2-2,2x,2)$ ，在两个给定区间各计一根，在整个 $(-4,4)$ 共计两根。线性因子只有根一。三次因子的链在上一页已证明全实轴共一根，并将它放在 $(5/4,4/3)$ 。三个因子两两互素，所以合计恰好四个不同实根，没有漏项。

附带的精确核验脚本还直接对六次平方自由部分建链，验证四个区间分别计一根、全区间计四根。因式分解只是让人容易复查的额外证书，隔离算法并不依赖先完成不可约分解。

四个互不相交的有理区间分别包住负平方根、二重有理根、三次无理根和正平方根；每段附不同根数与重数。 — 隔离区间与重数分别记录

推论与应用

怎样把重数放回正确的根

得到 $f$ 的单根区间 $I$ 后，对每个平方自由块 $F_k$ 在 $I$ 中计数。因为这些块两两互素，而 $I$ 只含 $f$ 的一个根，恰有一个块计数为一，其下标 $k$ 就是该根在 $F$ 中的重数。

上例的非恒定块是

F_1=(x^2-2)(x^3-x-1),\qquad F_2=x-1.

因此四个不同实根按重数合计为 $1+2+1+1=5$ ，不是七。另两个根是三次因子的非实共轭根。“多项式次数等于七”不能替代实根计数。

成本与可迁移的证书

若多项式次数为 $n$ ，Sturm链至多 $n+1$ 项，每次端点求值用Horner法可保守地在 $O(n^2)$ 次有理数算术内完成。若有效细分深度为 $D$ ，每层至多有 $n$ 个含根区间，连同其零根兄弟，整个树有 $O(n(D+1))$ 个节点，因此有保守的 $O(n^3(D+1))$ 次有理数算术预算，建链另计。

这不是同样大小的位运算界。余式系数和区间端点分母会增长；小根间距使 $D$ 变大。实际实现可使用适当带符号的子结式技术降低系数膨胀，但必须保持已证明的符号约定。

一份隔离证书至少要保留原系数、平方自由关系、初始根界、输出区间及各端点变号数。把上例的三次因子换成 $x^3-x+1$ 后，先重新计算，不要只把图中的红点移到负半轴；根区间、重数归属与全局计数都需要新的证书。

参考资料

Sturm Theory，§1 “Algorithm for Isolating Real Roots”，PDF第3–4页：计数驱动的区间细分及根间距对复杂性的作用。
Wenda Li、Grant Olney Passmore、Lawrence C. Paulson，Deciding Univariate Polynomial Problems Using Untrusted Certificates in Isabelle/HOL，2018年修订版，§§3–4：实根列表、隔离表示与证书检查的职责区分。本文另给中间半区的有限候选切口，以完整处理恰遇有理根的分支。

形式陈述 ​

明确输入和交付物 ​

去重不等于丢掉重数 ​

三种区间，三种动作 ​

为什么没有漏根，也为什么最终会停 ​

把一份七次输入算完 ​

怎样把重数放回正确的根 ​

成本与可迁移的证书 ​

反向链接