特殊矩陣 (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}=\left[\!\!\begin{array}{rrrr} 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{array}\!\!\right]$

行列式

三對角矩陣的行列式計算相當簡單，用歸納法可導出公式。考慮 $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}$

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

$\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\det A_2-b_2c_2\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$ 的領先主子陣 (leading principal submatrix，詳見“正定矩陣的性質與判別方法”)。對於 $n\times n$ 階三對角矩陣 $A=[a_{ij}]$ ，令 $a_{i}=a_{ii}$ ， $b_{i}=a_{i,i+1}$ ， $c_{i}=a_{i+1,i}$ ，不難歸納出下面的行列式遞迴算式：

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

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

$\begin{aligned} \det A_1&=1\\ \det A_2&=-4\\ \det A_3&=1\cdot\det A_2-3\cdot 2\cdot\det A_1=-10\\ \det A_4&=2\cdot\det A_3-1\cdot 3\cdot\det A_2=-8\end{aligned}$

類似的問題與解答請見“每週問題 December 13, 2010”，“每週問題 April 16, 2012”。

相似變換

有時候我們可以藉由一矩陣相似於對稱矩陣，從而證明該矩陣的特徵值全為實數，這是因為二相似矩陣有相同的特徵值集合且對稱矩陣必有實特徵值 (見“特殊矩陣 (9)：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}$

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

$\displaystyle \frac{b_1d_2}{d_1}=\frac{c_1d_1}{d_2},~\frac{b_2d_3}{d_2}=\frac{c_2d_2}{d_3}$

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

$\displaystyle \frac{b_id_{i+1}}{d_i}=\displaystyle{c_id_i}{d_{i+1}}$

交叉相乘後，整理成

$\displaystyle d_{i+1}^2=\left(\frac{c_i}{b_i}\right)d_i^2$

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

$d_{i+1}=\displaystyle\sqrt{\frac{c_i}{b_i}}\cdot 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$ ，令

$\displaystyle b_1^{\prime}=\frac{b_1}{a_1},~~d_1^{\prime}=\frac{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)$ 。令

$\displaystyle b'_2=\frac{b_2}{a_2-b'_1c_1},~~ d'_2=\frac{d_2-d_1^{\prime}c_1}{a_2-b'_1c_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}$

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

$\displaystyle d_3^{\prime}=\frac{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}$

再以反向迭代，得出解為

$\begin{aligned} 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\end{aligned}$

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

4 Responses to 特殊矩陣 (11)：三對角矩陣

Anonymous says:

10/30/2010 at 12:48 am

請問關於三對角矩陣的特徵值有無相關文章或公式？

ccjou says:

10/30/2010 at 7:59 am

三對角矩陣的特徵值沒有代數公式解，特殊形式矩陣的特徵方程可化為二階差分方程，由此可解出特徵值，請見例子
https://ccjou.wordpress.com/2010/02/10/%E6%AF%8F%E9%80%B1%E5%95%8F%E9%A1%8C-february-15-2010/

QR 演算法是一個相當有效的三對角矩陣特徵值數值計算法，請見
Numerical Recipes in FORTRAN 77: The Art of Scientific Computing

Click to access f11-3.pdf

CCH says:

11/06/2013 at 9:32 pm

內容文字第9行的–A3的”主子陣”==>應該是”領先主子陣”?

- ccjou says:
  
  11/06/2013 at 9:55 pm
  
  太對了，已更正。感謝。

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