特殊矩陣 (12):對角佔優矩陣

本文的閱讀等級:初級

如果一 n\times n 階矩陣 A=[a_{ij}] 每一列 (row) 的主對角元的絕對值大於該列非主對角元絕對值之和,也就是說,對於 i=1,2,\ldots,n

\displaystyle  \vert a_{ii}\vert>\sum_{j\neq i}\vert a_{ij}\vert

我們稱 A 為嚴格對角佔優 (strictly diagonally dominant)。若每一 i 滿足 \vert a_{ii}\vert\ge\sum_{j\neq i}\vert a_{ij}\vert,則稱為非嚴格對角佔優。例如,

B=\left[\!\!\begin{array}{rrc}    -4&-2&1\\    1&2&0\\    3&1&5    \end{array}\!\!\right]

是嚴格對角佔優矩陣因為

\begin{aligned}  \vert b_{11}\vert&=4>\vert b_{12}\vert+\vert b_{13}\vert=2+1=3\\    \vert b_{22}\vert&=2>\vert b_{21}\vert+\vert b_{23}\vert=1+0=1\\    \vert b_{33}\vert&=5>\vert b_{31}\vert+\vert b_{32}\vert=3+1=4.\end{aligned}


但是

C=\left[\!\!\begin{array}{rrc}    -2&-2&1\\    1&1&0\\    3&1&5    \end{array}\!\!\right]

不是對角佔優矩陣,計算檢查得知

\begin{aligned}  \vert b_{11}\vert&=2<\vert b_{12}\vert+\vert b_{13}\vert=2+1=3\\    \vert b_{22}\vert&=1\ge\vert b_{21}\vert+\vert b_{23}\vert=1+0=1\\  \vert b_{33}\vert&=5>\vert b_{31}\vert+\vert b_{32}\vert=3+1=4.\end{aligned}

 
對角佔優矩陣常出現於實際應用中,它具有什麼性質?嚴格對角佔優矩陣是可逆矩陣,亦即 A 的零空間 (nullspace) 僅包含零向量,即 {N}(A)=\{\mathbf{0}\}。使用逆否命題法。假設有 \mathbf{x}\neq\mathbf{0} 使得 A\mathbf{x}=\mathbf{0}。設 x_k 為向量 \mathbf{x} 的最大元,\vert x_k\vert\ge\vert x_j\vertj\neq k。乘開 A\mathbf{x}=\mathbf{0} 並取其第 k 元,就有

a_{k1}x_1+a_{k2}x_2+\cdots+a_{kn}x_n=0

將第 k 項抽離出來,

\displaystyle  a_{kk}x_k=-\sum_{j\neq k}a_{kj}x_j

等號左右取絕對值,再利用三角不等式可得

\begin{aligned}\displaystyle  \vert a_{kk}\vert\cdot\vert x_k\vert&=\left|\sum_{j\neq k}a_{kj}x_j\right|\le\sum_{j\neq k}\vert a_{kj}x_j\vert\\  &=\sum_{j\neq k}\vert a_{kj}\vert\cdot\vert x_j\vert\\    &\le\left(\sum_{j\neq k}\vert a_{kj}\vert\right)\vert x_k\vert.\end{aligned}

上面最後一個步驟使用已知條件 \vert x_k\vert\ge\vert x_j\vertj\neq k。消除 \vert x_k\vert 後即得

\displaystyle  \vert a_{kk}\vert\le\sum_{j\neq k}\vert a_{kj}\vert

我們得到與嚴格對角佔優矩陣互斥的結果,故得證。附帶一提,非嚴格對角佔優矩陣未必是可逆矩陣,譬如零矩陣。

 
嚴格對角佔優的另一個實用價值在於解線性方程。當 A^T 為嚴格對角佔優矩陣時,以高斯消去法解 A\mathbf{x}=\mathbf{b} 的過程不需要執行部分軸元法 (partial pivoting)。不過這個證明相當瑣碎,在此省略,以下僅討論部分軸元法的意義與其功能。看下面這個線性方程組:

\begin{aligned}  0x+y&=1\\  x+y&=2,\end{aligned}

其解為 x=y=1。如果將方程組改為

