广义特征值问题的QZ算法
字数 1606 2025-11-02 10:11:21

广义特征值问题的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化为上三角矩阵。

  1. 首先对B进行QR分解：\(B = Q_B R_B\)，其中\(R_B\)为上三角矩阵。
  2. 计算\(\tilde{A} = Q_B^T A Q_B\)，此时问题转化为\((\tilde{A}, R_B)\)，且\(R_B\)为上三角矩阵。
  3. 对\(\tilde{A}\)应用Householder变换，将其化为上Hessenberg矩阵H（次对角线以下全为零），同时保持\(R_B\)的上三角结构。具体做法：
    • 从第1列到第n-2列，对每一列应用左乘和右乘正交变换，消去当前列次对角线以下的元素，并同步更新\(R_B\)（左乘影响行，右乘影响列，但右乘不破坏\(R_B\)的三角结构）。
      最终得到：

\[Q^T A Z = H \quad (\text{上Hessenberg}), \quad Q^T B Z = T \quad (\text{上三角}) \]

其中\(Q, Z\)为正交矩阵。

步骤2：迭代降阶（隐式双步位移QZ迭代）
核心思想：通过位移技术加速拟三角矩阵的次对角线元素收敛到零。

  1. 选择位移：通常使用广义Rayleigh商或隐式双步位移（如从右下角2×2子矩阵计算位移对(α,β)）。
  2. 隐式QZ迭代：
    • 构造一个初等正交变换矩阵（如Givens旋转），作用于矩阵对(H,T)的第一行和第一列，引入一个非零元素，但保持H的Hessenberg形式。
    • 通过追赶（bulge chasing）将非零元素向下推移，直到次对角线以下全部恢复为零。
      具体流程：
      a. 计算初始变换矩阵，使\((H - \sigma_1 T)(H - \sigma_2 T)\)的第一列与某个向量对齐（实际中不显式计算乘积，而是通过解一个小规模问题确定变换）。
      b. 左乘变换到H和T，这会破坏H的Hessenberg形式（在第三行第一列引入非零元，称为bulge）。
      c. 依次应用Givens旋转（左乘和右乘），将bulge沿对角线向下移动，直到被逐出矩阵右下角。
  3. 重复迭代，直到H的某一次对角线元素可忽略（例如\(|h_{i+1,i}| < \epsilon (|h_{i,i}| + |h_{i+1,i+1}|)\)），此时可将问题分解为更小的子问题。

步骤3：提取特征值
当H和T均被化为拟三角矩阵（H是上三角或拟三角，T是上三角）时，广义特征值由对角线比值给出：

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

若\(T_{ii} = 0\)且\(H_{ii} \neq 0\)，则特征值为无穷；若两者均为零，则特征值不确定。

关键点说明

  • QZ算法通过正交变换保持数值稳定性，避免显式求逆。
  • 迭代中位移的选择影响收敛速度，隐式双步位移可避免复数运算（对实矩阵对）。
  • 最终形式为广义Schur分解：\(A = Q S Z^T, \quad B = Q T Z^T\)，其中S和T分别为上三角矩阵。

通过以上步骤，QZ算法可高效稳定地求解任意矩阵对的广义特征值问题。

广义特征值问题的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 = Q_ B R_ B\)，其中\(R_ B\)为上三角矩阵。 计算\(\tilde{A} = Q_ B^T A Q_ B\)，此时问题转化为\((\tilde{A}, R_ B)\)，且\(R_ B\)为上三角矩阵。 对\(\tilde{A}\)应用Householder变换，将其化为上Hessenberg矩阵H（次对角线以下全为零），同时保持\(R_ B\)的上三角结构。具体做法： 从第1列到第n-2列，对每一列应用左乘和右乘正交变换，消去当前列次对角线以下的元素，并同步更新\(R_ B\)（左乘影响行，右乘影响列，但右乘不破坏\(R_ B\)的三角结构）。 最终得到： \[ Q^T A Z = H \quad (\text{上Hessenberg}), \quad Q^T B Z = T \quad (\text{上三角}) \] 其中\(Q, Z\)为正交矩阵。 步骤2：迭代降阶（隐式双步位移QZ迭代） 核心思想：通过位移技术加速拟三角矩阵的次对角线元素收敛到零。 选择位移：通常使用广义Rayleigh商或隐式双步位移（如从右下角2×2子矩阵计算位移对(α,β)）。 隐式QZ迭代： 构造一个初等正交变换矩阵（如Givens旋转），作用于矩阵对(H,T)的第一行和第一列，引入一个非零元素，但保持H的Hessenberg形式。 通过追赶（bulge chasing）将非零元素向下推移，直到次对角线以下全部恢复为零。 具体流程： a. 计算初始变换矩阵，使\( (H - \sigma_ 1 T)(H - \sigma_ 2 T) \)的第一列与某个向量对齐（实际中不显式计算乘积，而是通过解一个小规模问题确定变换）。 b. 左乘变换到H和T，这会破坏H的Hessenberg形式（在第三行第一列引入非零元，称为bulge）。 c. 依次应用Givens旋转（左乘和右乘），将bulge沿对角线向下移动，直到被逐出矩阵右下角。 重复迭代，直到H的某一次对角线元素可忽略（例如\(|h_ {i+1,i}| < \epsilon (|h_ {i,i}| + |h_ {i+1,i+1}|)\)），此时可将问题分解为更小的子问题。 步骤3：提取特征值 当H和T均被化为拟三角矩阵（H是上三角或拟三角，T是上三角）时，广义特征值由对角线比值给出： \[ \lambda_ i = \frac{H_ {ii}}{T_ {ii}} \quad (\text{若}T_ {ii} \neq 0) \] 若\(T_ {ii} = 0\)且\(H_ {ii} \neq 0\)，则特征值为无穷；若两者均为零，则特征值不确定。 关键点说明 QZ算法通过正交变换保持数值稳定性，避免显式求逆。 迭代中位移的选择影响收敛速度，隐式双步位移可避免复数运算（对实矩阵对）。 最终形式为广义Schur分解：\(A = Q S Z^T, \quad B = Q T Z^T\)，其中S和T分别为上三角矩阵。 通过以上步骤，QZ算法可高效稳定地求解任意矩阵对的广义特征值问题。