为什么用迭代求特征值
特征值问题 一般不能通过有限次有理运算解出,所以计算必须是迭代的。对大型矩阵,通常不需要全部特征对,只需要最大的一个,或最接近某目标的一个。幂法与逆迭代只用矩阵与向量乘积或线性求解就能做到。它们是最简单的特征值算法,也是更复杂算法的基础。本单元用到消元法与迭代求解各单元中的线性方程组求解与分解概念;浮点运算的误差分析只在此提及,并不展开。
定义与假设
设 为实 矩阵。全篇假设 可对角化且特征值均为实数 ,特征向量 构成一组基。
定义 17.1.1
(严格占优特征值)
若对所有 有 ,称 为严格占优。此时其余特征值排成 ,而比值 满足 。
把初始向量写成 。系数 衡量初始向量含有多少所求的特征向量;以下定理假设 。
定义 17.1.2
(幂法与瑞利商)
幂法产生 ,即 。非零向量 的瑞利商(Rayleigh quotient)为 ;当 对称时它最为有用。
定义 17.1.3
(位移为 的逆迭代)
设实数 不是 的特征值。位移为 的逆迭代是对 施行幂法:解 ,再归一化 。
矩阵 只分解一次,此后每步只需两次三角求解。
收敛定理
定理 17.1.4
(幂法的收敛)
设 严格占优,,且 。则
因此 ,其中 。于是 以几何速率 趋近 所张的直线(若 , 的正负号交替)。
证明
(在特征基中展开初始向量)
展开 并用 ,得 。除以 得恒等式;再用三角不等式及 得不等式。把趋近 的向量归一化,所得单位向量趋近 ;当 时,因子 造成正负号交替。
定理 17.1.5
(对称情形下的瑞利商)
在幂法收敛定理的假设下,再设 对称,并取 为标准正交基。则对幂法的迭代,
故特征值估计以速率 收敛,是向量收敛速度的两倍。
证明
(瑞利商的标准正交展开)
瑞利商不受缩放影响,所以 ,其中 ,。由标准正交性,,,故
利用 、分母 ,以及 。
证明透视
误差为何变成平方
对称性只用了一次:它允许取标准正交特征基,使 与 都只是平方 之和,没有交叉项 。减去 后,分子中 的项消失,只剩下各个小系数的平方。每一项除以 后都带有 , 正由此而来。占优性经由 进入,而 使分母不为零。对非对称矩阵,交叉项以一阶大小保留下来,速率退回 ;下文常见错误一节会检验一个具体矩阵。
定理 17.1.6
(逆迭代的收敛)
设 不是特征值,且对所有 有 ,并设 。则迭代以几何速率 趋近 所张的直线。
证明
(逆迭代就是对逆矩阵施行幂法)
,故 。 的特征值为 ,模最大者对应下标 ,由假设它严格占优。对 应用幂法收敛定理,比值为 。
选取更接近 的 可使速率更快,而每步成本不变。此时 接近奇异,但实际上并不损害所算得解的方向,因为大的误差恰好落在 自身的方向上。
例题
例题 17.1.7
(幂法与瑞利商)
设 ,特征值为 (向量 )与 (向量 ),。此处 。未归一化的迭代为 ,即 。瑞利商为
| 0 | |||
| 1 | |||
| 2 | |||
| 3 |
例如 时 ,,。相继误差之比 、、 趋近 ,与瑞利商定理的预测一致。
例题 17.1.8
(带位移的逆迭代)
对同一个 取 ,最接近 。此时 ,行列式为 ,速率为 。从 出发,解一次得(差一个比例),再解一次得 。在特征基下,,且 ;对 有 ,,,与预测相符。瑞利商为 ,,趋近特征值 ;这是不带位移的幂法找不到的。
例题 17.1.9
(负的占优特征值)
设 、,故 ,。于是 ;归一化后的 在 为偶数时趋近 ,在 为奇数时趋近 。序列 没有极限,但它趋近的直线正是特征值 的特征向量所在直线,与幂法收敛定理所说一致。瑞利商则确实收敛:
时误差为 及 ,比值接近 。对称情形的误差界 给出 及 ,确实大于实际误差。
常见错误与细微之处
常见错误
(以为必定有占优特征值)
若 (例如 ),就没有占优特征值,迭代未必趋近任何直线。位移 把所有特征值移动同一数量,或可恢复占优性。
常见错误
(忽略初始向量的分量)
若 ,在精确运算下迭代收敛到另一个特征向量;浮点舍入误差通常会重新引入 的分量,但很慢,所以 极小的初始向量并不好。
常见错误
(期望向量本身收敛)
向量只在比例和正负号之内收敛,负占优特征值的例子正说明这一点;应用瑞利商或分量之比来估计 。
幂法每步是一次矩阵向量乘积;逆迭代每步是用已存分解作一次求解,绝不显式求逆。不可对角化或含复特征值的情形需要另行分析,上述定理并不涵盖。瑞利商定理中的对称假设也不是可有可无的。
反例模式
加倍的速率需要对称性
断言:幂迭代的瑞利商总以速率 收敛。取非对称矩阵 ,特征值为 (向量 )与 (向量 ),故 ;再取 。则 ,其中 ,且 。因此
()时误差为 ;()时为 。比值约为 ,接近 而非 ;事实上误差的大小约为 。修正后的陈述正是定理本身:对称 的速率为 ,一般可对角化的 的瑞利商只承袭向量的速率 。
习题
快速检查
(对 (特征值 与 )及 ,计算 的 ,并用特征向量写出 的公式。)
先求特征值 与 的特征向量,再用它们展开 。
解答 · 答案
,,。特征向量为: 对应 , 对应 ,且 。因此 。 时:,,与直接计算一致。第一分量之比 正趋近 。
快速检查
(证明 、 时幂法不收敛,并提出一个可补救的位移。)
先计算前几个迭代向量及 的特征值。
解答 · 答案
特征值为 ,模相等,没有占优特征值。迭代为 ,来回交替而不收敛。矩阵 的特征值为 与 ,对它用幂法有严格占优的特征值 (特征向量 ,比值 ),再减去 便得 的特征值。
快速检查
(某幂迭代的误差按 下降。要把误差缩小到 倍,需要多少次迭代才有保证?)
两边取对数。
解答 · 答案
需要 ,即 。故需 次迭代。
快速检查
(对 及位移 ,给出逆迭代的收敛速率,并从 作两次求解。)
最接近 的特征值是 ,另一个是 。
解答 · 答案
速率为 。 的行列式为 ,逆矩阵为 。第一次求解:。第二次求解:。分量之比由 变为 ,趋近特征值 的特征向量 的比值 。