實對稱矩陣特徵值變化界定的典型問題

本文的閱讀等級:中級

線性代數所處理的最佳化問題可概分為二大類:一是線性方程 A\mathbf{x}=\mathbf{b} 的最小平方近似解問題,即求出 \hat{\mathbf{x}} 使得誤差平方 \Vert \mathbf{b}-A\hat{\mathbf{x}}\Vert^2 具有最小值。內積空間理論導出最佳解須滿足正規方程式 (normal equation) A^TA\hat{\mathbf{x}}=A^T\mathbf{b} (見“ 從線性變換解釋最小平方近似”)。二是特徵分析推衍的二次型約束最佳化問題,即求單位向量 (unit vector) \mathbf{x} 使得 \mathbf{x}^TA\mathbf{x} 有最大值,其中 A 是實對稱矩陣。二次型 \mathbf{x}^TA\mathbf{x} 的極值產生條件是特徵方程式 A\mathbf{x}=\lambda\mathbf{x},極值大小則由 A 的特徵值決定 (見“二次型與正定矩陣”)。因為這個緣故,二次型約束最佳化也稱為實對稱矩陣的特徵值變化界定,下面我們討論兩個典型問題並說明完整的解法。

 
問題一 (取自 2012年台大資訊所碩士班入學試題):令 x_1,\ldots,x_n 為實數,且 x_1^2+\cdots+x_n^2=1,求 f(x_1,\ldots,x_n)=x_1x_2+x_2x_3+\cdots+x_{n-1}x_n 的最大值。


觀察發現目標函數 f 由交互乘積 x_ix_{i+1} 加總而成,這暗示 f 可寫成二次型形式,如下:

f(x_1,x_2,\ldots,x_n)=\begin{bmatrix}  x_1&x_2&\cdots&x_n  \end{bmatrix}\begin{bmatrix}  0&\frac{1}{2}&&&\\  \frac{1}{2}&0&\frac{1}{2}&&\\  &\ddots&\ddots&\ddots&\\  &&\frac{1}{2}&0&\frac{1}{2}\\  &&&\frac{1}{2}&0  \end{bmatrix}\begin{bmatrix}  x_1\\  x_2\\  \vdots\\  x_n  \end{bmatrix}=\mathbf{x}^TA\mathbf{x}

其中 \mathbf{x}=(x_1,\ldots,x_n)^TA=[a_{ij}] 為一 n\times n 階矩陣:a_{ij}=1/2\vert i-j\vert=1,否則 a_{ij}=0。因此,問題可簡明地表示為

\displaystyle\max_{\Vert\mathbf{x}\Vert=1}f(\mathbf{x})=\max_{\Vert\mathbf{x}\Vert=1}\mathbf{x}^TA\mathbf{x}

 
此例 A 是實對稱矩陣,也是三對角矩陣;前者說明 A 的特徵值 \lambda_1,\ldots,\lambda_n 皆為實數,後者指引特徵值的計算方法。Rayleigh 定理給出下面結果:

\displaystyle  \max_{\Vert\mathbf{x}\Vert=1}\mathbf{x}^TA\mathbf{x}=\max_{j=1,\ldots,n}\lambda_j=\lambda_{\max}

我們使用 Lagrange 乘數法來證明 (另一個證法使用正交對角化,見“Hermitian 矩陣的特徵值變化界定”)。令 Lagrangian 函數為 (見“Lagrange 乘數法”)

L(\mathbf{x},\lambda)=\mathbf{x}^TA\mathbf{x}+\lambda(1-\mathbf{x}^T\mathbf{x})

其中 \lambda 稱為 Lagrange 乘數。求 L 的偏導數並設為零,即得解的必要條件:

\displaystyle\begin{aligned}  \frac{\partial L}{\partial \mathbf{x}}&=2(A\mathbf{x}-\lambda\mathbf{x})=\mathbf{0}\\  \frac{\partial L}{\partial \lambda}&=1-\mathbf{x}^T\mathbf{x}=0.\end{aligned}

故知極值發生於 A\mathbf{x}=\lambda\mathbf{x}\Vert\mathbf{x}\Vert^2=1。將這兩個式子代入 f,就有

f(\mathbf{x})=\mathbf{x}^T(A\mathbf{x})=\mathbf{x}^T(\lambda\mathbf{x})=\lambda\Vert\mathbf{x}\Vert^2=\lambda

所以,f 的極大值就是 A 的最大特徵值 \lambda_{\max}

 
接下來計算三對角矩陣 A 的特徵值。考慮 n\times n 階三對角矩陣

B=\begin{bmatrix}  b&a&&&\\  c&b&a&&\\  &\ddots&\ddots&\ddots&\\  &&c&b&a\\  &&&c&b  \end{bmatrix}

其中 a\neq 0B 的特徵值為 (見“每週問題 February 15, 2010”)

\displaystyle  \mu_j=b+2a\sqrt{\frac{c}{a}}\cos\left(\frac{j\pi}{n+1}\right),~~j=1,2,\ldots,n

代入 a=c=1/2b=0,即得 A 的特徵值

\displaystyle  \lambda_j=\cos\left(\frac{j\pi}{n+1}\right),~~j=1,\ldots,n

