线性代数/主题：幂法

在实际应用中，计算特征值和特征向量是一个难题。对于应用中经常遇到的大型矩阵，找到并求解其特征多项式速度太慢，难度太大。因此，人们会采用其他间接的方法，这些方法不涉及特征多项式。这里我们将看到一种适用于“稀疏”大型矩阵（大多数条目为零）的方法。

假设 $n\!\times \!n$ 矩阵 $T$ 有 $n$ 个不同的特征值 $\lambda _{1}$, $\lambda _{2}$, ..., $\lambda _{n}$。 那么 $\mathbb {R} ^{n}$ 有一个基，它是由相关的特征向量 $\langle {\vec {\zeta }}_{1},\dots ,{\vec {\zeta }}_{n}\rangle$ 组成。 对于任何 ${\vec {v}}\in \mathbb {R} ^{n}$，其中 ${\vec {v}}=c_{1}{\vec {\zeta }}_{1}+\dots +c_{n}{\vec {\zeta }}_{n}$，对 ${\vec {v}}$ 迭代 $T$ 会得到以下结果。

${\begin{array}{rl}T{\vec {v}}&=c_{1}\lambda _{1}{\vec {\zeta }}_{1}+c_{2}\lambda _{2}{\vec {\zeta }}_{2}+\dots +c_{n}\lambda _{n}{\vec {\zeta }}_{n}\\T^{2}{\vec {v}}&=c_{1}\lambda _{1}^{2}{\vec {\zeta }}_{1}+c_{2}\lambda _{2}^{2}{\vec {\zeta }}_{2}+\dots +c_{n}\lambda _{n}^{2}{\vec {\zeta }}_{n}\\T^{3}{\vec {v}}&=c_{1}\lambda _{1}^{3}{\vec {\zeta }}_{1}+c_{2}\lambda _{2}^{3}{\vec {\zeta }}_{2}+\dots +c_{n}\lambda _{n}^{3}{\vec {\zeta }}_{n}\\&\vdots \\T^{k}{\vec {v}}&=c_{1}\lambda _{1}^{k}{\vec {\zeta }}_{1}+c_{2}\lambda _{2}^{k}{\vec {\zeta }}_{2}+\dots +c_{n}\lambda _{n}^{k}{\vec {\zeta }}_{n}\end{array}}$

如果其中一个特征值，例如 $\lambda _{1}$，其绝对值大于其他所有特征值，那么它的项将支配上述表达式。换句话说，用 $\lambda _{1}^{k}$ 除以该表达式，得到：

${\frac {T^{k}{\vec {v}}}{\lambda _{1}^{k}}}=c_{1}{\vec {\zeta }}_{1}+c_{2}{\frac {\lambda _{2}^{k}}{\lambda _{1}^{k}}}{\vec {\zeta }}_{2}+\dots +c_{n}{\frac {\lambda _{n}^{k}}{\lambda _{1}^{k}}}{\vec {\zeta }}_{n}$

并且，因为 $\lambda _{1}$ 被假定为具有最大的绝对值，随着 $k$ 变大，这些分数趋于零。因此，整个表达式趋于 $c_{1}{\vec {\zeta }}_{1}$.

也就是说（只要$c_{1}$ 不为零），随着$k$ 的增加，向量$T^{k}{\vec {v}}$ 将趋向于与主特征值相关的特征向量的方向，因此，长度之比$|\,T^{k}{\vec {v}}\,|/|\,T^{k-1}{\vec {v}}\,|$ 将趋向于该主特征值。

例如，（针对此的示例计算机代码位于练习之后），由于矩阵

$T={\begin{pmatrix}3&0\\8&-1\end{pmatrix}}$

是三角形的，它的特征值就是对角线上的元素，$3$ 和$-1$。随意取${\vec {v}}$ 的分量为$1$ 和$1$ 给出

${\begin{array}{c|ccccc}{\vec {v}}&T{\vec {v}}&T^{2}{\vec {v}}&\cdots &T^{9}{\vec {v}}&T^{10}{\vec {v}}\\\hline {\begin{pmatrix}1\\1\end{pmatrix}}&{\begin{pmatrix}3\\7\end{pmatrix}}&{\begin{pmatrix}9\\17\end{pmatrix}}&\cdots &{\begin{pmatrix}19\,683\\39\,367\end{pmatrix}}&{\begin{pmatrix}59\,049\\118\,097\end{pmatrix}}\end{array}}$

最后一个长度之比是$2.999\,9$。

有两个实现问题需要解决。第一个问题是，我们不会去寻找 $T$ 的幂并将它们应用于 ${\vec {v}}$，我们会计算 ${\vec {v}}_{1}$ 作为 $T{\vec {v}}$，然后计算 ${\vec {v}}_{2}$ 作为 $T{\vec {v}}_{1}$，等等（即我们永远不会分别计算 $T^{2}$，$T^{3}$，等等）。即使 $T$ 很大，只要它是稀疏的，这些矩阵向量乘积就可以很快完成。第二个问题是，为了避免生成超出计算机能力范围的过大数字，我们可以在每一步对 ${\vec {v}}_{i}$ 进行归一化。例如，我们可以将每个 ${\vec {v}}_{i}$ 除以它的长度（其他可能性是除以它最大的分量，或简单地除以它的第一个分量）。因此，我们通过生成以下内容来实现此方法。

