連立方程式の数値解法

連立方程式

　以下のように複数の線形方程式を同時に成り立たせる解 $\small x_1,x_2,\cdots,x_n$ を求める問題が連立方程式(Simultaneous Equations)である。

$\small \left[ \begin{array}{cccc} a_{11}&a_{12}&\cdots&a_{1n}\\ a_{21}&a_{22}&\cdots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots \\ a_{n1}&a_{n2}&\cdots&a_{nn} \end{array} \right] \left[ \begin{array}{c} x_1\\ x_2\\ \vdots\\ x_{n} \end{array} \right]=\left[ \begin{array}{l} b_1 \\ b_2\\ \vdots \\ b_n \end{array} \right]$ 上記の方程式を

$\small Ax=b$ と表すことにする。

　一般的な解を求める前に、下三角形(上三角形)以外の値が0である行列に関する連立方程式は手前(後ろ)から順番に解を求めることができるタイプの連立方程式であることに注意する。

$\small \left[ \begin{array}{cccc} l_{11}&0&\cdots&0\\ l_{21}&l_{22}&\cdots&0\\ \vdots&\vdots&\ddots&\vdots \\ l_{n1}&l_{n2}&\cdots&l_{nn} \end{array} \right] \left[ \begin{array}{c} y_1\\ y_2\\ \vdots\\ y_{n} \end{array} \right]=\left[ \begin{array}{l} b_1 \\ b_2\\ \vdots \\ b_n \end{array} \right]$

$\small \left[ \begin{array}{cccc} u_{11}&u_{12}&\cdots&u_{1n}\\ 0&u_{22}&\cdots&u_{2n}\\ \vdots&\vdots&\ddots&\vdots \\ 0&0&\cdots&u_{nn} \end{array} \right] \left[ \begin{array}{c} x_1\\ x_2\\ \vdots\\ x_{n} \end{array} \right]=\left[ \begin{array}{l} y_1 \\ y_2\\ \vdots \\ y_n \end{array} \right]$ それぞれ、

$\small Ly=b, Ux=y$ と表すことにする。具体的に解は

$\small y_i = \frac{1}{l_{ii}}\left( b_i-\sum_{j=1}^{i-1} l_{ij} y_j \right), \;\; i=1,2,\cdots,n \qquad \;\; \\ \small x_i = \frac{1}{u_{ii}}\left( y_i-\sum_{j=i+1}^{n} u_{ij} y_j \right), \;\; i=n,n-1,\cdots,1$ と書ける。もし、行列

$\small A$ が

$\small A=LU$ という形に分解できれば、一般の連立方程式は上記の比較的容易に解ける2つの連立方程式として解くことができる。このような行列の分解はLU分解(LU Decomposition)といわれる。

LU分解

　一般性を失うことなく、 $\small l_{ii} = 1, \;\; i = 1,2,\cdots,n$ とおく。実際に、行列の掛け算を計算し、それぞれの要素が行列 $\small A$ と等しいと置くと、

$\small l_{i1}u_{1j} + l_{i2}u_{2j} + \cdots l_{ii}u_{ij}= a_{ij}, \;\; i \leq j \\ \small l_{i1}u_{1j} + l_{i2}u_{2j} + \cdots l_{ij}u_{jj}= a_{ij}, \;\; i>j$ であり、

$\small n^2$ 個の未知数に対して、

$\small n^2$ 個の連立方程式となり、解を求めることができる。複雑に見えるが、この方程式は手前の

$\small j$ から順に解くことができて、

$\small u_{ij} = a_{ij}-\sum_{k=1}^{i-1} l_{ik}u_{kj}, \;\; i = 1, 2, \cdots, j \qquad \qquad \qquad \\ \small l_{ij} = \frac{1}{u_{jj}} \left( a_{ij}-\sum_{k=1}^{i-1} l_{ik}u_{kj} \right), \;\; i = j+1, j+2, \cdots, n$ と計算できる。計算に現れない要素は0である。効率的なプログラミングの工夫等はあるかもしれないが、上記の方法で連立方程式を解くことができる。

逆行列

　 $\small AA^{-1} = I$ を成り立たせる行列 $\small A^{-1}$ をという。ここで、 $\small I$ は単位行列といわれる行列であり、対角要素が1で、それ以外の要素が0である行列を表す。逆行列はLU分解実行後、単位行列の各列を $\small b$ に代入して、繰り返し連立方程式を解くことで求めることができる。連立方程式を解く以外でも逆行列の計算は必要となることがあるため、利用できるようにしておくとよいだろう。