線形方程式 - Tools on Number Theory

線形方程式
１２月２２日発表
1
今回のテーマ
正定値対称行列について

コレスキー法
反復法について



ヤコビ法
ガウス・ザイデル法
SOR法
2
１．正値対称行列
Aが実対称行列で，任意の X  0に対して
n
T
をみたすとき正定値という．
X AX   a x x  0
i , j 1
As
(k )
 aij
(k )
n

i , j  k 1
(k )
 (aij ( k ) )
(k  i, j  n)
n
ai(,kk11)
i , j k
ak( k1,1k)1
xi x j   (aij ( k 1) 
i , j k

j
も正値対称行列である．
なぜなら，As
n
ij i
aij
( k 1)
xi x j 

( k 1) 
a k 1,k 1 



ak( k1,1j) )xi x j
xk 1 
n a ( k 1)
i ,k 1
 ( k 1)
i  k ak 1,k 1
3


xi 



2
(k )
(k )
したがって，いま行列 As  (aij ) が正定値でない
と仮定すると
n
xk 1  
ai(,kk11)
( k 1)
i k ak 1,k 1
xi 0
( k 1)
を満たす xk 1 をとれば As
もまた正定値でないことに
なる．
この論法を続ければ結局 A  A (1)が正定値でないことになっ
て矛盾する．
したがって， As
(k )
, k  1,2,, n は正定値である．
4
•コレスキー法
Aが対称行列のならば A  LDLT と分解できた．
T
T
T
(k )




X

1
0

0

x
x

x
X
A
X
Aが正定値ならば
に
s
k
k 1
n
を代入して akk ( k )  0 がわかる．
1/ 2
D

 a11(1)

 



a22 ( 2)

ann ( n )








とおき S  D1 / 2 LT とおくと A  LD1 / 2 D1 / 2 LT  S T S
これをコレスキー分解という．
5
 s11

Sは右上三角行列で

S 



s12  s1n 

s22  s2n 
  
snn 
T
とすると，S S  Aは成分表示で s1i sij  s2i s2 j    sii sij  aij (i  j )
となり，これから次の関係式が得られる．
sii 
i 1
aii   ski2
k 1
i 1
sij  (aij   ski skj ) / sii
k 1
( s11  a11 )
( s1 j  a1 j s11 )
この式によって s11  a11 を出発値として
T
s
の順にSの成分を求めることができる．Sが求められればも
T
求まり s y  b, sx  y によって Ax  b の解が得られる．
これをコレスキー法という．
6
２．反復法
方程式Ax  bをそれと同値な x  (x)  Mx  c なる形に
( k 1)
(k )
 (x
)
変形し，初期値 x 0 から出発して逐次代入 x
を行って解を求める方法が反復法である．
与えられた行列Aを，
対角成分のみから成る対角行列D ，左下三角行列 E ，
および右上三角行列 F ，の和に分解しておく．
A=D + E + F
 a11



a22


D





ann 

 0

 a21
E   a31
 

 an1
0
a32
an 2
 0 a12



0


 F 
0


 



  0 

a13  a1n 

a23  a2 n 
0
 
  

0 
7
・ヤコビ法
非対角成分に相当する項をすべて右辺に移項した次
の形において反復を行う方法をヤコビ法という．
x1( k 1)  a11
1 

 1


b  (a12 x2
(k )

1 

 2


(k )
1 

nn 
n


(k )
n1 1
x2 ( k 1)  a22

 a13 x3( k )    a1n xn ( k ) 
b  (a21 x1

 a23 x3( k )    a2 n xn ( k ) 


xn
( k 1)
a
行列で表すと
x
( k 1)
D
b  (a x

1 



 a n 2 x2
b  (E  F ) x
(k )
 a

(k ) 

nn 1 n 1


x

(k ) 



すなわち
x ( k 1)   D 1 ( E  F ) x ( k )  D 1b
8
・ガウス・ザイデル法
ヤコビ法においてすべての量 x1 , x2 ,, xnに各段階で得
られている最新のデータを代入するようにしたものが
ガウス・ザイデル法である．
第１行目は x ( k 1) は同じ
1
(k )
第２行目は x2 ( k 1) においてヤコビ法の計算の a21 x1 を
( k 1)
x1( k 1)
で計算済みなので
a21 xに変える．
1
x j (k 1)  a jj
1 

 j


( k 1)
b  (a j1x1

  a jj 1x j 1(k 1)  a jj 1x j 1(k )   a jn xn(k ) 

行列で表すと
x ( k 1)  D 1 (b  Ex ( k 1)  Fx ( k ) )
すなわち
x ( k 1)  ( D  E ) 1 Fx ( k )  ( D  E ) 1 b
9
・SOR法（加速緩和
法）
ガウス・ザイデル法において各段階で計算された値 x j
( k 1)
を
次の段でそのまま採用せずに，ガウス・ザイデル法で本来修正
( k 1)
 x j ( k ) に加速パラメータ ( 1) を乗じてこの
される量 x j
修正量を拡大し，これを前段で得られている近似値に加えるの
がSOR法である．

( k 1)
 j ( k 1)  a jj 1 b j  (a j1 x1

xj
(k )
 xj
(k )

   a jj 1 x j 1( k 1)  a jj 1 x j 1( k )    a jn xn ( k ) 

  ( ( k 1)  x j )
(k )
10
行列で表すと
 ( k 1)  D 1 (b  Ex ( k 1)  Fx ( k ) )
x ( k 1)  x ( k )   ( ( k 1)  x ( k ) )
この２式から  ( k 1) を消去すれば次の式を得る
x
( k 1)
1
 (I  D E)

1 



1

 (k )



(1  )I  D F x
 (D  E)1b
11
•反復行列
これらの三種類の反復法はいずれも
x ( k 1)   ( x ( k ) )  Mx ( k )  Nb
の形に表現されている．行列Mを反復行列という．
各反復法における反復行列は次のようになっている
ヤコビ法
M j  D1 ( E  F )
ガウス・ザイデル法 M G  ( D  E ) 1 F
SOR法
M   ( I  D 1E ) 1{(1   ) I  D 1F}
12

Download Report