廣義收斂矩陣

本文的閱讀等級:高級

A 為一 n\times n 階矩陣,\lambda 為其特徵值。若譜半徑 \rho(A)<1,即所有特徵值都滿足 \vert\lambda\vert<1,可以證明 \lim_{k\to\infty}A^k=0,我們稱 A 為收斂矩陣 (見“譜半徑與矩陣範數”)。考慮一般廣義收斂矩陣 A 使得 \lim_{k\to\infty}A^k 存在,但不必是零矩陣。運用 Jordan 形式分析可以推導出廣義收斂矩陣的存在條件及其收斂形式。設 A 的 Jordan 形式為 J=M^{-1}AM,就有

A^k=(MJM^{-1})^k=MJ^kM^{-1}

Jordan 矩陣 J 為基本 Jordan 分塊 J_{\ast}(\lambda) 的直和,故冪矩陣 J^kJ^k_{\ast}(\lambda) 的直和 (見“Jordan 形式大解讀(上)”)。對於每一基本 Jordan 分塊 J_{\ast}(\lambda),若 \lim_{k\to\infty}J^k_{\ast}(\lambda) 全都存在,則 \lim_{k\to\infty}J^k 存在,即知 \lim_{k\to\infty}A^k 存在。既然 \lim_{k\to\infty}A^k 的存在條件等同於 \lim_{k\to\infty}J^k_{\ast}(\lambda) 的存在條件,下面我們將焦點轉移至基本 Jordan 分塊的冪矩陣。

 
考慮 m\times m 階基本 Jordan 分塊

\begin{aligned}  J_{\ast}(\lambda)&=\begin{bmatrix}  \lambda&1&~&~\\    ~&\ddots&\ddots&~\\    ~&~&\ddots&1\\    ~&~&~&\lambda    \end{bmatrix}=\begin{bmatrix}    \lambda&~&~&~\\    ~&\ddots&~&~\\    ~&~&\ddots&~\\    ~&~&~&\lambda    \end{bmatrix}+\begin{bmatrix}    0&1&~&~\\    ~&\ddots&\ddots&~\\    ~&~&\ddots&1\\    ~&~&~&0    \end{bmatrix}\\  &=\lambda I+J_{\ast}(0),\end{aligned}

利用二項式定理,可得 (詳細過程見“收斂矩陣”)

\displaystyle  J^k_{\ast}(\lambda)=\sum_{j=0}^{m-1}\binom{k}{j}\lambda^{k-j}J^j_{\ast}(0)=\begin{bmatrix}  \lambda^k&\binom{k}{1}\lambda^{k-1}&\binom{k}{2}\lambda^{k-2}&\cdots&\binom{k}{m-1}\lambda^{k-m+1}\\  &\lambda^k&\binom{k}{1}\lambda^{k-1}&\ddots&\vdots\\  &&\ddots&\ddots&\binom{k}{2}\lambda^{k-2}\\  &&&\lambda^k&\binom{k}{1}\lambda^{k-1}\\  &&&&\lambda^k  \end{bmatrix}

分開三種情況討論。若 \vert\lambda\vert>1,顯然 \lim_{k\to\infty}J^k_{\ast}(\lambda) 不存在。若 \vert\lambda\vert<1\lim_{k\to\infty}J^k_{\ast}(\lambda)=0。若 \vert\lambda\vert=1\lambda\neq 1,即 \lambda=e^{i\theta}0<\theta<2\pi,則 \left(J^k_{\ast}(\lambda)\right)_{ii}=\lambda^k 震盪不止,致使 J_{\ast}^k(\lambda) 無法趨於極限值。若 \lambda=1

\displaystyle  J_{\ast}^k(1)=\begin{bmatrix}  1&\binom{k}{1}&\binom{k}{2}&\cdots&\binom{k}{m-1}\\  &1&\binom{k}{1}&\ddots&\vdots\\  &&\ddots&\ddots&\binom{k}{2}\\  &&&1&\binom{k}{1}\\  &&&&\lambda^k  \end{bmatrix}

極限存在的唯一情況是 m=1,即 J_{\ast}(1)=[1]。總結以上討論,\lim_{k\to\infty}A^k 存在的條件如下:\vert\lambda\vert<1\lambda=1 的指標 (index,即最大基本分塊階數) 等於1,換句話說,\lambda=1 的代數重數等於幾何重數。

 
接著討論 \lim_{k\to\infty}A^k 的形式。簡明地說,\lim_{k\to\infty}A^k 存在的充要條件是 Jordan 矩陣具有下列分塊結構:

J=M^{-1}AM=\begin{bmatrix}  I_\beta&0\\  0&K  \end{bmatrix}

