M35
结构化绝对值方程的参数化松弛迭代：收敛性定理与公开算例复算
来源说明：本则出自独立撰写的第二批方案。它与前 20 则同样遵循八块结构与硬门槛要求，但撰写时未做英文文献检索，新颖性边界依据的是历届获奖图谱与既有知识，而非当轮查新。因此其「需核实」条目更多，启动前须自行补一轮英文检索。
1 · 研究问题
对绝对值方程（absolute value equation, AVE）Ax − |x| = b，当 A 属于对称正定或 M-矩阵等结构类时，参数化松弛迭代 x⁽ᵏ⁺¹⁾ = x⁽ᵏ⁾ + ω·M⁻¹(b − Ax⁽ᵏ⁾ + |x⁽ᵏ⁾|) 的收敛充分条件能否给出比"最小奇异值 > 1"通用条件更precise的显式刻画（含最优 ω 公式）？该条件预测的收敛区间与实测收敛区间的吻合度如何？
2 · 研究背景与空白
AVE 是带互补结构的非光滑线性系统，与线性互补问题（LCP）等价互转，是数值优化的标准测试台。基础理论：当 A 的最小奇异值 σ_min(A) > 1 时解存在唯一（Mangasarian–Meyer，2006，需核实精确陈述）；广义 Newton 法（Mangasarian，2009 前后，需核实）及大量后续迭代法（Picard 型、SOR 型、HSS 型）各有收敛条件。收敛性证明的数学内核是非光滑不动点映射的压缩性分析——|x| 的分片线性性使误差传播矩阵属于一个显式矩阵族，谱半径上界可以严格算。
已有工作：通用条件下的多族迭代法与收敛证明已密集发表（这是一个拥挤领域——本题的新颖性边界必须收窄到"结构类 + 最优参数显式公式 + 条件紧性实验"的组合）；丘奖相邻获奖论文：2025 优胜奖《A fast numerical method for solving absolute value equations》直接同对象——本题设计时即以"与它错位"为约束（见第 7 块）。
空白在：结构类（对称正定/M-矩阵）上收敛条件的紧性——文献条件多为充分不必要，条件预测区间与真实收敛区间的差距少有系统量化；而最优 ω 的显式公式在结构类上可用特征值区间算出（Chebyshev 型论证，初等可证）。适合学生：证明是干净的矩阵分析，实验协议可完全标准化。
3 · 可检验假设
- H1：A 对称正定且特征值 ∈ [μ, L]、μ > 1 时，所提迭代在显式 ω 区间内收敛，且最优 ω* 与渐近收敛率有闭式公式；公式预测的收敛率与实测（随机算例几何平均）偏差 ≤ 15%。
- H2：在 σ_min → 1⁺ 的病态端，结构条件给出的收敛区间严格宽于通用条件给出的区间（定量比较表）。
4 · 量化验收标准
- 方法学校验（硬门槛）：先独立复算已发表基线——广义 Newton 法在标准随机 AVE 算例族（σ_min(A) > 1，n ∈ {100, 500, 1000}，生成协议按原文）上重跑 ≥ 30 个算例，迭代次数与文献报告量级一致（均值偏差 ≤ 20%）。不过关（说明算例生成或实现有误）则全线无效。
- 定理交付：结构类收敛定理 + 最优 ω 闭式 + 完整证明；明确写出定理条件与通用条件的蕴含关系。
- 紧性实验：ω 网格 × 谱区间网格的收敛/发散相图（每格 ≥ 20 随机实例），与定理预测边界叠加，报告边界吻合带宽度。
- 对照协议：与广义 Newton 及至少一个近年方法在等浮点运算量与等墙钟时间双口径下对比（两种都报），随机种子固定。
- 统计口径：收敛率报几何平均 + 自助法 95% 置信区间；不挑选算例。
- 代码与全部算例生成脚本开源，一键复跑。
5 · 数据与工具
| 用途 | 来源 / 工具 |
|---|---|
| 数值实验 | NumPy/SciPy（稠密与稀疏两版），纯 CPU，n ≤ 5000 秒–分钟级 |
| 算例生成 | 按文献标准协议自写（均匀谱随机对称阵、M-矩阵由对角占优构造） |
| 基线方法 | 广义 Newton 与对照方法按原文自实现（仅对照与校验，不计入贡献） |
| 文献 | arXiv + 期刊（第 3 周做拥挤度扫描：搜索关键词 absolute value equation relaxation iteration convergence M-matrix） |
| 算力量级 | 全部实验笔记本数小时，纯 CPU |
6 · 方法路径
- 实现 AVE 算例生成器与广义 Newton 基线，完成第 4 块第 1 条复算硬门槛。
- 文献窗口（关键）：扫描近五年 AVE 迭代法清单，确认所提"结构类 + 最优参数"组合未被占据（能力边界核实步；若被占据见第 8 块换位）。
- 推导误差传播矩阵族的谱半径上界，证明收敛定理与最优 ω 闭式。
- 跑相图实验检验条件紧性；跑双口径对照实验。
- 病态端实验（σ_min → 1⁺）量化结构条件的增益。
- 独立交叉校验：用 SymPy 对 n = 3 小例符号验证误差传播矩阵推导；两名成员分别实现迭代核并比对轨迹。
7 · 新颖性边界
- 本课题不声称提出"第一个"AVE 迭代法（领域拥挤，通用条件下的迭代法已饱和），不把存在唯一性理论与广义 Newton（均已发表）计入贡献。
- 已有工作：Mangasarian–Meyer 存在唯一性；广义 Newton；Picard/SOR/HSS 型方法族（第 3 周核实清单到方法级）。丘奖相邻获奖论文：2025 优胜奖《A fast numerical method for solving absolute value equations》——本题与它的错位设计：不比"更快"，而做收敛条件的紧性刻画与最优参数闭式（评价维度转换：从速度基准转向理论–实测边界吻合），并限定结构矩阵类。
- 本项目贡献（主结论）：结构类上的收敛定理（含最优 ω 闭式）+ 条件紧性的首份系统相图。
- 价值：把"条件是否紧"这一文献少答的问题定量回答；负结果（条件远不紧）同样有效且照样成图。
8 · 决策门槛（go / no-go）
- 第 3 周末：拥挤度扫描完成。若"对称正定 + 最优 ω"组合已被发表 → 换位路径：转 M-矩阵类或区间矩阵类（同一证明骨架换矩阵族），或把评价维度再转向"不精确内解（M⁻¹ 用 CG 近似）下的收敛鲁棒性"。
- 第 6 周末：硬门槛复算通过。偏差超限 → 排查算例生成协议（最常见错误源），连续 2 周不过则请老师联系文献作者页面核对协议细节。
- 第 16 周末：定理若证不到预期强度（只得充分条件无最优 ω 闭式），降级路径：保留定理（弱版）+ 把最优 ω 改为数值确定并给出相图拟合公式（明确标注经验性）——主结论框架（定理 + 紧性相图）不变。
- 选择前提：适合喜欢矩阵分析、想要"建模–证明–实验"完整闭环但不想碰高风险开放问题的学生。
- 预算裁剪顺序：第二个对照方法 → 病态端实验密度 → 稀疏版实现；定理与相图不砍。