n$B!_(Bn $B9TNs$r9M$($k!%(B
$B9TNs@Q(B C = A B $B!'(B
($B9TNs(B C $B$N(B i $B9T(B j $BNsL\$NMWAG$r(B c_ij
$B$H=q$1$P(B)
n c_ij = $B-t(B a_ik b_kj k=1
$B9TNs!&%Y%/%H%k@Q(B b = A x $B!'(B
($B%Y%/%H%k(B b$B$N(B i $B9TL\$NMWAG$r(B b_i
$B$H=q$1$P(B)
n b_i = $B-t(B a_ik x_k k=1
$BO"N)0lb $B$KBP$7$F!"(B A x = b $B$rK~$?$9(B $B%Y%/%H%k(B x $B$r5a$a$k!#(B
LU$BJ,2r(B $B$H$O(B
$B9TNs(B A $B$r!"2<;03Q9TNs(B L$B!">e;03Q9TNs(B U $B$r(B $BMQ$$$F(B A = LU
$B$HJ,2r$9$k$3$H!#(B
$B$?$@$7!"(B L $B$K$D$$$F$O(B l_ij
= 0 (1 $B!e(B i $B!c(B j $B!e(B n)$B!$(B
U$B$K$D$$$F$O(B u_ij
= 0 (1 $B!e(B j $B!c(B i $B!e(B n)$B$G$"$k!#(B
LU $BJ,2r$rMQ$$$?O"N)0ly = b $B$r(B y$B$K$D$$$F2r$-!"$5$i$K!"(B U x = y $B$r(B x$B$K$D$$$F2r$/!#(B L, U $B$H$b;03Q9TNs$J$N$G4JC1$K2r$1$k!#(B ( x = U^{-1} L^{-1} b)
l_ii
=1), $B%/%i%&%H(B(Crout)$B7?(B(u_ii
=1) $B%/%i%&%H7?$G9M$($k$H(B A=LU $B$N(B A, L, U$B$N3F@.J,$K$D$$$F(B
j a_ij = $B&2(B l_ik u_kj (i $B!f(B j) k=1 i a_ij = $B&2(B l_ik u_kj (i < j) k=1$B$G$"$k$+$i!"AmOB$N:G8e$N9`$rJ,$1$k$H!"(B
j-1 a_ij = $B&2(B l_ik u_kj + l_ij (i $B!f(B j) k=1 i-1 a_ij = $B&2(B l_ik u_kj + l_ii u_ij (i < j) k=1$B$H$J$j!"$3$l$+$i!"4X78<0(B($B!y(B):
j-1 l_ij = a_ij - $B&2(B l_ik u_kj (i $B!f(B j) k=1 i-1 u_ij = (a_ij - $B&2(B l_ik u_kj) / l_ii (i < j) k=1$B$,@.$jN)$D$3$H$,$o$+$k!#(B
a[i,j]
$B$Na[i+1,j]
a[i][j]
$B$Na[i][j+1]
u_ii
= 1)$B$J$i(B:
l_ij = a_ij^(m) (j=m, i=m,...,n) u_ij = a_ij^(m)/l_ii (i=m, j=m+1,...,n) a_ij^(m+1) = a_ij^(m) - l_ik u_kj (i=m+1,...,n, j=m+1,...,n, k=m)$B%"%k%4%j%:%`$O(B$B$3$N$h$&$K(B$B$J$k!%(B
u_ii
= 1)$B$J$i(B:
for 1$B!e(Bs$B!c(Bm l_ij = a_ij^(s) (i=m, j=s) a_ij^(s+1) = a_ij^(s) - l_ik u_kj (i=m, j=s+1,...,n, k=s) u_ij = a_ij^(m)/l_ii (i=m, j=m+1,...,n)$B%"%k%4%j%:%`$O(B$B$3$N$h$&$K(B$B$J$k!%(B