双步QR算法计算矩阵特征值 题目描述 ： 给定一个n×n实矩阵A，要求计算它的所有特征值。双步QR算法是高效计算中小型稠密矩阵全部特征值的数值方法，特别适用于上Hessenberg矩阵。该算法通过隐式双步位移策略，在保持数值稳定性的同时避免复数运算，实现对实矩阵的特征值计算。 解题过程 ： 1. 矩阵预处理（上Hessenberg化） 目标 ：将矩阵A通过正交相似变换化为上Hessenberg矩阵H（即当i>j+1时h_ ij=0）。 步骤 ： a. 对k=1,2,...,n-2列依次进行： 选取Householder变换矩阵P_ k，使得A的第k列下方元素非零部分被消去。 b. 执行相似变换：A ← P_ k·A·P_ k^T，保持特征值不变。 作用 ：减少后续QR迭代的计算量，且Hessenberg结构在迭代中保持不变。 2. 双步位移策略原理 单步QR算法：H - μI = QR，H' = RQ + μI（μ为位移量）。 双步位移 ：连续使用两个单步位移，但隐式执行： a. 选取位移μ₁和μ₂（通常取H右下角2×2子矩阵的特征值）。 b. 计算向量v = (H - μ₁I)(H - μ₂I)e₁（e₁为第一标准基向量）。 c. 构造Householder变换使v对齐到e₁方向，并传播变换以保持Hessenberg形。 3. 隐式双步QR迭代 初始化 ：设当前矩阵为H（上Hessenberg形），迭代次数m=0。 循环直至收敛 （例如右下角子矩阵近似对角块）： a. 位移计算 ：取H右下角2×2块[ [ h_ {n-1,n-1}, h_ {n-1,n}], [ h_ {n,n-1}, h_ {n,n}] ]，计算其特征值μ₁, μ₂。 b. 首列变换 ： 计算向量v = (H - μ₁I)(H - μ₂I)·e₁（仅前三个分量非零）。 构造3×3 Householder矩阵P₀，使v映射到βe₁。 将P₀嵌入n×n矩阵U₀，更新H ← U₀·H·U₀^T。 c. ** bulge追逐** ： 对j=1 to n-3，构造Householder矩阵P_ j，消去H第j+1列在j+2行以下的非零元素。 每次变换后更新H ← P_ j·H·P_ j^T，使非零元素"下推"并保持Hessenberg形。 d. 收敛检查 ：若|h_ {n,n-1}|或|h_ {n-1,n-2}|小于容差，将右下角1×1或2×2块视为已收敛，对剩余子矩阵递归迭代。 4. 特征值提取 最终H近似为准上三角矩阵（实特征值在对角线，复特征值在2×2对角块）。 对每个1×1块：特征值即对角元。 对每个2×2块：计算其特征值（可能为共轭复数对）。 关键点 ： 隐式位移避免直接计算(H - μ₁I)(H - μ₂I)的QR分解，提升数值稳定性。 通过bulge追逐将双步位移的效果隐式实现，避免复数运算。 每次迭代复杂度O(n²)，优于显式QR算法的O(n³)。