Power iteration for matrices with power series entries

技术摘要：幂级数矩阵的幂迭代法

问题陈述
本文研究了针对以幂级数域（特别是 Levi-Civita 域 $\mathbb{C}$ 和 Puiseux 级数域）为矩阵元素的矩阵，寻找其特征值和特征向量的问题。虽然在代数几何和物理学（如哈密顿系统、电路网络）中，求解幂级数域上的多项式根是一个已被深入研究的问题，但解决这些域上的矩阵特征值问题却受到了较少的关注。现有的方法（例如计算特征多项式的根）被描述为计算成本极高。作者旨在将经典的幂迭代法（一种针对复矩阵的标准数值技术）适配到这些非阿基米德域中，在这些域中，标准的收敛定义并不直接适用。

方法论与理论框架
该方法论的核心依赖于 Levi-Civita 域（$\mathbb{R}$ 和 $\mathbb{C}$）的性质，这是一个非阿基米德、柯西完备、实闭（对于 $\mathbb{C}$ 是代数封闭）的有序域。作者区分了两种类型的收敛：

1. 强收敛： 关于序拓扑的收敛。
2. 弱收敛： 系数在通常意义上的收敛，这对于幂级数表示至关重要。

作者建立了关于弱收敛的若干辅助结果，包括：

• 对于“正则”序列（具有左有限支撑并集的序列），弱收敛在加法和乘法下的连续性。
• 在特定条件（如 $a[0] \neq 0$）下，逆运算（$1/a_k \to 1/a$）和平方根（$\sqrt{a_k} \to \sqrt{a}$）的弱收敛。
• 基于支撑集上有界子集上的系数一致收敛性的弱收敛判据。

幂迭代算法
本文证明了在以下条件下，幂迭代法对于 Levi-Civita 域 $\mathbb{C}$ 上的可对角化矩阵具有弱收敛性：

1. 矩阵具有至多有限的元素（即估值 $\lambda(a_{ij}) \geq 0$）。
2. 存在唯一的特征值，其“复部分”（即 $d^0$ 项的系数，记作 $\nu[0]$）的绝对值严格最大。
3. 初始向量在主特征向量方向上的分量不为零。

具体而言，若 $\nu_1$ 是主特征值，满足 $|\nu_1[0]| > |\nu_2[0]| \geq \dots$，则归一化向量序列 $x_k / \|x_k\|$ 弱收敛于归一化的主特征向量。此外，瑞利商 $u_k^* A u_k / \|u_k\|^2$ 弱收敛于主特征值。

为了处理最初不满足“至多有限”条件或主特征值不立即显见的矩阵，作者提出了一个缩放策略：

• 通过将矩阵元素按最小估值 $q_0$ 进行平移，创建一个新矩阵 $A' = d^{-q_0}A$。
• 分析“复部分”矩阵 $\pi(A')$（即 $0$ 阶系数矩阵）。
• 如果 $\pi(A')$ 具有一个占优特征值，则可以将幂迭代应用于缩放后的矩阵，以找到原矩阵的主特征值和特征向量。

该方法被扩展到了 Puiseux 级数域（它是 Levi-Civita 域的一个子域），使得该方法能够应用于具有 Puiseux 级数元素的矩阵。

关键结果

• 定理 5.5： 确立了如果一个可对角化矩阵 $A$（可能包含无穷大或无穷小的元素）可以被缩放，使得其“复部分”矩阵具有严格占优的特征值，则幂迭代法能成功找到模最大的特征值及其对应的特征向量。
• 推论 5.7： 确认该方法适用于 Puiseux 级数域上的可对角化矩阵，并在同一域内得出结果。
• 收敛证明： 本文利用序列的正则性以及 Levi-Civita 域中代数运算的连续性，为向量序列和瑞利商的弱收敛提供了严格证明。

实现与实验结果
作者使用 Python 实现了该算法。他们在具有 $\mathbb{R}\{\{t\}\}$ 上度为 21 的多项式的伴随矩阵上测试了该方法。

• 复杂度： 对于伴随矩阵，时间复杂度估计为 $O(n d_t \log(d_t))$，其中 $n$ 是矩阵维度，$d_t$ 是元素中变量 $t$ 的最大次数。对于任意矩阵，复杂度为 $O(n^2 d_t \log(d_t))$。
• 性能： 在一个特定的测试用例（21 次多项式）中，算法在 100 次迭代内收敛到最大根（近似为 $100 + t + \dots$）。误差显著下降，大多数分量的误差达到了 $10^{-12}$ 到 $10^{-14}$ 的数量级。在 Lenovo p50 上执行 100 次迭代的运行时间约为 135 秒。
• 观察： 作者指出，通过改进版本的算法可以大幅提升性能。他们还提到实现了逆向量迭代、子空间迭代和 QR 算法，作为寻找剩余向量或同时寻找所有向量的补充工具。

意义与主张
本文声称提供了第一个专门为具有幂级数元素的矩阵设计的幂迭代算法。作者认为，该方法不仅在理论上有意义，而且为开发寻找多元多项式根的进一步数值方法打开了大门。他们指出，这些新方法与依赖于计算特征多项式根的现有方法相比，可能会提供更好的稳定性和效率。这项工作通过将一种基本的迭代方法适配到非阿基米德域，架起了代数几何（Puiseux 级数在此类领域很常见）与数值线性代数之间的桥梁。