Tomasのアルゴリズム

Tomasのアルゴリズムは以下のような形式の連立方程式を特くためのアルゴリズムです。

$$\left( \begin{array}{ccc} b_1 & c_1 & 0 & 0 & 0 & \cdots & 0 \\ a_2 & b_2 & c_2 & 0 & 0 & \cdots & 0 \\ 0 & a_3 & b_3 & c_3 & 0 & \cdots & 0 \\ 0 & 0 & a_4 & b_4 & c_4 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & a_{n-1} & b_{n-1} & c_{n-1} \\ 0 & 0 & 0 & 0 & 0 & a_n & b_n \end{array} \right) \left( \begin{array}{ccc} x_1 \\ x_2 \\ x_3 \\ x_4 \\ \vdots \\ x_{n-1} \\ x_n \end{array} \right) = \left( \begin{array}{ccc} d_1 \\ d_2 \\ d_3 \\ d_4 \\ \vdots \\ d_{n-1} \\ d_n \end{array} \right)$$

1番目の式は以下の式で表されます。

$$b_1x_1 - c_1x_2 = d_1 \tag{1}$$

式(1)を変形して式(2)を得ます。

$$x_1 + \frac{c_1}{b_1}x_2 = \frac{d_1}{b_1} \tag{2}$$

ここで $e_1,\ f_1$ を式(3),(4)とします。

$$e_1 = \frac{c_1}{b_1} \tag{3}$$

$$f_1 = \frac{d_1}{b_1} \tag{4}$$

式(2),(3),(4)から式(5)を得ます。

$$x_1 + e_1x_2 = f_1 \tag{5}$$

連立方程式の2番目の式は以下の式で(6)表されます。

$$a_2x_1 + b_2x_2 + c_2x_3 = d_2 \tag{6}$$

式(5)を式変形し

$$x_1 = f_1 - e_1x_2 \tag{7}$$

式(6)に代入します。

$$a_2(f_1 - e_1x_2) + b_2x_2 - c_2x_3 = d_2 \\ a_2f_1 - a_2e_1x_2 + b_2x_2 - c_2x_3 = d_2 \\ (b_2 - a_2e_1)x_2 + c_2x_3 = d_2 - a_2f_1 \\ x_2 + \frac{c_2}{b_2 - a_2e_1}x_3 = \frac{d_2 - a_2f_1}{b_2 - a_2e_1} \tag{8}$$

ここで $e_2,\ f_2$ は式(9),(10)として、式(11)を得ます。

$$e_2 = \frac{c_2}{b_2 - a_2e_1} \tag{9}$$

$$f_2 = \frac{d_2 - a_2f_1}{b_2 - a_2e_1} \tag{10}$$

$$x_2 + e_2x_3 - f_2 \\ x_2 = f_2 - e_2x_3 \tag{11}$$

式(11)を連立方程式の3番目の式(12)に代入して式(13)を得ます。

$$a_3x_2 + b_3x_3 + c_3x_4 = d_3 \tag{12}$$

$$a_3(f_2 - e_2x_3) + b_3x_3 + c_3x_4 = d_3 \\ a_3f_2 - a_3e_2x_3 + b_3x_3 + c_3x_4 = d_3 \\ (b_3 - a_3e_2)x_3 + c_3x_4 = d_3 - a_3f_2 \\ x_3 + \frac{c_3}{b_3 - a_3e_2} = \frac{d_3 - a_3f_2}{b_3 - a_3e_2} \tag{13}$$

ここで $e_3,\ f_3$ は式(14),(15)として、式(16)を得ます。

$$e_3 = \frac{c_3}{b_3 - a_3e_2} \tag{14}$$

$$f_3 = \frac{d_3 - a_3f_2}{b_3 - a_3e_2} \tag{15}$$

$$x_3 = f_3 - e_3x_4 \tag{16}$$

これを繰り返して、式(17),(18),(19)を得ます。

$$e_i = \frac{c_i}{b_i - a_ie_{i-1}} \tag{17}$$

$$f_i = \frac{d_i - a_if_{i-1}}{b_i - a_ie_{i-1}} \tag{18}$$

$$x_{n-1} = f_{n-1} - e_{n-1}x_n \tag{19}$$

連立方程式の最後の式は式(20)となります。

$$a_nx_n + b_nx_n = d_n \tag{20}$$

式(19),(20)から $x_n$ を求めます。

$$-a_n(f_{n-1} - e_{n-1}x_n) + b_nx_n = d_n \\ -a_nf_{n-1} - a_ne_{n-1}x_n + b_nx_n = d_n \\ x_n(b_n - a_ne_{n-1}) = d_n - a_nf_{n-1} \\ x_n = \frac{d_n - a_nf_{n-1}}{b_n - a_ne_{n-1}} \tag{21}$$

$x_n$ を求めることができたので、式(20)から $x_{n-1}$ を求め、式(19)から $x_{n-1, n-2, ... 1}$ を求めます。