偽譜分析

Posted on 06/26/2013 by ccjou

本文的閱讀等級：高級

令 A 為一 n\times n 階矩陣。矩陣 A 的特徵值形成的集合稱為矩陣譜 (spectrum)，記為 \sigma(A)=\{\lambda\in\mathbb{C}\vert~\det(A-\lambda I)=0\}。現實應用中矩陣難免引入擾動，我們非常關心特徵值會有多大的變異，其中一部分固然來自擾動的直接衝擊，另一部分則取決於矩陣的固有性質。正規矩陣 A 的標記是 A 和 A^\ast 滿足交換律 AA^\ast=A^\ast A，並擁有一個令人稱頌的性質：可么正對角化，意思是 A 可分解為 A=U\Lambda U^\ast，其中 \Lambda=\hbox{diag}(\lambda_1,\ldots,\lambda_n)，\lambda_i\in\sigma(A)，且 U 是么正 (unitary) 矩陣，U^\ast=U^{-1} (見“特殊矩陣 (2)：正規矩陣”)。因為這個特性，正規矩陣特徵值的變化上界完全由擾動決定，所以相對不敏感。然而，對於非正規矩陣，縱使微小的擾動也可能引發特徵值的巨大改變 (見“特徵值的擾動分析”)。見下例：

\displaystyle A=\begin{bmatrix} 0&1\\ 0&0 \end{bmatrix},~~~E=\begin{bmatrix} 0&0\\ \epsilon&0 \end{bmatrix}。

矩陣 A 有重複的特徵值 0，但僅有一個線性獨立的特徵向量，因此不可對角化，自然是非正規矩陣。設微擾矩陣 E 的元 \epsilon 是一極小的正數。矩陣 A+E 有相異特徵值 \pm\sqrt{\epsilon}，但仍非正規矩陣。考慮一般情況，為了探討 A 的特徵值受到微擾矩陣 E 的影響，在 \Vert E\Vert\le\epsilon 的前提下，我們可以隨意設定 E，然後觀察收集 A+E 的特徵值。這個思想實驗的結果稱為矩陣 A 的偽譜 (pseudospectrum)，有下列三種等價的表達式：

  1. \displaystyle \sigma_\epsilon(A)=\{\lambda\in\mathbb{C}\vert~\lambda\in\sigma(A+E),\Vert E\Vert\le\epsilon\}

  2. \displaystyle \sigma_\epsilon(A)=\{\lambda\in\mathbb{C}\vert~\Vert(A-\lambda I)^{-1}\Vert\ge\epsilon^{-1}\}

  3. \displaystyle \sigma_\epsilon(A)=\{\lambda\in\mathbb{C}\vert~\Vert(A-\lambda I)\mathbf{x}\Vert\le\epsilon,\mathbf{x}\in\mathbb{C}^n,\Vert\mathbf{x}\Vert=1\}

明顯地，當 \epsilon\to 0，偽譜 \sigma_\epsilon(A) 收斂至矩陣譜 \sigma(A)。本文將證明這三種表達是等價的，並介紹幾個偽譜的性質 (取自[1,2])。

 
若 \lambda\in\sigma(A)，則 \lambda 屬於上述三個 \sigma_\epsilon(A)。以下假設 \lambda\notin\sigma(A)。為便利推演，我們設定 \Vert\cdot\Vert 是2-範數 (見“矩陣範數”)。下面是三種偽譜等價表達式的證明。

1\Rightarrow 2：給定 E 且 \Vert E\Vert\le\epsilon，假設 \lambda\in\sigma(A+E)，故知存在一 \mathbf{x}\in\mathbb{C}^n 且 \Vert\mathbf{x}\Vert=1，使得 (A+E)\mathbf{x}=\lambda\mathbf{x}。乘開上式，改寫為 \mathbf{x}=(\lambda I-A)^{-1}E\mathbf{x}。使用矩陣範數不等式，可得

\displaystyle 1=\Vert\mathbf{x}\Vert=\Vert(A-\lambda I)^{-1}E\mathbf{x}\Vert\le\Vert(A-\lambda I)^{-1}\Vert\cdot\Vert E\Vert\cdot\Vert\mathbf{x}\Vert\le\Vert(A-\lambda I)^{-1}\Vert\epsilon，

