带位移的QR迭代算法求解实矩阵特征值
字数 2474 2025-12-21 13:10:09

带位移的QR迭代算法求解实矩阵特征值

题目描述
给定一个实矩阵 A ∈ ℝⁿˣⁿ，要求计算其所有特征值（可能是实数或共轭复数对）。QR迭代算法是数值计算中求解一般矩阵所有特征值最核心的方法之一。然而，基本的QR迭代（即不带位移）收敛速度可能很慢，尤其对于具有相近或复数特征值的矩阵。带位移的QR迭代通过引入适当的位移（shift）来加速收敛，使其在每一步迭代中更快地将矩阵化为（拟）上三角形式（即Schur形式），从而揭示特征值。本题将详细讲解带位移的QR迭代算法的原理、Hessenberg预处理、单步位移与双步位移策略、以及完整的算法流程。

解题过程

我们循序渐进地讲解如何通过带位移的QR迭代求解实矩阵A的所有特征值。

1. 基本QR迭代算法回顾
基本QR迭代算法从一个初始矩阵 A₀ = A 开始，重复以下步骤：

  1. 对当前矩阵 Aₖ 进行QR分解：Aₖ = Qₖ Rₖ，其中Qₖ是正交矩阵，Rₖ是上三角矩阵。
  2. 计算下一个迭代矩阵：Aₖ₊₁ = Rₖ Qₖ。
    这个过程产生一个矩阵序列 {Aₖ}，在一般情况下，Aₖ 会收敛到一个上三角矩阵（或实Schur形式，即拟上三角矩阵），其对角线元素（或2×2块的特征值）就是A的特征值。

2. 预处理：约化为上Hessenberg形式
为了高效计算QR分解并保持结构，我们首先通过相似变换（正交变换）将A化为上Hessenberg形式H，即hᵢⱼ = 0 对于所有 i > j+1（次对角线以下全为零）。

  • 使用Householder反射或Givens旋转，经过n-2步将A变换为H：H = Qᵀ A Q，其中Q是正交矩阵。
  • 由于相似变换不改变特征值，A的特征值与H相同。而且上Hessenberg形式在QR迭代中能保持，大大减少计算量（每一步QR分解只需O(n²)而非O(n³)）。

3. 带位移的QR迭代：基本思想
在迭代中，若我们已知某个特征值λ的近似值σ，可以应用位移策略：对矩阵 (H - σI) 进行QR分解，然后反向组合并加回位移。
单步位移迭代（对于实矩阵，通常用单步位移处理实特征值）：

  1. 选择位移σₖ（通常取当前矩阵右下角元素hₙₙ，称为Rayleigh商位移）。
  2. 计算QR分解：Hₖ - σₖ I = Qₖ Rₖ。
  3. 更新：Hₖ₊₁ = Rₖ Qₖ + σₖ I。
    位移的引入可以加速右下角元素收敛到一个特征值（当hₙ,ₙ₋₁趋于零时，hₙₙ即为特征值）。

4. 双步位移策略：处理复特征值
对于实矩阵，复特征值成共轭对出现。若使用实位移（σ为实数），无法直接加速复特征值的收敛。Francis双步位移策略通过隐式地使用一对共轭复位移，保持所有计算在实数域内进行。

  • 设当前Hessenberg矩阵为H，我们希望应用两个位移σ₁和σ₂（通常取H右下2×2子矩阵的特征值，可能是实数或共轭复数）。
  • 显式计算矩阵 M = (H - σ₁ I)(H - σ₂ I) 的第一列，然后通过一个正交相似变换（通常是Householder反射）将M的第一列对齐到e₁方向，并将这个变换应用到H上，通过“ bulge chasing ”（追 bulge）过程，在保持上Hessenberg形式的同时，隐式地完成双步QR迭代。
  • 这个过程避免了复数运算，同时获得了双步位移的加速效果。

