2005/06/21 数値解析学と演習 福井 先生 今週からしばらく「連立一次方程式の解法」を学ぶ。 == 連立一次方程式の解法 Ax = b 数学的には、「クラーメルの方法」が知られている x_i = \frac{det A_1}{det A} # 直接法 この方法は、数値計算の世界では使えない # why ? => 計算量が多いから.. クラーメルの方法の計算量 det A に O(n^3) なので、n 個の解を求めるのに O(n^4) かかる => これから学ぶ「ガウスの消去法」だと、O(n^3) で良い # n が小ければ別にどうでもよいが、いまの PC ( cf. 512M ) なら、n=800 位まで Okey なので、n^3 と n^4 では、800 倍違うことになる !! # text p.148 「方程式を解く」ということは ? a_11 x_1 + a_12 x_2 + a_13 x_3 = b_1 a_21 x_1 + a_22 x_2 + a_23 x_3 = b_2 a_31 x_1 + a_32 x_2 + a_33 x_3 = b_3 から、 a_11' x_1 + 0 x_2 + 0 x_3 = b_1' 0 x_1 + a_22' x_2 + 0 x_3 = b_2' 0 x_1 + 0 x_2 + a_33' x_3 = b_3' 形に「変形」できれば良い。 そうすれば、 x_1 = \frac{b_1'}{a_11'} x_2 = \frac{b_2'}{a_22'} x_3 = \frac{b_3'}{a_33'} で解ける。 # では、闇雲にやってよいか ? # cf. a_ii 以外を無条件に 0 にする !! # a_11 x_1 + 0 x_2 + 0 x_3 = b_1 # 0 x_1 + a_22 x_2 + 0 x_3 = b_2 # 0 x_1 + 0 x_2 + a_33 x_3 = b_3 # これは、(おそらく..) 答が変ってしまう => 駄目 # => 方程式の答を変えず、要素を 0 にするような「操作」が欲しい.. # => あるか ? .. 実はある 「行列の基本操作」 「一つの行の定数倍を他の行から引き算する」という操作 方程式の根を変更せずに、係数を書き換える操作 => 「線型代数」で学んでいるはず !! # 二行目に一行目をα倍した数を引いてみると... (α_1 a_11 + a_21)x_1 + (α_1 a_12 + a_22)x_2 + (α_1 a_13 + a_23)x_1 = (α_1 b_1 + b_2) α_1 を上手く設定すれば、どれか一つの項を 0 にできる # 全部 0 になったら、Rank 落 !! この α_1 を上手く利用することにより、必要な場所の係数を 0 に変形して行く => ガウスの消去法 # 消す順番を工夫すれば、一旦 0 にした項目は 0 のまま.. # 結局、定数回数で答を得ることができる : 直接解法 方程式の解法 直接法: 「ガウス系統」 クラメール : n^4 ガウスの消去法 : \frac{2}{3}n^3 => \frac{1}{3}n^3 までできる 反復法: いくつかある ( 来週からやる ) ガウスの消去法 : 作成されたのは 19 世紀 その後、色々な解法が考えられたが.. 結局、ガウスの消去法が一番 !! # ガウス=ジョルダン法 # 色々な変形はあるが... ガウスの消去法の系統の色々なアルゴリズム 大雑把にいって、各々の係数を計算するのに.. 行方向の loop と列方向の loop の二つの loop が必要 更に、一つの係数のために、loop が一つ => 三重 loop になる 三つの loop の index 変数 ( 例えば, i, j, k ) の回す順番が異る # その他に、対称行列用もある.. => それだけで六通りもある.. # その他、細かい変形もある.. # 色々あっても、結局は、ガウスの消去法の変形といえる.. ## アルゴリズム的には、例外処理が異るので違うように見えるが.. ## => 結局は、「行列の基本操作」の繰り返し !! # メモリアクセス等の関係から、計算機によって、速度が変ったりするが、数学的には全く同じ !! # ガウスの消去法に関しては、これだけが本質 ## 昔、実際に、全ての解法を作って、試してみた !! ### => クラーメルの方法も色々あるが、結局は、ガウスの消去法 本質的な性質 「方程式の解を変えず、変形する方法がある」 ということ !! # この「基本操作」は、「連立方程式の解法」に対してのみ有効 ## 他の問題 ( cf. 固有値 ) では、他の解法が必要 !! クラーメルの方法は、良い方法だが、効率が悪い ガウスの消去法を越る「直接法」は他に出てこないだろう ? => 基本操作が他にない ガウスの消去法は、単純なことしか行っていない # 姑息な方法は色々あるが、結局、捨てられる.. 反復法は、まだ、色々出でくる可能性がある # 色々出てきるのは「これだ」という方法がないため.. Q. 何故、「直接解法」があるのに、「反復法」が必要か ? A. 行列の性質による 密(デンス)行列は、もう、直接解法で決り 疎(スパース)行列の場合は、反復解法が有利に.. 例 : 偏微分方程式の数値解法(差分近似)など 「近接効果」なので、近接する要素だけが 0 でない ( 遠くの場所は、影響を被らないので、係数が 0 になる ) => 連立方程式の係数が殆ど 0 # 疎行列で、基本操作をすると、折角 0 になっていた係数が 0 でなくなる ( fill-in ) という現象が生じる # 結局、0 の所の計算も必要 # 反復法の場合は 0 の所の計算をしなくて済む工夫が可能 # => 0 の所がおおければ多い程、計算が少くて済む !! ## 疎行列の場合に、直接法が使えないわけでないが、得をしない ## => 反復法であれば疎行列の旨味を使うことができる !! 疎(スパース)行列の計算例 n = 10^8 # これは、直接法では、解けない !! ( メモりに入りきらないから.. ) == [まとめ] 直接法は、ガウスの消去法で決り ガウスの消去法は、色々な変形が考えらえるが、殆ど、実行順序を変ているだけ ! 密行列の解法は、ガウスの消去法でやる。ただ、疎行列の場合の場合は、反復法が出てくる == ガウスの消去法 ( ガウス=ジョルダン法 ) の高速化 # 基本操作で、(必要とする対角要素以外の..)全ての係数を消す方法 # => ガウス=ジョルダン法 (ガウスの掃き出し法) # これを改良する。 前半は同じ ( 下半分の係数を 0 にする ) => 前進消去 : \frac{1}{3}n^3 : 三角錐の体積 # 上半分も、同じ方法だとすると、同じ (\frac{1}{3}n^3) だけかかる # (後退消去) 後半は、係数を消す代わりに、得られた解を用いて、代入しながら他の解を求める => 後退代入 : \frac{1}{2}n^2 : 三角形の面積 # 全体では、\frac{2}{3}n^3 と \frac{1}{3}n^3 + \frac{1}{2}n^2 の差 => ガウスの消去法 # ガウスは、計算機のなかった時代に考えた # => 手で計算していたので、できるだけ少い方法を考えたのだろう.. # 計算機でやっていると \frac{1}{3}n^3 と \frac{1}{2}n^2 は、それほど差がない。ところが、手計算だと、えらく違う.. == 昔の人は、「(掛け算より..)割り算は遅い」という思い込みがある # (手回し計算機である..)タイガー計算機で、割り算をしてみると、凄い差がある !! ## 昔の計算機は、確かに、掛け算より割り算がおそかったが、いまの計算機は、ほぼ、同じ位の速度なので、あまり気にしてもしょうがない。 == [演習] 課題 : ガウス消去法 text p. 149 の上の係数を入れる 2x+4y+6z=6 3x+8y+7z=15 5x+7y+21z=24 # text が間違っている !! ( 2x => 2z ) == [行列の種類] 実数係数 / 複素係数 : この二つはあまり差はない。 密行列と疎行列 : これは大きく違う 対称と非対称 : 構造があるかないか 工学の世界では、対称行列が良くでてくる 「保存則」が成立する世界の行列は、対称になる # 色々な理由で、わざと、非対称にすることはあるが、自然なのは、対称行列の形 # 密行列では、一般に非対称を考える 疎(スパース)行列 帯(バンド)行列 ( 構造をもっている.. ) 元のモデルが構造をもっており、その影響を受けている ランダムスパース行列 # 対角要素は、自分との関係を表すので、普通はある # => 対角要素以外の要素がランダムで 0 でない => ネットワークの接続関係 ( LSI の設計 ) などがランダムスパースになりやすい。 # 密は、直接、疎は、反復。帯行列は、直接でもできるが、ランダムは反復でしかできない.. == [枢軸選択の問題] 最後に答を求めるには、割り算が必要 対角要素が 0 になったら => そのままでは解けない 元々解けない可能性がある : Rank 落 ( 答は不定か不能 ) 逆に解があれば、行を入れ替えることにより解ける => 枢軸選び問題 == [逆行列] Ax=b を x=A^{-1}b として解くのは.. ? 数値計算の世界では「禁止」 計算量も多い / 誤差も大きい # 統計等の目的で、逆行列の要素が直接調べたいのであれば話は別だが.. # 連立方程式を解くために逆行列をもとめてはいけない 係数が共通で、定数項が異る連立方程式が沢山ある場合は ( 一度、逆行列を計算しておけば、なんども利用できるので.. ) 逆行列を計算する方法が望ましいように思えるが.. => 来週やる LU 分解を使えば、同じ問題を逆行列を求めるより「良い」解法が得られる。