数値解析 第11回 (1) 状況設定と LU 分解法の方針

状況設定

 前回と同じく
  • $A=(a_{ij})$:与えられた $n$ 次正則行列
  • $\xxx=(x_i)$:未知の $n$ 次元縦ベクトル
  • $\bbb=(b_i)$:与えられた $n$ 次元縦ベクトル
を用いて
$A\xxx=\bbb$
と表される連立一次方程式の解 $\xxx$ の近似値を求めます。 前回のガウスの消去法では拡大係数行列を扱いましたが、 今日勉強する LU 分解法では先ず係数行列 $A$ だけを処理します。

LU 分解法の方針

Step 1 係数行列 $A$ を
$A=LU$
の積の形に分解する。ただし、$L$ は
$\dps{ L=\mat{cc}{ \begin{array}[c]{cc} \ell_{11} & \\ \ell_{21} & \ell_{22} \\ \end{array} & \Huge{0} \\[-0.5em] \begin{array}{cc} \vdots & \vdots \\ \ell_{n1} & \ell_{n2} \\ \end{array} & \begin{array}{cc} \ddots & \\ \cdots & \ell_{nn} \\ \end{array} } }$
の形の 下三角行列、$U$ は
$\dps{ U=\mat{cc}{ \begin{array}{cc} 1 & u_{12}\\ & 1 \\ \end{array} & \begin{array}{cc} \cdots & u_{1n}\\ \cdots & u_{2n} \\ \end{array} \\[-0.5em] \Huge{0} & \begin{array}[b]{cc} \ddots & \vdots \\ & 1 \\ \end{array} } }$
の形の、対角成分が全て 1 の 上三角行列 である。 ( 大きい $0$ はそれぞれ対角線より上・下の成分が全て $0$ であることを表す。)
※ L は lower triangular matrix の L、U は upper triangular matrix の U です。 楽器のトライアングルとか「魔の三角海域バミューダ・トライアングル」とかの triangle ( 三角形 ) の形容詞形が triangular です。
Ex. $n=2$ のとき、
$\dps{ \left( \begin{array}[c]{cccc} a & b \\ c & d \\ \end{array} \right) = \left( \begin{array}[c]{cccc} a & 0 \\ c & d-\frac{bc}{a} \\ \end{array} \right) \left( \begin{array}[c]{cccc} 1 & \frac{b}{a} \\ 0 & 1 \\ \end{array} \right) }$
$n=3$ のとき
$\dps{ \left( \begin{array}[c]{cccc} a & b & c \\ d & e & f \\ g & h & i \\ \end{array} \right) = \left( \begin{array}[c]{cccc} a & 0 & 0 \\ d & e^{\prime} & 0 \\ g & h^{\prime} & i^{\prime} \\ \end{array} \right) \left( \begin{array}[c]{cccc} 1 & \frac{b}{a} & \frac{c}{a} \\ 0 & 1 & j \\ 0 & 0 & 1 \\ \end{array} \right) }$
ただし
$\dps{ e^{\prime} = e-\frac{bd}{a},\quad h^{\prime} = h-\frac{bg}{a},\quad j = \frac{1}{e^{\prime}}\left(f-\frac{cd}{a}\right),\quad i^{\prime} = i - \frac{cg}{a} - jh^{\prime} }$
Step 2 $\bbb$ と、Step 1 で求めた $L$ を用いて $L\yyy=\bbb$ の解 $\yyy$ を求める。
Step 3 Step 1 で求めた $U$ と Step 2 で求めた $\yyy$ を用いて $U\xxx=\yyy$ の解 $\xxx$ を求める。
すると、
$A\xxx=LU\xxx=L(U\xxx)=L\yyy=\bbb$
となって $A\xxx=\bbb$ の解 $\xxx$ が求まります。 後に見るように、$L$ や $U$ が三角行列であることで Step 2-3 が解き易くなっています。