5. 完整的带双步位移的隐式QR算法步骤
我们以实矩阵A为例，给出完整求解过程：

  1. 上Hessenberg化：使用Householder变换计算 H = Q₀ᵀ A Q₀，并存储变换矩阵Q₀（若需要特征向量）。
  2. 设置迭代：令当前矩阵为 H，设置收敛容差 ε（如 ε = 1e-12），迭代计数器 k=0。
  3. 检查收敛：扫描次对角线元素 |hᵢ,ᵢ₋₁|（i=n,n-1,...,2）。若某个 |hᵢ,ᵢ₋₁| ≤ ε·(|hᵢ₋₁,ᵢ₋₁| + |hᵢᵢ|)，则视为零。此时矩阵可分割为两个更小的块：
    • 若 i = n，则 hₙₙ 是一个特征值（1×1块），n 减 1。
    • 若 i = n-1，则右下2×2块的特征值是一对实特征值或共轭复对，将其分离，n 减 2。
  4. 选择位移：
    • 若当前右下块大小为1×1（即已收敛一个实特征值），用单步位移 σ = hₙₙ。
    • 若当前右下块大小为 m×m（m≥2），计算右下角2×2子矩阵的特征值作为位移对 (σ₁, σ₂)。若它们是实数，可能使用两个单步位移；若是共轭复数，则使用双步位移策略。
  5. 执行QR迭代：
    • 对于单步位移（实位移）：显式或隐式进行带位移的QR迭代一步。
    • 对于双步位移：采用上述隐式双步位移QR迭代（ bulge chasing ）。
  6. 更新迭代矩阵：得到新的Hessenberg矩阵 H（由于隐式变换，它仍是上Hessenberg形式）。
  7. 循环：k = k+1，返回步骤3，直到整个矩阵被分解为1×1和2×2块（即达到实Schur形式）。
  8. 提取特征值：从最终的拟上三角矩阵中，1×1块给出实特征值，2×2块通过求解二次方程给出两个特征值（可能为实数或共轭复数）。
  9. 特征向量（若需要）：累积所有相似变换的正交矩阵 Q_total = Q₀ Q₁ Q₂ ...，则 A 的特征向量可由 Q_total 的相应列给出（需进一步回代求解）。

6. 收敛性与复杂度

  • 带位移的QR迭代通常具有二次甚至三次局部收敛速度。
  • 由于每步迭代操作于上Hessenberg矩阵，QR分解成本为O(n²)。总迭代次数通常为O(n)（每个特征值约需2-3步），因此总复杂度约为O(n³)，与矩阵乘法的复杂度相当。
  • 该算法是数值稳定的，因为仅使用正交相似变换。

总结
带位移的QR迭代算法通过引入位移加速收敛，并借助隐式双步位移处理复特征值，是求解一般实矩阵所有特征值的标准方法。其核心步骤包括：上Hessenberg化、位移选择、隐式QR迭代、以及收敛判断与矩阵分割。该算法在实践中被广泛应用（如MATLAB的 eig 函数），是数值线性代数中特征值计算的基石之一。

