移位反幂法 - Ciallo Wiki

1 方法概览

1.1 基本问题与符号约定

移位反幂法用于求矩阵 \(A\) 的特征值与特征向量。给定标量移位参数 \(\sigma\)，将特征值问题 \[ Ax=\lambda x \] 转化为围绕 \(\sigma\) 的线性方程组求解子步骤。常见做法是在迭代中解 \[ (A-\sigma I)y=b \] 得到中间向量 \(y\)，再将其归一化并更新对特征对 \((\lambda,x)\) 的估计。

为便于表述，下文通常采用以下约定：迭代向量记为 \(x_k\)，线性方程的右端可取 \(b=x_k\) 或与之等价的向量；归一化操作用 \(\\| \cdot \\|\) 表示相应范数。特征值估计通常用 Rayleigh 商

\[ \mu_k=\frac{x_k^{\!*}Ax_k}{x_k^{\!*}x_k} \] 其中 \((\cdot)^{\!*}\) 表示转置共轭（复数情形），实数情形可视为普通转置。

1.2 与幂法的关系（为何“反幂”与“移位”）

普通幂法以反复应用 \(A\) 的方式放大最大模特征值对应的方向；其直觉是：在分解到各特征向量基底后，模最大的那一项增长最快。移位反幂法则通过两步“调焦”来改变增长的方向：

“移位”：考虑 \(A-\sigma I\)，使得与 \(\sigma\) 接近的特征值 \(\lambda\) 在变换后对应的量发生相对放大或缩小。
“反幂”：对 \((A-\sigma I)^{-1}\) 做幂迭代。由于 \((A-\sigma I)^{-1}\) 的特征值为 \(\frac{1}{\lambda-\sigma}\)，当 \(\lambda\) 接近 \(\sigma\) 时，\(\frac{1}{\lambda-\sigma}\) 的模会变大，从而主导迭代方向。

因此，它可以看作“在幂法框架内，把主导项从最大模特征值转移到移位附近的特征值”。

1.3 方法适用对象：对称、非对称与一般情形

对于复或实对称（Hermitian）矩阵，方法的理论性质更“干净”：Rayleigh 商具有良好几何意义，收敛与正交性相关的分析更容易建立。
对于一般非对称矩阵，迭代仍可能工作，但收敛行为更依赖谱结构（如是否存在接近的特征值、是否有良好条件的特征向量基）。数值上也可能出现对角化条件差导致的放大效应。
对于一般情形，移位反幂法常与子空间技术（如 Arnoldi、Lanczos 系列）或更稳健的求解策略结合，以提高可靠性与效率。

2 数学原理

2.1 由特征分解到迭代放大机理

若 \(A\) 可对角化（或在某种意义下可用特征向量展开），可写 \[ A = V\Lambda V^{-1},\quad (A-\sigma I)^{-1}=V(\Lambda-\sigma I)^{-1}V^{-1}. \] 令右端向量在特征向量方向上的展开为 \[ x_0=\sum_i c_i v_i. \] 迭代中求解 \((A-\sigma I)y=x_k\) 相当于 \[ y=(A-\sigma I)^{-1}x_k. \] 进一步展开可得每个特征方向被乘以 \(\frac{1}{\lambda_i-\sigma}\)。因此，当某个 \(\lambda_i\) 最接近 \(\sigma\) 时，对应方向的系数在迭代中相对增长最快，最终 \(x_k\) 会倾向于落在该方向附近（前提是该方向在初值中有非零分量且不会被其他数值因素抵消）。

2.2 移位参数 \(\sigma\) 对收敛方向的影响

\(\sigma\) 决定了“增长最大的 \(\frac{1}{\lambda_i-\sigma}\)”对应哪个特征值。更精确地说，迭代放大的主导项通常来自使 \(	\lambda_i-\sigma	\) 最小的那个（或多个非常接近的特征值所共同作用的子空间）。

因此：

若 \(\sigma\) 选得很接近目标特征值 \(\lambda_\star\)，收敛方向更快指向其特征向量（或相应不变子空间）。
若 \(\sigma\) 偏离目标，迭代可能收敛到另一个更接近 \(\sigma\) 的特征值方向。
若 \(\sigma\) 逼近某个特征值使 \(A-\sigma I\) 近奇异，则线性方程组求解会变得困难，数值误差可能显著放大，导致“看似快但不可靠”。

2.3 收敛速度与主导项分析

