Wielandt 緊縮──保特徵值的矩陣降階法

本文的閱讀等級:中級

考慮下面的 4\times 4 階矩陣的特徵值計算問題:

\displaystyle  A=\begin{bmatrix}  1&0&2&1\\  1&1&1&1\\  3&0&0&1\\  0&1&1&2  \end{bmatrix}

觀察發現 A 的每一列總和都是 4,表明 A 有特徵值 4,對應的特徵向量為 (1,1,1,1)^T (見“實對稱矩陣特徵值和特徵向量的探索解法”)。在一般情況下,如果已知 n\times n 階矩陣 A 的一個特徵值 \lambda 和對應的特徵向量 \mathbf{x},這項訊息如何幫助我們求得 A 的其餘特徵值和特徵向量?本文介紹一個保特徵值的矩陣降階法,稱為 Wielandt 緊縮 (deflation),因德國數學家維蘭特 (Helmut Wielandt) 得名。Wielandt 緊縮法利用特徵值 \lambda 和對應的特徵向量 \mathbf{x}A 降為一個 (n-1)\times(n-1) 階矩陣 \tilde{A},其中 \tilde{A}(n-1) 個特徵值等於 A 的其餘 (n-1) 個特徵值 (排除 \lambda)。

 
假設 n\times n 階矩陣 A=[a_{ij}] 有特徵值 \lambda,對應特徵向量 \mathbf{x},即 A\mathbf{x}=\lambda\mathbf{x}。令

\displaystyle  B=A-\lambda\mathbf{x}\mathbf{z}^T

其中 \mathbf{x}\mathbf{z}^T 是一 n\times n 階矩陣且 \hbox{rank}(\mathbf{x}\mathbf{z}^T)=1。上式右乘 \mathbf{x}

\displaystyle  B\mathbf{x}=A\mathbf{x}-\lambda\mathbf{x}\mathbf{z}^T\mathbf{x}=\lambda\mathbf{x}-\lambda\mathbf{x}(\mathbf{z}^T\mathbf{x})=\lambda\mathbf{x}(1-\mathbf{z}^T\mathbf{x})

其中 \mathbf{z}^T\mathbf{x} 是一純量。若 \mathbf{z}^T\mathbf{x}=1,則 B\mathbf{x}=\mathbf{0},可知 B 有特徵值 0,對應特徵向量 \mathbf{x}。以下限定 \mathbf{z}^T\mathbf{x}=1,我們宣稱 B=A-\lambda\mathbf{x}\mathbf{z}^T 排除 0 後的其餘 (n-1) 個特徵值和 A 排除 \lambda 後的其餘 (n-1) 個特徵值完全相同。若 A\mathbf{y}=\mu\mathbf{y}\mu\neq 0\mathbf{x}\mathbf{y} 是線性獨立集,下面證明存在 \mathbf{v}=c\mathbf{x}+d\mathbf{y} 使得 B\mathbf{v}=\mu\mathbf{v}。將 \mathbf{v} 的線性組合式代入前一式,等號左邊為

\displaystyle \begin{aligned}  B\mathbf{v}&=B(c\mathbf{x}+d\mathbf{y})=dB\mathbf{y}\\  &=d(A-\lambda\mathbf{x}\mathbf{z}^T)\mathbf{y}\\  &=dA\mathbf{y}-d\lambda\mathbf{x}\mathbf{z}^T\mathbf{y}\\  &=d\mu\mathbf{y}-d\lambda(\mathbf{z}^T\mathbf{y})\mathbf{x},  \end{aligned}

等號右邊是 \mu\mathbf{v}=c\mu\mathbf{x}+d\mu\mathbf{y}。比較等號兩邊 \mathbf{x} 的係數,可得 c\mu=-d\lambda(\mathbf{z}^T\mathbf{y})。設 d=\mu,則得 c=-\lambda(\mathbf{z}^T\mathbf{y}),也就有

\displaystyle  \mathbf{v}=-\lambda(\mathbf{z}^T\mathbf{y})\mathbf{x}+\mu\mathbf{y}

因為 \mathbf{x}\mathbf{y} 是線性獨立集且 \mu\neq 0,確認 \mathbf{v}\neq\mathbf{0},故 \mathbf{v} 是對應 B 的特徵值 \mu 的特徵向量。
更進一步,我們希望選擇 \mathbf{z} 使得 B 有一零列 (row)。假設 B 的第 r 列為零列,即 \mathbf{e}_r^TB=\mathbf{0}^T,其中 \mathbf{e}_r 表示單位向量,第 r 元為 1,其餘元為 0。所以,

\displaystyle\begin{aligned}  \mathbf{0}^T&=\mathbf{e}_r^TB=\mathbf{e}_r^T(A-\lambda\mathbf{x}\mathbf{z}^T)\\  &=\mathbf{e}_r^TA-\lambda\mathbf{e}_r^T\mathbf{x}\mathbf{z}^T=\mathbf{e}_r^TA-\lambda x_r\mathbf{z}^T,\end{aligned}

