数値解析 第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}}$

となります。