QR算法计算矩阵特征值 题目描述 给定一个n×n实矩阵A，要求计算它的所有特征值。QR算法是一种通过迭代将矩阵逐步转化为上三角矩阵（或拟上三角矩阵，若A有复特征值）来求解特征值的数值方法。上三角矩阵的对角线元素就是原矩阵的特征值。 解题过程 基本思想 QR算法的核心思想是迭代。在每一步迭代中，它将当前矩阵A_ k分解为一个正交矩阵Q_ k和一个上三角矩阵R_ k的乘积（即QR分解），然后反转顺序相乘得到下一个迭代矩阵A_ {k+1} = R_ k Q_ k。这个过程会逐渐将A_ k转化为一个上三角矩阵（对于对称矩阵）或一个上三角分块矩阵（Schur型，对于非对称矩阵），其对角线上的元素（或块）揭示了特征值。 预处理：Hessenberg化 直接对稠密矩阵应用QR算法效率较低。一个关键的预处理步骤是通过相似变换将原矩阵A转化为上Hessenberg矩阵（即所有下对角线以下的元素都为零）。这个变换通过Householder反射或Givens旋转实现，且是相似变换（B = P^T A P，P为正交矩阵），故变换后的矩阵B与原矩阵A具有相同的特征值。上Hessenberg矩阵的特殊结构能显著加速后续的QR分解过程。 带位移的QR迭代 基本的QR算法收敛可能很慢。为了加速收敛，引入了位移策略。最常用的是单步位移（对于实矩阵，若预期有复特征值，则用双步位移以避免复数运算）。在第k步迭代中： a. 选择一个位移量μ_ k。一个常见选择是取当前矩阵A_ k的右下角元素（Rayleigh商位移）或通过计算右下角2x2子矩阵的特征值来得到更精确的位移（Wilkinson位移）。 b. 计算位移后的QR分解：(A_ k - μ_ k I) = Q_ k R_ k。 c. 通过反转顺序并加回位移来形成下一个迭代矩阵：A_ {k+1} = R_ k Q_ k + μ_ k I。 位移策略能极大地改善收敛速度，特别是对于特征值分离较好的情况。 收敛性与终止条件 随着迭代的进行，矩阵A_ k的下次对角线元素会逐渐趋近于零。当某个下次对角线元素a_ {i+1,i}的绝对值小于一个预设的容差（例如，容差 = 机器精度 × (|a_ {i,i}| + |a_ {i+1,i+1}|)）时，我们就可以认为a_ {i+1,i}可视为零。此时，矩阵可以被“分割”成更小的块进行处理： 如果a_ {i,i}是一个1x1的块，那么它就是一个实特征值。 如果a_ {i,i}和a_ {i+1,i+1}以及它们之间的元素构成一个2x2的块，并且这个块对应的下次对角线元素已收敛到零，那么这个2x2块的特征值就是一对共轭复特征值（或两个实特征值）。 算法继续对尚未收敛的左上角子矩阵应用QR迭代，直到整个矩阵被分解。 提取特征值 当算法完全收敛后，得到的矩阵是一个上三角矩阵（或实Schur型矩阵）。该矩阵对角线上的1x1块直接给出实特征值，而2x2块的特征值可通过求解二次方程得到（这对原矩阵而言是一对共轭复特征值）。这些特征值的集合就是原矩阵A的特征值。 总结 QR算法通过预处理（Hessenberg化）和带位移的迭代（QR分解与顺序反转），将一个一般矩阵通过相似变换逐步化为能直接读取特征值的拟三角形式。位移策略是关键的速度提升手段，而收敛判断则允许算法递归地处理更小的子问题。