線形方程式 12月22日発表 1 今回のテーマ 正定値対称行列について コレスキー法 反復法について ヤコビ法 ガウス・ザイデル法 SOR法 2 1.正値対称行列 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(,kk11) i , j k ak( k1,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( k1,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(,kk11) ( 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 2.反復法 方程式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に各段階で得 られている最新のデータを代入するようにしたものが ガウス・ザイデル法である. 第1行目は x ( k 1) は同じ 1 (k ) 第2行目は 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 ) ) この2式から ( 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 D1 ( E F ) ガウス・ザイデル法 M G ( D E ) 1 F SOR法 M ( I D 1E ) 1{(1 ) I D 1F} 12
© Copyright 2024 ExpyDoc