A..2 LU分解とは

連立1次方程式を解くのに、逆行列を一度計算してしまえば、後は楽じゃない？

という考えに「それは勘違いです。LU 分解を使うべきです。」ということを、 以下の数小節を費やして説明する。

対角線より上にあるすべての成分が 0 であるような行列を 下三角行列と呼ぶ。 すなわち $L=(\ell_{ij})$ が下三角行列であるとは、

$$i>j\quad\Then\quad \ell_{ij}=0$$

が成り立つことをいう。

同様に対角線より下にあるすべての成分が 0 である行列を 上三角行列と呼ぶ。

正則な下三角行列の全体は乗法に関して群をなす。 上三角行列についても同様である。

行列 $A$ に対して、

$$A=L U,$$   $$\mbox{$L$ は下三角行列}$$$$,$$   $$\mbox{$U$ は上三角行列}$$

をみたす $L$ , $U$ が存在するとき、 $L$ と $U$ の組を $A$ の LU 分解とよび、 $L$ と $U$ の組を求めることを $A$ を LU 分解する、という。

• 与えられた正則行列 $A$ が LU 分解を持つためには、 $A$ のすべての首座小行列式 $\det A_k$ が 0 でないことが必要十分である。
• 任意の正則行列 $A$ に対して、適当に行の交換を行った行列 $PA$ は、 LU 分解を持つ ($P$ はいわゆる置換行列で、左からかけることで行の交換がおこる)。