矩陣範數

Posted on 05/10/2010 by ccjou

本文的閱讀等級：中級

幾何向量 \mathbf{x}=(x_1,\ldots,x_n)^T\in\mathbb{R}^n 的大小表現於其長度 \Vert\mathbf{x}\Vert=\sqrt{x_1^2+\cdots+x_n^2} (原點至向量端點的歐氏距離)，那麼矩陣 A 的大小應如何度量呢？矩陣的大小度量稱為矩陣範數 (norm)，記為 \Vert A\Vert。佈於相同數系 (\mathbb{R} 或 \mathbb{C}) 且尺寸相同的矩陣集合構成一個向量空間，因此最直接的度量方式是仿造向量長度來定義矩陣範數。令 m\times n 階矩陣 A=[a_{ij}] 的行向量 (column vector) 為 \mathbf{a}_1,\ldots,\mathbf{a}_n\in\mathbb{C}^m，其中 \mathbf{a}_j=(a_{1j},\ldots,a_{mj})^T。Frobenius 範數定義如下：

\displaystyle \Vert A\Vert_{F}=\sqrt{\Vert\mathbf{a}_1\Vert^2+\cdots+\Vert\mathbf{a}_n\Vert^2}=\sqrt{\sum_{i=1}^m\vert a_{i1}\vert^2+\cdots+\sum_{i=1}^m\vert a_{in}\vert^2}=\sqrt{\sum_{i=1}^m\sum_{j=1}^n\vert a_{ij}\vert^2}。

Frobenius 範數 \Vert A\Vert_{F} 也可以由下式算得：

\Vert A\Vert_{F}=\sqrt{\mathrm{trace}(A^{\ast}A)}。

直接展開計算可驗證上面二式相等：

\displaystyle \mathrm{trace}(A^{\ast}A)=\sum_{j=1}^{n}(\overline{A}^{T}A)_{jj}=\sum_{j=1}^{n}\sum_{i=1}^{m}\overline{a_{ij}}a_{ij}=\sum_{i=1}^{m}\sum_{j=1}^{n}\vert a_{ij}\vert^2。

另外，Frobenius 範數與 A 的奇異值有關。令 \sigma_1\ge\cdots\ge \sigma_r>0，\sigma_{r+1}=\cdots=\sigma_p，p=\min\{m,n\}，為 A 的奇異值，其中 r=\hbox{rank}A。下式成立 (證明見“SVD 於矩陣近似的應用”)：

\displaystyle \Vert A\Vert_F=\sqrt{\sum_{i=1}^r\sigma_i^2} 。

Ferdinand Georg Frobenius (1849–1917) From http://upload.wikimedia.org/wikipedia/commons/9/99/GeorgFrobenius.jpg

 
Frobenius 範數常出現於數值線性代數問題中，但並非對所有應用都有效，原因是 Frobenius 範數單純地視矩陣為向量空間中的物件，然而矩陣還有一個異於一般向量空間的特殊意義──線性變換，亦即矩陣具有移動向量空間的能力。雖然 norm 的意思代表標準定量，實際上矩陣範數卻不存在公認唯一的度量方式。為了設計出實用的度量，我們轉而探討矩陣範數必須具備什麼性質。

 
我們知道 n 維向量可以視作 n\times 1 階矩陣，故從向量長度 (也稱為向量範數) 下手收集它所必須滿足的條件。首先，向量長度不為負，稱為非負性 (non negativity)，即 \Vert\mathbf{x}\Vert\ge 0，且 \Vert\mathbf{x}\Vert=0 若 \mathbf{x}=\mathbf{0}。還有，向量可相加 \mathbf{x}+\mathbf{y} 也可以和純量相乘 c\mathbf{x}。三角不等式給出向量和的長度上界：

\Vert\mathbf{x}+\mathbf{y}\Vert\le\Vert\mathbf{x}\Vert+\Vert\mathbf{y}\Vert，

而純量乘法滿足 \Vert c\mathbf{x}\Vert=\vert c\vert\cdot\Vert\mathbf{x}\Vert，稱為均齊性 (homogeneity)。除了上述三個性質，矩陣範數 \Vert A\Vert 還反映了線性變換 A\mathbf{x} 與向量 \mathbf{x} 的長度變化關係。利用上述性質計算 A\mathbf{x} 的長度：

