双步隐式位移QR算法计算矩阵特征值

题目描述：
给定一个n×n的实矩阵A，要求计算它的所有特征值。为了提高标准QR算法的效率，特别是对于具有复数特征值的实矩阵，我们采用双步隐式位移QR算法。这个算法通过巧妙的技术避免复数运算，同时保持QR迭代的收敛性。

解题过程：

1. 预处理：将矩阵化为上Hessenberg形式

   • 首先使用Householder变换将矩阵A相似变换为上Hessenberg矩阵H（次对角线以下全为零）。这一步可减少后续迭代的计算量，因为QR分解在Hessenberg矩阵上更高效。
   • 相似变换保证特征值不变：H = Q₁ᵀAQ₁，其中Q₁是正交矩阵。

2. 双步隐式位移策略

   • 标准双步位移QR迭代会使用两个位移量（通常取矩阵右下角2×2子矩阵的特征值）。若特征值为复数，直接处理会引入复数运算。
   • 双步隐式位移的核心思想是：通过实矩阵运算隐式实现两次位移的效果，避免显式使用复数。具体步骤包括：
     a. 计算位移量：取H的右下角2×2块，设其特征值为σ₁和σ₂。
     b. 构造首个Householder向量：计算向量v = (H - σ₁I)(H - σ₂I)e₁（其中e₁是第一个标准基向量），但实际仅需前三个分量，因H是上Hessenberg矩阵。
     c. 应用隐式变换：通过一个特殊的正交变换矩阵P₀（由v构造），使P₀ᵀHP₀仍是上Hessenberg矩阵，但隐式引入了双位移的效果。

3. 保持上Hessenberg结构的隐式QR迭代

   • 从P₀出发，进行一系列Givens旋转或Householder变换，将P₀ᵀHP₀恢复为上Hessenberg形式。这一步称为"紧致化"（bulge chasing）：
     a. 从左到右依次应用正交变换，将次对角线下的非零元素"驱逐"到矩阵右下角。
     b. 每次变换后，矩阵保持相似性，且结构不变。
   • 最终得到新的上Hessenberg矩阵H'，完成一次双步隐式QR迭代：H' = QᵀHQ，其中Q是正交矩阵的乘积。

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

   • 重复迭代直到H的对角块分离：当次对角线元素|hᵢ₊₁,ᵢ|可忽略时，可解耦为更小的子矩阵。
   • 特征值从右下角开始收敛：2×2或1×1的对角块直接给出实特征值或共轭复特征值。
   • 最终所有特征值由对角块的特征值组成。

关键优势：

• 通过隐式处理避免了复数运算，全程使用实算术。
• 每次迭代复杂度为O(n²)，显著优于标准QR算法的O(n³)。
• 特别适合实矩阵含复数特征值的情况，是LAPACK等库中特征值计算的核心算法。