利用 LU 分解推導 Lehmer 矩陣的逆矩陣

本文的閱讀等級:初級

Lehmer 矩陣為一 n\times n 階對稱矩陣 A=[a_{ij}],其中

\displaystyle  a_{ij}=\frac{\min\{i,j\}}{\max\{i,j\}}=\left\{\begin{array}{ll}  j/i,&i\ge j\\  i/j,&j>i.  \end{array}\right.

Lehmer 矩陣是一種測試矩陣,通常用來評估逆矩陣算法的精確度。逆 Lehmer 矩陣為三對角矩陣 (見“特殊矩陣 (11):三對角矩陣”),並具有一種奇特的性質。令 A_n 表示 n\times n 階 Lehmer 矩陣。對於 m<n,除了 A_m^{-1}(m,m) 元,A_m^{-1} 恰為 A_n^{-1}m\times m 階領先主子陣 (即左上 m\times m 階分塊)。下面列舉 n=2,3,4 的 Lehmer 矩陣及其逆矩陣:

\displaystyle\begin{aligned}  \begin{bmatrix}  1&\frac{1}{2}\\[0.3em]  \frac{1}{2}&1\end{bmatrix}^{-1}&=\left[\!\!\begin{array}{rr}  \frac{4}{3}&-\frac{2}{3}\\[0.3em]  -\frac{2}{3}&\frac{\mathbf{4}}{\mathbf{3}}  \end{array}\!\!\right]\\  \begin{bmatrix}  1&\frac{1}{2}&\frac{1}{3}\\[0.3em]  \frac{1}{2}&1&\frac{2}{3}\\[0.3em]  \frac{1}{3}&\frac{2}{3}&1  \end{bmatrix}^{-1}&=\left[\!\!\begin{array}{rrr}  \frac{4}{3}&-\frac{2}{3}&0\\[0.3em]  -\frac{2}{3}&\frac{32}{15}&-\frac{6}{5}\\[0.3em]  0&-\frac{6}{5}&\frac{\mathbf{9}}{\mathbf{5}}  \end{array}\!\!\right]\\  \begin{bmatrix}  1&\frac{1}{2}&\frac{1}{3}&\frac{1}{4}\\[0.3em]  \frac{1}{2}&1&\frac{2}{3}&\frac{2}{4}\\[0.3em]  \frac{1}{3}&\frac{2}{3}&1&\frac{3}{4}\\[0.3em]  \frac{1}{4}&\frac{2}{4}&\frac{3}{4}&1  \end{bmatrix}^{-1}  &=\left[\!\!\begin{array}{rrrr}  \frac{4}{3}&-\frac{2}{3}&0&0\\[0.3em]  -\frac{2}{3}&\frac{32}{15}&-\frac{6}{5}&0\\[0.3em]  0&-\frac{6}{5}&\frac{108}{35}&-\frac{12}{7}\\[0.3em]  0&0&-\frac{12}{7}&\frac{\mathbf{16}}{\mathbf{7}}  \end{array}\!\!\right]  \end{aligned}

透過觀察不太容易歸納出 Lehmer 矩陣的逆矩陣公式,本文用 LU 分解推導逆矩陣 (見“LU 分解”)。對稱矩陣 A 的 LU 分解可表示為 A=LDL^T,其中 L 是下三角矩陣且主對角元等於 1D 是對角矩陣。若 A 可逆,則 A^{-1}=(L^{-1})^TD^{-1}L^{-1}。不過,這個方法並非絕對有效,關鍵在於能否得到 L^{-1} 的顯式表達式。

 
n=5 為例,運用 LU 分解演算法 (見“PA=LU 分解”),可得

\displaystyle  \begin{bmatrix}  1&\frac{1}{2}&\frac{1}{3}&\frac{1}{4}&\frac{1}{5}\\[0.3em]  \frac{1}{2}&1&\frac{2}{3}&\frac{2}{4}&\frac{2}{5}\\[0.3em]  \frac{1}{3}&\frac{2}{3}&1&\frac{3}{4}&\frac{3}{5}\\[0.3em]  \frac{1}{4}&\frac{2}{4}&\frac{3}{4}&1&\frac{4}{5}\\[0.3em]  \frac{1}{5}&\frac{2}{5}&\frac{3}{5}&\frac{4}{5}&1  \end{bmatrix}=\begin{bmatrix}  1&0&0&0&0\\[0.3em]  \frac{1}{2}&1&0&0&0\\[0.3em]  \frac{1}{3}&\frac{2}{3}&1&0&0\\[0.3em]  \frac{1}{4}&\frac{2}{4}&\frac{3}{4}&1&0\\[0.3em]  \frac{1}{5}&\frac{2}{5}&\frac{3}{5}&\frac{4}{5}&1  \end{bmatrix}\begin{bmatrix}  1&0&0&0&0\\[0.3em]  0&\frac{3}{4}&0&0&0\\[0.3em]  0&0&\frac{5}{9}&0&0\\[0.3em]  0&0&0&\frac{7}{16}&0\\[0.3em]  0&0&0&0&\frac{9}{25}  \end{bmatrix}\begin{bmatrix}  1&\frac{1}{2}&\frac{1}{3}&\frac{1}{4}&\frac{1}{5}\\[0.3em]  0&1&\frac{2}{3}&\frac{2}{4}&\frac{2}{5}\\[0.3em]  0&0&1&\frac{3}{4}&\frac{3}{5}\\[0.3em]  0&0&0&1&\frac{4}{5}\\[0.3em]  0&0&0&0&1  \end{bmatrix}

從上例呈現的模式可推測 n\times n 階下三角矩陣 L=[l_{ij}],其中 l_{ij}=j/ii\ge j,其餘元為 0,以及 n\times n 階對角矩陣 D=\hbox{diag}(d_1,\ldots,d_n),其中 d_i=(2i-1)/i^21\le i\le n。下面證明 A=LDL^T 的確是 Lehmer 矩陣。套用等差級數公式 \sum_{k=1}^{i}(2k-1)=i^2,分開三種情況討論:

(1) i=j

\displaystyle\begin{aligned}  a_{ii}&=\sum_{k=1}^nl_{ik}d_kl_{ik}=\sum_{k=1}^il^2_{ik}d_{k}\\  &=\sum_{k=1}^i\left(\frac{k}{i}\right)^2\left(\frac{2k-1}{k^2}\right)=\frac{1}{i^2}\sum_{k=1}^i(2k-1)=1.\end{aligned}

(2) i>j

\displaystyle\begin{aligned}  a_{ij}&=\sum_{k=1}^nl_{ik}d_kl_{jk}=\sum_{k=1}^jl_{ik}d_{k}l_{jk}\\  &=\sum_{k=1}^j\left(\frac{k}{i}\right)\left(\frac{2k-1}{k^2}\right)\left(\frac{k}{j}\right)=\frac{1}{ij}\sum_{k=1}^j(2k-1)=\frac{j}{i}.\end{aligned}

(3) i<j:因為 LDL^T 是對稱矩陣,使用 (2),a_{ij}=a_{ji}=i/j

 
利用 A=LDL^T 計算行列式,

\displaystyle\begin{aligned}  \det A&=(\det L)(\det D)(\det L^T)=\det D\\  &=\prod_{i=1}^n\frac{2i-1}{i^2}=\frac{1\cdot 3\cdot 5\cdots(2n-1)}{(n!)^2}=\frac{(2n)!}{2^n(n!)^3},  \end{aligned}

或表示為遞迴關係式

\displaystyle  \det A_1=1,~~~\det A_n=\frac{2n-1}{n^2}(\det A_{n-1}),~~n>1

數列 \{\det A_n\}_1^\infty 的前幾項為

\displaystyle  1,~\frac{3}{4},~\frac{5}{12},~\frac{35}{192},~\frac{21}{320},\ldots

因為每一領先主子陣滿足 \det A_i>0,可知 A_n 是實對稱正定矩陣 (見“正定矩陣的性質與判別方法”),表明 A_n 是可逆矩陣。

 
接著說明 A^{-1}=(L^{-1})^TD^{-1}L^{-1} 的計算過程。當 n=5L^{-1} 如下:

\displaystyle  \begin{bmatrix}  1&0&0&0&0\\  \frac{1}{2}&1&0&0&0\\[0.3em]  \frac{1}{3}&\frac{2}{3}&1&0&0\\[0.3em]  \frac{1}{4}&\frac{2}{4}&\frac{3}{4}&1&0\\[0.3em]  \frac{1}{5}&\frac{2}{5}&\frac{3}{5}&\frac{4}{5}&1  \end{bmatrix}^{-1}=\left[\!\!\begin{array}{rrrrc}  1&0&0&0&0\\[0.3em]  -\frac{1}{2}&1&0&0&0\\[0.3em]  0&-\frac{2}{3}&1&0&0\\[0.3em]  0&0&-\frac{3}{4}&1&0\\[0.3em]  0&0&0&-\frac{4}{5}&1  \end{array}\!\!\right]

令下三角矩陣 B=[b_{ij}],其中 b_{ii}=11\le i\le nb_{i+1,i}=-i/(i+1)1\le i<n,其餘元為 0。下面證明 B=L^{-1},即 LB=I (見“三角圖案矩陣的逆矩陣”)。因為 LB 是下三角矩陣,我們只要考慮 i\ge j 即可。

(1) i=j

\displaystyle  (LB)_{ii}=\sum_{k=1}^nl_{ik}b_{ki}=\sum_{k=1}^il_{ik}b_{ki}=l_{ii}b_{ii}=1.

(2) i>j

\displaystyle\begin{aligned}  (LB)_{ij}&=\sum_{k=1}^nl_{ik}b_{kj}=\sum_{k=1}^il_{ik}b_{kj}=l_{ij}b_{jj}+l_{i,j+1}b_{j+1,j}\\  &=\frac{j}{i}\cdot 1+\frac{j+1}{i}\left(-\frac{j}{j+1}\right)=0.\end{aligned}

 
最後代入已知的 BD,可得 A^{-1}=B^TD^{-1}B 各元。分開幾種情形討論:

(1) i=j1\le i<n

\displaystyle\begin{aligned}  (A^{-1})_{ii}&=\sum_{k=1}^nb_{ki}d_k^{-1}b_{ki}=\frac{b_{ii}^2}{d_i}+\frac{b_{i+1,i}^2}{d_{i+1}}\\  &=\frac{i^2}{2i-1}+\left(-\frac{i}{i+1}\right)^2\frac{(i+1)^2}{2i+1}\\  &=\frac{i^2}{2i-1}+\frac{i^2}{2i+1}=\frac{4i^3}{4i^2-1}.  \end{aligned}

(2) i=j=n

\displaystyle  (A^{-1})_{nn}=\sum_{k=1}^nb_{kn}d_k^{-1}b_{kn}=\frac{b_{nn}^2}{d_n}=\frac{n^2}{2n-1}.

(3) i=j+1

\displaystyle\begin{aligned}  (A^{-1})_{i+1,i}&=\sum_{k=1}^nb_{k,i+1}d_k^{-1}b_{ki}=\frac{b_{i+1,i+1}b_{i+1,i}}{d_{i+1}}\\  &=\frac{(i+1)^2}{2i+1}\left(-\frac{i}{i+1}\right)=-\frac{i(i+1)}{2i+1}.  \end{aligned}

(4) j=i+1:因為 A^{-1} 是對稱矩陣,使用 (3),

\displaystyle  (A^{-1})_{i,i+1}=(A^{-1})_{i+1,i}=-\frac{i(i+1)}{2i+1}

(5) \vert i-j\vert >1:在此情形下,b_{ki}b_{kj}=01\le k\le n,故 (A^{-1})_{ij}=0

下面整理出 Lehmer 矩陣的逆矩陣公式:

(A^{-1})_{ij}=\left\{  \begin{array}{cc}  \displaystyle\frac{4i^3}{4i^2-1},&i=j<n\\[0.8em]  \displaystyle\frac{n^2}{2n-1},&i=j=n\\[0.8em]  \displaystyle-\frac{i(i+1)}{2i+1},&\vert i-j\vert=1\\[0.8em]  0,&\vert i-j\vert >1.  \end{array}\right.

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

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s