2.3 LU分解を用いた連立1次方程式の解法

次正則行列がと LU 分解されているとき、連立1次方程式

$\displaystyle A x = b$

は少ない計算量で解くことが出来る。以下、このことを説明する。

$\displaystyle A x = b\qquad (\Iff\quad L U x = b)$

は

$\displaystyle L y = b, \quad U x = y$

という二つの問題に分解される。

まずは

$\begin{displaymath} \begin{array}{ccccccc} \ell_{11} y_1 & &&&& = b_1\\ \ell_... ...} y_2 & +\ell_{n3} y_3&\cdots& +\ell_{nn}y_n& = b_n \end{array}\end{displaymath}$

ということであり、これは上から順に

$\displaystyle y_1$	$\displaystyle =$	$\displaystyle b_1/\ell_{11},$
$\displaystyle y_2$	$\displaystyle =$	$\displaystyle \left(b_2-\ell_{21}y_1\right)/\ell_{22},$
$\displaystyle y_3$	$\displaystyle =$	$\displaystyle \left(b_3-\ell_{31}y_1-\ell_{32}y_2\right)/\ell_{33},$
		$\displaystyle \cdots$
$\displaystyle y_i$	$\displaystyle =$	$\displaystyle \left(b_i-\dsp\sum_{j=1}^{i-1}\ell_{ij}y_j\right)/\ell_{ii},$
		$\displaystyle \cdots$
$\displaystyle y_n$	$\displaystyle =$	$\displaystyle \left(b_n-\dsp\sum_{j=1}^{n-1}\ell_{nj}y_j\right)/\ell_{nn}$

と解くことが出来る (

が正則であると仮定したことから、

も正則で、すべての

について $\ell_{ii}\ne 0$ が成り立つことに注意)。

これを計算するには、 $1+2+\cdots+n=n(n+1)/2$ 回の乗除算で十分である ⁶。

$\begin{yodan}[実は「下三角行列の逆行列は下三角」の別証にな... ...逆行列が下三角行列であることを示している。 \qed \end{yodan}$

同様には

$\begin{displaymath} \begin{array}{lllllll} u_{11} x_1 & \cdots& +u_{1,n-2} x_{n... ...n-1,n}x_n &=y_{n-1},\\ & & & & u_{n,n}x_n &=y_{n} \end{array}\end{displaymath}$

ということである。やはり

が正則という仮定から、 $u_{ii}\ne 0$ ( $i=1,\dots,n$ ) が導かれることに注意すると、この連立方程式は、下から順に

	$\displaystyle x_{n}$	$\displaystyle = {y_n}/{u_{nn}},$
	$\displaystyle x_{n-1}$	$\displaystyle = \left(y_{n-1}-u_{n-1,n}x_n\right)/u_{n-1,n-1},$
	$\displaystyle x_{n-2}$	$\displaystyle = \left(y_{n-2}-u_{n-2,n-1}x_{n-1}-u_{n-2,n}x_n\right)/u_{n-2,n-2},$
	$\displaystyle \vdots$	$\displaystyle \qquad\qquad\vdots$
	$\displaystyle x_{i}$	$\displaystyle = \left(y_i-\dsp\sum_{j=i+1}^{n}u_{ij}x_j\right)/u_{ii},$
	$\displaystyle \vdots$	$\displaystyle \qquad\qquad\vdots$
	$\displaystyle x_{1}$	$\displaystyle = \left(y_1-\dsp\sum_{j=2}^{n}u_{1j}x_j\right)/u_{11}$