其中 \beta 代表 \lambda=1 的代數重數,且 \rho(K)<1 (分塊 K 的特徵值之絕對值都小於1)。若 \beta=0,可知 \rho(A)=\rho(J)=\rho(K)<1,則 \lim_{k\to\infty}A^k=0。若 \beta>0

\lim_{k\to\infty}A^k=\lim_{k\to\infty}M\begin{bmatrix}  I_\beta&0\\  0&K^k  \end{bmatrix}M^{-1}=M\begin{bmatrix}  I_\beta&0\\  0&0  \end{bmatrix}M^{-1}=P

M=\begin{bmatrix}  X&Y  \end{bmatrix},其中 Xn\times\beta 階,Yn\times(n-\beta) 階。分塊 X 的行向量就是對應 \lambda=1 的特徵向量,故 N(I-A)=C(X)。考慮

\begin{aligned}  I-A&=I-MJM^{-1}=\begin{bmatrix}  X&Y  \end{bmatrix}\begin{bmatrix}  0&0\\  0&I_{n-\beta}-K  \end{bmatrix}\begin{bmatrix}  X&Y  \end{bmatrix}^{-1}\\  &=\begin{bmatrix}  0&Y(I_{n-\beta}-K)  \end{bmatrix}\begin{bmatrix}  X&Y  \end{bmatrix}^{-1},\end{aligned}

分塊 I_{n-\beta}-K 為上三角矩陣且其主對角元皆不為零,故為可逆矩陣,推知 C(I-A)=C(Y(I_{n-\beta}-K))=C(Y)。因為 M 是可逆矩陣,C(X)C(Y) 不交集,故 N(I-A)\cap C(I-A)=\{\mathbf{0}\}。寫出 PI-P 的表達式:

P=\begin{bmatrix}  X&Y  \end{bmatrix}\begin{bmatrix}  I_\beta&0\\  0&0  \end{bmatrix}\begin{bmatrix}  X&Y  \end{bmatrix}^{-1}=\begin{bmatrix}  X&0  \end{bmatrix}\begin{bmatrix}  X&Y  \end{bmatrix}^{-1}

I-P=\begin{bmatrix}  X&Y  \end{bmatrix}\begin{bmatrix}  0&0\\  0&I_{n-\beta}  \end{bmatrix}\begin{bmatrix}  X&Y  \end{bmatrix}^{-1}=\begin{bmatrix}  0&Y  \end{bmatrix}\begin{bmatrix}  X&Y  \end{bmatrix}^{-1}

上式說明 C(P)=C(X)C(I-P)=C(Y)。因為 P^2=P,故 P 是冪等矩陣,滿足 N(P)=C(I-P)C(P)=N(I-P) (見“特殊矩陣(5):冪等矩陣”)。綜合以上結果可推論 C(P)=N(I-A)N(P)=C(I-A)\lim_{k\to\infty}A^k=P 即是沿著子空間 C(I-A)N(I-A) 的投影矩陣 (見“直和與投影”)。

 
最後我們說明 P 的計算法。雖然 P 可由 Jordan 形式求得,但 Jordan 形式在本質上是ㄧ個數值不穩定結構 (見“Jordan 形式大解讀 (下)”),因此勢必另尋他法。下面介紹基於秩分解和奇異值分解的算法。若 A 為一 n\times n 階廣義收斂矩陣,寫出 I-A 的秩分解 I-A=GH (見“秩分解──目視行秩等於列秩”),其中 Gn\times r 階,Hr\times n 階,且 \text{rank}(I-A)=\text{rank}G=\text{rank}H=r。我們聲稱 r\times rHG 是可逆矩陣。利用此性質:C(B)\cap N(B)=\{\mathbf{0}\} 等價於 \text{rank}B=\text{rank}(B^2) (證明見“每週問題 August 9, 2010”) 和矩陣秩性質 (見等式五和不等式二,“破解矩陣秩的等式與不等式證明”),以及 \dim N(G)=0,可得

\displaystyle\begin{aligned}  r=\text{rank}(GH)&=\text{rank}(GHGH)\\  &=\text{rank}(HGH)-\dim(N(G)\cap C(HGH))\\  &=\text{rank}(HGH)\le\text{rank}(HG),  \end{aligned}

\text{rank}(HG)=r。沿著子空間 C(I-A)N(I-A) 的投影矩陣即為

\displaystyle  P=I-G(HG)^{-1}H

首先證明 P 是一投影矩陣,即 P^2=P,如下:

\displaystyle\begin{aligned}  P^2&=(I-G(HG)^{-1}H)^2\\  &=I-2G(HG)^{-1}H+G(HG)^{-1}HG(HG)^{-1}H\\  &=I-G(HG)^{-1}H=P,  \end{aligned}

N(P)=C(I-P)C(P)=N(I-P)。因為 C((HG)^{-1}H)=C(H)

