A..4 LU分解があれば連立1次方程式はすぐ解ける (逆行列の代わりになる)

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

$$A x = b$$

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

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

は

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

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

まず $Ly = b$ は

$$\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}$$

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

$$y_1 = b_1/\ell_{11},$$

$$y_2 = \left(b_2-\ell_{21}y_1\right)/\ell_{22},$$

$$y_3 = \left(b_3-\ell_{31}y_1-\ell_{32}y_2\right)/\ell_{33},$$

$$\cdots$$

$$y_i = \left(b_i-\dsp\sum_{j=1}^{i-1}\ell_{ij}y_j\right)/\ell_{ii},$$

$$\cdots$$

$$y_n = \left(b_n-\dsp\sum_{j=1}^{n-1}\ell_{nj}y_j\right)/\ell_{nn}$$

と解くことが出来る ($A$ が正則であると仮定したことから、$L$ も正則で、 すべての $i$ について $\ell_{ii}\ne 0$ が成り立つことに注意)。

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

同様に $Ux = y$ は

$$\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}$$

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

$$x_{n} = {y_n}/{u_{nn}},$$

$$x_{n-1} = \left(y_{n-1}-u_{n-1,n}x_n\right)/u_{n-1,n-1},$$

$$x_{n-2} = \left(y_{n-2}-u_{n-2,n-1}x_{n-1}-u_{n-2,n}x_n\right)/u_{n-2,n-2},$$

$$\vdots \qquad\qquad\vdots$$

$$x_{i} = \left(y_i-\dsp\sum_{j=i+1}^{n}u_{ij}x_j\right)/u_{ii},$$

$$\vdots \qquad\qquad\vdots$$

$$x_{1} = \left(y_1-\dsp\sum_{j=2}^{n}u_{1j}x_j\right)/u_{11}$$

と解くことができる。

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

まとめると、 $n(n+1)/2+n(n+1)/2=n(n+1)$ 回の乗除算で連立1次方程式が解 けることになる⁴。 これは連立1次方程式を「普通に」解く場合に、 $n^3$ に比例する回数の乗除算が必要なことと比較して、 ($n$ が大きな場合は) かなり少ない回数となる。

普通に解く $O(n^3)$     v.s.      LU分解(が与えられていてそれ)を使った場合 $n^2$ 程度