数値解析 第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 が解き易くなっています。