其中 $ m \geq n $（若 $ m < n $，可对 $ A^T $ 操作）。  

双对角化QR迭代算法计算矩阵奇异值 题目描述 双对角化QR迭代算法是计算矩阵奇异值分解（SVD）的核心数值方法。其核心思想是将任意矩阵通过双对角化预处理转化为双对角矩阵，再通过隐式QR迭代算法逐步逼近奇异值。最终，双对角矩阵的非零元素收敛到原矩阵的奇异值。这一方法结合了高效预处理和稳定迭代，是LAPACK等标准库中SVD计算的基础。 解题过程 双对角化预处理 目标：将任意矩阵 \( A \in \mathbb{R}^{m \times n} \) 转化为双对角矩阵 \( B \)，即仅主对角线及其上方一条对角线非零，形式如下： \[ B = \begin{pmatrix} d_ 1 & e_ 1 & 0 & \cdots & 0 \\ 0 & d_ 2 & e_ 2 & \cdots & 0 \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & \cdots & 0 & d_ {n-1} & e_ {n-1} \\ 0 & \cdots & 0 & 0 & d_ n \end{pmatrix} \] 其中 \( m \geq n \)（若 \( m < n \)，可对 \( A^T \) 操作）。 方法：通过左乘Householder反射矩阵 \( U_ k \) 和右乘Householder反射矩阵 \( V_ k \)，逐步消去非双对角元素。具体步骤： 左乘 \( U_ 1 \) 消去 \( A \) 第一列下方元素。 右乘 \( V_ 1 \) 消去 \( U_ 1A \) 第一行右侧元素（保留第一行前两个元素）。 重复交替左乘和右乘，直至得到 \( B = U^T A V \)，其中 \( U, V \) 为正交矩阵。 意义：双对角化将SVD问题简化为双对角矩阵 \( B \) 的奇异值计算，且 \( B \) 的奇异值等于 \( A \) 的奇异值。 隐式QR迭代求奇异值 目标：对双对角矩阵 \( B \) 进行迭代，使其非对角元素 \( e_ i \) 趋于零，此时对角线元素 \( d_ i \) 收敛到奇异值。 关键步骤： 计算位移量 ：每次迭代选取位移量 \( \mu \)，常用Wilkinson位移（取 \( B \) 右下角 \( 2 \times 2 \) 子矩阵的特征值中更接近 \( d_ n \) 的一个）。 隐式QR步骤 ： 计算Givens旋转 \( G_ 1 \)，使向量 \( (d_ 1^2 - \mu, d_ 1e_ 1) \) 的第二分量归零，对 \( B \) 左乘 \( G_ 1 \)（仅影响前两行）。 右乘Givens旋转恢复双对角形式：通过右乘旋转矩阵逐列消去因左乘引入的非零元素。 重复此过程，使非零元素“追逐”至矩阵右下角，最终非对角元素 \( e_ i \) 逐渐衰减。 收敛判断 ：当某个 \( |e_ i| \) 小于容差（如 \( \epsilon \cdot (|d_ i| + |d_ {i+1}|) \)）时，设 \( e_ i = 0 \)，将 \( B \) 分割为更小的子矩阵分别处理。 优势：隐式QR避免直接形成 \( B^T B \)（可能数值不稳定），且每次迭代仅需 \( O(n) \) 操作。 后处理与SVD重构 当所有 \( e_ i \) 收敛到零时，对角线元素 \( d_ i \) 即为 \( A \) 的奇异值。 若需要显式SVD（\( A = U \Sigma V^T \)），需记录双对角化和QR迭代中的正交变换： 左变换累积为 \( U = U_ 1 U_ 2 \cdots U_ k \)。 右变换累积为 \( V = V_ 1 V_ 2 \cdots V_ k \)。 最终 \( \Sigma \) 为由 \( d_ i \) 构成的对角矩阵。 总结 双对角化QR迭代算法通过预处理降低问题复杂度，再结合隐式QR迭代的稳定性，高效精确地计算奇异值。其核心贡献在于将密集矩阵的SVD转化为稀疏（双对角）矩阵的迭代问题，是现代数值线性代数中SVD计算的基石。