线性代数 Cheat Sheet 5-8：特征值的迭代估计

Author: nex3z 2018-12-08

1. 幂算法

　　幂算法适用于 $n \times n$ 矩阵 $A$ 由严格占优特征值（亦称主特征值）$\lambda_1$ 的情况。$\lambda_1$ 为主特征值的意思是 $\lambda_1$ 的绝对值比其他特征值的绝对值都大。此时，幂算法产生一个近似 $\lambda_1$ 的数列和一个近似对应主特征向量的向量序列。

　　为简单起见，假设 $A$ 可对角化，特征向量 $\boldsymbol v_1, \cdots, \boldsymbol v_n$ 是 $\mathbb{R}^n$ 的基，并且 $\boldsymbol v_1, \cdots, \boldsymbol v_n$ 已经过排列，使对应的特征值 $\lambda_1, \cdots, \lambda_n$ 的绝对值递减，$\lambda_1$ 是主特征值，即有

$$\begin{equation} |\lambda_1| > |\lambda_2| \geq |\lambda_3| \geq \cdots \geq |\lambda_n| \tag{1} \end{equation}$$

假设 $\boldsymbol x \in \mathbb{R}^n$，$\boldsymbol x = c_1 \boldsymbol v_1 + \cdots + c_n \boldsymbol v_n$，那么

$$\begin{equation} A^k \boldsymbol x = c_1 (\lambda_1)^k \boldsymbol v_1 + c_2 (\lambda_2)^k \boldsymbol v_2 + \cdots + c_n (\lambda_n)^k \boldsymbol v_n \; (k = 1,2,\cdots) \end{equation}$$

假设 $c_1 \neq 0$，等式除以 $(\lambda_1)^k$，

$$\begin{equation} \frac{1}{(\lambda_1)^k}A^k \boldsymbol x = c_1 \boldsymbol v_1 + c_2 (\frac{\lambda_2}{\lambda_1})^k \boldsymbol v_2 + \cdots + c_n (\frac{\lambda_n}{\lambda_1})^k \boldsymbol v_n \; (k = 1,2,\cdots) \end{equation}$$

由 $(1)$，所有分数 $\frac{\lambda_2}{\lambda_1}, \cdots, \frac{\lambda_n}{\lambda_1}$ 的值都小于 $1$，因此，它们的幂趋于零，故

$$\begin{equation} 当 k \rightarrow \infty 时，\frac{1}{(\lambda_1)^k}A^k \boldsymbol x \rightarrow c_1 \boldsymbol v_1 \end{equation}$$

因此对足够大的 $k$，$A^k \boldsymbol x$ 的数量倍的方向几乎与特征向量 $c_1 \boldsymbol v_1$ 的方向相同。由于正的数量倍不会改变向量的方向，因此若给定 $c_1 \neq 0$，则 $A^k \boldsymbol x$ 的方向几乎与 $\boldsymbol v_1$ 或 $-\boldsymbol v_1$ 一致。

　　估计严格占优特征值的幂算法
1. 选择一个最大分量为 $1$ 的初始向量 $\boldsymbol x_0$。
2. 对 $k = 0,1,\cdots,$
　　a. 计算 $A \boldsymbol x_k$。
　　b. 设 $\mu_k$ 是 $A \boldsymbol x$ 中绝对值最大的一个分量。
　　c. 计算 $\boldsymbol x_{k+1} = (1 / \mu_k) A \boldsymbol x_k$。
3. 几乎对所有选择的 $\boldsymbol x_0$，序列 $\{\mu_k\}$ 近似于主特征值，而序列 $\{\boldsymbol x_k\}$ 近似于对应的特征向量。

2. 逆幂法

　　在知道特征值 $\lambda$ 的一个较好的初始估值 $\alpha$ 后，逆幂法可用来对任一特征值作近似估值。此时，令 $B = (A – \alpha I)^{-1}$，并对 $B$ 应用幂算法，可以证明，若 $\lambda_1, \cdots, \lambda_n$ 是 $A$ 的特征值，则 $B$ 的特征值是

$$\begin{equation} \frac{1}{\lambda_1 – \alpha}, \frac{1}{\lambda_2 – \alpha}, \cdots, \frac{1}{\lambda_n – \alpha} \end{equation}$$

而且 $A$ 的对应于 $\lambda_1, \cdots, \lambda_n$ 的特征向量是 $B$ 的对应于上面这些特征值的特征向量。

　　估计 $A$ 的特征值 $\lambda$ 的逆幂法
1. 选择一个非常接近 $\lambda$ 的初始估值 $\alpha$。
2. 选择一个最大分量为 $1$ 的初始向量 $\boldsymbol x_0$。
3. 对 $k = 0, 1, \cdots,$
　　a. 从 $(A – \alpha I)\boldsymbol y_k = \boldsymbol x_k$ 中解出 $\boldsymbol y_k$。（实际上是计算 $\boldsymbol y_k = (A – \alpha I)^{-1} \boldsymbol x_k$，即 $\boldsymbol y = B \boldsymbol x_k$）
　　b. 设 $\mu_k$ 是 $\boldsymbol y_k$ 中绝对值最大的分量。
　　c. 计算 $v_k = \alpha + (1 / \mu_k)$。（由 $\mu_k = 1 / {v_k – \alpha}$，得 $v_k = \alpha + (1 / \mu_k)$）
　　d. 计算 $\boldsymbol x_{k+1} = (1 / \mu_k)\boldsymbol y_k$。（$\boldsymbol x_{k+1}$ 中的最大分量为 $1$）
4. 几乎对所有选择的 $\boldsymbol x_0$，序列 $v_k$ 趋向于 $A$ 的特征值 $\lambda$，而序列 $\{\boldsymbol x_k\}$ 趋向于对应的特征向量。