相似矩阵与变化的元素
特征值算法可以改变矩阵,而不改变它的特征值。在无位移 QR 迭代中,先分解当前矩阵,再把两个因子按相反次序相乘。
定义 5.5.1
(无位移 QR 迭代)
从 出发,分解并重新组合:
这里 是正交矩阵, 是上三角矩阵。对非奇异矩阵,我们选取 对角元素为正的唯一 QR 分解。
最后一个等式说明 与 正交相似,因此保持对称性和特征值不变。我们希望矩阵逐渐接近对角矩阵,使对角元素成为有用的特征值近似。
下面只在一个具体的二维情形中证明这种行为,并不断言它对所有矩阵成立。
定理 5.5.2
(对称 2 阶矩阵的 QR 迭代收敛)
设实对称正定矩阵 具有标准正交特征向量 和特征值 。假设第一坐标向量在 方向有非零分量:
则 收敛到 ,非对角元素的绝对值为 ,对角误差为 。若 ,非对角元素一开始就是零。
为什么 QR 迭代跟随原矩阵的幂
记 ,。反复使用相似变换得到 。
引理 5.5.3
(迭代给出幂的 QR 分解)
对每个 ,
并且这是 的正对角 QR 分解。
证明
(对幂次归纳)
先取 ,此时空乘积为 。然后 ;因此将归纳假设左乘 ,得到 。各 的乘积是对角元素为正的上三角矩阵,所以 (1) 是 的正对角 QR 分解。
有了 (1),收敛定理就归结为对 的幂迭代。
证明
(由第一列读出迭代矩阵的行为)
分解 (1) 的第一列是 。在特征向量基下展开,
它张成的直线与 张成的直线的夹角 满足 。与其正交的单位向量也接近 张成的直线。在这个变化的标准正交基下,非对角元素的绝对值为 ;第一个对角误差为 ,第二个则有相反的误差。因此非对角元素为 ,对角误差为 。
证明透视
一个算法,两种观点
QR 迭代不断改变坐标: 是在随 变化的标准正交基下写出的 。等式 (1) 说明这个基来自 的 QR 分解,其第一列就是对 的普通幂迭代;第二列则由正交性决定,所以在二维空间中一列就足够。各 的对角元素为正,固定了符号,因此第一个基向量是 。假设 使夹角远离直角, 使其正切衰减。正定性只用来使特征值的次序与它们的模的次序一致。
例子与停止信息
例题 5.5.4
(手算第一个迭代矩阵)
对 ,特征值为 和 ,且 ,所以 。第一步中, 的两列为 和 。Gram-Schmidt 给出 、;然后 ,余量 的长度为 ,所以 的第二列是 。因此
这与证明中的公式一致: 给出 、,所以非对角元素为 ,第一个对角元素为 。
推论 5.5.5
(由对角元素得到谱区间)
对称迭代矩阵 满足: 的某个特征值位于 ,并且某个特征值位于 。
证明
(坐标向量的残差)
将单位向量 和近似特征值 代入,残差是 ,范数为 。对对称矩阵,若单位向量对数值 的残差范数为 ,则必有特征值与 相差不超过 :把该向量在标准正交特征基下展开,残差平方为 。矩阵 与 有相同的特征值。对 和 的论证相同。
这是精确算术下的残差证书。
例题 5.5.6
(后面的迭代矩阵与谱区间)
继续取 。由 ,公式给出 、 和 (迹为 ):
| 0 | 2 | 1 | 2 |
| 1 | 2.8 | 0.6 | 1.2 |
| 2 | 2.97561 | 0.21951 | 1.02439 |
| 3 | 2.99726 | 0.07397 | 1.00274 |
时,两个区间 与 重合,都是 ,所以不能用来分开两个特征值。 时它们是 和 ; 时是 和 :区间半径 每步缩小的倍数趋近 ,与速度 的预测一致。
常见错误
(把两个重叠的区间当作两个特征值)
每个区间只保证其中有某个特征值。如果两个对角区间重叠,如上面 的情形,证书并不保证它们确定不同的特征值;两个区间可能指向同一个特征值。
例题 5.5.7
(已经按正确次序对角化的矩阵)
对 ,,所以 、。正对角分解为 、,于是 ,每个迭代矩阵都等于 。非对角元素一开始就是零,与定理对 的陈述一致。
假设排除了什么情况
反例模式
QR 迭代永远不改变的对称矩阵
很容易以为每个实对称矩阵都会被驱向对角形式。取 。它既对称又正交,特征值为 和 。其正对角 QR 分解是 ,因此每个 QR 迭代都等于 ,非对角元素永远不消失。此时 在 与 之间交替,故其张成的直线不收敛。这个不定例子不属于正定定理;特征值的模相同使幂迭代论证失效。每个迭代矩阵都有正确的谱,但矩阵本身没有变化:仅有正交相似性并不能迫使非对角元素减小。
常见错误
(以为较大的特征值一定排在前面)
即使 正定,初始分量也影响所述排序:若 ,则 ,所以 ,假设不成立。迭代始终保持这个顺序。它已经是对角矩阵,却没有变成 。
实用的 QR 特征值求解器还采用位移和降阶等方法;它们的收敛和浮点分析需要单独论证。
练习与解答
快速检查
(为什么 与 有相同的特征值?)
把 用 表示出来。
解答 · 答案
,其中 正交,所以 与 相似,而相似矩阵有相同的特征多项式。
快速检查
(在正定定理中,第一基方向的几何速度由什么决定?)
看夹角 的正切。
解答 · 答案
几何速度是 ;初始系数比控制乘法常数。对角误差每步的速度是 。
快速检查
(若对称迭代矩阵的某个对角元素 、非对角元素 ,给出第一列所保证的谱区间。)
使用残差 。
解答 · 答案
至少有一个特征值位于 。
快速检查
(当 时会发生什么?若要求较大特征值排在第一位,定理的哪个假设失效?)
等于哪个特征向量?
解答 · 答案
每个迭代都是同一个对角矩阵; 在 的特征方向上没有分量,所以 不成立。