\begin{aligned} \Vert A\mathbf{x}\Vert^2&=\Vert x_1\mathbf{a}_1+\cdots+ x_n\mathbf{a}_n\Vert^2\\ &\le\left(\Vert x_1\mathbf{a}_1\Vert+\cdots+\Vert x_n\mathbf{a}_n\Vert\right)^2\\ &=\left(\vert x_1\vert\cdot\Vert\mathbf{a}_1\Vert+\cdots+\vert x_n\vert\cdot\Vert\mathbf{a}_n\Vert\right)^2,\end{aligned}

利用 Cauchy-Schwarz 不等式 (見“Schwarz 不等式”)，可得

\begin{aligned} \left(\vert x_1\vert\cdot\Vert\mathbf{a}_1\Vert+\cdots+\vert x_n\vert\cdot\Vert\mathbf{a}_n\Vert\right)^2&\le\left(\Vert\mathbf{a}_1\Vert^2+\cdots+\Vert\mathbf{a}_n\Vert^2\right)\cdot\left(\vert x_1\vert^2+\cdots+\vert x_n\vert^2\right)\\ &=\Vert A\Vert^2_{F}\cdot\Vert\mathbf{x}\Vert^2,\end{aligned}

也就有 \Vert A\mathbf{x}\Vert\le\Vert A\Vert_F\cdot\Vert\mathbf{x}\Vert。這個結果暗示矩陣乘法 AB 可能也存在類似關係，亦即 \Vert AB\Vert_{F}\le\Vert A\Vert_F\cdot\Vert B\Vert_{F}。設 B=\begin{bmatrix} \mathbf{b}_1&\cdots&\mathbf{b}_p \end{bmatrix} 為 n\times p 階矩陣，將 AB 展開並使用上面得到的不等式，結果如下：

\begin{aligned} \Vert AB\Vert^2_{F}&=\left\Vert\begin{bmatrix} A\mathbf{b}_1&\cdots&A\mathbf{b}_p \end{bmatrix}\right\Vert^2_{F}\\ &=\Vert A\mathbf{b}_1\Vert^2+\cdots+\Vert A\mathbf{b}_p\Vert^2\\ &\le\Vert A\Vert_F^2\cdot\Vert\mathbf{b}_1\Vert^2+\cdots+\Vert A\Vert^2_F\cdot\Vert\mathbf{b}_p\Vert^2\\ &=\Vert A\Vert_F^{2}(\Vert\mathbf{b}_1\Vert^2+\cdots\Vert\mathbf{b}_p\Vert^2)=\Vert A\Vert_F^2\cdot\Vert B\Vert^2_F,\end{aligned}

證得 \Vert AB\Vert_{F}\le\Vert A\Vert_F\cdot\Vert B\Vert_F，稱為次可乘性 (submultiplicativity)。這個不等式連同前述三個源自向量長度的性質構成矩陣範數必須滿足的條件：

(1) \Vert A\Vert\ge 0，且 \Vert A\Vert=0 當且僅當 A=0。

(2) \Vert cA\Vert=\vert c\vert\cdot\Vert A\Vert

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

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

 
明顯地，Frobenius 範數滿足這四個條件，但從這些條件如何推導其他更具實用價值的矩陣範數定義？關鍵在條件 (4)。當 B 退化為向量 \mathbf{x} 時，條件 (4) 為 \Vert A\mathbf{x}\Vert\le\Vert A\Vert\cdot\Vert\mathbf{x}\Vert。如果 \mathbf{x}\neq\mathbf{0}，就有

\displaystyle\Vert A\Vert\ge\frac{\Vert A\mathbf{x}\Vert}{\Vert\mathbf{x}\Vert}。

由於 \Vert A\mathbf{x}\Vert/\Vert\mathbf{x}\Vert 不大於 \Vert A\Vert，此結果誘生下面這個合理的定義：

\displaystyle\Vert A\Vert_2=\max_{\mathbf{x}\neq\mathbf{0}}\frac{\Vert A\mathbf{x}\Vert}{\Vert\mathbf{x}\Vert}，

