LU分解とは何か

Aを $n \times n$行列、bをn次元ベクトルとするとき、行列方程式

 

Ax=b (5)

をLU分解法で解くことを考えよう。 行列AのLU分解とは、行列Aを三角行列Lと上三角行列Uの積で

A=LU (6)

と表すことである。ここで、 $n \times n$行列Lが下三角行列とは、行列Lの 第i-j成分をL_ijと書くとき、

$$L_{ij}= 0~~(\mbox{$i>j$ のとき})$$ (7)

が成立することである。また、 $n \times n$行列Uが上三角行列とは、行列Uの 第i-j成分をU_ijと書くとき、

$$U_{ij}= 0~~(\mbox{$i<j$ のとき})$$ (8)

が成立することである。行列AがLU分解されると 2.5は次のように解かれる。

Ax=LUx=b (9)

より、y=Uxと置いて、まず、

 

Ly=b (10)

を解く。三角行列を係数とする方程式2.10は容易に解くことができる。 実際、 $y=(y_1,y_2,\cdots,y_n)$とするとき、2.10を $y_n,y_{n-1},\cdots,y_1$の順に解いていけばよい。この計算はO(n²)回の 浮動小数点数演算でできる。こうして、yが求められたならば、

Ux=y (11)

を解いて、xを求めればよい。この計算もO(n²)でできる。