二次型與正定矩陣

Posted on 10/21/2009 by ccjou

本文的閱讀等級：中級

令 A=[a_{ij}] 為一個 n\times n 階實矩陣，\mathbf{x}=\begin{bmatrix} x_1\\ \vdots\\ x_n \end{bmatrix} 為 n 維實向量，具有以下形式的實函數稱為二次型 (quadratic form)：

f(\mathbf{x})=\mathbf{x}^TA\mathbf{x}。

請注意，二次型 \mathbf{x}^TA\mathbf{x} 是一個純量。任意二次型 \mathbf{x}^TA\mathbf{x} 都可以轉換為等價的 \mathbf{x}^TB\mathbf{x}，其中 B 是一個實對稱矩陣。利用一點運算技巧改寫矩陣乘法公式可得

\begin{aligned}\displaystyle \mathbf{x}^TA\mathbf{x}&=\sum_{i=1}^n\sum_{j=1}^na_{ij}x_ix_j\\ &=\sum_{i=1}^n\sum_{j=1}^n\frac{1}{2}(a_{ij}+a_{ji})x_ix_j\\ &=\mathbf{x}^T\left[\frac{1}{2}(A+A^T)\right]\mathbf{x}.\end{aligned}

矩陣 A 與 B=\frac{1}{2}(A+A^T) 有相等的二次型，不難驗證 \frac{1}{2}(A+A^T) 是對稱的。例如，

\begin{bmatrix} x&y \end{bmatrix}\begin{bmatrix} 5&4\\ 2&7 \end{bmatrix}\begin{bmatrix} x\\ y \end{bmatrix}=5x^2+6xy+7y^2=\begin{bmatrix} x&y \end{bmatrix}\begin{bmatrix} 5&3\\ 3&7 \end{bmatrix}\begin{bmatrix} x\\ y \end{bmatrix}。

 
正定矩陣的概念建立於二次型之上。若 A 是一個實對稱矩陣且任一 \mathbf{x}\neq\mathbf{0} 滿足 \mathbf{x}^TA\mathbf{x}>0，我們稱 A 是正定的，詳見“特殊矩陣 (6)：正定矩陣”。因此僅討論具對稱性的二次型已足夠應付一般的問題，這與我們習慣將對稱性納入正定的定義其道理是相同的。

 
特徵值與特徵向量是線性代數裡分析矩陣結構與線性變換最重要的概念，二次型的最大化 (或最小化) 問題是特徵值和特徵向量的一個典型應用。設 A 是實對稱矩陣，考慮此問題：

最大化 \mathbf{x}^TA\mathbf{x}，\mathbf{x} 滿足 \Vert\mathbf{x}\Vert^2=\mathbf{x}^T\mathbf{x}=1。

求解這個約束最佳化 (constrained optimization) 問題的傳統方法是引入 Lagrangian 函數 (見“Lagrange 乘數法”)：

L(\mathbf{x},\lambda)\equiv\mathbf{x}^TA\mathbf{x}-\lambda(\mathbf{x}^T\mathbf{x}-1)。

產生極值的必要條件是 L 對 \mathbf{x} 的各元的一次偏導數都等於零，亦即 \mathbf{x} 是 L 的一個駐點 (參見“最佳化理論與正定矩陣”)。因為 A^T=A，請讀者自行計算驗證

\mathbf{0}=\nabla_{\mathbf{x}}L=2(A\mathbf{x}-\lambda\mathbf{x})。

單位向量 (unit vector) \mathbf{x} 要使\mathbf{x}^TA\mathbf{x} 最大化的必要條件即為特徵方程式 A\mathbf{x}=\lambda\mathbf{x}，將此式代入二次型可得

\mathbf{x}^TA\mathbf{x}=\mathbf{x}^T(\lambda\mathbf{x})=\lambda\Vert\mathbf{x}\Vert^2=\lambda。

實對稱矩陣的特徵值必為實數，因此使二次型最大化的向量 \mathbf{x} 正是對應最大特徵值的特徵向量。

 
另一方面，我們也可以直接利用實對稱矩陣是正交可對角化此性質來分解二次型。設 A=Q\Lambda Q^{T}，其中 Q 是正交特徵向量矩陣，Q^T=Q^{-1}，\Lambda=\mbox{diag}(\lambda_1,\ldots,\lambda_n) 是主對角特徵值矩陣。令 \mathbf{y}=Q^{T}\mathbf{x}，二次型可用主對角分解化簡為

\mathbf{x}^TA\mathbf{x}=\mathbf{x}^TQ\lambda Q^{T}\mathbf{x}=\mathbf{y}^T\Lambda\mathbf{y}=\lambda_1y_1^2+\lambda_2y_2^2+\cdots+\lambda_ny_n^2。

