广义特征值问题的QZ算法

题目描述
给定两个n×n矩阵A和B，广义特征值问题要求求解标量λ和非零向量x，使得满足方程：

\[A\mathbf{x} = \lambda B\mathbf{x} \]

当B可逆时，问题可转化为标准特征值问题\(B^{-1}A\mathbf{x} = \lambda\mathbf{x}\)，但直接求逆可能数值不稳定，尤其当B接近奇异时。QZ算法通过同时将A和B转化为上三角矩阵（或拟三角矩阵）来避免显式求逆，适用于任意矩阵对(A,B)。

解题过程

1. 问题转化：Hessenberg-三角分解

• 目标：通过正交变换将A化为上Hessenberg矩阵，同时将B化为上三角矩阵。
• 步骤：
  • 首先对B进行QR分解：\(B = QR\)，其中Q正交，R为上三角矩阵。
  • 计算\(\tilde{A} = Q^\top A Q\)，此时原问题等价于\(\tilde{A}\mathbf{y} = \lambda R\mathbf{y}\)（其中\(\mathbf{y} = Q^\top\mathbf{x}\)）。
  • 对\(\tilde{A}\)应用Householder变换，将其化为上Hessenberg矩阵H，同时保持R的上三角性（需右乘变换矩阵的转置以保证B的形式不变）。
• 结果：得到矩阵对(H, T)，其中H为上Hessenberg矩阵，T为上三角矩阵，且广义特征值不变。

2. 迭代降阶：隐式QZ迭代

• 核心思想：通过一系列正交变换，使H的非对角元素逐渐趋近于零，同时保持T的上三角性。
• 单步迭代流程：
  • 步骤1（位移选择）：计算广义特征值的近似位移（如通过H和T的右下角2×2子矩阵的广义特征值）。
  • 步骤2（隐式变换）：
    • 构造一个正交矩阵P，使其第一列与向量\((H - \sigma T)e_1\)（其中σ为位移）共线。
    • 对H和T同时左乘P、右乘Pᵀ：

\[ H \leftarrow P H P^\top, \quad T \leftarrow P T P^\top \]

- 此时H可能不再保持Hessenberg形式，但可通过额外的Givens旋转恢复其结构，同时保持T的上三角性。  

• 步骤3（收敛检查）：若H的次对角线元素\(|h_{i+1,i}|\)小于容差，则可将问题分解为更小的子问题。

3. 特征值提取

• 当H和T均转化为拟三角矩阵（H为准上三角，T为上三角）时，广义特征值由对角线比值给出：

\[ \lambda_i = \frac{H_{ii}}{T_{ii}} \quad (\text{若}T_{ii} \neq 0) \]

• 若T_{ii}=0而H_{ii}≠0，则特征值为无穷；若H_{ii}=T_{ii}=0，则特征值不确定（退化情况）。

4. 特征向量计算（可选）

• 通过反向代入法求解广义特征向量：
  • 利用变换后的矩阵对(H, T)，从最后一个非零行开始逐行求解\((H - \lambda T)\mathbf{y} = 0\)。
  • 最终通过正交变换还原原问题的特征向量：\(\mathbf{x} = Q\mathbf{y}\)。

关键点

• QZ算法通过正交变换避免数值不稳定性，适用于任意矩阵对，无需B可逆。
• 隐式位移技术加速收敛，类似标准QR算法中的双步位移策略。
• 实际实现需处理数值误差（如零除问题）和退化情况。