譜半徑與矩陣範數

本文的閱讀等級:高級

\vert z\vert<1,我們知道 \lim_{k\to\infty}z^k=0\sum_{k=0}^{\infty}z^k=\frac{1}{1-z}。讀者自然會問:矩陣是否也擁有類似的性質?矩陣範數 (matrix norm) 是一種矩陣「大小」的度量,我們不妨由此著手。令 A=[a_{ij}] 為一 n\times n 階矩陣,我們曾經證明:若 \Vert A\Vert<1,其中 \Vert\cdot\Vert 可為任何標準矩陣範數 (稍後詳述),則 Neumann 無窮級數 \sum_{k=0}^{\infty}A^k 收斂 (見“Neumann 無窮級數”)。然而 \Vert A\Vert<1 並非 \sum_{k=0}^{\infty}A^k 收斂的必要條件,例如,A=\begin{bmatrix}  0&3\\  0&0  \end{bmatrix} 的特徵值皆為零且 \Vert A\Vert=3,但是 \sum_{k=0}^{\infty}A^k=\begin{bmatrix}  1&3\\  0&1  \end{bmatrix}。除了矩陣範數,矩陣的特徵值也具有度量矩陣「大小」的功能。考慮特徵方程 A\mathbf{x}=\lambda\mathbf{x},則 \Vert A\mathbf{x}\Vert=\vert\lambda\vert\cdot\Vert\mathbf{x}\Vert,故 \vert\lambda\vert 決定了向量 A\mathbf{x} 的長度伸縮。令 \sigma(A)A 的所有相異特徵值所成的集合,稱為矩陣譜 (spectrum),並令 \rho(A)A 的最大絕對特徵值,稱為譜半徑 (spectral radius),即

\displaystyle  \rho(A)=\max_{\lambda\in\sigma(A)}\vert\lambda\vert

在複數平面上,A 的所有特徵值都位於圓心在原點,半徑等於 \rho(A) 的圓內。類似矩陣範數,譜半徑同樣可控制冪矩陣 A^k 的成長。本文討論兩個問題:(1) 如何利用譜半徑 \rho(A) 判別收斂矩陣 \lim_{k\to\infty}A^k=0 和 Neumann 無窮級數 \sum_{k=0}^{\infty}A^k 的收斂性?(2) 譜半徑和矩陣範數有何關係?

 
開始之前,我們先回顧矩陣範數的定義 (見“矩陣範數”):

(P1) \Vert A\Vert\ge 0,且 \Vert A\Vert=0A=0

(P2) \Vert cA\Vert=\vert c\vert\cdot\Vert A\Vertc 為一純量。

(P3) \Vert A+B\Vert\le\Vert A\Vert+\Vert B\Vert

(P4) \Vert AB\Vert\le\Vert A\Vert\cdot\Vert B\Vert

下面是幾個常用的矩陣範數,它們全都滿足上述界定性質。

Frobenius 範數: \Vert A\Vert_F=\sqrt{\sum_{i=1}^n\sum_{j=1}^n\vert a_{ij}\vert^2}

2-範數: \Vert A\Vert_2=\max_{\Vert\mathbf{x}\Vert_2=1}\Vert A\mathbf{x}\Vert_2

1-範數:\Vert A\Vert_1=\max_{\Vert\mathbf{x}\Vert_1=1}\Vert A\mathbf{x}\Vert_1=\max_{1\le j\le n}\sum_{i=1}^n\vert a_{ij}\vert

\infty-範數:\Vert A\Vert_{\infty}=\max_{\Vert\mathbf{x}\Vert_{\infty}=1}\Vert A\mathbf{x}\Vert_{\infty}=\max_{1\le i\le n}\sum_{j=1}^n\vert a_{ij}\vert

 
針對第一個問題,定理一闡明譜半徑、收斂矩陣和 Neumann 無窮級數的等價關係。

 
定理一:令 A 為一 n\times n 階矩陣,以下陳述是等價的:

(1) \rho(A)<1

