把附近的特征值变成占优特征值
幂迭代放大与最大模特征值对应的特征向量。要寻找接近给定位移 的特征值,可以改为对 使用幂迭代。实际运算通过求解线性方程组进行,不必显式形成逆矩阵。
设 且 对称,具有标准正交特征向量 和实特征值 。选取不是特征值的位移 ,并假设
定义 5.4.1
(带位移的反幂迭代)
从 、 出发,以位移 作反幂迭代,即求解并归一化:
在精确算术中, 可逆,故 。固定位移时,一次矩阵分解可以用于后续所有求解。
定理 5.4.2
(迭代直线的几何收敛)
假设 ,则 张成的直线与 张成的直线之间的夹角至少以几何速度趋于零。更精确地,令
则
这里的夹角是直线之间的夹角,因此 的符号交替不会妨碍收敛。
证明
(位移逆矩阵的幂)
由 (2) 归纳可知, 是下式的归一化结果:
每个系数除以 的系数。所得正交部分的欧几里得(Euclidean)范数等于两条直线夹角的正切,且不超过 (3) 右侧。条件 (1) 保证 。
证明透视
位移为什么改变目标
位移后逆矩阵的特征值是 。 中最接近 的特征值,在取逆后变成模最大的特征值。要得到上述一维收敛结论,必须有严格唯一的最近特征值,还必须有非零的初始对应系数。
二维计算
例题 5.4.3
(对角矩阵的反幂迭代)
取 、 和 。逆矩阵的特征值为 和 ,所以误差比率 。第 步后第二坐标与第一坐标的比为 。向量可能反向,但其张成的直线迅速接近第一坐标轴。
常见错误
(以为位移后的矩阵一定正定)
这个位移比起 更接近 ,但 是不定矩阵。对称性仍然保留,正定性却没有保证。因此不能假定要求矩阵对称正定的 Cholesky 求解器适用于每一种位移。
残差提供事后证书
定理 5.4.4
(对称矩阵的残差证书)
对该对称矩阵 、任意单位向量 和实数 ,定义 。则
因此区间 至少包含一个特征值。
证明
(在特征基中展开)
展开 ,则
由于系数的平方和为一,便得到 (4)。
对于非零非单位向量,类似的界需将残差范数除以 。这种形式的证书依赖对称性。仅凭该结论,无法确定它定位的是哪一个特征值,也无法在特征值聚集时证明某个特征向量方向。
命题 5.4.5
(Rayleigh 商使残差最小)
对固定的单位向量 ,Rayleigh 商 使 在实数 中最小。
证明
(对位移配方)
将平方展开:。这是 的二次函数,首项系数为正,其导数 只在 处为零。
常见错误
(轻信随便算出来的残差)
在精确算术中,小残差给出数学证书。实际计算的残差本身也必须有足够的精度,才能支撑预期保证:若 与 几乎相等,它们在浮点运算中的差可能被舍入误差主导。
反例模式
位移不能凭空产生缺失的分量
令 、,并取 。反幂迭代始终留在第二坐标轴上。在精确算术中,它永远不会到达目标特征向量,因为初始对应系数为零。同样,位移恰好等于特征值时方程组奇异,不满足上述假设。实际计算的舍入误差可能引入缺失分量。两个不同特征值到位移等距也可能使迭代不收敛:取 、,当两个分量都非零时迭代会在两条直线之间交替。
带证书的例题
例题 5.4.6
(较差向量给出的宽松证书)
设 ,单位向量 。则 ,,所以 。区间为 ,其中含有特征值 ,但不含 。界 (4) 并不紧:。残差大时,得到的结论较弱,但仍然正确。
例题 5.4.7
(沿迭代过程的证书)
继续取 、 和 。在每个迭代向量处计算 和 :
| 0 | 2.5 | 1.5 |
| 1 | 1.01523 | 0.21320 |
| 2 | 1.000078 | 0.015306 |
当 时,区间 的两个端点恰好是两个特征值,所以 (4) 取等号。 时区间为 ,其中含有 ; 时 ,而证书半径为 。证书半径依次缩小约 倍和 倍;渐近地每一步的倍数为 。
例题 5.4.8
(两个特征值到位移等距)
对 、 和 ,逆矩阵的特征值为 和 。第一次求解得 ,于是 ,下一次求解得 。迭代向量在两条不同的直线之间交替,并不收敛;但取 时,每个残差证书 都等于 ,并正确地把一个特征值定位在 内。
练习与解答
快速检查
(对特征值 和位移 ,反幂迭代的比率 是多少?)
比较两个特征值到位移的距离。
解答 · 答案
。
快速检查
(为什么即使 张成的直线收敛,向量也可能交替改变符号?)
看 的符号。
解答 · 答案
当 时,占优的逆矩阵特征值 为负,因此 的系数每一步都会变号,而它张成的直线不变。
快速检查
(一个单位向量的 Rayleigh 商为 、残差范数为 。由 (4) 可得到什么保证?)
取 、。
解答 · 答案
至少有一个特征值位于 ;仅凭该证书不能确定它是哪一个。
快速检查
(如果最接近位移的特征值重数为二,为什么上面收敛到指定单个特征向量的证明不适用?)
哪一个假设不成立?
解答 · 答案
严格不等式 (1) 不成立,占优逆特征空间为二维。若初始向量在该空间上的投影非零,迭代直线收敛到该投影张成的直线;否则在精确算术中永远不会到达该空间。