Pellet 圆盘计数与根簇证书

求根器给出三个靠得很近的小数，可能是三个不同根，也可能是一个重根的数值分裂。若输入系数本来带误差，这个区别甚至不能由当前资料决定。根簇证书换一个可稳定回答的问题：这只圆盘里按重数一共有几个根，而且允许系数怎样变化后仍保持这个数？

形式陈述

把圆心移到零，再找占优势的一项

p(z)=\sum_{m=0}^n a_mz^m,\qquad a_n\ne0,

系数、圆心 $c$ 属于复数，半径 $r>0$ 。准确写成

p(c+w)=\sum_{j=0}^n b_jw^j.

若对某个整数 $0\le k\le n$ 有

|b_k|r^k>\sum_{j\ne k}|b_j|r^j, \tag{1}

则开圆盘 $D(c,r)$ 恰有 $k$ 个根，计入重数，而且圆周无根。这是Pellet计数中最直接的 $T_k$ 优势测试。 $k=0$ 给无根圆盘； $k=n$ 给包含全部根的圆盘；其他 $k$ 给局部根簇总数。

在圆周上，以 $b_kw^k$ 为基准，其模是 $|b_k|r^k$ ，其他项之和严格较小。Rouché定理遂给同样的总重数 $k$ ，证明只有这一步。重要的计算工作在于：怎样可靠得到每个系数、它的模界以及严格余量。

直觉

“一项赢过所有其他项”是一张容易检查的票据

让 $w$ 沿圆周转一圈， $b_kw^k$ 的方向转 $k$ 圈。如果其他项的合力始终不足以把它推到零，真实多项式就保留这个读数。系数绝对值求和故意不利用相位抵消，计算方便，代价是有时会拒绝本来有效的圆盘。

因此“测试成功”能认证根数，“没有任何一项成功”只表示这个测试还没有答案。它既不是“没有根”，也不表示一定有根贴在边界。

例子与边界

两个不同半径分别给一根与三根

取

p(z)=z^3-4z+1.

在圆心零、半径 $1/2$ 时，一次项贡献 $2$ ，其余项大小之和为 $1+1/8=9/8$ ，所以盘内恰有一个根。在半径三时，三次项贡献27，其余项为13，故盘内恰有三个根。于是中间环域恰有两个根，两个边界都不含根。

改变圆心以后必须重算系数。由二项式展开，

b_j=\sum_{m=j}^n\binom mj a_mc^{m-j}. \tag{2}

不能只把图上的圆移动，却继续使用以零为圆心的 $(a_j)$ 。

测试失败的两种完全不同的原因

$p(z)=z^2-1,r=1$ 时，常数项与二次项大小相同，没有严格优势；两个根确实在圆周上，不能使用本页计数。

$p(z)=z^2+2z+2,r=1$ 时，同样没有一项胜过其他项之和，但根是 $-1\pm i$ ，模均为 $\sqrt2$ 。整个闭单位圆盘其实无根。换一个界、圆心或半径可能成功；这次失败没有证明边界存在零点。

若 $p(z)=(z-c)^3$ ，任意正半径都能通过 $k=3$ 测试。圆盘里却只有一个不同零点。把“总重数三”改写成“三个各自唯一的根”，就超出了证书。

推论与应用

以模的上下界代替不可靠小数

假设得到可靠实数界 $L_k\le|b_k|$ 、 $U_j\ge|b_j|$ 。若

\Delta=L_kr^k-\sum_{j\ne k}U_jr^j>0, \tag{3}

则仍成功。Gaussian有理数可以直接采用

L_k=\max(|\operatorname{Re}b_k|,|\operatorname{Im}b_k|), \qquad U_j=|\operatorname{Re}b_j|+|\operatorname{Im}b_j|.

这样全过程仅需有理运算。它们不是最紧的模包围，但每个比较都保留方向。若使用浮点平方根，则必须另给向外舍入或误差包围，普通显示的小数不是证明。

原坐标系数误差怎样传到移动的圆

允许真实输入为

q(z)=\sum_{m=0}^n(a_m+\delta_m)z^m, \qquad |\delta_m|\le\epsilon_m.

在 $|z-c|=r$ 上，有

|q(z)-p(z)|\le E(c,r):=\sum_{m=0}^n\epsilon_m(|c|+r)^m. \tag{4}

若只知道 $C\ge|c|$ ，可把右端改成 $\sum\epsilon_m(C+r)^m$ 。由(3)，基准 $p$ 在该圆周的模至少为 $\Delta$ ；因此

\Delta>E(c,r) \tag{5}