明顯地,\lambda_1>\lambda_2>\cdots>\lambda_n,故目標函數 f 有最大值 \lambda_{\max}=\cos(\pi/(n+1))

 
問題二:令 x_1,\ldots,x_n 為實數,已知 x_1+\cdots+x_n=0x_1^2+\cdots+x_n^2=1,求 f(x_1,\ldots,x_n)=x_1x_2+x_2x_3+\cdots+x_{n-1}x_n+x_nx_1 的最大值。

 
如問題一解法,將目標函數 f 改寫成二次型矩陣表達式:

f(x_1,x_2,\ldots,x_n)=\begin{bmatrix}  x_1&x_2&\cdots&x_n  \end{bmatrix}\begin{bmatrix}  0&\frac{1}{2}&&&\frac{1}{2}\\  \frac{1}{2}&0&\frac{1}{2}&&\\  &\ddots&\ddots&\ddots&\\  &&\frac{1}{2}&0&\frac{1}{2}\\  \frac{1}{2}&&&\frac{1}{2}&0  \end{bmatrix}\begin{bmatrix}  x_1\\  x_2\\  \vdots\\  x_n  \end{bmatrix}=\mathbf{x}^TA\mathbf{x}

其中 \mathbf{x}=(x_1,x_2,\ldots,x_n)^TA 與問題一的差異在於 a_{1n}=a_{n1}=1/2。令 \mathbf{e}=(1,\ldots,1)^T,則 \mathbf{x}^T\mathbf{e}=x_1+\cdots+x_n=0,也就是說 \mathbf{x}\perp\mathbf{e},故原問題可表示為

\displaystyle\max_{\Vert\mathbf{x}\Vert=1\atop\mathbf{x}\perp\mathbf{e}}f(\mathbf{x})=\max_{\Vert\mathbf{x}\Vert=1\atop\mathbf{x}\perp\mathbf{e}}\mathbf{x}^TA\mathbf{x}

 
我們的任務限定在子空間 \mathrm{span}\{\mathbf{e}\}^{\perp}=\{\mathbf{x}\in\mathbb{R}^n\vert\mathbf{x}\perp\mathbf{e}\} 中尋找一單位向量 \mathbf{x} 使得 f 有最大值。這裡常數向量 \mathbf{e} 有甚麼特殊涵義呢?計算發現 A\mathbf{e}=\mathbf{e},即 \mathbf{e} 是對應特徵值 1 的特徵向量。此例 A 同時是實對稱矩陣、馬可夫矩陣 (Markov matrix) 和循環矩陣 (circulant matrix)。實對稱矩陣的特徵值都是實數,而馬可夫矩陣的最大特徵值是 1,相重數為 1,故令 \lambda_1=1 (見“馬可夫過程”)。另外,實對稱矩陣的特徵向量構成 \mathbb{R}^n 的一組單範正交基底 (orthonormal basis) (見“實對稱矩陣可正交對角化的證明”),即知 \mathrm{span}\{\mathbf{e}\}^{\perp}=\mathrm{span}\{\mathbf{u}_2,\ldots,\mathbf{u}_n\},其中 \mathbf{u}_i (i=2,\ldots,n) 代表對應特徵值 \lambda_i 的單範正交特徵向量。因此推論

\displaystyle  \max_{\Vert\mathbf{x}\Vert=1\atop\mathbf{x}\perp\mathbf{e}}\mathbf{x}^TA\mathbf{x}=\max_{\Vert\mathbf{x}\Vert=1\atop\mathbf{x}\in\mathrm{span}\{\mathbf{u}_2,\ldots,\mathbf{u}_n\}}\mathbf{x}^TA\mathbf{x}=\max_{j=2,\ldots,n}\lambda_j

矩陣 A 的第二大特徵值即為所求。

 
考慮 n\times n 階循環矩陣

C=\begin{bmatrix}    c_0&c_1&c_2&\cdots&c_{n-1}\\    c_{n-1}&c_0&c_1&\cdots&c_{n-2}\\    c_{n-2}&c_{n-1}&c_0&\cdots&c_{n-3}\\    \vdots&\vdots&\ddots&\ddots&\vdots\\    c_1&c_2&\cdots&c_{n-1}&c_0    \end{bmatrix}

其特徵值為 (見“特殊矩陣 (7):循環矩陣”)

\displaystyle  \mu_j=\sum_{k=0}^{n-1}c_ke^{-2\pi i(j-1)k/n},~~j=1,\ldots,n

上式中 i=\sqrt{-1}。代入 c_1=c_{n-1}=1/2c_0=c_2=\cdots=c_{n-2}=0,就得到 A 的特徵值:

\displaystyle\begin{aligned}  \lambda_j&=\frac{1}{2}\left(e^{-2\pi i(j-1)/n}+e^{-2\pi i(j-1)(n-1)/n}\right)\\  &=\frac{1}{2}\left(e^{-2\pi i(j-1)/n}+e^{2\pi i(j-1)/n}\right)\\  &=\cos\left(\frac{2\pi(j-1)}{n}\right),~~~j=1,\ldots,n.\end{aligned}

不難確認 \lambda_1=1,第二大特徵值是 \lambda_2=\lambda_n=\cos(2\pi/n),此即答案。

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

發表迴響

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

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s