特殊矩陣 (11)：三對角矩陣

本文的閱讀等級：初級

如果 $$n$$ 階方陣 $$A=[a_{ij}]$$ 除了主對角線元以及比主對角線低一列和高一列的對角線之外，其餘皆為零元，我們稱它為三對角（tridiagonal）矩陣，也就是說，當 $$\vert i-j\vert>1$$，$$a_{ij}=0$$；如下例，

$$A=\begin{bmatrix}

1&2&0&0\\

3&2&3&0\\

0&2&1&1\\

0&0&3&2

\end{bmatrix}$$

三對角矩陣常出現於數值分析問題，本文僅介紹三對角矩陣的幾個基本性質，包括行列式計算、相似變換的應用以及求解線性方程式。

 

三對角矩陣雖然外型類似主對角矩陣，但未必保有簡單的矩陣性質，舉例來說，三對角矩陣的逆矩陣並非三對角矩陣，而是具有高密度的非零元分佈型態。以上面的矩陣為例，其逆矩陣為

$$A^{-1}=\begin{bmatrix}

1.750&-0.250&-1.500&0.750\\

-0.375&0.125&0.750&-0.375\\

-1.500&0.500&1.000&-0.500\\

2.250&-0.750&-1.500&1.250

\end{bmatrix}$$

 

三對角矩陣的行列式計算相當簡單，用歸納法可導出公式。考慮 $$3\times 3$$ 階三對角矩陣：

$$A_3=\begin{bmatrix}

a_{1}&b_{1}&0\\

c_{1}&a_2&b_2\\

0&c_2&a_3

\end{bmatrix}$$

取第三列的共因子展開式，之後再繼續展開低階行列式，如下：

$$\mathrm{det}A_3=a_3\begin{vmatrix}

a_1&b_1\\

c_1&a_2

\end{vmatrix}-c_2\begin{vmatrix}

a_1&0\\

c_1&b_2

\end{vmatrix}=a_3\mathrm{det}A_2-b_2c_2\mathrm{det}A_1$$

上式中 $$1\times 1$$ 階矩陣 $$A_1=[a_{1}]$$ 和 $$2\times 2$$ 階矩陣 $$A_2=\begin{bmatrix}

a_{1}&b_{1}\\

c_{1}&a_{2}

\end{bmatrix}$$ 為 $$A_3$$ 的主子陣（詳細定義請見“正定矩陣的性質與判別方法”）。對於 $$n\times n$$ 階三對角矩陣 $$A=[a_{ij}]$$，令 $$a_{i}=a_{ii}$$，$$b_{i}=a_{i,i+1}$$，$$c_{i}=a_{i+1,i}$$，不難歸納出下面的行列式遞迴算式：

$$\mathrm{det}A_{k+1}=a_{k+1}\mathrm{det}A_{k}-b_{k}c_{k}\mathrm{det}A_{k-1}$$

其中 $$k=2,3,\ldots,n-1$$。上例中，

$$\mathrm{det}A_1=1$$

$$\mathrm{det}A_2=-4$$

$$\mathrm{det}A_3=1\cdot\mathrm{det}A_2-3\cdot 2\cdot\mathrm{det}A_1=-10$$

$$\mathrm{det}A_4=2\cdot\mathrm{det}A_3-1\cdot 3\cdot\mathrm{det}A_2=-8$$

 

有時候我們可以藉由一矩陣相似於對稱矩陣，從而證明該矩陣的特徵值全為實數，這是因為二相似矩陣有相同的特徵值集合且對稱矩陣必有實特徵值（參見“特殊矩陣 (九)：Hermitian 矩陣”）。三對角實矩陣是個典型的例子，如果三對角實矩陣有實特徵值，則必然相似於對稱矩陣。下面使用三階矩陣說明，設可逆主對角矩陣 $$D=\mathrm{diag}(d_1,d_2,d_3)$$，$$d_i\neq 0$$，考慮

$$D^{-1}A_3D=\begin{bmatrix}

1/d_1&0&0\\

0&1/d_2&0\\

0&0&1/d_3

\end{bmatrix}\begin{bmatrix}

a_1&b_1&0\\

c_1&a_2&b_2\\

0&c_2&a_3

\end{bmatrix}\begin{bmatrix}

