Next: ピボット付きLU分解を求めるコマンド Up: LU分解法 Previous: LU分解法

 

LU分解とは何か

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

 
Ax=b (5)

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

A=LU (6)

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

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

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

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

が成立することである。行列ALU分解されると 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(n2)回の 浮動小数点数演算でできる。こうして、yが求められたならば、

Ux=y (11)

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



s oishi
2000-05-04