估計特徵值範圍的 Gershgorin 圓

本文的閱讀等級:中級

給定一 n 階方陣 A,例如,

A=\left[\!\!\begin{array}{rcc}    -4&0&1\\    -1&3&1\\    1&2&5    \end{array}\!\!\right]

如何估計 A 的特徵值於複數平面的座落位置?早於近代數值分析發展之前,白俄羅斯數學家葛西果靈 (S. A. Gershgorin) 在1931年就已提出一個簡單且有效的特徵值範圍估計方法,稱為 Gershgorin 圓。

 
A=[a_{ij}]n\times n 階矩陣,令 r_i 表示第 i 列所有非主對角元的絕對值之和,即

\displaystyle  r_i=\sum_{j=1,j\neq i}^n\vert a_{ij}\vert

在複數平面上,我們定義 Gershgorin 圓為

D_i=\left\{z\in\mathbb{C}\,\vert\,\vert z-a_{ii}\vert\le r_i\right\}

也就是說,a_{ii} 為圓心,r_i 為半徑。Gershgorin 圓估計定理宣稱:矩陣 A 的每一個特徵值都在一個或多個 Gershgorin 圓內,換句話說,特徵值必定座落於所有 Gershgorin 圓的聯集區域 D_1\cup\cdots\cup D_n。若 A 是對角矩陣,則圓半徑退化為 0,得知對角矩陣的主對角元等於特徵值。下面我們證明 Gershgorin 圓估計定理。令 \lambdaA 的一特徵值,\mathbf{x}=(x_1,\ldots,x_n) 為對應的特徵向量。假設座標 x_i 有最大絕對值,由於特徵向量不得為零向量,推知 \vert x_i\vert>0。特徵向量不受伸縮影響,故可令 x_i=1。考慮 A\mathbf{x}=\lambda\mathbf{x} 的第 i 個元,

\displaystyle\sum_{j=1}^na_{ij}x_j=\lambda x_i

x_i=1 代入上式,可得

\displaystyle\lambda-a_{ii}=\sum_{j=1,j\neq i}^na_{ij}x_j

等號兩邊取絕對值,因為對於任意 j,都有 \vert x_j\vert\le 1,推得以下結果:

\displaystyle\vert\lambda-a_{ii}\vert=\begin{vmatrix}    \sum_{j=1,j\neq i}^na_{ij}x_j    \end{vmatrix}\le\sum_{j=1,j\neq i}^n\vert a_{ij}\,\vert\,\vert x_j\vert\le\sum_{j=1,j\neq i}^n\vert a_{ij}\vert=r_i

這也就證明了 \lambda\in D_i,所有 Gershgorin 圓的聯集涵蓋 A 的全部特徵值。上例中,矩陣 A 的特徵值為 -4.1442.3905.754,而 Gershgorin 圓為(見下圖)

\begin{aligned}  D_1&=\{z\,\vert\,\vert z+4\vert\le 1\}\\    D_2&=\{z\,\vert\,\vert z-3\vert\le 2\}\\    D_3&=\{z\,\vert\,\vert z-5\vert\le 3\}\end{aligned}

Gershigorin 圓

 
下面介紹 Gershgorin 圓估計定理於判定特徵值的應用。若

\vert a_{ii}\vert>\sum_{j\neq i}\vert a_{ij}\vert,~~i=1,\ldots,n

我們稱 A 為 (嚴格) 對角佔優 (diagonally dominant) 矩陣 (見“特殊矩陣 (12):對角佔優矩陣”)。根據 Gershgorin 圓估計定理,對角佔優矩陣不可能有零特徵值,因此必為可逆矩陣。使用同樣方法可以證明下列性質:若 A 為一實對稱對角佔優矩陣且主對角元皆不為負數,則特徵值必大於或等於零,也就是說,A 是一半正定矩陣。若 A 為一對角佔優矩陣且主對角元皆為正數/負數,則特徵值的實部必為正數/負數。

 
讀者或許懷疑:如果以矩陣 A 的第 j 行所有非主對角元的絕對值之和當作圓半徑,上述關係依然成立嗎?是的,理由是 A 與其轉置 A^T 擁有相同的特徵值。令

