形式陈述
本页以 Hermitian(实情形为对称)矩阵的特征值与特征向量理路特征值与特征向量Eigenvalue and eigenvector满足 Tv=λv 且 v 非零的标量 λ 与向量 v。问题为主范围,因为 Rayleigh 商迭代的局部三次收敛依赖这一结构。固定移位逆迭代本身可用于更一般的可对角化矩阵,但后文标准的谱距离和收敛阶结论均按 Hermitian 主线解读。
固定移位逆迭代输入矩阵 、移位 、非零初值 、容差和最大迭代数。每一步求解一个移位线性方程组理路线性方程组System of linear equations可写为矩阵方程 Ax=b 的有限个一次方程系统。
而不是形成 。若 可对角化, 不等于任何特征值,并且 有唯一主模特征值,则该过程就是对逆移位算子做幂迭代理路幂迭代Power method · Power iteration反复应用矩阵并归一化,以谱隙筛出唯一主模特征方向,同时用残差判断所得特征对。。对 normal 或 Hermitian 矩阵,若离 最近的特征值 简单、距离严格小于其他特征值,且初值含有该方向,则轨道趋向这一特征方向。若下一近特征值为 ,方向误差有以下谱比的几何上界;精确渐近因子还取决于相应次主分量是否出现:
固定 时,可先对 做一次分解,每步只复用因子完成三角求解理路三角线性方程求解Triangular solve · Forward substitution · Backward substitution按依赖顺序用前代或回代求解三角系统,作为 LU、Cholesky 与 QR 分解后的共同计算底层。。稠密一次分解为 ,每个后续迭代为 ;稀疏情形取决于因子填充和所用线性求解器。
Rayleigh 商迭代把移位改为
动态移位通常每步都改变矩阵,稠密实现因而需要新的分解,不能复用固定移位成本。对 Hermitian 矩阵的简单特征对,从足够近且含目标分量的初值出发,只要该次移位系统非奇异、迭代有定义,方向角误差满足局部三次上界 ;一般非正规矩阵没有这条无条件结论,局部阶和吸引域都更复杂。
两种算法都用
评估特征对。完成准则包括尺度化残差、相位对齐后的方向变化、线性求解后向误差、非有限值和迭代上限。若某次移位恰等于特征值,系统精确奇异;此时应依据当前残差判断是否已经得到特征对,或转入明确的零空间处理,而不是继续除法。
直觉
移位反演把每个特征值 变成 。原谱中离 最近的点,反演后的模最大,于是普通幂迭代能够把它筛出。固定移位决定目标位置,动态 Rayleigh 移位则让当前向量反过来预测特征值,再把下一次放大中心移到更接近目标的地方。
接近收敛时 必然接近奇异,这不是偶然故障,而是“目标方向被强烈放大”的机制。危险在于线性系统必须仍以小后向误差求解;随手添加正则项会改变反演谱,也就改变正在逼近的特征问题。
移位逆算子的谱放大
例子与边界
对
逆移位特征值为 。目标 对应唯一主模 ,次大模为 ,所以只要初值第二分量非零,方向误差至多按 的几何尺度衰减;若初值第一分量为零而第三分量非零,则实际谱比更小,为 。一次分解 后,每一步只是三角求解与归一化。
Rayleigh 商迭代的三次机制可以在二维对角例子中精确看见。取
其中 是以目标特征向量 为中心的有符号局部角参数。Rayleigh 商为 ,代入逆迭代可得
当 很小时,方向误差每步立方,且符号翻转只代表在目标方向两侧交替。
动态移位也可能在尚未收敛时恰好奇异。取 ,,其中 任意小。Rayleigh 商恰为零,但 ,而 因中间坐标不相容而无解。故“足够接近”本身不能保证每一步可继续求解;奇异处理和残差判断属于算法必须给出的退出分支。
固定移位若恰位于两个 normal 特征值的中点,反演后会出现等模主值,迭代可能无法选择唯一方向。非正规矩阵中,“离移位最近”也不足以单独预测行为,因为特征向量条件性和伪谱会影响线性求解与吸引域;三次结论不能从 Hermitian 情形直接照搬。
推论与应用
对 Hermitian 矩阵,有限维谱定理理路有限维谱定理Finite-dimensional spectral theorem有限维复正规算子存在正交规范特征基;实数情形对应自伴算子。提供正交特征基,使逆迭代的每个谱分量按 (λj−μ)^{-1} 独立缩放;Rayleigh 商更新的局部高阶收敛正是在这个坐标分解中证明。
固定移位适合在已知谱位置附近求一个特征向量,最大优势是分解可复用;Rayleigh 商迭代以更高的局部速度换取每步重新分解。若同一移位要处理多个初值或多个右端,复用因子的收益尤其明显。
这两种方法一次追踪一个特征方向。需要整个谱时,QR 特征值算法理路QR 特征值算法QR algorithm · Shifted QR algorithm · Francis QR algorithm先化 Hessenberg 或三对角形,再用隐式移位 QR、bulge chasing 与 deflation 计算 Schur 形和全部特征值。通过隐式移位、Hessenberg 结构和 deflation 同时组织多个不变子空间,不是简单重复单向量逆迭代。
将候选 代回原方程后,Hermitian 残差证书理路Hermitian 特征对的残差与方向证书Hermitian eigenpair residual bound · Residual-gap eigenvector angle bound把可计算特征对残差分别转成谱距离、结构化后向误差与有谱隙条件的方向界,并核验三阶扰动。把谱距离与方向误差分开:前者由残差控制,后者还要除以候选值到其余谱的可靠距离。若目标是一簇近重根,子空间残差界理路谱簇子空间的残差与间隔界Invariant subspace residual bound · Davis–Kahan sin theta theorem · Subspace angle residual certificate把近似子空间的残差投到互补谱块,证明 Frobenius 与分隔区间下的二范数角度界,避免追踪重根内部任意基。度量整簇的主角,避免追踪簇内任意选定的轴。
参考资料
- 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.