即證明 \Vert(A-\lambda I)^{-1}\Vert\ge\epsilon^{-1}。

2\Rightarrow 3：假設 \Vert(A-\lambda I)^{-1}\Vert\ge\epsilon^{-1}，必定存在 \mathbf{z}\in\mathbb{C}^n 使得 \Vert(A-\lambda I)^{-1}\Vert=\Vert(A-\lambda I)^{-1}\mathbf{z}\Vert/\Vert\mathbf{z}\Vert。令 \mathbf{y}=(A-\lambda I)^{-1}\mathbf{z}。合併以上結果，

\displaystyle \frac{1}{\epsilon}\le\frac{\Vert(A-\lambda I)^{-1}\mathbf{z}\Vert}{\Vert\mathbf{z}\Vert}=\frac{\Vert\mathbf{y}\Vert}{\Vert(A-\lambda I)\mathbf{y}\Vert}，

故單位向量 \mathbf{x}=\mathbf{y}/\Vert\mathbf{y}\Vert 滿足 \Vert(A-\lambda I)\mathbf{x}\Vert\le\epsilon。

3\Rightarrow 1：假設存在 \mathbf{x} 且 \Vert\mathbf{x}\Vert=1 使得 \Vert(A-\lambda I)\mathbf{x}\Vert\le\epsilon。我們要證明存在 E 且 \Vert E\Vert\le\epsilon 使得 \lambda\in\sigma(A+E)。令 \mathbf{y}\in\mathbb{C}^n 且 \Vert\mathbf{y}\Vert=1 滿足 (A-\lambda I)\mathbf{x}=\delta\mathbf{y}，其中 0\le\delta\le\epsilon。設 E=-\delta\mathbf{y}\mathbf{x}^\ast，則

\displaystyle (A+E)\mathbf{x}=(A-\delta\mathbf{y}\mathbf{x}^\ast)\mathbf{x}=A\mathbf{x}-\delta\mathbf{y}=A\mathbf{x}-A\mathbf{x}+\lambda\mathbf{x}=\lambda\mathbf{x}，

表明 \lambda\in\sigma(A+E)，且 \Vert E\Vert=\Vert\delta\mathbf{y}\mathbf{x}^\ast\Vert\le\delta\Vert\mathbf{y}\Vert\cdot\Vert\mathbf{x}^\ast\Vert=\delta\le\epsilon。

 
下面介紹偽譜的一些基本性質。對於 S,T\subset\mathbb{C}，我們定義兩集合之和為 S+T=\{s+t\vert~s\in S,t\in T\}。

 
(1) 緊緻性：\sigma_\epsilon(A) 是 \mathbb{C} 的一個緊集 (compact set)。

矩陣的特徵值為矩陣各元的連續函數 (見“特徵值的連續性”)。根據第一個定義式，我們可以將 \sigma_\epsilon(A) 看成是矩陣 A+E 通過一連續函數 (即特徵值抽取函數) 的值域。因為 \Vert E\Vert\le\epsilon 是一緊集，經連續函數的值域仍為緊集，故可推論 \sigma_\epsilon(A) 是一緊集。

 
(2) 平移：若 c\in\mathbb{C}，則 \sigma_{\epsilon}(A+cI)=\sigma_\epsilon(A)+c。

當矩陣與一純量矩陣相加，矩陣譜以線性方式改變，即有 \sigma(A+cI+E)=\sigma(A+E)+c，使用第一個定義式即證得所求。

 
(3) 純量乘法：若 c\in\mathbb{C}，則 \sigma_{\epsilon\vert c\vert}(cA)=c\sigma_\epsilon(A)。

當矩陣乘以一純量時，矩陣範數以線性方式改變。設 \lambda\in\sigma_{\epsilon\vert c\vert}(cA)，根據第二個定義式，