${\begin{array}{rl}{\vec {w}}_{0}&={\vec {v}}_{0}/|{\vec {v}}_{0}|\\{\vec {v}}_{1}&=T{\vec {w}}_{0}\\{\vec {w}}_{1}&={\vec {v}}_{1}/|{\vec {v}}_{1}|\\{\vec {v}}_{2}&=T{\vec {w}}_{2}\\&\vdots \\{\vec {w}}_{k-1}&={\vec {v}}_{k-1}/|{\vec {v}}_{k-1}|\\{\vec {v}}_{k}&=T{\vec {w}}_{k}\end{array}}$

直到我们满意为止。 然后向量 ${\vec {v}}_{k}$ 是特征向量的近似值，并且占主导地位的特征值的近似值是比率 $|{\vec {v}}_{k}|/|{\vec {w}}_{k-1}|=|{\vec {v}}_{k}|$.

我们“满意”的一种方法是迭代，直到我们的特征值近似值稳定下来。 例如，我们可以决定，不是在某个固定次数的步骤之后停止迭代过程，而是当 $|{\vec {v}}_{k}|$ 与 $|{\vec {v}}_{k-1}|$ 之差小于百分之一，或者当它们在第二位有效数字上达成一致时。

收敛速度由 $|\lambda _{2}/\lambda _{1}|$ 的幂趋于零的速度决定，其中 $\lambda _{2}$ 是第二大范数的特征值。 如果该比率远小于一，则收敛速度很快，但是如果它仅略小于一，则收敛速度可能非常慢。 因此，幂次法不是最常用的求特征值的方法（尽管它是最简单的方法，这就是为什么它作为在不求解特征多项式的情况下计算特征值的可能性说明）。 相反，存在各种方法，通常通过首先用与它相似的另一个矩阵替换给定的矩阵 $T$，因此具有相同的特征值，但采用某种简化形式，例如三对角线形式：唯一的非零项位于对角线上，或者在其上方或下方。 然后可以使用特殊技术来查找特征值。 一旦知道特征值，就可以轻松计算 $T$ 的特征向量。 这些其他方法超出了我们的范围。 一个很好的参考是（Goult 等人 1975）。

练习

问题 1

使用十次迭代估计这些矩阵的最大特征值，从分量为 $1$ 和 $2$ 的向量开始。将答案与通过求解特征方程获得的答案进行比较。

1. ${\begin{pmatrix}1&5\\0&4\end{pmatrix}}$
2. ${\begin{pmatrix}3&2\\-1&0\end{pmatrix}}$

问题 2

通过迭代直到 $|{\vec {v}}_{k}|-|{\vec {v}}_{k-1}|$ 的绝对值小于 $0.01$ 来重新执行先前的练习。在每一步中，通过将每个向量除以其长度来进行归一化。需要多少次迭代？答案有显著差异吗？

问题 3

使用十次迭代估计这些矩阵的最大特征值，从分量为 $1$，$2$ 和 $3$ 的向量开始。将答案与通过求解特征方程获得的答案进行比较。

1. ${\begin{pmatrix}4&0&1\\-2&1&0\\-2&0&1\end{pmatrix}}$
2. ${\begin{pmatrix}-1&2&2\\2&2&2\\-3&-6&-6\end{pmatrix}}$

问题 4

通过迭代直到 $|{\vec {v}}_{k}|-|{\vec {v}}_{k-1}|$ 的绝对值小于 $0.01$ 来重新执行先前的练习。在每一步中，通过将每个向量除以其长度来进行归一化。需要多少次迭代？答案有显著差异吗？

问题 5

如果 $c_{1}=0$ 会发生什么？也就是说，如果初始向量在相关特征向量的方向上没有任何分量，会发生什么？

问题 6

如何采用幂法来找到最小特征值？

解决方案

这是用于执行上述计算的计算机代数系统 Octave 的代码。（它经过轻微编辑以删除空行等。）

计算机代码

>T=[3, 0;
8, -1]
T=
3 0
8 -1
>v0=[1; 2]
v0=
1
1
>v1=T*v0
v1=
3
7
>v2=T*v1
v2=
9
17
>T9=T**9
T9=
19683 0
39368 -1
>T10=T**10
T10=
59049 0
118096 1
>v9=T9*v0
v9=
19683
39367
>v10=T10*v0
v10=
59049
118096
>norm(v10)/norm(v9)
ans=2.9999

备注：我们在这里忽略 Octave 的功能；有一些内置函数可以自动应用非常复杂的方法来找到特征值和特征向量。相反，我们只是将系统用作计算器。

参考资料

• Goult, R.J.; Hoskins, R.F.; Milner, J.A.; Pratt, M.J. (1975), Computational Methods in Linear Algebra, Wiley.