为什么近似特征向量有用
特征向量指出线性变换保持的方向,相应特征值给出沿该方向的缩放。对大型矩阵而言,为了求一个特征对而构造特征多项式并求其所有根,可能计算昂贵且在数值上困难。幂迭代则反复应用矩阵,使主导特征值对应的分量相对于其他分量增长。这只有在初始向量含有该分量,且各特征值的模具有严格间隔时才按下述方式奏效。
我们先使用实向量和 Euclidean 范数。复特征值及非对称矩阵需要额外注意:特征值的模不同于它们的代数大小,非对称矩阵的特征向量也不必正交。除明确讨论舍入外,下文迭代结论均指精确算术。
归一化幂迭代
定义 5.2.1
(归一化幂迭代)
设 ,起点 。每当 时,计算
第一步后每个迭代向量的范数都是一。归一化限制向量的增长或下溢;在精确算术中它不改变方向。若某次乘积为零,上述更新无定义,实现时必须停止或选择其他起点。
定理 5.2.2
(主导特征值定理)
设 , 有实特征向量基 ,对应实特征值满足
写 ,并假设 。令 。则每一步都有定义,归一化迭代趋近 张成的直线。更精确地,对 ,
常数可依赖于 和 。若 ,符号交替:直线收敛,但带方向的向量一般不收敛。当模的比值接近一时收敛缓慢;初始主导分量的大小也会影响初期表现。
证明
(提出主导幂因子)
在特征向量基中展开:
括号中除 外的和,由三角不等式知其范数至多为 。其 系数始终为 ,所以 非零。将 归一化便得到迭代向量。括号中的表达式趋近非零向量 ,因此当 足够大时,其范数有远离零的下界。映射 在远离零的局部区域 Lipschitz,故归一化保留 误差。因子 给出所示符号。
证明透视
幂迭代证明中各假设在哪里起作用
因子 被提出,所以一切都由括号中的向量读出,该向量收敛到 。严格不等式 使每个比值 都以 的速度衰减。假设 用了两次:它使极限向量非零,因而归一化在其附近是光滑映射;它也使每一步都有 。实特征向量基则使展开成为可能。若 、 且 ,同一论证表明迭代改为收敛到 的方向;若 ,比值不衰减,论证什么也得不到。
实特征向量基是充分条件,不是必要条件。缺陷矩阵及复主导特征值对需要另行分析;不能仅因为某个特征值在列表中写在第一位就应用此定理。若 ,所有非主导分量在取一次正整数次幂后便消失,结论立即成立。
例题 5.2.3
(对角矩阵上的幂迭代)
对 、,第 个归一化迭代为
方向以由 决定的速度趋近 。若改取 ,每次迭代都等于该向量:方法找到特征值 2,却永远不会发现 4。精确乘法的重复不会修复初始主导系数为零的问题。
Rayleigh 商与残差
定义 5.2.4
(Rayleigh 商)
对非零 ,其 Rayleigh 商为
若 是满足 的精确实特征向量,则商等于 。非零缩放(包括改变符号)不改变该商。因此即使归一化幂迭代的符号交替,它仍可用于估计特征值。
命题 5.2.5
(对称矩阵的 Rayleigh 商)
若 为实对称矩阵,选取特征值为 的标准正交特征向量基 。写 ,则
此商是加权平均,权重非负且和为一。这些界依赖于对称性和实特征值;任意实矩阵不一定满足。
定理 5.2.6
(对称矩阵的商收敛)
设 为实对称矩阵, 为标准正交特征向量基,,初始向量沿 的系数非零,并设 如主导特征值定理中所定义。则
证明
(在特征向量基中看商误差)
记 。商的误差为 。非主导系数相对于主导系数为 ,其平方给出上述速度。
这个更快的商误差估计源于正交性,不能对一般非对称矩阵直接假定。
例题 5.2.7
(向量误差与商误差)
对上述对角矩阵例子,
向量方向误差的尺度是 ,而商误差的尺度是 。这些速度描述精确算术中 增大时的行为;舍入和有限精度最终会限制改进。
由于 ,最初几个迭代向量给出:
| 第二坐标 | 商误差 | |
|---|---|---|
| 1 | 0.4472 | 0.4000 |
| 2 | 0.2425 | 0.1176 |
| 3 | 0.1240 | 0.0308 |
第二坐标每步大约减半,而商误差每步缩小的倍数接近四,与尺度 和 相符。
定理 5.2.8
(特征值残差证书)
给定候选值 和非零 ,定义特征对残差 。其与缩放无关的范数是 。对称矩阵 满足
证明
(在特征向量基中展开)
展开 。残差范数平方为 ,至少等于最小距离的平方乘以 。开方并除以 即得该界。
常见错误
(把小残差当作邻近特征向量)
残差小只能保证附近有某个特征值;但它本身不能指出是哪一个,也不能证明 接近指定的特征向量。后者需要分离的单特征值及进一步估计。
反例模式
残差很小却没有邻近特征值
非对称矩阵中,相同的特征值距离结论可能严重失效。取 、,其中 。两个特征值都是 1,但当 时,
而 到谱的距离始终为一。小残差仍有后向解释:扰动 的秩至多为一,满足 ,其范数为 。但这不必迫使未扰动的非正规矩阵具有邻近特征值。
失败情形与寻找其他特征值
主导特征值定理中模的严格间隔,不能减弱为 ,下面的例子说明了这一点。
反例模式
模相等时没有主导直线
对 、,迭代在 和 间交替。对应直线不趋于单一特征方向。两个特征值的模相同,缺少严格间隔条件。在实数运算中,一对复主导共轭特征值也可能产生旋转行为。
若要寻找选定实位移 附近的特征值,可以对 使用幂迭代,前提是 可逆。若 ,变换后的特征值为 ;若距离 唯一最近的实特征值是单重的,它便成为模唯一最大的变换后特征值。若 有实特征向量基且起始向量沿该方向的分量非零,前述定理说明变换算子的幂迭代在精确算术中趋近该特征方向。计算时每一步求解 ,而不是显式形成逆矩阵。位移接近特征值可以加快分离,但也使方程求解变得病态。若 本身是特征值,逆不存在,上述迭代无定义。
例题 5.2.9
(用反迭代求特征值 4)
设 ,。则 可逆,。逆矩阵的特征值 来自 ,是模唯一最大的一个,比率 。从 出发, 步后的方向与 成比例。 时它与 成比例,Rayleigh 商为 ; 时它与 成比例,商为 。方向趋近 ,商趋近 ,尽管 既不是 的最大特征值,也不是最小特征值:是位移选定了目标。若取 ,则 奇异,迭代便没有定义。
常见错误
(以相邻迭代向量接近作为停止准则)
停止时,缩放残差比单纯观察相邻归一化迭代向量是否接近更有信息量。小变化可能反映停滞或符号约定,而 与 代表相同特征方向。解释残差大小时,仍须考虑矩阵结构、尺度、精度及所需特征值间隔。
练习与解答
快速检查
(从 出发,对 做一步归一化幂迭代,并求结果的 Rayleigh 商。)
先把 归一化。
解答 · 答案
,所以 。其商为 。
快速检查
(对 、,带方向的迭代序列是否收敛?其特征方向和 Rayleigh 商如何变化?)
看 的符号。
解答 · 答案
主导特征值为 ,对应系数非零。迭代向量趋近符号交替的 ,所以带方向的序列不收敛;特征方向趋近 ,Rayleigh 商趋近 。
快速检查
(对 ,用位移 作反迭代。变换后哪个特征方向占主导?说明对初始向量的一个条件。)
算出 的特征值。
解答 · 答案
变换后的特征值为 。唯一最大模为 1,对应原特征值 4 和 。起始向量的第二坐标必须非零。
快速检查
(实对称矩阵的候选对 满足 和 。可对其谱得出什么结论?若没有更多信息,对指定特征向量不能得出什么结论?)
使用残差证书。
解答 · 答案
至少有一个特征值与 的距离不超过 。这本身不能确定是哪个特征值,也不能证明接近指定特征向量;需要间隔及适当的特征向量估计。