\begin{aligned}  10^{-4}x+y&=1\\    x+y&=2,\end{aligned}

明顯地,xy 都應該近似 1,精確的解為

\displaystyle  x=\frac{1}{1-0.0001},~y=2-\frac{1}{1-0.0001}

 
考慮使用電腦程式求解大尺寸線性方程所遭遇的問題;由於電腦程式採用浮點算術,所以無法避免捨入誤差 (round-off error)。舉例來說,假設浮點數僅允許儲存三個位元,如 \pm .d_{1}d_{2}d_{3}\times 10^{e}。對上例的增廣矩陣執行消去法得到梯型矩陣:

\begin{bmatrix}    0.0001&1&\vline&1\\    1&1&\vline&2    \end{bmatrix}\sim\begin{bmatrix}    0.0001&1&\vline&1\\    0&-9999&\vline&-9998    \end{bmatrix}

但精確度至三位元浮點數的儲存內容為

\begin{bmatrix}    0.1\times 10^{-3}&1&\vline&1\\    0&-(0.1)\times 10^{5}&\vline&-(0.1)\times 10^{5}    \end{bmatrix}

使用反向迭代法,由第二式解出 y=1,代回第一式解出 x=0,計算結果錯的離譜。

 
捨入誤差造成災難的原因出在軸元的數值太小,最簡單的解決方法是將方程組的兩列對調,然後再執行消去法,如下:

\begin{bmatrix}    1&1&\vline&2\\    0.0001&1&\vline&1    \end{bmatrix}\sim\begin{bmatrix}    1&1&\vline&2\\    0&0.9999&\vline&0.9998    \end{bmatrix}

這時第二式以 0x+(0.1)\times 10^{-4}y=(0.1)\times 10^{-4} 形式儲存,解出 y=1,代回第一式得到 x=1,比較此結果與實際的 x1.\overline{0001},計算誤差為 0.\overline{0001}

 
部分軸元法是指在每一次消去法進行之前,我們先搜尋軸元所在位置及其底下的各個元,從其中挑選出絕對值最大的元,然後交換兩列將絕對值最大的元置於軸元位置,見下例:

\begin{bmatrix}    \ast&\ast&\ast&\ast&\ast\\    0&3&\bullet&\bullet&\bullet\\    0&1&\blacktriangle&\blacktriangle&\blacktriangle \\    0&5&\star&\star&\star    \end{bmatrix}\sim\begin{bmatrix}    \ast&\ast&\ast&\ast&\ast\\    0&5&\star&\star&\star\\    0&1&\blacktriangle &\blacktriangle &\blacktriangle \\    0&3&\bullet&\bullet&\bullet    \end{bmatrix}

A^T 為嚴格對角佔優矩陣,每次消去步驟遇到的軸元都比下面各個元的絕對值大,因此不需要執行部分軸元法。

 
A 是一 Hermitian 非嚴格對角佔優矩陣且所有主對角元皆非負數,則 A 是半正定矩陣。利用 Gershgorin 圓定理可判定對角佔優矩陣的特徵值,詳細介紹請見“估計特徵值範圍的 Gershgorin 圓”。

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

4 則回應給 特殊矩陣 (12):對角佔優矩陣

  1. 小中 說道:

    第一行 “如果一………滿足" 的那個條件是怎麼來的??

    • ccjou 說道:

      你是說誰先指出這個條件?十九世紀以來,數學家們希望找出一些可判定非零行列式(即可逆矩陣)的條件。根據維基百科,對角佔優矩陣已有超過100年歷史,並且被許多數學家重新發現。請見下文圖一:
      http://www.math.wisc.edu/~hans/paper_archive/other_papers/hs057.pdf
      至於數學家是如何找到這個條件?很抱歉,我也不知道。多數的數學家向來不願意與世人分享他們發現某個定理或性質的過程。

  2. Lin 說道:

    很好奇非严格的对角占优矩阵有怎样的性质呢?

    • ccjou 說道:

      如果是指可逆,當A僅有一列(row) k 滿足 \vert a_{kk}\vert=\sum_{j\neq k}\vert a_{kj}\vert,其餘所有列 i\neq k 滿足嚴格對角佔優條件,則A是可逆矩陣。

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s