核心概述
在给定多项式系数后，采用同时迭代（Durand–Kerner/Aberth）或实根隔离与精炼（如 Sturm/Jenkins–Traub）以返回全部根的数值近似或实根集合，复杂度与次数与收敛轮次相关，为本仓库实现约定的接口与精度语义服务。
原文引述
Description: Find all roots of a polynomial. Durand–Kerner (Weierstrass) simultaneous iteration for complex roots; Aberth for faster convergence; real-coefficient real roots via Jenkins–Traub or Sturm sequences. Time: O(n·iter) for Durand–Kerner; typically O(n log n) iterations Status: tested ——摘自本节点现有英文注释
展开阐述
-
函数/接口（据实现）
- vector<complex
> durandKerner(const vector<complex >& coeff, int maxIter=200, double eps=1e-12) - 输入系数（升幂），返回所有根的复数近似（顺序任意）。
- vector
realRoots(const vector & coeff) - 实系数多项式的实根（隔离+精炼），可用 Sturm 序列或 Jenkins–Traub。
- 可选：aberth(coeff) 为 Durand–Kerner 的加速版。
- vector<complex
-
Durand–Kerner 算法（同时迭代）
- 初始猜测：取 n 个初始点 z_i^{(0)}，常用 z_i = r·e^{2πi·i/n}，其中 r 为 1 或稍大。
- 迭代更新（k→k+1）：
- 对每个 i：z_i^{(k+1)} = z_i^{(k)} − P(z_i^{(k)}) / ∏_{j≠i} (z_i^{(k)} − z_j^{(k)})。
- 终止：当所有 |P(z_i)| < eps 或变化量小于 eps 时停止。
- 收敛性：对一般多项式全局收敛，但速度依赖初始值与根分布。
-
Aberth 方法（带修正）
- 在 Durand–Kerner 更新中加入 Aberth 修正项，加速收敛：
- Δ_i = P(z_i) / P’(z_i) · 1 / (1 − Σ_{j≠i} 1/(z_i−z_j))
- z_i ← z_i − Δ_i
- 通常收敛更快，但实现稍复杂。
- 在 Durand–Kerner 更新中加入 Aberth 修正项，加速收敛：
-
实根隔离（Sturm 序列）
- 构造 Sturm 序列（多项式与其导数的辗转相除余式序列）。
- 用变号数统计确定区间内实根个数，再二分隔离每个根，最后用牛顿法精炼。
- 适合需要精确实根与根的计数/隔离区间。
-
数值与实现注意
- 复数运算：std::complex
或 long double；注意舍入与极小值处理。 - 初值选择：随机扰动或按单位圆分布可避免对称性导致的循环。
- 多重根：Durand–Kerner 收敛变慢；Aberth 与 Jenkins–Traub 对重根更稳健。
- 系数缩放：大系数可先归一化以改善数值稳定性。
- 复数运算：std::complex
-
输出语义
- durandKerner 返回复数根列表，无特定顺序；实根的虚部应近 0。
- realRoots 返回实根列表（升序），若虚部显著非零则过滤。
-
复杂度
- 每轮迭代 O(n^2)（计算所有点的分母）；总迭代次数通常 O(log(1/eps))。
- Aberth 每轮 O(n)（需 P’），但常数更大。
-
使用与注意
- 低次多项式（≤4）优先用解析公式（二次、卡丹、Ferrari）。
- 若仅需求一个近似根，可用牛顿法（需导数）或二分法（实根）。
- 对符号计算或精确根，需代数数库，超出本模板范围。