\displaystyle  N(P)=C(I-P)=C(G(HG)^{-1}H)=C(GH)=C(I-A)

因為 N((HG)^{-1}H)=N(H)

\displaystyle  C(P)=N(I-P)=N(G(HG)^{-1}H)=N(GH)=N(I-A)

因此證明 P 是沿著子空間 N(P)=C(I-A)C(P)=N(I-A) 的投影矩陣。

 
如果採用奇異值分解,寫出

\displaystyle  I-A=U\Sigma V^\ast=\begin{bmatrix}  U_1&U_2  \end{bmatrix}\begin{bmatrix}  D&0\\  0&0  \end{bmatrix}\begin{bmatrix}  V_1^\ast\\  V_2^\ast  \end{bmatrix}=U_1DV_1^\ast

其中 UVn\times n 階么正矩陣 (unitary matrix),D=\text{diag}(\sigma_1,\ldots,\sigma_r)\sigma_1\ge\cdots\ge\sigma_r>0 是奇異值 (見“奇異值分解 (SVD)”)。因為 U_1Dn\times r 階,V_1^\astr\times n 階,且 \text{rank}(U_1D)=\text{rank}(V_1^\ast)=r,套用秩分解給出的投影矩陣公式,可得

\displaystyle\begin{aligned}  P&=I(U_1D)(V_1^\ast U_1D)^{-1}V_1^\ast\\  &=I-U_1DD^{-1}(V_1^\ast U_1)^{-1}V_1^\ast\\  &=I-U_1(V_1^\ast U_1)^{-1}V_1^\ast.  \end{aligned}

Advertisements
本篇發表於 線性代數專欄, 數值線性代數 並標籤為 , , , , 。將永久鏈結加入書籤。

6 則回應給 廣義收斂矩陣

  1. ddlai 說道:

    最後一段話不大了解。因為 P^2 = P,P 是冪等矩陣,所以,C(P) 和 N(P) 構成整個向量空間。由結論知 C(P) = N(I – A),N(P) = C(I – A),所以C(I – A)和N(I – A)同樣構成整個向量空間,P應是自N(I – A)投影至C(P)的投影矩陣,而有N(P) = C(I – A)。

    • ccjou 說道:

      我不是很清楚你的疑問所在,不過你寫出的最後一句話並不正確。冪等矩陣 P 是「沿著」(不是「自」) 零空間 N(P) 投影至行空間 C(P) 的投影矩陣,所以也可以說 P 是沿著 C(I-A) 投影至 N(I-A) 的投影矩陣。因為 PA=P 即有 P(I-A)=0,這指出 PC(I-A) 投影至 \{\mathbf{0}\},所以我們說 P 是沿著 C(I-A) 投影至 N(I-A)=C(P) 的投影矩陣。

      • ddlai 說道:

        我的疑問在於不了解「沿著」的意思。一般來說,由投影的模糊概念,當x在欲投影的空間時,投影矩陣P應有P(x)= x,因此投影矩陣是把它欲投影的空間映射到它的值空間,也就是說,它的值空間也就是它的行空間C(P)應等於它所欲投影的空間。而且投影矩陣還應把它欲投影空間的正交補集映射到\{0\},如此才能把任意的x投影到它欲投影的空間。所以,如果說P是沿著C(I-A)投影至N(I-A) = C(P),那是不是意指PC(I-A)映射到它的投影空間呢?

        • ccjou 說道:

          為容易閱讀我將你的回覆中的LaTex修訂過了,$$P$$ 的語法改為 $後面輸入latex(五個小寫英文字母)、空格、數學式,再以$結束。

          本文的投影並非一定是正交投影,可以是斜投影,故而沒有正交補集的概念,僅有補集概念。投影所「沿著」的子空間就是值域 (投影空間) 的補集。所謂「沿著」的意義最好從圖形上看,請見「直和與投影」:
          https://ccjou.wordpress.com/2010/04/06/%E7%9B%B4%E5%92%8C%E8%88%87%E6%8A%95%E5%BD%B1/

          在三維空間中,如果我說 P 是沿著一 (穿越原點) 直線 L 投影至平面 Q 的投影矩陣,那麼直線 L 上的所有點不就被投影至原點?空間的所有點則被投影至平面 Q,此即投影空間。換句話說,L=N(P),因為 x\in N(P),即有 Px=0。而 Q=C(P),因為 Q 中任一向量皆為 Pyy\in\mathbb{R}^3

          • ddlai 說道:

            我想我了解了。這投影的概念,感覺起來跟代數學裡的商空間有異曲同工之妙。在「直和與投影」一文中的直線L可被看作是商空間,而投影映射則是限定於其欲投影空間的商變換。在沿著直線L投影的平面Q上,任一點總是可以寫作沿直線L投影的零向量和視平面上任一點上為向量的相加,此即為陪集的概念。

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s