稱為2-範數 (2-norm)，因為它由歐氏向量長度所定。矩陣2-範數的意義十分明顯：\Vert A\Vert_2 控制了向量 \mathbf{x} 經線性變換 A 映射後的像 (image) A\mathbf{x} 的長度增長，故2-範數被歸於算子範數 (operator norm)。

 
不需要經過計算，我們也能判讀出一些特殊矩陣的矩陣2-範數。例如，單位矩陣 I 不改變向量 \mathbf{x}，因此 \Vert I\Vert_2=1。么正 (unitary) 矩陣 U 與正交 (orthogonal) 矩陣 Q 滿足 \Vert U\mathbf{x}\Vert_2=\Vert\mathbf{x}\Vert_2 和 \Vert Q\mathbf{x}\Vert_2=\Vert\mathbf{x}\Vert_2，故 \Vert U\Vert=\Vert Q\Vert=1。對角矩陣 A=\mathrm{diag}(a_{1},\ldots,a_{n}) 的矩陣2-範數為 \Vert A\Vert_2=\mathrm{max}_{i}\vert a_i\vert。對角矩陣 A 的主對角元即為其特徵值，我們或許因此猜測矩陣範數 \Vert A\Vert_2 即為最大的特徵值絕對值。不過事情沒那麼簡單，因為 A 未必是方陣，縱使 A 是方陣也不一定成立，如下例，A=\begin{bmatrix} 0&3\\ 0&0 \end{bmatrix}，A 的特徵值為 0，但 \Vert A\Vert_2=3。

 
設 A 為 m\times n 階矩陣，將 \Vert A\Vert_2 平方：

\displaystyle \Vert A\Vert^2_2=\max_{\mathbf{x}\neq\mathbf{0}}\frac{\Vert A\mathbf{x}\Vert^2}{\Vert\mathbf{x}\Vert^2}=\max_{\mathbf{x}\neq\mathbf{0}}\frac{\mathbf{x}^{\ast}A^{\ast}A\mathbf{x}}{\mathbf{x}^{\ast}\mathbf{x}}。

上式也可以表示為 (見“Hermitian 矩陣特徵值的變化界定”)：

\displaystyle \Vert A\Vert^2_2=\max_{\Vert\mathbf{x}\Vert=1}\mathbf{x}^{\ast}A^{\ast}A\mathbf{x}。

“奇異值分解的幾何意義”一文曾經證明

\displaystyle\max_{\Vert\mathbf{x}\Vert=1}\mathbf{x}^{\ast}A^{\ast}A\mathbf{x}=\lambda_{\mathrm{max}}，

其中 \lambda_{\mathrm{max}} 是 n 階半正定矩陣 A^{\ast}A 的最大特徵值，而 A 的最大奇異值等於 \sigma_{\mathrm{max}}=\sqrt{\lambda_{\mathrm{max}}}，所以，

\Vert A\Vert_2=\sigma_{\mathrm{max}}=\sigma_1。

 
我們得到出乎意外的簡潔結論：矩陣2-範數 \Vert A\Vert_2 即為 A 的最大奇異值。最後剩下一個問題要回答：我們定義的矩陣範數必須滿足前述四個條件。很容易驗證 \Vert A\Vert_2=\mathrm{max}_{\Vert\mathbf{x}\Vert=1}\Vert A\mathbf{x}\Vert 滿足前三個條件；利用不等式 \Vert A\mathbf{x}\Vert\le\Vert A\Vert_2\cdot\Vert\mathbf{x}\Vert 可得

\Vert AB\mathbf{x}\Vert\le\Vert A\Vert_2\cdot\Vert B\mathbf{x}\Vert\le\Vert A\Vert_2\cdot\Vert B\Vert_2\cdot\Vert\mathbf{x}\Vert，

因此，

\displaystyle\Vert AB\Vert_2=\max_{\mathbf{x}\neq\mathbf{0}}\frac{\Vert AB\mathbf{x}\Vert}{\Vert\mathbf{x}\Vert}\le\Vert A\Vert_2\cdot\Vert B\Vert_2。

 
我們知道矩陣2-範數由歐式向量誘生，如果改變向量範數自然可誘生其他矩陣範數 (見“向量範數”)，最常見的有兩種：1-範數和 \infty-範數，分別定義如下：