因為 Q 是正交矩陣，\Vert\mathbf{y}\Vert=\Vert Q^T\mathbf{x}\Vert=\Vert\mathbf{x}\Vert=1 (見“特殊矩陣 (3)：么正矩陣（酉矩陣）”)，故可推論 \mathbf{y}^T\Lambda\mathbf{y} 的最大值即為 A 的最大特徵值。

 
統計學中的主成分分析 (principal components analysis)，簡稱 PCA，是二次型最大化的典型應用。設 \mathbf{y} 是由 n 個隨機變數組成的向量，

\mathbf{y}=\begin{bmatrix} Y_1\\ Y_2\\ \vdots\\ Y_n \end{bmatrix}。

我們沿用機率學的慣用符號，以大寫英文字母表示隨機變數，請特別注意各符號的意義勿與矩陣混淆。共變異數矩陣 (covariance matrix) \Sigma 的第 (i,j) 元定義為隨機變數 Y_i 和 Y_j 的共變異數或稱協方差：

\Sigma_{ij}=\mathrm{cov}(Y_i,Y_j)=E\left[(Y_i-\mu_i)(Y_j-\mu_j)\right]，

其中 \mu_i=E[Y_i] 為 Y_i 的期望值。因此 \Sigma_{ij}=\Sigma_{ji}，共變異數矩陣是對稱的，可表示為

\Sigma={E}\left[(\mathbf{y}-{E}(\mathbf{y}))(\mathbf{y}-{E}(\mathbf{y}))^T\right]。

假設每個隨機變數的期望值為零，{E}(Y_i)=0，共變異數矩陣可化簡為

\Sigma={E}[\mathbf{y}\mathbf{y}^T]。

 
主成分分析的目的在尋找單位向量 \mathbf{x} 使隨機變數向量 \mathbf{y} 於 \mathbf{x} 方向的投影具有最大變異量。因為 \mathbf{y} 的期望值為零，\mathbf{x} 為常數向量可以提至期望值運算符號之外，就有

{E}[\mathbf{x}^T\mathbf{y}]=\mathbf{x}^T{E}[\mathbf{y}]=\mathbf{x}^T\mathbf{0}=0，

所以

\mathrm{var}\{\mathbf{x}^T\mathbf{y}\}={E}\left[(\mathbf{x}^T\mathbf{y})^2\right]。

上式指出對於任意非零向量 \mathbf{x}，\mathrm{var}\{\mathbf{x}^T\mathbf{y}\}\ge 0。展開等號右側，

\mathrm{var}\{\mathbf{x}^T\mathbf{y}\}={E}[(\mathbf{x}^T\mathbf{y})(\mathbf{y}^T\mathbf{x})]=\mathbf{x}^T{E}[\mathbf{y}\mathbf{y}^T]\mathbf{x}=\mathbf{x}^T\Sigma\mathbf{x}\ge 0。

推知共變量矩陣 \Sigma 是半正定，故其特徵值皆不為負，對應 \Sigma 最大特徵值的特徵向量指向最大投影變異的方向，見下圖。

Quadratic form

主成分分析

繼續閱讀：
This entry was posted in 線性代數專欄, 二次型 and tagged , , , , , , , . Bookmark the permalink.

12 Responses to 二次型與正定矩陣

  1. levinc417 says:
    01/22/2012 at 4:43 pm

    中間有段亂碼唷~

    Reply
  2. levinc417 says:
    01/22/2012 at 4:51 pm

    也不是亂碼啦，轉換沒成功的樣子~~
    對了老師~舊討論區還沒重建好嘛？ 想找幾個以前大家討論過的舊文看，都看不到了 >”<

    Reply
  3. ccjou says:
    01/22/2012 at 9:38 pm

    謝謝，確實是轉換出錯。

    年後管理員會另尋其他空間恢復討論區。

    Reply
  4. 張盛東 says:
    02/20/2014 at 1:34 pm

    老師，請教一個問題。
    已知A,B,C為半正定（semi positive definite）矩陣，證明: 對任意x，如果二次型x^T(A*B*C)x = 0, 則A*B*C=0.
    這題我想很久都找不到思緒，希望老師指點一下。

    Reply
    • ccjou says:
      02/20/2014 at 2:12 pm

      A,B,C為半正定隱含Hermitian，是吧？
      x,A,B,C都是複矩陣？而問題是x^T(A*B*C)x，並非x*(A*B*C)x？

      (補充)
      喔，我會錯意了，*是乘法運算，不是conjugate transpose？問題是
      實對稱矩陣A,B,C>=0 & x^T(ABC)x=0 ===> ABC=0

      Reply
    • ccjou says:
      02/23/2014 at 10:04 pm

      如果A,B,C之中任一矩陣為正定，我找到二種方法可證明ABC=0。但仍無法證明A,B,C皆不可逆(全部都是半正定而非正定)的情況。你確定這個命題是正確的？

      Reply
  5. Yufeng Lyu (@LyuYufeng) says:
    06/30/2016 at 10:28 pm

    周老师，\bf{x}^T[\dfrac{1}{2}(A+A^T)]\bf{x}^T这个公式第二个转置符号是不是错了？

    Reply

Leave a comment