在理想化条件下（如对称情形且目标特征值与其他特征值间隔足够），可将误差在特征向量基底下的衰减比与 \[

\left	\frac{\lambda_j-\sigma}{\lambda_\star-\sigma}\right

\] 联系起来：主导误差项来自第二接近 \(\sigma\) 的特征值，其比值越小，收敛通常越快。

当与 Rayleigh 商更新结合（见后文 3.2）时，\(\sigma\) 可以动态接近当前的特征值估计，使得局部收敛速度提升，特别是在对称问题中更常表现出快速的局部收敛特征。

2.4 目标特征值选择策略（靠近性与稳定性权衡）

选 \(\sigma\) 常见依据包括：

靠近性：若可获得对目标特征值的先验信息（经验估计、物理量换算、粗网格估计等），将 \(\sigma\) 置于目标附近可显著提升指向性。
稳定性：过于精确甚至“落在”特征值附近会导致 \(A-\sigma I\) 条件数变差。工程上通常在“足够靠近”与“避免病态求解”之间折中。
迭代更新：通过 Rayleigh 商迭代将 \(\sigma\) 随当前近似自适应调整，减少对初始 \(\sigma\) 的敏感性，但代价是每步线性方程组仍需高质量求解。

3 具体算法流程

3.1 标准移位反幂法步骤

一种常见的标准流程可描述为：

给定初始向量 \(x_0\neq 0\)，设置移位参数 \(\sigma\)。
对 \(k=0,1,2,\dots\)：

解线性方程

\[ (A-\sigma I)y_{k}=x_k \]

归一化

x_{k+1}=\frac{y_k}{\\|y_k\\|}

以 Rayleigh 商或其他指标作为特征值估计并判断停止。

该方法的关键在于：每次迭代都在“同一个移位”附近对 \((A-\sigma I)^{-1}\) 的效果进行放大。

3.2 Rayleigh商更新与“更聪明的移位”

Rayleigh 商更新的思想是令移位参数随当前近似变化。典型做法：

使用当前向量 \(x_k\) 计算

\[ \mu_k=\frac{x_k^{\!*}Ax_k}{x_k^{\!*}x_k} \]

令下一步移位取 \(\sigma=\mu_k\)，或在其附近选择。
再解对应的

\[ (A-\mu_k I) y_k = x_k. \] 由于 \(\mu_k\) 在对称情形中与真实特征值具有更强的局部一致性，这种“动态移位”常能带来局部更快的收敛。

3.3 初始向量的选择与鲁棒性

初始向量 \(x_0\) 需要满足基本的非退化条件：其在目标特征向量（或目标不变子空间）方向上的分量不应为零。若采用随机初值，通常可在概率上避免恰好错过目标方向。

此外，鲁棒性还与以下因素相关：

初值过于接近与 \(\sigma\) 对应方向无关的子空间时，迭代可能收敛到其他特征对。
对非对称矩阵，若特征向量基条件差，初值虽然包含目标分量，也可能因数值放大而表现出不稳定。

3.4 归一化、停止准则与误差度量

归一化是维持尺度一致性并避免溢出/下溢的常规操作。停止准则常见于：

残差范数：计算

\[ r_k = Ax_k - \mu_k x_k, \]

当 \(\\|r_k\\|\) 小于容差时停止。
- 特征值变化：当 \(	\mu_{k+1}-\mu_k	\) 或相对变化量足够小。
- 向量变化：如 \(\\|x_{k+1}-x_k\\|\) 或其归一化版本。

在实践中，残差通常比“纯粹看 Rayleigh 商变化”更可靠，因为它直接反映近似是否满足特征方程。

4 线性方程组求解

4.1 直接法：分解与回代（如LU）

移位反幂法的每一步都需要解 \((A-\sigma I)y=b\)。若采用直接法，常见思路是对 \(A-\sigma I\) 做分解（如 LU 分解，对复一般矩阵；对对称结构可用更专业的分解路径），然后回代得到解向量。

直接法的优点是每步求解较稳定、误差可控；缺点是分解成本高，且若 \(\sigma\) 在迭代中变化（如 Rayleigh 更新），分解往往需要重做，成本会显著增加。

4.2 迭代法：预条件与求解器选型

当矩阵规模较大或稀疏结构明显时，通常使用迭代求解器（如基于 Krylov 子空间的方法）来求解线性方程组。由于 \((A-\sigma I)\) 的性质可能随 \(\sigma\) 改变，求解器选型与预条件器搭配对效率影响很大。

