矩陣範數

本文的閱讀等級:中級

幾何向量 \mathbf{x} 的大小表現於其長度 \Vert\mathbf{x}\Vert (原點至向量端點的歐氏距離),但矩陣 A 的大小應如何度量呢?矩陣的大小度量稱為矩陣範數 (norm),也記作 \Vert A\Vert。佈於相同數系 (\mathbb{R}\mathbb{C}) 且尺寸相同的矩陣集合構成一向量空間,因此最直接的度量方式是仿造向量長度來定義矩陣範數。令 m\times n 階矩陣 A=[a_{ij}] 的行向量 (column vector) 為 \mathbf{a}_1,\ldots,\mathbf{a}_n。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\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_pp=\min\{m,n\},為 A 的奇異值,其中 r=\hbox{rank}A。下式成立 (詳見“SVD 於矩陣近似的應用”):

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

 
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}=(x_1,\ldots,x_n)^T 的長度改變。利用上述性質計算 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=0A=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

 
Am\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=1a_{kj}\ge 0x_j=-1a_{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

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

2 則回應給 矩陣範數

  1. Yu Sixie 說道:

    周老师您好:

    因为{ 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的列向量的线性组合。

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

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s