ガウスの消去法 nt.math.se.tmu.ac.jp.pptVIP

ガウスの消去法 （Gaussian elimination） ガウスの消去法とは…　　　連立方程式系を解く基本的なアルゴリズム 簡単な例 　　　　　 　　　　　 　　 　　　　　 　　 　 これらを方程式を同時に満たす変数の値を求める． 　場合によっては，解がないことや，いくつもあることもある． (例えば のように2つの方程式が矛盾する時や， 　2つの方程式が同じとか，方程式の数より変数の個数が多い時) 　方程式の個数と変数の個数は等しいものとし，解があるときは一意な解を求める． * 方程式に対して解を変えないで実行出来る操作 方程式の入れかえ：明らかに，方程式を書き下す順番は解に影響しない行列の表現では，この操作は行列(と右辺のベクトル)の行の入れかえに対応する． 変数名のつけかえ：この操作は，行列の上では列の入れかえに対応する(列iとjを入れかえた時は変数　と　も入れかえなければならない) 式の定数倍：行列(と右辺のベクトル)上のある行を定数倍する ２つの式の和：２つの式の和をとり、一方の式をその和と入れかえる 例 添字を使って変数名をつける 3つ以上の変数の場合も扱いやすいように 2式=1式-2式 3式=2式-2×3式 3式=1式＋3式 3式より 2式に代入 1式に代入 この例はガウスの消去法の２つの基本的段階を示している． 第１段階は前進消去段階で，系統的に変数を処理していき， 対角要素より下の要素がすべてゼロになるよう変換する． この処理は，三角化とよばれることもある． 第２段階は後退代入段階で，第１段階でえられた三角行列を使って変数の値を計算する． 方法の概略 一般に，Ｎ個の未知数をもつＮ個の方程式からなる解く系を解く これらの方程式は行列を使うと１つの式 すなわち，　　　　　のように書ける．ただし　　は係数行列，　は変数，　は方程式の右辺を表す．　の要素は　　の行と一緒に扱われるので，　を　　の第　　　　　列と　みなし　　　　　　　の行列を用いて両者を保持すると便利である． 前進消去は次のようにまとめられる． はじめに，第１式に適当な数を掛けたものを第１式以外の 各式に対し加えて，第１式以外から第１変数を消去する． 次に，第２式に適当な数を掛けたものを第３式から第Ｎ式の それぞれに対して加えて，第１，２以外の各式から第２変数 を消去する． 次にはじめの３式以外のすべての式から第３変数を消去す るというようにする． 第ｉ変数を第ｊ式　　　　　　　　から消去する時は，第ｉ式を　 　　　倍したものを第ｊ式から引く． この処理は次のコードのようにもっと簡潔に書ける． for (i=1;i=N;i++) for (j=i+1;j=N;j++) for (k=N+1;k=i;k--) a[j][k] -=a[i][k]* a[j][i]/a[i][i]; 　　　　　　　　　　　　　　　　　　　　　　　　　 #計算時間は　　　に比例 　　　　　　　　　　　　　　　　　　　　　　　　 #同じ行の他の要素を計算する前 に # a[i][j]を壊さないよう逆方向に進む a[i][i]はゼロ，またはゼロによる割算が発生した場合は．．． 　　　　　その外側のループでｉ行を適当な(ｉ＋１とＮの間の)行と入れかえて，a[i][i]がゼロでないようにすれば解決 　　(そのような行が見つからないときには，その行列は特異．すなわち一意な解が存在しない) 　第i列の対角要素より下の要素を消去するのに使われる要素a[i][i]を枢軸とよぶ． 実際には，第i列で非ゼロ要素をもつ行を探すだけでなく，第i列で絶対値が最大の要素をもつ行を使うのがよい． 　 なぜなら，行の定数倍に使われる枢軸要素が非常に小さい と，大きな計算誤差が生じることがあるからである． a[i][i]が非常に小さいと，第i変数を第j式から消去する時に 使われるスケーリング因子a[j][i]/ a[i][i]が非常に大きくなる． 実際，それは係数が小さく見えるほどまでに大きくなり， a[j][i]の値が丸め差のために歪んでしまうこともある． 　　 　例：　　0.001　　－6　　=－6.001 　　　　　　3　　+5　　=2 eliminate() { int i,j,k,max; float t;