ガウス消去法(II) LU分解

行列のLU分解とは

与えられる行列Aに対して、以下の分解を考える。 $$ A=LU $$ ここで、Lは下三角行列、Uは上三角行列です。LU分解は連立一次方程式の計算に使用されています。

行列のLU分解とは

ガウス消去法によって、行列のLU分解ができます。以下、$4\times 4$の行列$A$を例にして説明します。

Aの第i列の対角成分以下の要素を消去するために、以下の作業行列$E_i$が用意されます。

$$ E_1= \left( \begin{array}{cccc} 1 & 0 & 0 & 0\\ f_{21} & 1 & 0 & 0 \\ f_{31} & 0 & 1 & 0\\ f_{41} & 0 & 0 & 1 \end{array} \right) $$$$ E_2= \left( \begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 \\ 0 & f_{32} & 1 & 0\\ 0 & f_{42} & 0 & 1 \end{array} \right) $$$$ E_3= \left( \begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0\\ 0 & 0& f_{43} & 1 \end{array} \right) $$

ガウス消去法によって、以下の分解ができます。 $$ E_3E_2E_1 A = U $$ よって、 $$ A = E_1^{-1} E_2^{-1} E_3^{-1} U = LU \quad (L := E_1^{-1} E_2^{-1} E_3^{-1} ) $$

Lの各成分を計算すると、以下の形が分かります。

$$ L= \left( \begin{array}{cccc} 1 & 0 & 0 & 0\\ -f_{21} & 1 & 0 & 0 \\ -f_{31} & -f_{32} & 1 & 0\\ -f_{41} & -f_{42} & -f_{43} & 1 \end{array} \right) $$

上記の計算過程によって、ガウス消去法の各列の作業とともに、Lの各列の成分を計算でき、Aの対角成分以下に格納することができます。 即ち、ガウス消去法の計算後、以下の行列が得られます。

$$ \left( \begin{array}{cccc} u_{11} & u_{12} & u_{13} & u_{14}\\ -f_{21} & u_{22} & u_{23} & u_{24} \\ -f_{31} & -f_{32} & u_{33} & u_{34}\\ -f_{41} & -f_{42} & -f_{43} & u_{44} \end{array} \right) $$

演習1

行列のLU分解を行い、上記の説明のようにLとUを求めてください。

$$ A= \left( \begin{array}{cccc} 2& 1 & -2 & 3\\ 2 & 0 & 4 & 1 \\ 3 & 0 & 5& 2\\ 1 & -1 & 2 & 1 \end{array} \right) $$

Step 1.

Aの行列の第1行を使って、行列の一番目の列の対角以下の成分を0に変形します。

まず、第1行のalpha倍を第2,3,4行に加えます。 作業行列$E_1$の成分 $f_{j1}$ (j=2,3,4)をAの第1列格納する。

Step 2.

Aの行列の第2行を使って、2番目の列の対角以下の成分を0に変形します。

第2行のalpha倍を第3,4行に加えます。 作業行列$E_2$の成分 $f_{j2}$ (j=3,4)をAの第2列の対角以下に格納する。

Step 3.

Aの行列の第3行を使って、3番目の列の対角以下の成分を0に変形します。

第2行のalpha倍を第4行に加えます。 作業行列$E_3$の成分 $f_{43}$をAの第3列の対角以下に格納する。

コードのまとめ

上記の計算をここにまとめて書いてください。行の番号iに関するループを使ってください。

LU分解による連立一次方程式を解く

AのLU分解が分かると、以下の2つの三角行列に関する方程式を解いてから、Ax=bの解は容易に計算できます。

$$ Ly=b, Ux=y $$

$Ly=b$の計算方法

Lは以下の形を持っています。 $$ L= \left( \begin{array}{cccc} 1 & 0 & 0 & 0\\ l_{21} & 1 & 0 & 0 \\ l_{31} & l_{32} & 1 & 0\\ l_{41} & l_{42} & l_{43} & 1 \end{array} \right) $$

よって、$Ly=b$の解$y=(y_1, y_2, y_3, y_4)$は以下のように$y_i$を順番に算出することができます。

for loopでまとめます。

演習2

上記のAのLU分解に利用して、以下の$b_1$, $b_2$に関する連立一次方程式$Ax=b_1, Ax=b_2$を解いてください。 $$ b_1= \left( \begin{array}{cccc} 11\\ -5\\ -5\\ -4 \end{array} \right),\quad b_2= \left( \begin{array}{cccc} 10\\ 18\\ 26\\ 9 \end{array} \right) $$

演習3

以下の行列$A_2$のLU分解を計算してください。

演習4

$A_2 x=b$を解いてください。ただし、$b$はすべて成分が1である$6\times 1$ベクトルです。