其中 x_r 是特徵向量 \mathbf{x} 的第 r 元。因為 \mathbf{x}\neq\mathbf{0},必定存在一 x_r\neq 0。若 \lambda\neq 0,由上式推知

\displaystyle  \mathbf{z}^T=\frac{1}{\lambda x_r}\mathbf{e}_r^TA=\frac{1}{\lambda x_r}\begin{bmatrix}  a_{r1}&a_{r2}&\cdots&a_{rn}\end{bmatrix}

計算驗證

\displaystyle  \mathbf{z}^T\mathbf{x}=\frac{1}{\lambda x_r}\mathbf{e}_r^TA\mathbf{x}=\frac{1}{\lambda x_r}\lambda\mathbf{e}_r^T \mathbf{x}=1

 
以上例說明計算過程。已知 A 有特徵值 \lambda=4,特徵向量 \mathbf{x}=(1,1,1,1)^T。選擇 r=1,可得

\displaystyle  \mathbf{z}^T=\frac{1}{4\cdot 1}\begin{bmatrix}  1&0&2&1  \end{bmatrix}=\frac{1}{4}\begin{bmatrix}  1&0&2&1  \end{bmatrix}

接著消滅 B 的第 1 列,如下:

\displaystyle  B=\begin{bmatrix}  1&0&2&1\\  1&1&1&1\\  3&0&0&1\\  0&1&1&2  \end{bmatrix}-4\frac{1}{4}\begin{bmatrix}  1\\  1\\  1\\  1  \end{bmatrix}\begin{bmatrix}  1&0&2&1  \end{bmatrix}=\left[\!\!\begin{array}{rccrc}  0&\vline&0&0&0\\ \hline  0&\vline&1&-1&0\\  2&\vline&0&-2&0\\  -1&\vline&1&-1&1  \end{array}\!\!\right]

\displaystyle  \tilde{A}=\left[\!\!\begin{array}{crc}  1&-1&0\\  0&-2&0\\  1&-1&1  \end{array}\!\!\right]

因為 B=\begin{bmatrix}  0&0\\  \ast&\tilde{A}  \end{bmatrix} 是一分塊下三角矩陣,其特徵值即為主對角分塊 0\tilde{A} 的特徵值聯集,故證明 Wielandt 緊縮所產生的低階矩陣 \tilde{A} 具有特徵值不變性。如果選擇 r=2,則得

\displaystyle  B'=\begin{bmatrix}  1&0&2&1\\  1&1&1&1\\  3&0&0&1\\  0&1&1&2  \end{bmatrix}-4\frac{1}{4}\begin{bmatrix}  1\\  1\\  1\\  1  \end{bmatrix}\begin{bmatrix}  1&1&1&1  \end{bmatrix}=\left[\!\!\begin{array}{rrrc}  0&-1&1&0\\  0&0&0&0\\  2&-1&-1&0\\  -1&0&0&1  \end{array}\!\!\right]

使用排列矩陣置換列行指標 12。設

\displaystyle  P=\begin{bmatrix}  0&1&0&0\\  1&0&0&0\\  0&0&1&0\\  0&0&0&1  \end{bmatrix}

即有

\displaystyle  B''=P^{-1}B'P=P^TB'P=\left[\!\!\begin{array}{rrrc}  0&0&0&0\\  -1&0&1&0\\  -1&2&-1&0\\  0&-1&0&1  \end{array}\!\!\right]

因為 B'' 相似於 B',可知 B''B' 擁有相同的特徵值,故 B'' 的右下 3\times 3 階分塊 \displaystyle  \tilde{A}'=\left[\!\!\begin{array}{rrc}  0&1&0\\  2&-1&0\\  -1&0&1  \end{array}\!\!\right] 即為所求的低階矩陣,也就是刪除 B' 的第 2 列與第 2 行後所得的子陣。請讀者自行驗證 \tilde{A}\tilde{A}' 有相同的特徵值。

 
最後我們討論 Wielandt 緊縮在實際應用時可能發生的一些情況。第一,先前的推倒過程假設 A 有非零特徵值,以及線性獨立的特徵向量。因為這個緣故,除了實對稱可逆矩陣 (實對稱矩陣有單範正交 (orthonormal) 的特徵向量),Wielandt 緊縮不適用於一般任意矩陣。第二,Wielandt 緊縮僅有保特徵值的矩陣降階功能,故必須搭配其他的特徵值數值計算方法使用,譬如,Power 移動迭代法 (見“Power 迭代法”)。此外,矩陣的降階過程很容易引進捨入誤差,這意味 Wielandt 緊縮產生的低階矩陣只能提供近似的特徵值。

This entry was posted in 線性代數專欄, 數值線性代數 and tagged , , , . Bookmark the permalink.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s