d_1&0&0\\

0&d_2&0\\

0&0&d_3

\end{bmatrix}$$

我們試圖找尋 $$d_i$$ 使得 $$D^{-1}A_3D$$ 為對稱矩陣，將上式乘開得到

$$D^{-1}A_3D=\begin{bmatrix}

a_1&b_1d_2/d_1&0\\

c_1d_1/d_2&a_2&b_2d_3/d_2\\

0&c_2d_2/d_3&a_3

\end{bmatrix}$$

欲使上面的矩陣對稱，必定要有

$$b_1d_2/d_1=c_1d_1/d_2$$

$$b_2d_3/d_2=c_2d_2/d_3$$

此二等式的形式相同，故可推得一般式為

$$b_id_{i+1}/d_i=c_id_i/d_{i+1}$$

交叉相乘後，整理成

$$d_{i+1}^2=({c_i}/{b_i})d_i^2$$

三對角實矩陣相似於對稱矩陣的條件是所有 $$c_i/b_i>0$$。設初始值 $$d_1=1$$，以遞迴公式計算

$$d_{i+1}=\sqrt{{c_i}/{b_i}}d_i$$

如此便得到相似變換矩陣 $$D$$。

 

三對角矩陣的特殊型態也可以減少高斯消去法於求解線性方程的計算量，在數值線性代數裡我們稱它為三對角矩陣演算法（tridiagonal matrix algorithm，簡稱 TDMA）。考慮線性方程組：

$$\begin{bmatrix}

a_{1}&b_{1}&0\\

c_{1}&a_2&b_2\\

0&c_2&a_3

\end{bmatrix}\begin{bmatrix}

x_1\\x_2\\x_3

\end{bmatrix}=\begin{bmatrix}

d_1\\d_2\\d_3

\end{bmatrix}$$

首先將所有的 $$c_i$$ 消去，並使主對角元為 $$1$$。將第一列乘以 $$1/a_1$$，令

$$b_1^{\prime}=b_1/a_1$$

$$d_1^{\prime}=d_1/a_1$$

原方程式變為

$$\begin{bmatrix}

1&b_{1}^{\prime}&0\\

c_{1}&a_2&b_2\\

0&c_2&a_3

\end{bmatrix}\begin{bmatrix}

x_1\\x_2\\x_3

\end{bmatrix}=\begin{bmatrix}

d_1^{\prime}\\d_2\\d_3

\end{bmatrix}$$

再將第一列乘以 $$-c_1$$，加至第二列，之後再將第二列乘以 $$1/(a_2-b_1^{\prime}c_1)$$，令

$$b_2^{\prime}=b_2/(a_2-b_1^{\prime}c_1)$$

$$d_2^{\prime}=(d_2-d_1^{\prime}c_1)/(a_2-b_1^{\prime}c_1)$$

等價的方程式變為

$$\begin{bmatrix}

1&b_{1}^{\prime}&0\\

0&1&b_2^{\prime}\\

0&c_2&a_3

\end{bmatrix}\begin{bmatrix}

x_1\\x_2\\x_3

\end{bmatrix}=\begin{bmatrix}

d_1^{\prime}\\d_2^{\prime}\\d_3

\end{bmatrix}$$

繼續對第三列做同樣運算，令

$$d_3^{\prime}=(d_3-d_2^{\prime}c_2)/(a_3-b_2^{\prime}c_2)$$

最後得到如下形式的上三角形係數矩陣：

$$\begin{bmatrix}

1&b_{1}^{\prime}&0\\

0&1&b_2^{\prime}\\

0&0&1

\end{bmatrix}\begin{bmatrix}

x_1\\x_2\\x_3

\end{bmatrix}=\begin{bmatrix}

d_1^{\prime}\\d_2^{\prime}\\d_3^{\prime}

\end{bmatrix}$$

再以反向迭代，得出解為

$$x_3=d_3^{\prime}$$

$$x_2=d_2^{\prime}-b_2^{\prime}x_3$$

$$x_1=d_1^{\prime}-b_1^{\prime}x_2$$

對於 $$n\times n$$ 階三對角係數矩陣，高斯消去法原本需要的計算量 $$O(n^3)$$ 將可減少為 $$O(n)$$，細節就留給讀者自行驗證。