LU分解

本記事では、LU分解について解説します。LU分解はその特徴から、計算のコストを抑えることができる（4.LU分解の応用で解説）ため、コンピュータによる計算を多く用いる分野で力を発揮します。

1. LU分解とは

LU分解とは、

与えられた正方行列Aを、対角成分がすべて1である下三角行列Lと、対角成分に0を含まない上三角行列Uの積に表すこと

すなわち、

$A=LU$

の形に分解することを言います。

(LU分解のLは下三角行列(lower triangular matrix),Uは上三角行列(upper triangular matrix)から来ています。)

　　例題1.

$$以下の行列 A,下三角行列 L,上三角行列 U が A = LU を満たすことを確かめよ。 \\ A = \begin{pmatrix} 2 & 1 & -1 \\ 4 & 5 & 0 \\ -2 & 8 & 8 \end{pmatrix}, \quad L = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & 3 & 1 \end{pmatrix}, \quad U = \begin{pmatrix} 2 & 1 & -1 \\ 0 & 3 & 2 \\ 0 & 0 & 1 \end{pmatrix}$$

【解答】

$$\begin{aligned} LU &= \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & 3 & 1 \end{pmatrix} \begin{pmatrix} 2 & 1 & -1 \\ 0 & 3 & 2 \\ 0 & 0 & 1 \end{pmatrix} \\ &= \begin{pmatrix} 1\cdot2 + 0 + 0 & 1\cdot1 + 0 + 0 & 1\cdot(-1) + 0 + 0 \\ 2\cdot2 + 1\cdot0 + 0 & 2\cdot1 + 1\cdot3 + 0 & 2\cdot(-1) + 1\cdot2 + 0 \\ -1\cdot2 + 3\cdot0 + 0 & -1\cdot1 + 3\cdot3 + 0 & -1\cdot(-1) + 3\cdot2 + 1\cdot1 \end{pmatrix} \\ &= \begin{pmatrix} 2 & 1 & -1 \\ 4 & 5 & 0 \\ -2 & 8 & 8 \end{pmatrix}\\ &= A \end{aligned}$$ LU分解の一例として上のようなものがあげられます。対角成分がすべて1である下三角行列Lと、対角成分に0を含まない上三角行列Uとなっていることにも注意しましょう。

2. 2次正方の場合のLU分解

具体的な2次の行列 $A$ を使ってLU分解を行ってみます。 Aが以下で与えられたとします。

$$A = \begin{pmatrix} 2 & 1 \\ 4 & 5 \end{pmatrix}$$

未知の実数成分を持った $L$ と $U$ を掛け合わせて、これが $A$ に一致するような方程式を立てます。

$$\begin{pmatrix} 1 & 0 \\ l_{21} & 1 \end{pmatrix} \begin{pmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 4 & 5 \end{pmatrix}$$

左辺の行列の積を展開すると、次のようになります。

$$\begin{pmatrix} u_{11} & u_{12} \\ l_{21}u_{11} & l_{21}u_{12} + u_{22} \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 4 & 5 \end{pmatrix}$$

よって

• $u_{11} = 2$

• $u_{12} = 1$

• $l_{21}u_{11} = 4$

• $l_{21}u_{12} + u_{22} = 5$

  ゆえに

• $l_{21} = 2$

• $u_{22} = 3$

これで、以下のような$L$ と $U$ が得られました。

$$L = \begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix}, \quad U = \begin{pmatrix} 2 & 1 \\ 0 & 3 \end{pmatrix}$$

これが3次や4次の行列になったら、計算がすごく面倒になりそうですね…。

そうですね。では、行基本変形によるLU分解をしてみましょう。

3. 行基本変形によるLU分解

先ほどの行列 $A = \begin{pmatrix} 2 & 1 \\ 4 & 5 \end{pmatrix}$ をもう一度考えます。

行基本変形を行って、上三角行列 $U$ を作りにいきます。 この場合、2行目から1行目の-2倍を足します。

$$\begin{pmatrix} 2 & 1 \\ 4 - 2 \times 2 & 5 - 1 \times 2 \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 0 & 3 \end{pmatrix}$$

これで、上三角行列 $U$ が完成しました。

…。これがLU分解とどう関係があるんですか？

行基本変形とはどのような操作だったでしょうか？

行基本変形は、基本行列を左からかける操作でした。…あっ、今回はその基本行列が下三角行列となっていますね！下三角行列の逆行列も下三角であって、さらに対角成分がすべて1なので、LU分解のLが構成できますね！

その通りです。では「行基本変形によって対角成分に0を含まない上三角行列が作れれば、LU分解可能」といえるでしょうか？ 上三角行列が作れたら、$A = LU$ の形になるってことですよね。じゃあ、作れれば必ずLU分解できる…？でも、対角成分がすべて1である下三角行列Lの構成のためには$L^{-1}$が下三角になってないといけませんよね...? そうですね。具体的には、「Uの構成が、ある行の定数倍を下の行に足す操作のみで行える時」と言えます。

なるほど、そうすれば$L^{-1}$は対角成分がすべて1で、下三角行列となり、無事に対角成分がすべて1である下三角行列Lが構成できますね。

　　例題2.

$$以下の行列AをLU分解せよ.\\ A = \begin{pmatrix} 2 & -1 & 1 \\ 4 & 1 & -1 \\ 2 & -4 & 3 \end{pmatrix}$$

