摘要：三對(duì)角線性方程組三對(duì)角線性方程組對(duì)于熟悉數(shù)值分析的同學(xué)來(lái)說(shuō)，并不陌生，它經(jīng)常出現(xiàn)在微分方程的數(shù)值求解和三次樣條函數(shù)的插值問(wèn)題中。

??三對(duì)角線性方程組,對(duì)于熟悉數(shù)值分析的同學(xué)來(lái)說(shuō)，并不陌生，它經(jīng)常出現(xiàn)在微分方程的數(shù)值求解和三次樣條函數(shù)的插值問(wèn)題中。三對(duì)角線性方程組可描述為以下方程組：
$$a_{i}x_{i-1}+b_{i}x_{i}+c_{i}x_{i+1}=d_{i}$$
其中$1leq i leq n, a_{1}=0, c_{n}=0.$ 以上方程組寫成矩陣形式為$Ax=d$，即：

$$ {egin{bmatrix} {b_{1}}&{c_{1}}&{}&{}&{0} {a_{2}}&{b_{2}}&{c_{2}}&{}&{} {}&{a_{3}}&{b_{3}}&ddots &{} {}&{}&ddots &ddots &{c_{n-1}} {0}&&&{a_{n}}&{b_{n}} end{bmatrix}} {egin{bmatrix}{x_{1}}{x_{2}}{x_{3}}vdots {x_{n}}end{bmatrix}}={egin{bmatrix}{d_{1}}{d_{2}}{d_{3}}vdots {d_{n}}end{bmatrix}} $$

??三對(duì)角線性方程組的求解采用追趕法或者Thomas算法，它是Gauss消去法在三對(duì)角線性方程組這種特殊情形下的應(yīng)用，因此，主要思想還是Gauss消去法，只是會(huì)更加簡(jiǎn)單些。我們將在下面的算法詳述中給出該算法的具體求解過(guò)程。
??當(dāng)然，該算法并不總是穩(wěn)定的，但當(dāng)系數(shù)矩陣$A$為嚴(yán)格對(duì)角占優(yōu)矩陣（Strictly D iagonally Dominant, SDD）或?qū)ΨQ正定矩陣（Symmetric Positive Definite, SPD）時(shí)，該算法穩(wěn)定。對(duì)于不熟悉SDD或者SPD的讀者，也不必?fù)?dān)心，我們還會(huì)在我們的博客中介紹這類矩陣。現(xiàn)在，我們只要記住，該算法對(duì)于部分系數(shù)矩陣$A$是可以求解的。

??追趕法或者Thomas算法的具體步驟如下：

1.創(chuàng)建新系數(shù)$c_{i}^{*}$和$d_{i}^{*}$來(lái)代替原先的$a_{i},b_{i},c_{i}$,公式如下：

$$ c^{*}_i = left{ egin{array}{lr} frac{c_1}{b_1} & ; i = 1 frac{c_i}{b_i - a_i c^{*}_{i-1}} & ; i = 2,3,...,n-1 end{array} ight. d^{*}_i = left{ egin{array}{lr} frac{d_1}{b_1} & ; i = 1 frac{d_i- a_i d^{*}_{i-1}}{b_i - a_i c^{*}_{i-1}} & ; i = 2,3,...,n-1 end{array} ight. $$

2.改寫原先的方程組$Ax=d$如下：

$$ egin{bmatrix} 1 & c^{*}_1 & 0 & 0 & ... & 0 0 & 1 & c^{*}_2 & 0 & ... & 0 0 & 0 & 1 & c^{*}_3 & 0 & 0 . & . & & & & . . & . & & & & . . & . & & & & c^{*}_{n-1} 0 & 0 & 0 & 0 & 0 & 1 end{bmatrix} egin{bmatrix} x_1 x_2 x_3 . . . x_k end{bmatrix} = egin{bmatrix} d^{*}_1 d^{*}_2 d^{*}_3 . . . d^{*}_n end{bmatrix} $$

3.計(jì)算解向量$x$，如下：
$$ x_n = d^{*}_n, qquad x_i = d^{*}_i - c^{*}_i x_{i+1}, qquad i = n-1, n-2, ... ,2,1$$

??以上算法得到的解向量$x$即為原方程$Ax=d$的解。
??下面，我們來(lái)證明該算法的正確性，只需要證明該算法保持原方程組的形式不變。
??首先，當(dāng)$i=1$時(shí)，
$$1*x_{1}+c_{1}^{*}x_{2}=d_{1}^{*} Leftrightarrow 1*x_{1}+frac{c_{1}}{b_{1}}x_{2}=frac{d_{1}}{b_{1}}Leftrightarrow b_{1}*x_{1}+c_{1}x_{2}=d_{1}$$
??當(dāng)$i>1$時(shí)，

$$ 1*x_{i}+c_{i}^{*}x_{i+1}=d_{i}^{*} Leftrightarrow 1*x_{i}+frac{c_{i}}{b_{i} - a_{i} c^{*}_{i-1}}x_{i+1}=frac{d_{i}- a_{i} d^{*}_{i-1}}{b_{i} - a_{i} c^{*}_{i-1}} Leftrightarrow (b_{i} - a_{i} c^{*}_{i-1})x_{i}+c_{i}x_{i+1}=d_{i}- a_{i} d^{*}_{i-1} $$

結(jié)合$a_{i}x_{i-1}+b_{i}x_{i}+c_{i}x_{i+1}=d_{i}$，只需要證明$x_{i-1}+c_{i-1}^{*}x_{i}=d_{i-1}^{*}$,而這已經(jīng)在該算法的第（3）步的中的計(jì)算$x_{i-1}$中給出。證明完畢。

??我們將要求解的線性方程組如下：

$$ {egin{bmatrix} 4&1&{0}&{0}&{0} {1}&{4}&{1}&{0}&{0} {0}&{1}&{4}&{1}&{0} {0}&{0}&{1}&{4}&{1} {0}&{0}&{0}&{1}&{4} end{bmatrix}} {egin{bmatrix}{x_{1}}{x_{2}}{x_{3}}{x_{4}} {x_{5}}end{bmatrix}}={egin{bmatrix}{1