線型方程式 - Tools on Number Theory

線型方程式
吉水由美
•発表内容
線型方程式について学んできた中で，
LU分解と反復法の最初の部分について
発表しようと思います．
•ガウスの消去法について
a11 x1  a12 x2    a1n xn  b1
(1)
(1)
(1 )
(1 )
a21 x1  a22 x2    a2 n xn  b2
(1)
(1)
(1 )
(1 )

(1)
(1)
(1 )
(1 )
an1 x1  an 2 x2    ann xn  bn
次のような演算で消去を行い，右上三角行列を作り，
方程式を解く方法
（各係数の右上の添字は消去の過程を表すためにつけ
たもの）
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
ik
ik /a
k
k
i
i 
ik b
k
(k

1
)
(k
)
(k
)
(k
)
(k

1
)
•ガウスの消去法の演算回数
n1

k 1
1 3
(n  k )( n  k  2)  n  O(n 2 )
3
3
(
1
3
)
n
より，約
回の乗算と加算が必要
(k)
(k)
• LU 分解
AA (a
ij )
(1
)
(1
)
( 1)
m 21
a21

a11 (1 )，
 1

  m21
M 1    m31


 m
 n1
0
1
0
0
0
0
1
0
0
0
0
(1 )
a n1
m n1  ( 1)
a11 とおき
，
(1 )
(1)

a11 a12
0

 (1 )
(1 )
0
a
a

(1 )
21
22

A 
0



0

 a (1 ) a (1 )
1  とおくと
n2
 n1
 a1n 

(1)
 a2 n 

 
(1 ) 
 ann

M
1A A
(1)
(2)
つまり，消去の第１段は行列 M 1 を左からかけたこと
に等しい．
(1 )
第 k段は  1
0

Mk  



0

０
0
0
1
 mk 1, k
 mn , k
1
0
0



(k )
a jk

 ， m jk 
( k)

a
kk

 (jk
1
, ,n
)

1
(k)
(k
1) と表せる
とおくと MA
A
k
最終段まで進むと
(n)
M
M
M
M
A

A
n

1 n

2
2 1
 a (1)
 11


U  
０




(1)
a12
(1)
a13
( 2)
a22
( 2)
a23
( 3)
a33
a1(1n) 
 a2( 2n) 

 a3(3n) 


 
(n) 
ann


AX  b の右辺のベクトル b にも同様の操作
M
M
M
b

b を行なえば
n

1
n

2 M
2
1
(n)
UX

b
は
となる
AX  b
(
n
)
M k の逆行列は
Mk
1
1

0





0

０

0
1


mk 1,k

1
0

0
mn,k
0

1








1

で与えられる（これは Mk Mk I からわかる）

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
0


1
0


m32

1

0


0


mn 2
mn 3
1
1

M n 1 M n1
mnn 1
0

0
0


となる
0

1

M1A
A
であり，これを A の
LU分解という
•LU分解に必要な演算回数
計算時間の大部分はLU分解の過程で費やされる．
そこで必要な回数は
n 1 n
n
1 3
2
  1  n  O ( n )
加減算の回数：
3
k 1i k 1 j k 1
乗算の回数：
n 1 n
1 3
2
  (1 1 )  n  O ( n )
3
k 1i k 1
j  k 1
n
したがって，LU分解の過程で，加減算と乗算それぞれ
3
(
1
3
)
n
約
回必要になる．
そして，LU分解された行列を使って右辺ベクトル b の
異なる複素組の連立１次方程式を解くときには，1組の
方程式あたり約 n 2 回の加減算と乗算がそれぞれ必要
になる．
•対称行列の LDLT 分解
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 


，
1 
とおいて
vkj 
akj
(k)
akk
(k )
(k  j )
と表せる
Aが対称行列（A  A のこと）とする
T
第（ｋ－１）段までで得られた行列 A( k ) の
第ｋ行以下の小行列を
 ak ,k
ak , k 1

(k)
(k)
 a k 1, k
ak 1, k 1
(k )
As  

(k )
 a (k )
a
n
,
k
n , k 1

(k )
とおくと As ( k ) は対称である
(k )


(k)
ak 1, n 