【解答と解説】 行列 $A$ を上三角行列 $U$ にある行の定数倍を下の行に足す行基本変形だけで変形し、行基本変形の積で下三角行列 $L$を構成します。

ステップ1：1列目の消去

• 2行目に1行目の $-2$ 倍を足す。 $\rightarrow L$ の $(2, 1)$ 成分は $2$
• 3行目に1行目の $-1$ 倍を足す。 $\rightarrow L$ の $(3, 1)$ 成分は $1$

$$\begin{pmatrix} 2 & -1 & 1 \\ 0 & 3 & -3 \\ 0 & -3 & 2 \end{pmatrix}$$

ステップ2：2列目の消去

• 3行目に2行目を足す。 $\rightarrow L$ の $(3, 2)$ 成分は $-1$

$$\begin{pmatrix} 2 & -1 & 1 \\ 0 & 3 & -3 \\ 0 & 0 & -1 \end{pmatrix}$$

これで対角成分の下がすべて $0$ になったので、これが上三角行列 $U$ です。

ステップ3：行列 L の構成 行った行基本変形に対応する基本行列の積の逆行列を考えれば、Lは以下のように与えられます。

$$L = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & -1 & 1 \end{pmatrix}$$

【答え】

$$A = LU = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & -1 & 1 \end{pmatrix} \begin{pmatrix} 2 & -1 & 1 \\ 0 & 3 & -3 \\ 0 & 0 & -1 \end{pmatrix}$$

---

　　例題3.

$$以下の行列AはLU分解可能か判定せよ.\\ A = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 4 & 5 \\ 1 & 1 & 1 \end{pmatrix}$$

【解答と解説】 行列 $A$ を上三角行列 $U$ に行基本変形だけで変形できるか確認します。

ステップ1：1列目の消去

• 2行目に1行目の $-2$ 倍を足す。
• 3行目に1行目の $-1$ 倍を足す。

$$\begin{pmatrix} 1 & 2 & 3 \\ 0 & 0 & -1 \\ 0 & -1 & -2 \end{pmatrix}$$

ステップ2：2列目の確認

変形後の行列において、2行目の対角成分（$(2, 2)$ 成分）が $0$ となりました。 行の入れ替えを行わずに、3行目の $(3, 2)$ 成分である $-1$ を消去し、上三角行列を作ることはできない。

【答え】

行の入れ替えを行わずに対角成分に $0$ を含まない上三角行列が作れないため、LU分解不可能である。

4. LU分解の応用

分解の条件と分解の手法について話してきましたが、そもそもLU分解できてうれしいことってどんなところにあるのでしょうか？

LU分解できることのメリットは、計算コストの削減にあります。

連立1次方程式 $Ax = b$ を解く時、AがLU分解できるとします。このとき方程式は次のように書き換えられます。

$$LUx = b$$

ここで、$Ux = y$ と置いてみましょう。すると、元の複雑な連立方程式は、次の2つのシンプルなステップに分けて解くことができます。

① $Ly = b$ を解く（前進代入法）

$L$ は下三角行列です。つまり、一番上の行には未知数が1つしか含まれていないため、$y_1$ が即座に求まります。その求まった値を2行目に代入すれば $y_2$ が求まり…というように、上から下へと順番に代入していくだけで、簡単に解 $y$ を求めることができます。これを前進代入法と呼びます。

② $Ux = y$ を解く（後退代入法）

次に、いま求まった $y$ を使って $Ux = y$ を解きます。$U$ は上三角行列なので、今度は一番下の行の未知数が即座に求まります。そこから下から上へと順番に代入していくことで、最終的な解 $x$ が求まります。これを後退代入法と呼びます。

どちらも三角行列になっているおかげで、連立方程式を解く計算が、スルスルと進むわけですね。これはコンピュータの計算を使う分野ではかなり活躍しそうな方法ですね。

そして、 LU分解による解法の最大の特長は、係数行列 $A$ が固定で、右辺の $b$ がさまざまに動く場合に、計算コストを劇的に抑えられる点にあります。

具体的にはどのような場面があるのでしょうか？ 例えば、物理や工学のシミュレーションにおいて、解くことが困難な非線形微分方程式の近似解を求める「有限要素法」と呼ばれる手法があります。 この計算過程で、連立1次方程式を大量に解く作業が生じますが、これはちょうど「係数行列 $A$ は一定のままで、$b$ がさまざまに動く」という設定になっています。 なるほど。もし $b$ が変わるたびに毎回ゼロから掃き出し法を行うと、膨大な計算時間がかかってしまいまね。 $A$ をLU分解して $L$ と $U$ の行列情報をコンピュータのメモリに保存しておけば、 $b$ が変わるたびに、計算の軽い「前進代入法」と「後退代入法」を行うだけで次々と新しい解 $x$ を導き出すことができるというわけですね。 この工夫により、計算時間は大きく短縮されます。LU分解は単なる手計算のテクニックではなく、コンピュータによる数値計算の分野において、有限要素法に限らず広く利用されている極めて強力で重要なツールなのです。

まとめ

LU分解は、連立方程式の右辺が変わった時でも、一から掃き出し法をやり直すことなく瞬時に答えを出すことができます。だからこそ、現代のコンピュータ計算において欠かせない技術となっているのです。

---