(2) \lim_{k\to\infty}A^k=0

(3) \sum_{k=0}^{\infty}A^k 收斂,且 (I-A)^{-1}=\sum_{k=0}^{\infty}A^k

證明如下。

(1)\Rightarrow(2):見“收斂矩陣”。

(2)\Rightarrow(3):考慮

(I-A)(I+A+A^2+\cdots+A^{k-1})=I-A^k

k\to\infty,若 A^k\to 0,則 (I-A)^{-1} 存在,且 (I-A)^{-1}=\sum_{k=0}^{\infty}A^k

(3)\Rightarrow(1):若 \sum_{k=0}^{\infty}A^k 收斂,考慮 Jordan 形式 J=M^{-1}AM,即知 \sum_{k=0}^{\infty}J^k 收斂。故對於任一基本 Jordan 分塊 J_{\ast}(\lambda)\sum_{k=0}^{\infty}J^k_{\ast}(\lambda) 收斂。利用二項式定理,可算得 m\times m 階分塊 (詳細過程見“收斂矩陣”)

\displaystyle  J_{\ast}^k(\lambda)=\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}

換句話說,對於任一 \lambda\in\sigma(A)\left(\sum_{k=0}^{\infty}J^k_{\ast}(\lambda)\right)_{ii}=\sum_{k=0}^{\infty}\lambda^k 也收斂,由此斷定 \vert\lambda\vert<1,證得 \rho(A)<1

 
接著回答第二個問題,矩陣譜半徑的上界由矩陣範數給定,如下。

 
定理二:對於每一矩陣範數 \Vert A\Vert\rho(A)\le\Vert A\Vert

考慮 A\mathbf{x}=\lambda\mathbf{x},設 n\times n 階矩陣 X=\begin{bmatrix}  \mathbf{x}&\mathbf{0}&\cdots&\mathbf{0}  \end{bmatrix},很容易驗證 AX=\lambda X。利用矩陣範數性質 (P2) 和 (P4),

\vert\lambda\vert\cdot\Vert X\Vert=\Vert\lambda X\Vert=\Vert AX\Vert\le\Vert A\Vert\cdot\Vert X\Vert

就有 \vert\lambda\vert\le\Vert A\Vert,推得 \rho(A)\le\Vert A\Vert

 
以定理二為前導,定理三陳述譜半徑和矩陣範數的等式表達。

 
定理三:對於每一矩陣範數 \Vert A\Vert\rho(A)=\lim_{k\to\infty}\Vert A^k\Vert^{1/k}

A 有特徵值 \lambda,則 A^k 有特徵值 \lambda^k。因為 \vert\lambda\vert^k=\vert\lambda^k\vert,可知 \rho(A)^k=\rho(A^k)。根據定理二,\rho(A^k)\le\Vert A^k\Vert,所以 \rho(A)\le\Vert A^k\Vert^{1/k}。對於任意 \epsilon>0,矩陣 A/(\rho(A)+\epsilon) 的特徵值之絕對值小於1,就有 \rho(A/(\rho(A)+\epsilon))<1,由定理一可得

\displaystyle  \lim_{k\to\infty}\left(\frac{A}{\rho(A)+\epsilon}\right)^k=0

矩陣範數性質 (P1) 指定零矩陣的範數必為零,即有

\displaystyle  \lim_{k\to\infty}\left\Vert\frac{A^k}{(\rho(A)+\epsilon)^k}\right\Vert=\lim_{k\to\infty}\frac{\Vert A^k\Vert}{(\rho(A)+\epsilon)^k}=0

k 趨於無窮大的過程中,必存在一正整數 L 使得 \Vert A^L\Vert/(\rho(A)+\epsilon)^L<1。利用矩陣範數性質 (P4),對於任意正整數 m,可歸納得

\displaystyle  \frac{\Vert A^{mL}\Vert}{(\rho(A)+\epsilon)^{mL}}\le\frac{\Vert A^L\Vert^m}{(\rho(A)+\epsilon)^{mL}}=\left(\frac{\Vert A^L\Vert}{(\rho(A)+\epsilon)^L}\right)^m<1

