Tomasのアルゴリズム

公開:2020/10/21
更新:2020/10/22
3 min読了の目安(約2900字TECH技術記事

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

(b1c10000a2b2c20000a3b3c30000a4b4c400000an1bn1cn100000anbn)(x1x2x3x4xn1xn)=(d1d2d3d4dn1dn) \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番目の式は以下の式で表されます。

b1x1c1x2=d1(1) b_1x_1 - c_1x_2 = d_1 \tag{1}

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

x1+c1b1x2=d1b1(2) x_1 + \frac{c_1}{b_1}x_2 = \frac{d_1}{b_1} \tag{2}

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

e1=c1b1(3) e_1 = \frac{c_1}{b_1} \tag{3}
f1=d1b1(4) f_1 = \frac{d_1}{b_1} \tag{4}

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

x1+e1x2=f1(5) x_1 + e_1x_2 = f_1 \tag{5}

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

a2x1+b2x2+c2x3=d2(6) a_2x_1 + b_2x_2 + c_2x_3 = d_2 \tag{6}

式(5)を式変形し

x1=f1e1x2(7) x_1 = f_1 - e_1x_2 \tag{7}

式(6)に代入します。

a2(f1e1x2)+b2x2c2x3=d2a2f1a2e1x2+b2x2c2x3=d2(b2a2e1)x2+c2x3=d2a2f1x2+c2b2a2e1x3=d2a2f1b2a2e1(8) 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}

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

e2=c2b2a2e1(9) e_2 = \frac{c_2}{b_2 - a_2e_1} \tag{9}
f2=d2a2f1b2a2e1(10) f_2 = \frac{d_2 - a_2f_1}{b_2 - a_2e_1} \tag{10}
x2+e2x3f2x2=f2e2x3(11) x_2 + e_2x_3 - f_2 \\ x_2 = f_2 - e_2x_3 \tag{11}

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

a3x2+b3x3+c3x4=d3(12) a_3x_2 + b_3x_3 + c_3x_4 = d_3 \tag{12}
a3(f2e2x3)+b3x3+c3x4=d3a3f2a3e2x3+b3x3+c3x4=d3(b3a3e2)x3+c3x4=d3a3f2x3+c3b3a3e2=d3a3f2b3a3e2(13) 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}

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

e3=c3b3a3e2(14) e_3 = \frac{c_3}{b_3 - a_3e_2} \tag{14}
f3=d3a3f2b3a3e2(15) f_3 = \frac{d_3 - a_3f_2}{b_3 - a_3e_2} \tag{15}
x3=f3e3x4(16) x_3 = f_3 - e_3x_4 \tag{16}

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

ei=cibiaiei1(17) e_i = \frac{c_i}{b_i - a_ie_{i-1}} \tag{17}
fi=diaifi1biaiei1(18) f_i = \frac{d_i - a_if_{i-1}}{b_i - a_ie_{i-1}} \tag{18}
xn1=fn1en1xn(19) x_{n-1} = f_{n-1} - e_{n-1}x_n \tag{19}

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

anxn+bnxn=dn(20) a_nx_n + b_nx_n = d_n \tag{20}

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

an(fn1en1xn)+bnxn=dnanfn1anen1xn+bnxn=dnxn(bnanen1)=dnanfn1xn=dnanfn1bnanen1(21) -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}

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