证明每个允许的 $q$ 在该圆盘都有同一个总重数 $k$ 。这是对整个误差族的统一保证，不是从若干系数扰动实验外推。

也可以逐个计算平移误差：由(2)，第 $j$ 个平移系数的误差至多

e_j=\sum_{m=j}^n\binom mj\epsilon_m|c|^{m-j}.

将这些误差按 $r^j$ 求和，再次使用二项式公式，恰得到 $\sum_j e_jr^j=E(c,r)$ 。这解释了(4)同时计入主项下界的损失和其他项上界的增加。只给其他项加误差而把主项当成准确值，会夸大安全余量。

若 $|a_n|>\epsilon_n$ ，所有允许输入的次数都仍为 $n$ 。没有这项前提，最高次系数可能消失，根也可能在系数变化时逃向无穷；不能保持原次数来做全局总数闭合。

从局部圆盘走到全部根覆盖

给出有限只闭包两两不相交的圆盘 $D(c_s,r_s)$ ，各有严格成功证书和正整数计数 $k_s$ 。如果输入次数统一为 $n$ ，而

\sum_s k_s=n, \tag{6}

就证明每个允许多项式的全部复根都位于这些圆盘内，按总重数无遗漏、无重复。

多项式共有 $n$ 个复根这一事实也可在当前接口内获得：在足够大的圆上，首项 $a_nz^n$ 胜过全部低次项，Rouché给圆内总重数 $n$ 。旧系数根界还提供全部根的统一外界。式(6)使局部已认证重数用完总数，所以外部不可能再有根。

若圆盘重叠，同一个根可能被重复计入；若计数和小于 $n$ ，只证明局部结果。程序分别拒绝这两种不完整清单。圆盘边界本身已由严格优势排除，不需要给边界根任意归属。

六次系数族的三簇证书

基准为

p(z)=(z-1)^3(z+1)^2(z-2i).

允许全部七项原坐标系数的复模误差各不超过 $1/1000$ 。以 $1,-1,2i$ 为圆心，各取半径 $1/4$ 。按上述有理上下界，扣除系数误差后的严格余量分别是

\frac{165259}{4096000},\qquad \frac{701259}{4096000},\qquad \frac{4729683}{4096000}.

三者均正，圆盘闭包互不相交，且各自计数为 $3,2,1$ 。最高次系数的模至少 $999/1000$ ，所以次数始终六，计数也恰好闭合。由此不只是准确基准，而是整个输入误差族都获得全部根簇覆盖。

基准的三重根在扰动后可以分成三个不同根；误差族中也包括未扰动的基准，所以无法统一宣称每个成员都有六个不同根。根簇的直径给位置范围，总重数给数量；精确因式分解才能对某个准确输入另谈不同根与重数。

实现代价与无法承诺的停止

一只圆盘用朴素式(2)需 $O(n^2)$ 次复数算术，全部优势量可在 $O(n)$ 个模界和幂值上形成。 $m$ 只候选圆盘的直接检查需 $O(mn^2+m^2)$ 次算术，后一项检查两两距离；还须记录 $O(mn)$ 个平移系数及 $O(m)$ 个余量。精确有理数位成本另计。

这个过程是验证给定根簇，不保证自动寻找任意输入的最优圆盘。一个失败的候选可能只需改变尺度，也可能需要更准系数。若输入只给固定误差盒，根簇内部的不同根数一般不可识别，继续提高计算精度也不会增加输入信息。公开程序因此保留未决状态，不通过无限缩盘来伪称完整隔离。

参考资料

Ruben Becker、Michael Sagraloff、Vikram Sharma、Chee Yap，A Near-Optimal Subdivision Algorithm for Complex Root Isolation based on the Pellet Test and Newton Iteration，2016年v4，§3.1 Definition1、式(3)–(4)与Theorem1，印刷12–13页， $T_k$ 圆盘计数。本页只使用该充分判据并直接证明，不采用后续Graeffe/Newton加速或其位复杂度。
同论文引言的系数oracle模型说明：有限精度下不能自动区分一个重根与附近多个简单根。本文固定误差族、统一余量和全部根簇清单另行展开，并明确验证与自动隔离的差别。

形式陈述 ​

把圆心移到零，再找占优势的一项 ​

“一项赢过所有其他项”是一张容易检查的票据 ​

两个不同半径分别给一根与三根 ​

测试失败的两种完全不同的原因 ​

以模的上下界代替不可靠小数 ​

原坐标系数误差怎样传到移动的圆 ​

从局部圆盘走到全部根覆盖 ​

六次系数族的三簇证书 ​

实现代价与无法承诺的停止 ​

反向链接