多项式的根界 | Codeboy's Blog

想找到多项式 $f(x)=x^3-x-1$ 的所有实根，先得知道应该搜到哪里。画出 $[-2,2]$ 里的曲线，看不到区间外有没有另一个零点；把图画得更宽，也没有回答“多宽才够”。根界把这个无限搜索问题变成有限范围：只看系数，就能证明范围外绝不可能有根。

本页只做位置保证。它不会告诉我们范围内有几个实根，更不会把复根变成实根。下一步的Sturm 计数正是用来回答数量问题的。

若要在复平面里按簇计数，Pellet圆盘证书先将多项式移到候选圆心，再用一项严格胜过其余项来认证盘内总重数。多只不相交圆盘的计数和等于固定次数时，才得到全部根簇覆盖；系数外界本身仍只提供位置，不代替这些局部整数与完整性检查。

形式陈述

从最高次项与其余项的竞争开始

设

f(z)=a_nz^n+a_{n-1}z^{n-1}+\cdots+a_0, \qquad n\ge1,\quad a_n\ne0,

系数可以是复数。记

M=\max_{0\le k<n}\left|\frac{a_k}{a_n}\right|, \qquad R=1+M.

Cauchy 根界说：每个复根 $\alpha$ 都满足

\boxed{|\alpha|<R.}

这里比较的是低次项系数与首项系数的比值。把整个多项式乘以任何非零常数，所有比值不变，根界也不变；这符合根本来就没有改变的事实。

对 $x^3-x-1$ ，低次系数是 $0,-1,-1$ ，所以 $M=1$ ，全部复根都在 $|z|<2$ 内。特别地，全部实根都在开区间 $(-2,2)$ 内，而且 $\pm2$ 肯定不是根。这个严格不等式使它可以直接接入要求端点非根的实根计数。

直觉

为什么根跑不出去

先处理 $M=0$ ：此时 $f(z)=a_nz^n$ ，唯一的不同根是零，结论成立。以下设 $M>0$ 。

|a_n|r^n =\left|\sum_{k=0}^{n-1}a_k\alpha^k\right| \le\sum_{k=0}^{n-1}|a_k|r^k \le |a_n|M\sum_{k=0}^{n-1}r^k.

因为 $r>1$ ，有限几何和满足

\sum_{k=0}^{n-1}r^k=\frac{r^n-1}{r-1}<\frac{r^n}{r-1}.

消去正数 $|a_n|r^n$ ，得到 $1<M/(r-1)$ ，也就是 $r<1+M$ 。

这个证明的机制很具体：当 $r$ 太大时，最高次项的大小超过所有低次项大小之和，低次项即使尽力朝相反方向相加，也无法将它抵消成零。不需要预先知道根的表达式。

例子与边界

变量缩放会改变界的松紧

根界是一份正确证书，但不一定紧。对 $f(x)=x^2-100$ ，直接计算得到 $|\alpha|<101$ ，而实际根是 $\pm10$ 。原因是系数比较没有利用不同次数的尺度。

令 $x=ty$ ，其中 $t>0$ ，并除以新的首项系数：

\frac{f(ty)}{a_nt^n} =y^n+\sum_{k<n}\frac{a_k}{a_nt^{n-k}}y^k.

对 $y$ 的根应用根界，再乘回 $t$ ，可得

|\alpha|<t\left(1+\max_{k<n}\frac{|a_k/a_n|}{t^{n-k}}\right).

在 $x^2-100$ 中取 $t=10$ ，变成 $y^2-1$ ，于是得到 $|\alpha|<20$ 。这比101小得多，且每一步都是有理数运算。缩放并没有求出根，只是换了更合适的长度单位。

如果只需要一个安全初始区间，没有必要为了最紧的界先解另一个困难的优化问题。对有理系数，取一个不小于 $R$ 的整数 $B$ ，则 $(-B,B)$ 已经包含全部实根。严格根界保证即使 $B=R$ ，端点也不会碰根。

三种不能从根界读出的信息

根界不证明有实根。 $x^2+1$ 也给出 $R=2$ ，但其中没有实根。根界的意思是“如果有根，它一定在这里”，不是“这里一定有实根”。

根界不是根间距。 $(x-1)(x-1-1/N)$ 的两个根相距 $1/N$ ，而系数和一个粗根界都可以一直保持在固定尺度。实根隔离的细分次数会受到这个小间距影响，不能只看 $R$ 就宣布所需精度固定。

近似系数需要额外误差数据。 若某项只知道约等于 $0.001$ ，把它当成精确的有理数 $1/1000$ 得到的是另一个多项式的证书。要处理测量系数，必须为每项给出包含真值的界，并为首项绝对值提供严格正下界，再用这些上、下界控制系数比值。

推论与应用

倒过来，还能把根与零隔开

若 $a_0\ne0$ ，零不是根，可以对倒数多项式

f^*(z)=z^nf(1/z)=a_0z^n+a_1z^{n-1}+\cdots+a_n

再用一次同样的界。 $\alpha$ 是 $f$ 的根，当且仅当 $1/\alpha$ 是 $f^*$ 的根。因此令

R^*=1+\max_{1\le k\le n}\left|\frac{a_k}{a_0}\right|,

便有

\boxed{\frac1{R^*}<|\alpha|<R.}

对 $x^3-x-1$ ， $R=R^*=2$ ，所以每个根的模都在 $1/2$ 与 $2$ 之间。这说明 $[-1/2,1/2]$ 没有实根，却仍然不能决定正根和负根各有几个。

如果 $a_0=0$ ，不能把上式中的分母当作一个很小的数。先提取最大的 $x^k$ 因子： $f=x^kh$ 且 $h(0)\ne0$ 。零根的重数是 $k$ ，其余根再对 $h$ 使用倒数界。比如 $x^2(x^2-3)$ 的零根确实存在，任何声称“全部根离零有正距离”的结论都会出错。

自己复算一份范围证书

取

P(x)=(x-1)(x^2-2)(x^3-x-1) =x^6-x^5-3x^4+2x^3+3x^2-2.

最高次系数为一，低次系数最大绝对值为三，所以全部复根满足 $|\alpha|<4$ 。若只关心实根，可以把 $(-4,4)$ 交给下一页的计数器。

再计算 $P$ 的倒数界：常数项为 $-2$ ，其余系数的最大绝对值为三，所以 $R^*=1+3/2=5/2$ 。因此每个根还满足 $|\alpha|>2/5$ 。这两条证书只使用展开系数；右边给出的因式分解不是使用根界的前提。

完成后，试把 $P$ 乘以 $-14$ ：根界应保持不变。再把常数项改成零：倒数界必须停下来先处理零根。能解释这两步，比记住一个上界公式更重要。

参考资料

Francis J. Wright，Mathematics and Algorithms for Computer Algebra, Part 1: Matrices, polynomials and equations，2003年7月9日版，§4 “Polynomial root bounds”，Proposition 6，讲义页21：Cauchy严格根界及几何和证明。
Joachim von zur Gathen、Jürgen Gerhard，Modern Computer Algebra，第3版，Cambridge University Press，2013，实根计算与系数高度相关章节。本文的倒数界、缩放例子与六次多项式范围证书均由上面的不等式直接推导。

形式陈述 ​

从最高次项与其余项的竞争开始 ​

为什么根跑不出去 ​

变量缩放会改变界的松紧 ​

三种不能从根界读出的信息 ​

倒过来，还能把根与零隔开 ​

自己复算一份范围证书 ​

反向链接