直接法で解こうなんて狂気の沙汰だケロ！！ [ひとこと言わねば]
ラプラス方程式
に差分法を用いることによって
と得られる連立方程式をガウス消去法などの直接法で解こうなんて狂気の沙汰と言わざるを得ない。
――時々、こういう無謀なことをしようとする⑨未満がいたりする。さらに、逆行列を利用して解こうとする命知らずさえいたりする！！――
仮にx軸、y軸方向にそれぞれ１００分割すると、未知数の数は、およそ１００×１００＝１万だから、連立方程式の係数行列は１万行×１万列、要素数１億という超巨大な行列になってしまう。しかも、n元１次連立方程式のガウス消去法の計算量はO(n³）だから10000³=10¹²という天文学的な計算量になってしまう。
もっともこの係数行列の圧倒的多数は０なので、計算法を工夫することによって、計算量を大きく減らすことはできるだろう。しかし、この係数行列は帯行列（Band Matrix）――行列の対角成分
のある一定幅（Band）に０でない要素がすべて収まっている密な行列のこと――ではない疎の行列なので、計算の省力化には自ずと限界がある。
だから、こういった連立方程式を解くには、ガウス・ザイデル法やSOR法といった反復法を使ったほうがいいんだにゃ。
――ddt³さんは、「直接法にも、こうした連立方程式を解く、いい解法があります」と反論するかもしれない(^^ゞ――
収束の遅いガウス・ザイデル法はともかく、SOR法の場合、１００×１００程度の分割ならば、収束判定条件にもよるけれど、反復回数が１０００回程度で収束するだろうから、反復法の計算量は１００×１００×１０００＝１千万=10⁷のオーダーでとどまるにゃ。
したがって、計算時間は
直接法は反復法の１０万倍の計算時間を要してしまう！！
計算を工夫することによって仮に直接法が計算速度が１０００倍速くなったとしても、計算時間は直接法：反復法＝１００：１だケロ。プログラムを作ることも容易だし、反復法の優位性は明らかだにゃ。
だから、この問題を直接法で解こうなんてアホウな真似をしてはいけない。
ではあるが、ガウス・ザイデル法やSOR法は、1回の反復で隣接する格子にしか計算の影響が及ばず一般に収束が遅い。
ということで、ラプラス方程式（１）に差分法を用いて得られる連立方程式（２）、または、（３）をより速く解く方法について、次回、考えることにするにゃ。
2017-12-24 12:00
nice!(0)
コメント(3)
自分も5000×5000を越えたら反復派です(^^)。自作のs-オーダリングを使っても、直接法の計算時間は最良で1/100になる程度。という事は、反復法の1000倍くらい。
特に差分法や有限要素法では係数行列が正定値対称になるので、共役勾配法が絶対にお勧め。さらにIndex配列を使用して非零成分だけ記憶し演算量を減らすと、10倍くらい加速させられる。
ところで分割数は、50×50＝2500程度にしませんか？。これならs-オーダリングで加速させると、5分以内を保証します(^^)。
by ddtddtddt (2017-12-25 08:27)
そうそう、なぜ自分が共役勾配法にこだわるかと言いますと、共役勾配法は反復法なんですけど、係数行列の寸法をn×nとすると「理論上はn回の反復で正解に達する」事を証明できるからです(^^)。
イメージとしては、ちょっと複雑なグラム・シュミットの直交化って感じです。ただし共役勾配法は、丸め誤差や桁落ち誤差に非常に弱いといわれていまして、そのために計算を安定させる前処理部分がけっこう鬱陶しかったりします(^^;)。
でも使ってみると経験的には、少なくとも正定値対称行列に対しては前処理なしでも、十分行けます。非常に悪条件な特異に近い係数行列についても試した事がありますが、大丈夫でした。
by ddtddtddt (2017-12-25 18:04)
コメントありがとうございます。
共役勾配法は専門家の方法ですよ。数値計算の初心者向けの解法ではないと思います。
今回、取り上げた差分法を用いたラプラス方程式の解法の場合、実質、使用する係数は５つだけですから、シンプルなガウス・ザイデル法やSOR程度で十分だと思います。計算格子の数が５０×５０程度ならば、ガウス・ザイデル法であってもリターンキーを押した瞬間に計算が終わってしまいますからね。
ただ、SORで、１００×１００で計算したとき、すぐに答えが出なかったので、
――それでも数秒から１０秒くらい――
「これくらいになると、この方法（SOR）ではまずいのか」と強い不安に襲われました(^^ゞ
明日から、３回にわたって、差分法を用いた２次元非定常熱伝導方程式の解法をやりますが、とある条件の場合、陽解法の解法と反復法の一つであるヤコビ法は一致し、一回反復することとタイムステップを１つ進めることが同じ作業であるということを少し話します。ですから、むしろシンプルな反復法の方が都合がいい(^^)
by nemurineko (2017-12-25 18:54)