如果一 $$n\times n$$ 階矩陣 $$A=[a_{ij}]$$ 每一列其主對角元的絕對值大於該列非主對角元絕對值之和，也就是說，對於 $$i=1,2,\ldots,n$$，滿足
$$\vert a_{ii}\vert>\sum_{j\neq i}\vert a_{ij}\vert$$
我們稱 $$A$$ 為對角佔優（diagonally dominant）。例如，
$$B=\begin{bmatrix}
-4&-2&1\\
1&2&0\\
3&1&5
\end{bmatrix}$$
是對角佔優矩陣因為
$$\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$$
$$C=\begin{bmatrix}
-2&-2&1\\
1&1&0\\
3&1&5
\end{bmatrix}$$
不為對角佔優矩陣，計算檢查得知
$$\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$$
對角佔優矩陣常出現於實際應用中，它有什麼特性？對角佔優矩陣是可逆矩陣，亦即 $$A$$ 的零空間僅包含零向量，$$\mathcal{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\vert$$，$$j\neq k$$。乘開 $$A\mathbf{x}=\mathbf{0}$$ 並取其第 $$k$$ 元，就有
$$a_{k1}x_1+a_{k2}x_2+\cdots+a_{kn}x_n=0$$
將第 $$k$$ 項抽離出來，
$$a_{kk}x_k=-\sum_{j\neq k}a_{kj}x_j$$
等號左右取絕對值，再利用三角不等式可得
$$\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$$
上面最後一個步驟使用已知條件 $$\vert x_k\vert\ge\vert x_j\vert$$，$$j\neq k$$。消除 $$\vert x_k\vert$$ 後便有
$$\vert a_{kk}\vert\le\sum_{j\neq k}\vert a_{kj}\vert$$
這個結果違反了對角佔優條件，推論最初假設存在非零向量 $$\mathbf{x}$$ 滿足 $$A\mathbf{x}=\mathbf{0}$$ 是錯的，證得 $$A$$ 是可逆矩陣。
對角佔優的另一個實用價值在於解線性方程。當 $$A^T$$ 為對角佔優矩陣時，以高斯消去法解 $$A\mathbf{x}=\mathbf{b}$$ 的過程不需要執行部分軸元法（partial pivoting）。不過這個證明相當瑣碎，在此省略，以下僅討論部分軸元法的意義與其功能。看下面這個線性方程組：
$$0x+y=1$$
$$x+y=2$$
其解為 $$x=y=1$$。如果將方程組改為
$$10^{-4}x+y=1$$
$$x+y=2$$
明顯地，$$x$$ 和 $$y$$ 都應該近似 $$1$$，精確的解為
$$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&\vert&1\\
1&1&\vert&2
\end{bmatrix}\sim\begin{bmatrix}
0.0001&1&\vert&1\\
0&-9999&\vert&-9998
\end{bmatrix}$$
但精確度至三位元浮點數的儲存內容為
$$\begin{bmatrix}
0.1\times 10^{-3}&1&\vert&1\\
0&-(0.1)\times 10^{5}&\vert&-(0.1)\times 10^{5}
\end{bmatrix}$$
再使用反向迭代法，由第二式解出 $$y=1$$，代回第一式解出 $$x=0$$，計算結果錯的離譜！
捨去誤差造成災難的原因出在軸元的數值太小，最簡單的解決方法是將方程組的兩列對調，然後再執行消去法，如下：
$$\begin{bmatrix}
1&1&\vert&2\\
0.0001&1&\vert&1
\end{bmatrix}\sim\begin{bmatrix}
1&1&\vert&2\\
0&0.9999&\vert&0.9998
\end{bmatrix}$$
這時第二式以 $$0x+(0.1)\times 10^{-4}y=(0.1)\times 10^{-4}$$ 形式儲存，解出 $$y=1$$，代回第一式得到 $$x=1$$，比較此結果與實際的 $$x$$ 解 $$1.\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$$ 為對角佔優矩陣，每次消去步驟遇到的軸元都比下面各個元的絕對值大，因此不需要執行部分軸元法。
沒有留言:
張貼留言