Skip to content

算法Algorithm

Hermitian 特征问题的逆迭代与 Rayleigh 商迭代

施工中 · 内容逐步修订

Inverse iteration · Shifted inverse iteration · Rayleigh quotient iteration · 逆迭代与 Rayleigh 商迭代

通过求解移位线性系统放大目标附近的特征方向,并用动态 Rayleigh 移位获得 Hermitian 问题的局部三次收敛。

形式陈述 ​

本页以 Hermitian(实情形为对称)矩阵的特征值与特征向量问题为主范围,因为 Rayleigh 商迭代的局部三次收敛依赖这一结构。固定移位逆迭代本身可用于更一般的可对角化矩阵,但后文标准的谱距离和收敛阶结论均按 Hermitian 主线解读。

固定移位逆迭代输入矩阵 A、移位 μ、非零初值 x0、容差和最大迭代数。每一步求解一个移位线性方程组

(A−μI)yk+1=xk,xk+1=yk+1‖yk+1‖2,

而不是形成 (A−μI)−1。若 A 可对角化,μ 不等于任何特征值,并且 (A−μI)−1 有唯一主模特征值,则该过程就是对逆移位算子做幂迭代。对 normal 或 Hermitian 矩阵,若离 μ 最近的特征值 λj 简单、距离严格小于其他特征值,且初值含有该方向,则轨道趋向这一特征方向。若下一近特征值为 λℓ,方向误差有以下谱比的几何上界;精确渐近因子还取决于相应次主分量是否出现:

|λj−μλℓ−μ|.

固定 μ 时,可先对 A−μI 做一次分解,每步只复用因子完成三角求解。稠密一次分解为 Θ(n3),每个后续迭代为 Θ(n2);稀疏情形取决于因子填充和所用线性求解器。

Rayleigh 商迭代把移位改为

μk=xk∗Axkxk∗xk,(A−μkI)yk+1=xk,xk+1=yk+1‖yk+1‖2.

动态移位通常每步都改变矩阵,稠密实现因而需要新的分解,不能复用固定移位成本。对 Hermitian 矩阵的简单特征对,从足够近且含目标分量的初值出发,只要该次移位系统非奇异、迭代有定义,方向角误差满足局部三次上界 |tan⁡ϕk+1|≤C|tan⁡ϕk|3;一般非正规矩阵没有这条无条件结论,局部阶和吸引域都更复杂。

两种算法都用

θk=xk∗Axkxk∗xk,rk=Axk−θkxk

评估特征对。完成准则包括尺度化残差、相位对齐后的方向变化、线性求解后向误差、非有限值和迭代上限。若某次移位恰等于特征值,系统精确奇异;此时应依据当前残差判断是否已经得到特征对,或转入明确的零空间处理,而不是继续除法。

直觉

移位反演把每个特征值 λi 变成 1/(λi−μ)。原谱中离 μ 最近的点,反演后的模最大,于是普通幂迭代能够把它筛出。固定移位决定目标位置,动态 Rayleigh 移位则让当前向量反过来预测特征值,再把下一次放大中心移到更接近目标的地方。

接近收敛时 A−μkI 必然接近奇异,这不是偶然故障,而是“目标方向被强烈放大”的机制。危险在于线性系统必须仍以小后向误差求解;随手添加正则项会改变反演谱,也就改变正在逼近的特征问题。

移位逆算子的谱放大
例子与边界

对

A=diag(1,4,9),μ=3.5,

逆移位特征值为 −0.4,2,2/11。目标 4 对应唯一主模 2,次大模为 0.4,所以只要初值第二分量非零,方向误差至多按 0.4/2=0.2 的几何尺度衰减;若初值第一分量为零而第三分量非零,则实际谱比更小,为 (2/11)/2=1/11。一次分解 A−3.5I 后,每一步只是三角求解与归一化。

Rayleigh 商迭代的三次机制可以在二维对角例子中精确看见。取

A=diag(1,3),xk=(sin⁡ϕk,cos⁡ϕk)T,

其中 ϕk 是以目标特征向量 e2 为中心的有符号局部角参数。Rayleigh 商为 μk=3−2sin2⁡ϕk,代入逆迭代可得

tan⁡ϕk+1=−tan3⁡ϕk.

当 ϕk 很小时,方向误差每步立方,且符号翻转只代表在目标方向两侧交替。

动态移位也可能在尚未收敛时恰好奇异。取 A=diag(−1,0,1),x=(ε,1,ε)T/1+2ε2,其中 ε≠0 任意小。Rayleigh 商恰为零,但 Ax≠0,而 Ay=x 因中间坐标不相容而无解。故“足够接近”本身不能保证每一步可继续求解;奇异处理和残差判断属于算法必须给出的退出分支。

固定移位若恰位于两个 normal 特征值的中点,反演后会出现等模主值,迭代可能无法选择唯一方向。非正规矩阵中,“离移位最近”也不足以单独预测行为,因为特征向量条件性和伪谱会影响线性求解与吸引域;三次结论不能从 Hermitian 情形直接照搬。

推论与应用

对 Hermitian 矩阵,有限维谱定理提供正交特征基,使逆迭代的每个谱分量按 (λj−μ)^{-1} 独立缩放;Rayleigh 商更新的局部高阶收敛正是在这个坐标分解中证明。

固定移位适合在已知谱位置附近求一个特征向量,最大优势是分解可复用;Rayleigh 商迭代以更高的局部速度换取每步重新分解。若同一移位要处理多个初值或多个右端,复用因子的收益尤其明显。

这两种方法一次追踪一个特征方向。需要整个谱时,QR 特征值算法通过隐式移位、Hessenberg 结构和 deflation 同时组织多个不变子空间,不是简单重复单向量逆迭代。

将候选 (θk,xk) 代回原方程后,Hermitian 残差证书把谱距离与方向误差分开:前者由残差控制,后者还要除以候选值到其余谱的可靠距离。若目标是一簇近重根,子空间残差界度量整簇的主角,避免追踪簇内任意选定的轴。

参考资料
  • Lloyd N. Trefethen and David Bau III, Numerical Linear Algebra, SIAM, 1997, Lectures 27–29.
  • Beresford N. Parlett, The Symmetric Eigenvalue Problem, SIAM Classics, 1998, Chs. 4 and 9.
  • Gene H. Golub and Charles F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, 2013, §7.6.
关系图谱13 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系