QR分解法求矩阵特征值 题目描述 给定一个n×n的实矩阵A，要求使用QR分解法计算该矩阵的所有特征值。QR分解法是一种通过迭代将矩阵收敛到上三角矩阵（或分块上三角矩阵）来求解特征值的方法，特别适用于求解中小规模稠密矩阵的特征值问题。 解题过程 1. 算法基本原理 QR分解法的核心思想是通过一系列正交相似变换，将原矩阵A逐步转化为一个上三角矩阵（或Schur标准型）。由于相似变换保持特征值不变，而三角矩阵的特征值就是其对角线元素，因此可以通过迭代过程求得特征值。 2. 基本QR迭代算法步骤 步骤1：初始化 设A₀ = A（原始矩阵），k = 0（迭代次数计数器） 步骤2：QR分解 对当前矩阵Aₖ进行QR分解： Aₖ = QₖRₖ 其中Qₖ是正交矩阵（QₖᵀQₖ = I），Rₖ是上三角矩阵。 步骤3：矩阵重构 计算下一次迭代矩阵： Aₖ₊₁ = RₖQₖ 步骤4：收敛判断 检查Aₖ₊₁是否满足收敛条件： 检查次对角线元素是否足够小（小于预设容差ε） 或者检查迭代次数是否达到最大限制 步骤5：迭代或终止 如果未收敛，令k = k+1，返回步骤2 如果已收敛，Aₖ₊₁的对角线元素就是特征值的近似值 3. 算法优化：上Hessenberg化 为了提高计算效率，通常先通过相似变换将矩阵化为上Hessenberg形式： 使用Householder变换将A化为上Hessenberg矩阵H H与A相似，具有相同的特征值 对上Hessenberg矩阵进行QR迭代，计算量大大减少 4. 位移技术加速收敛 为了加快收敛速度，引入位移技术： 单步位移： Aₖ - μₖI = QₖRₖ Aₖ₊₁ = RₖQₖ + μₖI 其中位移μₖ通常取Aₖ的右下角元素 双步位移（隐式位移）： 使用两个连续的位移，避免复数运算，提高数值稳定性 5. 特征值提取 当矩阵收敛到上三角形式（实Schur形式）时： 对角线上的1×1块给出实特征值 对角线上的2×2块给出共轭复特征值对 通过求解2×2矩阵的特征方程得到复特征值 6. 数值稳定性考虑 使用Givens旋转或Householder反射进行QR分解 采用隐式位移技术避免数值误差 设置合理的收敛容差（通常为10⁻¹²~10⁻¹⁵） 7. 算法复杂度分析 预处理为上Hessenberg形式：O(n³) 每次QR迭代：O(n²) 总复杂度：O(n³) + k×O(n²)，其中k为迭代次数 这个算法通过正交相似变换保持了数值稳定性，是求解中小规模稠密矩阵特征值的标准方法。