分块矩阵的广义特征值问题QZ算法

我将为您详细讲解分块矩阵的广义特征值问题的QZ算法，这是一个用于求解广义特征值问题Ax = λBx的重要数值算法。

问题描述
给定两个n×n矩阵A和B，广义特征值问题要求找到标量λ和非零向量x，使得Ax = λBx。当A和B是大型分块矩阵时，直接求解变得困难。QZ算法通过同时将A和B转化为上三角形式来求解广义特征值问题。

算法步骤详解

第一步：矩阵预处理

1. 首先对矩阵A和B进行平衡处理，通过对角变换D₁AD₂和D₁BD₂来改善数值稳定性，其中D₁和D₂是对角矩阵
2. 平衡的目标是使对应行和列的范数尽可能接近，减少后续计算的舍入误差

第二步：Hessenberg-三角分解

1. 对矩阵B进行QR分解：B = QR，其中Q是正交矩阵，R是上三角矩阵
2. 将A变换为Hessenberg形式：通过正交相似变换P，使得PᵀAP是上Hessenberg矩阵
3. 同时保持B的三角性：PᵀBP仍然是上三角矩阵
4. 具体过程：
   • 从第一列开始，对每一列应用Householder变换
   • 每次变换只影响当前列下方的元素
   • 确保正交变换同时作用于A和B

第三步：隐式双步QR迭代

1. 这是QZ算法的核心部分，通过迭代将A的次对角线元素驱向零
2. 每次迭代包含以下子步骤：
   a. 选择位移：通常使用广义Rayleigh商或Wilkinson位移
   b. 计算初始变换：基于位移构造正交矩阵
   c. 追击过程：通过一系列Givens旋转或反射，将扰动传播到整个矩阵
   d. 保持结构：确保A保持Hessenberg形式，B保持三角形式

第四步：特征值提取

1. 当迭代收敛后，A和B都变为拟三角形式
2. 特征值通过解2×2子问题得到：
   • 对于1×1块：λ = aᵢᵢ/bᵢᵢ
   • 对于2×2块：解det(A₂₂ - λB₂₂) = 0
3. 特殊情况处理：
   • 当bᵢᵢ接近零时，对应无限特征值
   • 检测和处理病态情况

第五步：特征向量求解（可选）

1. 逆迭代法：对每个特征值λ，解(A - λB)x = 0
2. 使用回代法利用三角结构
3. 正交化处理接近的特征值对应的特征向量

数值稳定性考虑

• 算法中大量使用正交变换，具有良好的数值稳定性
• 需要监控条件数，避免除零错误
• 对接近奇异的B矩阵需要特殊处理

收敛性分析

• QZ算法通常具有二次收敛性
• 对于病态问题可能需要更多迭代步骤
• 实际应用中通常需要O(n³)次运算

这个算法通过将复杂的分块矩阵广义特征值问题转化为更易处理的形式，是数值线性代数中求解广义特征值问题的标准方法。