2005/07/12 数値解析学と演習 福井 先生 前記も、今週、来週になった。 来週は、まとめとテストなので、前記の講議は、今週は最後 == # 今日は、SOR 法 連立一次方程式 Ax = b を解く状況というのは、偏微分方程式 ( 後期の 11 月 ) を解くために利用する ことが多い 解法 (有限) 差分法 -- スパース行列◎ 有限要素法 -- スパース行列◎ => 0 が多いので反復法 境界要素法 -- 密行列 # 係数の計算方法に関しては、その時に話す.. 形状がよければ、バンド行列になるが.. # 二次元だと、それほど 0 が多くないので、スパースを意識した消去法も使われていた # 三次元だと、反復法 反復法 ヤコビ法 並列用途でなければつかわない ガウスザイデル法 普通はこれ SOR 法 ガウスザイデル法の変形 ------------------ ここまでは確定 CG 法 まだ、確立していないので、詳しくは話さない # 二、三年後に内容が変るかも.. == [ガウスザイデル法] ( 先週学んだ ) x_1' = \frac{1}{a_11} ( b_1 - a_12 x_2 - a_13 x_3 ) x_2' = \frac{1}{a_22} ( b_2 - a_21 x_1' - a_23 x_3 ) x_3' = \frac{1}{a_33} ( b_2 - a_31 x_1' - a_32 x_2' ) x_k を利用して x_{k+1} 計算している これを x_{k+1} = x_k + Δx_k と考えることができる。 この差分 Δx_k の前に係数 ω をかけたものを考える x_{k+1} = x_k + ωΔx_k ( 0 < ω < 2 ) # ω=1 の時には、ガウスザイデル法と全く同じ これが SOR ( Successive Over-Relaxation method : 逐次過剰緩和 ) 法 数列が、片側から収束する場合は、ωを大きく取る (ω > 1) と早く収束する 数列が、両側から収束する場合は、ωを小さく取る (ω < 1) と早く収束する # ωが 2 より小さいことが、収束の必要十分条件 (数学的に証明されている : オストロフスキーの定理 : cf バーガ著「大型行列の反復解法」サイエンス社) # ω = 1.8 〜 1.99 程度が一般的 ( 片側から収束することが多い ) # このωの値は、経験的に解る # 計算を繰り返すと、良い数値がわかってくる # あまり「数学的」でない # # この値は、「偏微分方程式」の場合 # # どの値が良いかは、方程式の形による !! # # SOR 法は、「偏微分方程式(流体)」を対象にしていることが多い # 今は、CG 法を使うことが、多いが、好みがあるので.. # 流体では、SOR 法が主流 なぜ、ωをいい加減に決めてよいか ? 結局は、方程式を満す答であればよいので、収束したかどうかが判定可能 !! <=> 常微分方程式などは、誤差が累積することがあり、それを判定できない。 数学的な解析を行う 実験値と比較する 等々、誤差に関する解析が必要 # 最終的に「解かどうかの判定ができる」ことが強い !! # ω は反復回数 ( 実行速度 ) だけに関係し、収束性 ( 答が正いかどうか . ) とは無関係 !! # 計算の途中で、解法を切り替えても問題ない !! == [余談] ソ連の本はぶ厚い => ページ数で報酬が出た 数式が書き下されていた => アメリカで翻訳がすぐに出たので楽は楽だった == 収束判定 # 3, 4 次元なら、目でみれば済むが.. 一億自由度だったらどうする ? 二つの判定方針 |x_{k+1}-x_k| < ε # ノルムによって色々ある # 演算量は n 程度 # 根の桁数が同じならこの「絶対誤差評価」で良いが、根の桁数に差がある場合は、「相対誤差 (= 絶対誤差 / x_k)」を使う必要がある ( ただ、その場合は、 x_k が 0 の近くの時に困るので適当に組み合わせて処理する ) ## 「数値計算において 0 は(良い意味での..)特異点」 ## 0 割の問題もあるが.. ## 0 の囘りでは、精度が上るという性質がある ## cf テーラー展開 f(x)=0 の囘りが精度がよい ## f(x+k) = f(x) + .. ## f(x)=0 だと、高次の項の値が利用されるので、誤差が小くなる |Ax-b| < ε # 演算量は n^2 程度 [評価方法] \sum_{j=1}^n a_ij x_j - b_i < ε_i で評価するが.. ε_i = max( |a_ij xj|, |b_i| ) x 10^q # q は、有効桁数 とすると良い。 # 和の計算をする時には、その内の絶対値の大きいものの影響を受けるので、その項目で考える。 # 計算に無駄がなければ、計算量が多い方が、誤差が多い !! # 本来は前者の方が望ましいのだが... ( 後者でないと駄目な場合がある ) # ( 行列の行ベクトルが.. ) 直交していれば、どちらで行っても同じ 平行に近い場合が問題 交点の近くでは (有限桁の計算のせいで.) ぼけて来る [例] 二次方程式の根が完全に分離している場合 => x 軸とほぼ直交 => 計算は楽 重根の場合 接している所では、答がぼやけてしまう # f(x) で計算すれば、結局はどこでもよいので、構わないのだが.. => 前者の方法では、ε内に入らず、いったりきたりする => 後者の方法を利用する必要がある # 偏微分方程式の場合、差分の値を小くすると結果的に、係数行列が平行に近付くことになるので、このような現象がよく起きる !! # 大きな、「一般的な」行列を解くのは、「演習」の時くらい # 普通は、偏微分方程式なので、一般的な形ではない # 天気予報が正確にできればお金になるのだが.. 正確に求められていない.. # 線型計画法を解く場合は「お金」になる.. # cf. 物流 / 半導体の生産スケジュール # 1 月の予測に 1 週間かかるが、一日でできればとってもお金になる # # カーナビで、交通渋滞を解決するには、高速に答がえられないとだめ == [演習] # 先週、ガウスザイデル法が解けていれば、SOR 法もできると思われる。 # 先週配布した、プリントの問題にする.. 先週配布した p.58 の例題 ωを 1.8 〜 1.9 で試してみる # 効率が悪くても、最悪の場合は、 # ガウスザイデル法で計算し、 # 差を求め # ω倍して足す # 形にすれば、できる 係数 A = ( 5 -4 -2 1 ) b = ( 5 ) 2 3 1 2 21 -2 2 8 2 16 4 1 -3 5 18