双步隐式位移QR算法计算实非对称矩阵特征值

题目描述
双步隐式位移QR算法是一种高效计算实非对称矩阵（非对称但元素全为实数）全部特征值的数值方法。它通过迭代将矩阵逐步化简为实舒尔形式（准上三角矩阵），从而直接读取特征值（对角线块为1×1或2×2块，对应实特征值或共轭复特征值）。该方法的核心创新是避免复数运算，通过隐式处理双位移（两个位移量的组合）来保持计算在实数域内进行，显著提升稳定性和效率。

解题过程

1. 预处理：化简为上海森伯格（Hessenberg）矩阵
   • 原因：上海森伯格矩阵（次对角线以下全为零）能保留原矩阵特征值，且QR迭代时运算量从O(n³)降为O(n²)。
   • 方法：通过Householder变换将原矩阵A正交相似变换为上海森伯格矩阵H，即 \(H = Q^T A Q\)。
   • 示例：若A为5×5矩阵，变换后H形式如下（×为非零元素）：

\[ H = \begin{pmatrix} × & × & × & × & × \\ × & × & × & × & × \\ 0 & × & × & × & × \\ 0 & 0 & × & × & × \\ 0 & 0 & 0 & × & × \end{pmatrix} \]

2. 双步隐式位移QR迭代

   • 步骤1：选择位移量
     取H右下角2×2子矩阵 \(H_{n-1:n, n-1:n}\) 的特征值作为位移量σ₁和σ₂。由于H为实矩阵，若特征值为复数，则必为共轭对（如σ₁ = a+bi, σ₂ = a-bi）。
   • 步骤2：隐式构造第一列变换向量
     • 计算向量 \(v = (H - σ₁I)(H - σ₂I)e₁\)，其中e₁为第一标准基向量。由于σ₁和σ₂共轭，v为实向量。
     • 通过v构造Householder变换矩阵P₀，使P₀作用后v的第一个非零元素以下部分被清零。
   • 步骤3：隐式追迹（Bulge Chasing）
     • 对H应用P₀：\(H ← P₀ H P₀^T\)。这会破坏上海森伯格形式，在次对角线下方引入一个“凸起”（bulge）。
     • 通过一系列正交相似变换（Householder或Givens旋转）将凸起从左上角逐行“追赶”至右下角，恢复上海森伯格形式。每一步变换仅影响局部矩阵块，避免全局重构。
     • 示例：在5×5矩阵中，凸起最初出现在(3,1)位置，通过左乘和右乘变换矩阵，逐步将其移至(4,2)、(5,3)，最后消去。

3. 收敛判断与特征值提取

   • 每次迭代后，检查次对角线元素是否可忽略（如 \(|h_{i+1,i}| < ε \cdot (|h_{i,i}| + |h_{i+1,i+1}|)\)）。若可忽略，则矩阵可分解为更小的块：
     • 1×1块：直接给出实特征值。
     • 2×2块：计算其特征值（可能为实根或共轭复根）。
   • 对未收敛的子块重复步骤2-3，直至全部特征值解出。

总结
该算法通过隐式追迹避免显式复数运算，兼具高效性和数值稳定性，是LAPACK等库中计算实非对称矩阵特征值的标准方法。关键点在于位移量的合理选择与凸起的有效管理。