\displaystyle \frac{1}{\epsilon\vert c\vert}\le\Vert(cA-\lambda I)^{-1}\Vert=\frac{1}{\vert c\vert}\left\|\left(A-\frac{\lambda}{c}I\right)^{-1}\right\|，

此即 \lambda/c\in\sigma_\epsilon(A)。

 
一 n\times n 階矩陣 A 的數值域 (numerical range) 定義為 (見“數值域”) \displaystyle W(A)=\left\{\mathbf{x}^\ast A\mathbf{x}\vert~\mathbf{x}\in\mathbb{C}^n, \mathbf{x}^\ast\mathbf{x}=1\right\}。下面性質說明偽譜與數值域的包容關係。

(4) 數值域之偽譜包容性：\sigma_\epsilon(A)\subseteq W(A)+\Delta_{\epsilon}，其中 \Delta_{\epsilon}=\{z\in\mathbb{C}\vert~\vert z\vert\le\epsilon\}。

若 \lambda\in\sigma_\epsilon(A)，根據第一個定義式，可知存在 E 且 \Vert E\Vert\le\epsilon 使得 \lambda\in\sigma(A+E)。所以存在 \mathbf{x}\in\mathbb{C}^n 且 \Vert\mathbf{x}\Vert=1 滿足 (A+E)\mathbf{x}=\lambda\mathbf{x}，也就有

\displaystyle \lambda=\mathbf{x}^\ast\lambda\mathbf{x}=\mathbf{x}^\ast(A+E)\mathbf{x}=\mathbf{x}^\ast A\mathbf{x}+\mathbf{x}^\ast E\mathbf{x}，

其中 \mathbf{x}^\ast A\mathbf{x}\in W(A) 且 \mathbf{x}^\ast E\mathbf{x}\in W(E)。因為 \Vert E\Vert\le\epsilon，可知 W(E) 位於半徑等於 \epsilon 的圓盤內，即 W(E)\subseteq\Delta_\epsilon。

 
(5) 相似矩陣之偽譜包容性：若 A=SBS^{-1}，則 \sigma_\epsilon(A)\subseteq\sigma_{\kappa(S)\epsilon}(B)，其中 \kappa(S)=\Vert S\Vert\cdot\Vert S^{-1}\Vert 是條件數。

假設 \lambda\in\sigma_\epsilon(A)，使用矩陣範數不等式，可得

\displaystyle\begin{aligned} \frac{1}{\epsilon}\le\Vert(A-\lambda I)^{-1}\Vert&=\Vert(S(B-\lambda I)^{-1}S^{-1}\Vert\\ &\le\Vert S\Vert\cdot\Vert(B-\lambda I)^{-1}\Vert\cdot\Vert S^{-1}\Vert\\ &=\kappa(S)\Vert(B-\lambda I)^{-1}\Vert ,\end{aligned}

故證明 \lambda\in\sigma_{\kappa(S)\epsilon}(B)。若 S 為一么正矩陣，則 \kappa(S)=1，可知偽譜具有么正相似不變性，即 \sigma_\epsilon(A)=\sigma_\epsilon(B)。若 A 可對角化為 A=S\Lambda S^{-1}，利用性質 (2) 可證明 \sigma_\epsilon(A)\subseteq\sigma(A)+\Delta_{\kappa(S)\epsilon}。

 
與數值域相比，偽譜的研究社群顯得冷清許多，可能有兩個原因。第一，矩陣譜 \sigma(A) 是一離散集合，因此隨著微擾 \epsilon 改變的偽譜 \sigma_\epsilon(A) 未必是連通集，並且不保證是凸集 (見[2]圖例3-6)，故而喪失了凸集擁有的美好性質，但數值域則沒有這些遺憾。第二，性質 (4) 說明偽譜 \sigma_\epsilon(A) 被 A 的數值域 W(A) 和圓盤 \Delta_\epsilon 之和所包含。這意味，在很大的程度上，數值域足以覆蓋偽譜所要解決的問題範疇。

 
參考來源：
[1] Pseudospectra Gateway
[2] Scholarpedia: Pseudospectrum

This entry was posted in 特徵分析, 線性代數專欄 and tagged , , , . Bookmark the permalink.

Leave a comment