数値解析 第11回 (4) LU 分解法 Step 2-3 の手順
Step 3 の手順
$U$ は上三角行列ですので、Step 3 は、
ガウスの消去法の Step 2 を $U$ と $\yyy$ で書き直したものになります。
ただし $u_{ii}=1$ ですので
前回の Step2 と違って $\dps{\frac{1}{u_{ii}}}$ は不要です。
Algorithm ( Step 3 )
for $i = n$ downto $1$
$\dps{x_i = y_i - \sum_{j=i+1}^n u_{ij}\,x_j}$
Step 2 の手順
逆に $L$ は下三角行列ですので、$L\yyy=\bbb$ という式を上の成分から順に見てゆきます。
赤字の数が未知数で、ひとつずつ求まってゆくことがわかります。
$\require{color}$
- 第 $1$ 成分: $\ell_{11}\,\textcolor{red}{y_1} = b_1$
- 第 $2$ 成分: $\ell_{21}\,y_1 + \ell_{22}\,\textcolor{red}{y_2} = b_2$
- 第 $3$ 成分: $\ell_{31}\,y_1 + \ell_{32}\,y_2 + \ell_{33}\,\textcolor{red}{y_3} = b_3$
$\vdots$
- 第 $i$ 成分: $\ell_{i1}\,y_1 + \cdots + \ell_{i,i-1}\,y_{i-1} + \ell{ii}\,\textcolor{red}{y_i} = b_i$
具体的には
Algorithm ( Step 2 )
for $i = 1$ to $n$
$\dps{y_i = \left(b_i - \sum_{j=1}^{i-1} \ell_{ij}\,y_j\right) / \,\ell{ii}}$
となります。