\displaystyle \Vert A\Vert_1=\max_{\Vert\mathbf{x}\Vert_1=1}\Vert A\mathbf{x}\Vert_1。

\displaystyle \Vert A\Vert_{\infty}=\max_{\Vert\mathbf{x}\Vert_{\infty}=1}\Vert A\mathbf{x}\Vert_{\infty}。

下面我們證明 \Vert A\Vert_1 等於最大的行絕對值和，\Vert A\Vert_{\infty} 等於最大的列絕對值和。對於任一 \mathbf{x}，\Vert\mathbf{x}\Vert_1=\sum_{j=1}^n\vert x_j\vert=1，

\displaystyle\begin{aligned} \Vert A\mathbf{x}\Vert_1&=\sum_{i=1}^n\left\vert\sum_{j=1}^n a_{ij}x_j\right\vert\le\sum_{i=1}^n\sum_{j=1}^n\vert a_{ij}\vert\cdot\vert x_j\vert\\ &=\sum_{j=1}^n\left(\vert x_j\vert\sum_{i=1}^n\vert a_{ij}\vert\right)\le\left(\sum_{j=1}^n\vert x_j\vert\right)\left(\max_{1\le j\le n}\sum_{i=1}^n\vert a_{ij}\vert\right)\\ &=\max_{1\le j\le n}\sum_{i=1}^n\vert a_{ij}\vert.\end{aligned}

若 A 的第 k 行有最大的絕對值和，設 \mathbf{x}=\mathbf{e}_k，\Vert\mathbf{e}_k\Vert_1=1，則 \Vert A\mathbf{e}_k\Vert_1=\max_{1\le j\le n}\sum_{i=1}^n\vert a_{ij}\vert，上式等號成立。使用同樣方法亦可證得

\displaystyle \Vert A\mathbf{x}\Vert_{\infty}=\max_{1\le i\le n}\left\vert\sum_{j=1}^na_{ij}x_j\right\vert\le\max_{1\le i\le n}\sum_{j=1}^n\vert a_{ij}\vert\cdot\vert x_j\vert\le\max_{1\le i\le n}\sum_{j=1}^n\vert a_{ij}\vert。

若 A 的第 k 列有最大絕對值和，設 x_j=1 若 a_{kj}\ge 0，x_j=-1 若 a_{kj}<0，則 \Vert\mathbf{x}\Vert_{\infty}=\max_{1\le j\le n}\vert x_j\vert=1，可證明上式等號成立。因此1-範數和 \infty-範數可用下列方式計算：

\displaystyle \Vert A\Vert_1=\max_{1\le j\le n}\sum_{i=1}^n\vert a_{ij}\vert,~~~\Vert A\Vert_{\infty}=\max_{1\le i\le n}\sum_{j=1}^n\vert a_{ij}\vert。

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

5 Responses to 矩陣範數

  1. Yu Sixie says:
    01/07/2014 at 10:34 am

    周老师您好：

    因为{ a}_{ i }是A的行向量，所以我不太明白为什么: { \Vert A x\Vert }^{ 2 }={ \Vert { x }_{ 1 }{ a }_{ 1 }+\cdots+{ x }_{ n }{ a}_{ n }\Vert }^{ 2 }

    我觉得{ a }_{ i }应该是A的列向量才能得到: { \Vert A x\Vert }^{ 2 }={ \Vert { x }_{ 1 }{ a }_{ 1 }+\cdots+{ x }_{ n }{a}_{ n }\Vert }^{ 2 }, 因为A x表示对A的列向量的线性组合。

    如有理解错误，烦请您原谅。

    Reply
  2. 耿阳 says:
    06/25/2017 at 2:47 pm

    周老師，您好！關於矩陣範數滿足的第一個條件
    “\Vert A \Vert = 0 若 A = 0” 應該是 “\Vert A \Vert = 0 當且僅當 A = 0”？
    我參考了：https://en.wikipedia.org/wiki/Matrix_norm

    Reply
  3. Skyz says:
    09/19/2017 at 11:25 am

    下面我們證明
    \Vert A\Vert_1
    等於最大的行絕對值和，
    \Vert A\Vert_{\infty}
    等於最大的列絕對值和
    為什麼是要證明這件事情呢
    思索很久還是不得其解

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s