線形方程式１２月２２日発表 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