常见做法是选择适配矩阵特性的方法，例如：

若结构接近对称且可用相应预条件，可用适配的 Krylov 求解器；
若一般非对称，可能更偏向使用通用的非对称求解策略。

4.3 预条件器如何提升效率

预条件器用于降低线性系统的“有效难度”，通常通过改善谱分布、降低迭代次数或减少残差收缩所需的步数。

效果上可以理解为：移位使得 \((A-\sigma I)\) 的谱位置发生变化，而预条件器试图抵消这种不利影响。工程上常见的预处理来自：

基于稀疏结构的近似因子；
基于块结构或物理分块的近似；
多重网格或不完全分解的变体（视问题结构而定）。

4.4 数值稳定性问题：病态、舍入误差与对策

当 \(\sigma\) 接近某个特征值时，\(A-\sigma I\) 可能病态，表现为：

线性求解误差在回代后被放大；
迭代中 Rayleigh 商更新可能导致移位进一步走向不稳定区。

对策包括：

避免选择过于贴近导致近奇异的 \(\sigma\)，采用“略微偏离”的策略；
提升线性求解精度（更紧的线性残差容差）以避免误差积累；
使用更强的预条件器或更稳定的求解器；
在对称问题中可利用数值对称性保持操作一致性（如共轭转置处理）。

5 计算实现与工程实践

5.1 复杂度分析：每步成本与迭代次数

移位反幂法的总成本通常由“每步线性方程组求解”主导。若 \(\sigma\) 固定，则可在某些直接法或带缓存的预条件器设置中复用结构信息；若 \(\sigma\) 每步更新，则难以完全复用，成本随迭代次数增加。

迭代步数与收敛性强相关：移位越接近目标、初值越合适，通常需要的特征迭代步数越少；但另一方面，越接近意味着线性系统越困难。

5.2 稀疏矩阵场景下的实现要点

稀疏矩阵通常建议：

利用稀疏存储格式，避免形成稠密矩阵；
在预条件器或求解器中尽量保留稀疏算子；
控制中间向量运算的内存开销，尤其在大规模问题中避免频繁分配。

此外，归一化与残差计算的开销需要与稀疏乘法成本平衡；残差停止准则能显著减少无效迭代，但会增加每步的额外运算。

5.3 大规模问题的加速技巧（分解重用、批处理）

常见加速思路包括：

分解重用：当 \(\sigma\) 固定或变化不大时，尽量复用某些预计算结果（如分解结构或预条件器更新策略）。
批处理多右端：若需要同时计算多个特征对，可能利用相同的线性算子对多个向量进行求解，从而提高算子利用率。
粗细网格或层级策略：先在较小规模或低精度模型中估计目标特征值，再在原规模进行精修。

5.4 并行与分布式计算的常见做法

并行实现通常围绕两类操作展开：

稀疏矩阵-向量乘法与向量点积/范数计算；
线性方程组求解器内部的迭代与预条件器应用。

分布式环境中，通信主要来自全局点积与残差范数评估；因此工程上常通过减少同步次数、合并归约操作、选择通信更友好的求解器与预条件方案来提升性能。

6 变体与相关方法

6.1 反幂法（\(\sigma=0\) 的特殊情形）

当移位参数取 \(\sigma=0\) 时，方法退化为反幂法。此时迭代等价于对 \(A^{-1}\) 的幂迭代，目标特征值倾向于与 0 最接近的那部分谱（前提是 \(A\) 可逆且初值包含相应方向分量）。由于线性系统变为 \(Ay=b\)，很多实现也更简单直接。

6.2 反幂法与谱投影法的联系

在更抽象的观点下，\((A-\sigma I)^{-1}\) 的作用相当于对谱进行某种权重放大，从而将迭代向特定谱区域的子空间投影。谱投影法通常以更显式的方式构造投影算子，而移位反幂法则通过反复应用逆算子“隐式完成”类似效果。两者在思想层面同属“围绕谱结构聚焦”的类别。

6.3 Rayleigh商迭代（与动态移位的比较）

Rayleigh 商迭代通常将 \(\sigma\) 取为当前 Rayleigh 商 \(\mu_k\)。与固定移位的移位反幂法相比，它是一种动态移位策略，能够在近似较好时更快地逼近目标特征值。代价是每步线性系统通常都不同，需要更频繁地更新求解过程。

6.4 与子空间迭代/Arnoldi-Lanczos的协同使用

