線性代數/主題：冪法

在實際應用中，計算特徵值和特徵向量是一個難題。對於應用中經常遇到的大型矩陣，找到並求解其特徵多項式速度太慢，難度太大。因此，人們會採用其他間接的方法，這些方法不涉及特徵多項式。這裡我們將看到一種適用於“稀疏”大型矩陣（大多數條目為零）的方法。

假設 $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.