所以,對於任意 \epsilon>0 以及任何正整數 m

\rho(A)\le\Vert A^{mL}\Vert^{1/mL}<\rho(A)+\epsilon

\epsilon\to 0,推知 \rho(A)=\lim_{m\to\infty}\Vert A^{mL}\Vert^{1/mL}=\lim_{k\to\infty}\Vert A^k\Vert^{1/k}

 
下面介紹兩個應用。設 A=[a_{ij}]B=[b_{ij}] 同為 n\times n 階矩陣。令 A\ge B 表示對於每一 i,j 都有 a_{ij}\ge b_{ij}

例一:若 A\ge B\ge 0,則 \rho(A)\ge\rho(B)

A\ge B\ge 0 可推論 A^k\ge B^k\ge 0,其中 k 是任何正整數。因為每一 i,j(A^k)_{ij}\ge(B^k)_{ij}\ge 0,故知 \Vert A^k\Vert_F\ge\Vert B^k\Vert_F。計算 k 次方根,並令 k 趨於無窮大:

\displaystyle  \lim_{k\to\infty}\Vert A^k\Vert^{1/k}_F\ge\lim_{k\to\infty}\Vert B^k\Vert^{1/k}_F

由定理三,立得 \rho(A)\ge\rho(B)

 
例二:若 A\ge 0,則

\rho(A)<r~~\Leftrightarrow~~(rI-A)^{-1}\ge 0

(\Rightarrow):若 \rho(A)<r,則 \rho(A/r)<1。利用定理一,rI-A=r(I-\frac{A}{r}) 可逆,又因 A\ge 0,可得

\displaystyle  (rI-A)^{-1}=\frac{1}{r}\sum_{k=0}^{\infty}\left(\frac{A}{r}\right)^k\ge 0

(\Leftarrow):對於任一 m\times n 階矩陣 B=[b_{ij}],定義 \vert B\vert=[\vert b_{ij}\vert] 為一同尺寸矩陣,其中各元 \vert b_{ij}\vertB 的對應元的絕對值構成。(注意,請勿將行列式與絕對矩陣混淆。) 若矩陣 B, C 可乘,則

\displaystyle  \left(\vert BC\vert\right)_{ij}=\left\vert\sum_{k}b_{ik}c_{kj}\right\vert\le\sum_{k}\vert b_{ik}\vert\cdot\vert c_{kj}\vert=\left(\vert B\vert\cdot\vert C\vert\right)_{ij}

因此 \vert BC\vert\le\vert B\vert\cdot\vert C\vert。證明步驟如下:假設 (rI-A)^{-1}\ge 0。考慮 A\mathbf{x}=\lambda\mathbf{x},因為 A\ge 0,可知 \vert A\vert=A,利用上述不等式,

\vert\lambda\vert\cdot\vert\mathbf{x}\vert=\vert\lambda\mathbf{x}\vert=\vert A\mathbf{x}\vert\le\vert A\vert\cdot\vert\mathbf{x}\vert=A\vert\mathbf{x}\vert

不等式兩邊乘以 -1,再同加 r\vert\mathbf{x}\vert,可得

(rI-A)\vert\mathbf{x}\vert\le(r-\vert\lambda\vert)\vert\mathbf{x}\vert

因為 (rI-A)^{-1}\ge 0,上式左乘 (rI-A)^{-1} 仍維持不等關係,

\mathbf{0}\le\vert\mathbf{x}\vert\le(r-\vert\lambda\vert)(rI-A)^{-1}\vert\mathbf{x}\vert

由此可知 r-\vert\lambda\vert\ge 0。但 r\neq\vert\lambda\vert,否則 \vert\mathbf{x}\vert=\mathbf{0},違反特徵向量不得為零向量的要求。故對於每一 \lambda\in\sigma(A)\vert\lambda\vert<r,證得 \rho(A)<r

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

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s