🍙

Tomasのアルゴリズム

3 min read

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} を求めます。