带位移的QR迭代算法求解实矩阵特征值 题目描述 给定一个实矩阵 A ∈ ℝⁿˣⁿ，要求计算其所有特征值（可能是实数或共轭复数对）。QR迭代算法是数值计算中求解一般矩阵所有特征值最核心的方法之一。然而，基本的QR迭代（即不带位移）收敛速度可能很慢，尤其对于具有相近或复数特征值的矩阵。带位移的QR迭代通过引入适当的位移（shift）来加速收敛，使其在每一步迭代中更快地将矩阵化为（拟）上三角形式（即Schur形式），从而揭示特征值。本题将详细讲解带位移的QR迭代算法的原理、Hessenberg预处理、单步位移与双步位移策略、以及完整的算法流程。 解题过程 我们循序渐进地讲解如何通过带位移的QR迭代求解实矩阵A的所有特征值。 1. 基本QR迭代算法回顾 基本QR迭代算法从一个初始矩阵 A₀ = A 开始，重复以下步骤： 对当前矩阵 Aₖ 进行QR分解：Aₖ = Qₖ Rₖ，其中Qₖ是正交矩阵，Rₖ是上三角矩阵。 计算下一个迭代矩阵：Aₖ₊₁ = Rₖ Qₖ。 这个过程产生一个矩阵序列 {Aₖ}，在一般情况下，Aₖ 会收敛到一个上三角矩阵（或实Schur形式，即拟上三角矩阵），其对角线元素（或2×2块的特征值）就是A的特征值。 2. 预处理：约化为上Hessenberg形式 为了高效计算QR分解并保持结构，我们首先通过相似变换（正交变换）将A化为上Hessenberg形式H，即hᵢⱼ = 0 对于所有 i > j+1（次对角线以下全为零）。 使用Householder反射或Givens旋转，经过n-2步将A变换为H：H = Qᵀ A Q，其中Q是正交矩阵。 由于相似变换不改变特征值，A的特征值与H相同。而且上Hessenberg形式在QR迭代中能保持，大大减少计算量（每一步QR分解只需O(n²)而非O(n³)）。 3. 带位移的QR迭代：基本思想 在迭代中，若我们已知某个特征值λ的近似值σ，可以应用位移策略：对矩阵 (H - σI) 进行QR分解，然后反向组合并加回位移。 单步位移迭代（对于实矩阵，通常用单步位移处理实特征值）： 选择位移σₖ（通常取当前矩阵右下角元素hₙₙ，称为Rayleigh商位移）。 计算QR分解：Hₖ - σₖ I = Qₖ Rₖ。 更新：Hₖ₊₁ = Rₖ Qₖ + σₖ I。 位移的引入可以加速右下角元素收敛到一个特征值（当hₙ,ₙ₋₁趋于零时，hₙₙ即为特征值）。 4. 双步位移策略：处理复特征值 对于实矩阵，复特征值成共轭对出现。若使用实位移（σ为实数），无法直接加速复特征值的收敛。Francis双步位移策略通过隐式地使用一对共轭复位移，保持所有计算在实数域内进行。 设当前Hessenberg矩阵为H，我们希望应用两个位移σ₁和σ₂（通常取H右下2×2子矩阵的特征值，可能是实数或共轭复数）。 显式计算矩阵 M = (H - σ₁ I)(H - σ₂ I) 的第一列，然后通过一个正交相似变换（通常是Householder反射）将M的第一列对齐到e₁方向，并将这个变换应用到H上，通过“ bulge chasing ”（追 bulge）过程，在保持上Hessenberg形式的同时，隐式地完成双步QR迭代。 这个过程避免了复数运算，同时获得了双步位移的加速效果。 5. 完整的带双步位移的隐式QR算法步骤 我们以实矩阵A为例，给出完整求解过程： 上Hessenberg化 ：使用Householder变换计算 H = Q₀ᵀ A Q₀，并存储变换矩阵Q₀（若需要特征向量）。 设置迭代 ：令当前矩阵为 H，设置收敛容差 ε（如 ε = 1e-12），迭代计数器 k=0。 检查收敛 ：扫描次对角线元素 |hᵢ,ᵢ₋₁|（i=n,n-1,...,2）。若某个 |hᵢ,ᵢ₋₁| ≤ ε·(|hᵢ₋₁,ᵢ₋₁| + |hᵢᵢ|)，则视为零。此时矩阵可分割为两个更小的块： 若 i = n，则 hₙₙ 是一个特征值（1×1块），n 减 1。 若 i = n-1，则右下2×2块的特征值是一对实特征值或共轭复对，将其分离，n 减 2。 选择位移 ： 若当前右下块大小为1×1（即已收敛一个实特征值），用单步位移 σ = hₙₙ。 若当前右下块大小为 m×m（m≥2），计算右下角2×2子矩阵的特征值作为位移对 (σ₁, σ₂)。若它们是实数，可能使用两个单步位移；若是共轭复数，则使用双步位移策略。 执行QR迭代 ： 对于单步位移（实位移）：显式或隐式进行带位移的QR迭代一步。 对于双步位移：采用上述隐式双步位移QR迭代（ bulge chasing ）。 更新迭代矩阵 ：得到新的Hessenberg矩阵 H（由于隐式变换，它仍是上Hessenberg形式）。 循环 ：k = k+1，返回步骤3，直到整个矩阵被分解为1×1和2×2块（即达到实Schur形式）。 提取特征值 ：从最终的拟上三角矩阵中，1×1块给出实特征值，2×2块通过求解二次方程给出两个特征值（可能为实数或共轭复数）。 特征向量（若需要） ：累积所有相似变换的正交矩阵 Q_ total = Q₀ Q₁ Q₂ ...，则 A 的特征向量可由 Q_ total 的相应列给出（需进一步回代求解）。 6. 收敛性与复杂度 带位移的QR迭代通常具有二次甚至三次局部收敛速度。 由于每步迭代操作于上Hessenberg矩阵，QR分解成本为O(n²)。总迭代次数通常为O(n)（每个特征值约需2-3步），因此总复杂度约为O(n³)，与矩阵乘法的复杂度相当。 该算法是数值稳定的，因为仅使用正交相似变换。 总结 带位移的QR迭代算法通过引入位移加速收敛，并借助隐式双步位移处理复特征值，是求解一般实矩阵所有特征值的标准方法。其核心步骤包括：上Hessenberg化、位移选择、隐式QR迭代、以及收敛判断与矩阵分割。该算法在实践中被广泛应用（如MATLAB的 eig 函数），是数值线性代数中特征值计算的基石之一。