線形方程式
11月24日
今日のテーマ

T
LU 分解と LDL 分解について
•前回(ガウスの消去法)の復習
a11 x1  a12 x2 
 a1n xn  b1
a21 x1  a 22 x2 
 a2 n x n  b2
( 1)
a n1 x1  a n 2 x2 
 ann x n  bn
( 1)
( 1)
(1 )
(1 )
(1 )
( 1)
(1 )
( 1)
( 1)
( 1)
(1)
次のような演算で消去を行い,右上三角行列を作り,方程式を
解く方法
(各係数の右上の添字は消去の過程を表すためにつけたもの)
a

a
m
i
j
i
j 
i
k a
k
j
(
k

1
)
(
k
)
(
k
)
(
k
)
(
i,j
k
1
, ,n

1
)
,m

a
b

b
m
i
i 
i
k b
k
ik
ik /a
k
k
(k

1
)
(k
)
(k
)
(k
)
(k

1
)
(k)
(k)
• LU 分解
(1)
(1)
AA (a
ij )
( 1)
m 21
a21

a11 (1 ) ,
 1

  m21
M 1    m31


 m
 n1
0
1
0
,
0
0
1
0
0
0
0
0
(1 )
a n1
m n1  ( 1)
a11
0

0
0  とおくと

0
1 
とおき
 a11( 1) a12( 1)
 (1)
(1 )
 a 21 a22
(1 )
A 

 a (1) a ( 1)
n2
 n1
a1n 

( 1)
a2 n 


(1 )
ann 
( 1)
M
1A A
(1)
(2)
つまり,消去の第1段は行列 M 1 を左からかけたことに等しい.
第 k段は
1

0

Mk  



0

とおくと
0
0
0
1
 mk 1, k
 mn , k
M
kA A
(k)
1
0
0
(k
1)





 ,


1 
m jk 
a jk
(k )
a kk
( k)
(jk
1
, ,n
)
と表せる
 a11(1) a12( 1)

最終段まで進むと
( 2)

a22
( n)

M
M
M
M
A
U  
n

1 n

2
2 1  A

0


( 1)
a13
( 2)
a 23
( 3)
a33
a1n 
( 2)
a 2n 
( 3) 
a3n 

( n) 
ann 
( 1)
AX  b
の右辺のベクトルb にも同様の操作
(
n
)
を行なえば
M
M
M
M
b

b
n

1 n

2
2 1
AX  b は UX  b(n) となる
M k の逆行列は
Mk
1
1

0





0

0
0
1
mk 1, k
0
1
mn , k
1
0
0
で与えられる(これは Mk Mk I からわかる)








1 

1 
1
1 2

1

1
n

1 n

1
L

M
MM
M とおくと
 1

 m21
m
L   31



m
 n1
LU  M1
1
0
1
m32
0
0
1
0
0
1
mn 2
mn 3
1
M n 1 M n1
mnn 1
0

0
0


0 
1 
M1A
A
であり,これを A の LU 分解という
となる
T
•対称行列の LDL 分解
A の LU 分解を A  LU とするとき
 a11(1 )


D

 0

a22 ( 2)
U  DV
1


V 




v12
v13
1
v23
1
0 




(n) 
a nn 
とおいて
v1 n 

v2 n 
 v
 , kj

1 

akj
(k)
akk
(k )
(k  j )
と表せる
Aが対称行列(A  Aのこと)とする
第(k-1)段までで得られた行列
第k行以下の小行列を
T
 ak ,k ( k ) ak , k 1( k )

(k)
(k)
 a k 1, k
ak 1, k 1
(k )
As  

 a (k ) a (k )
n , k 1
 n, k
とおくと
(k )
As は対称である
A
(k )
の


(k)
ak 1, n 


(k )
a n, n 
ak ,n
(k )
なぜなら,第(k-1)段で行われる変形は
aij
(k)
 aij
であるが, alm aml
(1)

( k  1)
(1)
ai , k  1
( k 1)
ak 1, k 1
( k  1)
ak 1, j
であったから aij
(2)
( k 1)
aji が分かり
(2)
aij aji とつづき aij aji が分かる.ゆえに As は対称
(3)
(3)
vkj 
(k)
(k)
akj
(k )
akk
(k )

a jk
(k )
akk
(k )
(k )
 m jk となり V  LT である.
つまり対称行列は A LDL と分解できる. A  LU ,U  DV
T
より A LDV
これを A のLDL 分解という
T
ダウンロード

LU分解