(k )
a n, n 
ak ,n
(k )
なぜなら，第（ｋ－１）段で行われる変形は
aij
(k)
 aij
( k 1)

ai , k  1
( k 1)
ak 1, k 1
( k  1)
ak 1, j
であるが，alm aml であったから aij
(1)
(1)
aij aji とつづき aij aji
(3)
vkj 
(3)
(k)
akj
(k )
akk
(k )

a jk
(k )
akk
(k )
 m jk
(2)
( k 1)
aji が分かり
(2)
(k)
が分かる．
(k )
ゆえに
は対称
As
T
となり V  L である．
T
A
LDL
つまり対称行列は
と分解できる．
これを A の LDLT 分解という
• LDLT 分解に必要な計算回数
分解の過程で必要な計算回数は
n k 1
加減算の回数：
1 3
2
  i   k  n  O(n )
6
k 1i 1 k 1
n
k 1 i 1  1 3
2
n  O(n )
乗算の回数：     2 1 
k 1 i 1
j 1 
6
n
したがって，分解の過程で，加減算と乗算それぞれ
3
約 (1 6) n 回必要になる．
そして，分解された方程式を解くときには，
約 n 2 回の加減算と乗算がそれぞれ必要になる．
•反復法とは…
ガウスの消去法をまともに解くと，大きい行列では計
算回数が多くなってしまう．
このため，適当に近似を繰り返していくことで解を求め
ることはできないだろうか，ということが考えられてきた．
連立方程式
Ax  b
で，真の解を x ，ある計算により n 回目で求めら
れたものを x (n )とする．計算回数を増やして
lim x( n)  x
n
となったとする．
このように計算回数を増やして，真の解に近づける
方法を反復法という．
•解の収束の条件
Ax  b ・・① を同値な x  Mx  c ・・② に変形する．
x ( k 1)  Mx( k )  c
・・③ が
(0)
x
適当な初期値
から出発して計算をしていき，
①の解
x に収束すればよい．
x
Ｋ回目の計算誤差を
e ( k )  x ( k )  x とおく．
③から②を引くと
x
( k 1)
e
 x  M (x
( k 1)
 Me
(k )
(k )
 x)
一般には初期値 x ( 0 ) は任意に選ぶので，その誤差
e
(0)
x
(0)
x
(k )
は０ではない．反復とともに x が x に収束するため
には， e (k ) が反復とともに０に収束しなければならない．
そのためには反復行列Mの固有値の絶対値がすべて
１より小さくなくてはならない．
Mの固有値がすべて１より小さければ，反復と共に誤差
は e ( k 1)  Me ( k ) にしたがって減少し，０に収束する．
( k 1)
(k )
すなはち，x
 Mx  c が収束するための必要
十分条件は，反復行列Mのすべての固有値の絶対値
が１より小さいことである．
•ヤコビ法
非対角成分に相当する項をすべて右辺に移項した
次の形において反復を行う方法をヤコビ法という．
( k 1)
1
x
x2
( k 1)
1 

11 
1


a
a
b  (a12 x2
(k )
1 

22 
2


(k )
21 1
1 

nn 
n


(k )
n1 1
b  (a x
 a13 x3
(k )
 a23 x3

(k ) 

1n n


 a x
(k )

(k ) 

2n n


 a x

xn
( k 1)
a
b  (a x
行列で表すと
すなわち
x
( k 1)
D

1 



 a n 2 x2
(k )
 a
b  (E  F ) x

(k ) 



x ( k 1)   D 1 ( E  F ) x ( k )  D 1b

(k ) 

nn 1 n 1


x
ただし
 0

 a11





 a21 0

a22


a

E

a
0
D
31
32




 


 




a
nn


 an1 an 2   0 
 0 a12

0

F  



a13  a1n 

a23  a2 n 
0
 
  

0 
まとめ
ガウスの消去法よりも計算回数が少なくてすむ方
法がいくつかあることがわかりました．
線型方程式については，たくさん学ぶことがありま
す．今後の課題としては，行列の固有値問題につ
いて学んでいきたいと思います．
ガウスの消去法についての説明や，コレスキー法，
反復法など今まで学んできたことはホームページ
に載せてあります．
http://tnt.math.metro-u.ac.jp/labo/grad/2004/yumi

Download Report