QR分解法计算矩阵特征值

题目描述：给定一个n×n实矩阵A，要求通过QR分解法计算A的所有特征值。QR算法是一种通过迭代QR分解将矩阵逐步转化为上三角矩阵（或拟上三角矩阵）的方法，从而近似特征值。

解题过程：

1. 算法原理
   QR算法基于一个关键观察：如果矩阵A可以分解为A=QR（Q是正交矩阵，R是上三角矩阵），那么通过构造新矩阵A₁=RQ，A₁与A相似（因为A₁=RQ=QᵀA Q），因此特征值相同。重复这一过程，矩阵序列会收敛到上三角矩阵，对角线元素即为特征值。

2. 基本QR迭代步骤

   • 步骤1：对当前矩阵Aₖ进行QR分解：Aₖ = QₖRₖ
   • 步骤2：计算新矩阵Aₖ₊₁ = RₖQₖ
   • 步骤3：检查Aₖ₊₁是否接近上三角矩阵（非对角线元素足够小）
   • 步骤4：若未收敛，令k=k+1返回步骤1；若收敛，对角线元素即为特征值

3. 实际改进：上Hessenberg化
   直接对稠密矩阵进行QR迭代效率低。实际中先通过Householder变换将矩阵化为上Hessenberg形式（类似上三角但多一次对角线）：

   • 对i=1到n-2列：
     • 计算Householder反射矩阵Hᵢ使第i列下方元素归零
     • 执行相似变换：A ← HᵢAHᵢ
       这样得到的Hessenberg矩阵保持特征值且QR分解更高效。

4. 位移加速收敛
   为加快收敛速度，引入位移策略：

   • 隐式位移：每次迭代取右下角2×2子矩阵的特征值作为位移量μ
   • 带位移的QR迭代：Aₖ - μI = QₖRₖ, Aₖ₊₁ = RₖQₖ + μI
   • 双步位移：对实矩阵避免复数运算，使用两个连续位移

5. 具体计算示例（简化）
   设矩阵A已化为Hessenberg形式：
   ⎡ 4 -1 0 ⎤
   ⎢-1 4 -1⎥
   ⎣ 0 -1 4⎦

   第一次迭代：

   • 对A进行QR分解（使用Givens旋转）：
     G₁₂消去(2,1)元素得G₁₂A，再G₂₃消去(3,2)元素得R
     Qᵀ = G₂₃G₁₂
   • 计算A₁ = RQ = RG₁₂ᵀG₂₃ᵀ
   • 迭代后次对角线元素逐渐减小

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

   • 当次对角线元素|aᵢ₊₁,ᵢ| < ε时，可分离特征值
   • 2×2块可能给出共轭复特征值
   • 最终矩阵形式：
     ⎡ λ₁ × × ⎤
     ⎢ λ₂ × ⎥
     ⎣ λ₃⎦
     对角线块（1×1或2×2）的特征值即为原矩阵特征值。

7. 算法复杂度与稳定性

   • 每步QR分解复杂度O(n²)（Hessenberg矩阵）
   • 通常需O(n)次迭代收敛
   • 数值稳定性好，是计算中小规模矩阵特征值的标准方法

通过以上步骤，QR算法能有效计算实矩阵的全部特征值，特别适合中小规模稠密矩阵。对于对称矩阵会退化为三对角形式，进一步简化计算。