在较复杂问题中，仅靠单向量迭代可能不够稳健。协同使用的典型方式包括：

将移位反幂作为预处理或“加速器”，用于提高某个子空间内的特征提取速度；
与子空间迭代结合，以更可靠地捕捉接近的特征值与对应不变子空间；
对非对称问题，结合 Arnoldi 类方法能更好地处理一般谱结构。

这类组合往往在“可靠性与成本”之间取得更平衡的折中。

7 例题与直观理解

7.1 简单矩阵示例：手工演算的收敛现象

考虑带有明显特征分解的低维矩阵，可以直接观察当 \(\sigma\) 靠近某个特征值时，\((A-\sigma I)^{-1}\) 的作用会放大其对应方向。即便只做几步迭代，归一化后的 \(x_k\) 也会逐渐与目标特征向量的方向一致，而 Rayleigh 商则向目标特征值收拢。

手工演算的重点不在于数值精度，而在于验证“最近的特征值方向更快被放大”的机制。

7.2 图像/几何直觉：为什么会“抓住”目标特征向量

从几何上看，解 \((A-\sigma I)y=x_k\) 相当于将向量通过某个“线性变换”重新投影到更接近目标谱方向的区域。归一化确保尺度不跑偏，而方向会随着迭代被逐步校正。若 \(\sigma\) 让目标特征值对应的逆变换权重最大，那么迭代便像“在方向上找最亮的那束光”，最终收敛到它所代表的方向。

7.3 常见踩坑：移位选错导致“反向尬住”

典型失误包括：

\(\sigma\) 选择得不在目标附近，导致迭代转而收敛到另一个特征值附近；
初值与目标方向分量过小，使得误差初期被其他方向主导；
\(\sigma\) 过于靠近某个特征值导致线性系统求解误差放大，出现停滞或来回跳动。

这些情况的共同点是：迭代的“聚焦点”没有落在目标不变子空间上，或聚焦过程受数值误差扰动。

7.4 经验参数建议：\(\sigma\)、初值与容差取法

工程经验通常包括：

\(\sigma\) 取目标附近的中间值，避免过度贴近导致线性系统过病态；
初值可用随机向量或基于物理量构造的猜测向量，以提高包含目标分量的概率；
容差方面，特征迭代停止建议以残差范数控制更稳健；线性方程组若用迭代法，需保证其求解精度不会成为整体误差主导项。

在对称问题中，Rayleigh 商更新的局部表现往往更理想；而对一般非对称问题，建议更谨慎地监控残差变化与迭代稳定性。

8 常见问题（FAQ）

8.1 移位参数应如何选取与更新？

若有先验估计，可令 \(\sigma\) 位于目标特征值的附近作为初始移位。
若缺少先验且希望自适应，可使用 Rayleigh 商更新，让 \(\sigma\) 随当前近似调整。
无论哪种方式，都应监控 \(A-\sigma I\) 求解的数值难度；当线性求解变得困难时，可能需要调整 \(\sigma\) 或加强预条件与线性求解精度。

8.2 若目标特征值重数较高怎么办？

当目标特征值重数较高时，迭代通常会收敛到该特征值对应的不变子空间中的某个方向，而不一定固定到某个唯一特征向量。此时可考虑：

使用子空间扩展（多向量版本）以获得更丰富的基；
依靠残差与子空间投影来判断收敛到正确的空间；
结合子空间迭代方法提高区分相近特征方向的能力。

8.3 对非对称矩阵是否仍有效？

移位反幂法对非对称矩阵并非“必然失效”。它仍能通过 \((A-\sigma I)^{-1}\) 的谱权重把迭代拉向移位附近的谱。但由于非对称问题的特征向量可能高度非正交，收敛速度与稳定性可能更波动。常见做法是加强残差监控、选择更稳健的线性求解与预条件方案，必要时与 Arnoldi 类方法协同。

8.4 如何判断迭代失败或停滞？

可从以下迹象判断问题：

- Rayleigh 商变化很小但残差 \(\\|Ax_k-\mu_k x_k\\|\) 仍不降低，说明停滞可能来自数值误差或错误聚焦；

向量在迭代中来回摆动且残差不单调下降，可能是移位选择不当或线性求解精度不足；
线性系统求解迭代次数急剧上升，提示 \(\sigma\) 导致近奇异或预条件失效。

一旦发现上述信号，通常需要调整 \(\sigma\)、改进预条件器、提高线性求解精度或更换策略（如增加子空间维度）。