\displaystyle  c_j=\sum_{i=1,i\neq j}^n\vert a_{ij}\vert

以行定義的 Gershgorin 圓為

D^{\prime}_j=\left\{z\in\mathbb{C}\,\vert\,\vert z-a_{jj}\vert\le c_j\right\}

同樣地,特徵值必定座落於所有 Gershgorin 圓的聯集區域 D^{\prime}_1\cup\cdots\cup D^{\prime}_n,如此一來,估計範圍可進一步縮小為 (\cup_{i=1,\ldots,n}D_i)\cap(\cup_{i=1,\ldots,n}D^{\prime}_i)。上例中,按各行計算的 Gershgorin 圓分別是

\begin{aligned}  D^{\prime}_1&=\{z\,\vert\,\vert z+4\vert\le 2\}\\    D^{\prime}_2&=\{z\,\vert\,\vert z-3\vert\le 2\}\\    D^{\prime}_3&=\{z\,\vert\,\vert z-5\vert\le 2\}\end{aligned}

下圖顯示由兩組 Gershgorin 圓交集產生的更精確特徵值估計區域。

兩組 Gershgorin 圓交集

 
Gershgorin 圓對特徵值的估計結果還可以進一步深化。如果 k 個圓聯集與其餘 n-k 個圓聯集並無交集,則前者包含 k 個特徵值而後者恰有 n-k 個特徵值。推論過程如下。抽取 A 的主對角元另設為 D=\mathrm{diag}(a_{11},\ldots,a_{nn}),考慮下列矩陣鏈

B(t)=(1-t)D+tA

我們採用連續論證法(continuity argument)。對於 0\le t\le 1,不難確認 B(t) 的主對角元恆等於 A 的主對角元,故兩矩陣有相同的圓心,但 B(t) 的圓半徑則為 A 圓半徑的 t 倍。以 D_i(t) 表示 B(t) 的 Gershgorin 圓:

D_i(t)=\left\{z\in\mathbb{C}\,\vert\,\vert z-a_{ii}\vert\le tr_i\right\}

在不失一般性的原則下,假設矩陣 A 的兩組圓聯集 \cup_{i=1,\ldots,k}D_i\cup_{i=k+1,\ldots,n}D_i 不相交。從 t=0t=1 的變化過程中,圓 D_i(t) 逐漸從點 a_{ii} 增大至 A 的 Gershgorin 圓 D_i=D_i(1),因此對於任意 t,區域 \cup_{i=1,\ldots,k}D_i(t)\cup_{i=k+1,\ldots,n}D_i(t) 也不相交。矩陣鏈 B(t) 的特徵值 \lambda_i(t)t 的連續函數,始點為 \lambda_i(0)=a_{ii},終點 \lambda_i(1)A 的特徵值。在整個連續改變過程中,特徵值軌跡 \lambda_i(t)i=1,\ldots,k,由 \cup_{i=1,\ldots,k}D_i(t) 所包覆,所以終點 \lambda_i(1)i=1,\ldots,k,必定屬於 A 的圓聯集 \cup_{i=1,\ldots,k}D_i。同樣道理,A 的其餘 n-k 個特徵值也屬於\cup_{i=k+1,\ldots,n}D_i

 
Gershgorin 圓給出的特徵值估計範圍可以提供特徵值估計值給一些特定算法 (如 Power 法),也可用來分析算法近似特徵值的準確度。許多特徵值算法對給定矩陣 A 執行一連串的相似變換 P^{-1}AP,目的在使變換後的矩陣更具有主對角形式。Gershgorin 圓提供了相似變換生成矩陣的主對角元與 A 的特徵值的誤差範圍。

相關閱讀:
廣告
本篇發表於 線性代數專欄, 數值線性代數 並標籤為 , , , 。將永久鏈結加入書籤。

發表迴響

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

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s