線性代數 Cheat Sheet 5-8：特徵值的迭代估計
Contents
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\}$ 趨向於對應的特徵向量。