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

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

$$U x=b$$

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

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

は下の方程式から順に

$$x_n = b_n/u_{nn},$$

$$x_{n-1} = (b_{n-1}-u_{n-1,n}x_n)/u_{n-1,n-1},$$

$$\vdots$$

$$x_{i} = \left(b_{i}-\sum_{j=i+1}^n u_{i,j}x_j\right)/u_{ii}$$

$$\vdots$$

$$x_{1} = \left(b_{1}-\sum_{j=2}^n u_{1,j}x_j\right)/u_{11}$$

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

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

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

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

$$L y=b,$$

$$U x=y$$

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