next up previous
Next: B..5.3 Cholesky 分解 Up: B..5 行列の分解について Previous: B..5.1 LU 分解


B..5.2 三角行列係数の連立1次方程式

三角行列係数の連立1次方程式は非常に簡単に解くことができる。 これを上三角行列の場合に見てみよう。

$\displaystyle U x=b
$

において $ U=(u_{ij})$ が上三角行列とする。

$\displaystyle \begin{array}{ccccccccccccccccc}
u_{11} x_1 &+& u_{12} x_2 &+& \...
...n=b_2\\
& & & & \ddots & & \vdots \\
& & & & & & u_{nn}x_n=b_n
\end{array}$

は下の方程式から順に
  $\displaystyle x_n$ $\displaystyle =$ $\displaystyle b_n/u_{nn},$
  $\displaystyle x_{n-1}$ $\displaystyle =$ $\displaystyle (b_{n-1}-u_{n-1,n}x_n)/u_{n-1,n-1},$
    $\displaystyle \vdots$  
  $\displaystyle x_{i}$ $\displaystyle =$ $\displaystyle \left(b_{i}-\sum_{j=i+1}^n u_{i,j}x_j\right)/u_{ii}$
    $\displaystyle \vdots$  
  $\displaystyle x_{1}$ $\displaystyle =$ $\displaystyle \left(b_{1}-\sum_{j=2}^n u_{1,j}x_j\right)/u_{11}$

と解ける。 要するにこれは Gauss の消去法の後退代入過程と同じである。 この計算は数値的安定性に関しても申し分のないものになっている。

行列 $ A$ の LU 分解 $ A=L U$ があるとき、$ A x=b$ の解は

$\displaystyle x=U^{-1} (L^{-1}b)
$

と書けるので、三角行列係数の方程式

$\displaystyle L y=b,
$

$\displaystyle U x=y
$

を順に解けば得られることが分かる。よって、これは非常に簡単に計算できる。


next up previous
Next: B..5.3 Cholesky 分解 Up: B..5 行列の分解について Previous: B..5.1 LU 分解
桂田 祐史
2012-07-11