1-7 行列の分解とLU分解

読み始める前の問い

同じ係数行列で右辺だけ違う方程式を何度も解くとき、毎回消去をやり直す必要があるだろうか。
このページでできるようになること
消去の前処理を $LU$ 分解として保存し、複数の右辺へ再利用できるようになる。
同じ係数行列で右辺だけが異なる方程式を何度も解くとき、毎回消去法を最初から行うのは無駄です。LU分解は、消去の履歴を下三角行列に保存し、以後は二つの簡単な三角方程式へ分けます。

消去を行列として記録する

$$ A=\begin{pmatrix} 2&1&1\\ 4&-1&0\\ -2&2&1 \end{pmatrix} $$
を考えます。第一列を消去するため
$$ R_2\leftarrow R_2-2R_1, \qquad R_3\leftarrow R_3+R_1 $$
とすると
$$ \begin{pmatrix} 2&1&1\\ 0&-3&-2\\ 0&3&2 \end{pmatrix}. $$
さらに $R_3\leftarrow R_3+R_2$ として
$$ U=\begin{pmatrix} 2&1&1\\ 0&-3&-2\\ 0&0&0 \end{pmatrix} $$
を得ます。
使用した消去係数は $2,-1,-1$ です。符号を戻して下三角に並べると
$$ L=\begin{pmatrix} 1&0&0\\ 2&1&0\\ -1&-1&1 \end{pmatrix}. $$
直接掛けると $LU=A$ になります。

LU分解

正方行列 $A$ を
$$ A=LU $$
と表し、$L$ が対角成分1の下三角行列、$U$ が上三角行列であるとき、これをLU分解という。

なぜ消去係数がLになるか

消去操作を表す基本行列の積を $E$ とすれば $EA=U$、したがって
$$ A=E^{-1}U. $$
一つの行へ前の行の $-c$ 倍を加える消去行列の逆は、同じ位置へ $c$ を入れた下三角基本行列です。消去を列の上から順に行えば、それらの逆の積 $E^{-1}$ は下三角になり、対角成分はすべて1です。これが $L$ です。

証明を読む前の見取り図

消去行列の積を逆にたどって下三角行列を作り、$Ax=b$ を二つの三角系へ分ける。

pivot交換を要しない場合のLU分解

Gauss消去の各段階で行交換を使わず、主成分で割らずに上三角行列 $U$ まで消去できる正方行列 $A$ は、対角成分1の下三角行列 $L$ を用いて $A=LU$ と分解できる。

第 $k$ 列の主成分より下を消す操作を、基本行列 $E_k$ の左乗で表す。すべての消去後に
$$ E_s\cdots E_1A=U $$
となる。各 $E_i$ は対角成分1の下三角行列で、逆行列も同じ位置の符号を反転した対角成分1の下三角行列である。よって
$$ A=E_1^{-1}\cdots E_s^{-1}U. $$
下三角行列の積が下三角であることは、第 $i,j$ 成分の和で $i< j$ のとき非零項が存在しないことから従う。対角成分は1の積で1である。したがって $L:=E_1^{-1}\cdots E_s^{-1}$ と置けばよい。

方程式を二段階で解く

$Ax=b$ は
$$ LUx=b $$
です。まず $y=Ux$ と置いて $Ly=b$ を前進代入で解き、次に $Ux=y$ を後退代入で解きます。右辺 $b$ が変わっても $L,U$ は再利用できます。
下三角方程式
$$ \begin{pmatrix}1&0&0\\2&1&0\\-1&-1&1\end{pmatrix} \begin{pmatrix}y_1\\y_2\\y_3\end{pmatrix} =\begin{pmatrix}b_1\\b_2\\b_3\end{pmatrix} $$
は上から
$$ y_1=b_1, \quad y_2=b_2-2y_1, \quad y_3=b_3+y_1+y_2 $$
と順に解けます。