連立1次方程式の数値解法の使用条件

質問

数値計算で物理現象を解いていく問題では多くの場合、最終的には大規模な連立1次方程式を解くというところに行きつきます（行列を解く）。その場合、解く物理問題によって行列の形式が決まってくる場合とか、あるいはその性質は期待できない問題とがあると思います。例えば、行列が必ず（正値の？）対称行列になることがわかっている問題とか、です。では行列の性質を期待しない場合の高速解法にはどのようなものがあるでしょうか。ガウスの消去法はまるで紙と鉛筆で解いていくことをプログラミングしたようなところがあります。ピボットの問題とかはありますが。でもたぶん遅いんだろうなあとは思いますが。

教科書を読んでみるとだいたい、細かい解説が書いてありますが、ユーザという立場からは内容はどうでもいいから、自分の問題に対して早くて正確な解を得る方法だけ教えて欲しいと思うのですが。共役勾配法を使った計算例があったので、勉強してプログラムを作って走らせてみたら全く結果がおかしいのですが、よく読んでみたら、共役勾配法は正値対象行列に限定だそうで、がっかりしました。

行列の性質を限定しない高速解法にはどのようなものがあるのでしょうか。なお、よく問題になる条件数の問題とか10^10と10^(-10)が係数に含まれるとかいろいろ問題がありますが、今回の問題としてはそのような極端なことが起こらないということではあります。共役勾配法はいろんなファミリーがありますが、その中で正値対象行列でなくてもいいというものあるでしょうか。解説書には解法の冒頭に書いてもらいたいものですが。
よろしくお願いします。

回答No.2

ddtddtddt

やはり#1さんの仰るように、万能選手はいません。ケースバイケースが基本です。

　使用条件の中で自分の経験で一番広いと思えるのは、係数行列が疎行列です。多くの偏微分方程式の数値解法では、近似を用いて離散化すると、非零要素数が係数行列の全要素数の1%にも満たないのが普通です。

　そういう場合ガウス法でも色々やりようはあります。最も基本的には、Active列の零要素の掃き出しは省略できる、です。ただ掃き出しを進めて行くと、疎行列は急速に密化します。そこで昔は、できるだけ密化が遅れるようにあらかじめ行番号と列番号を付け変えて、できるだけブロック化してからガウス法を行う、という事もやられていたようです。

　個人的経験では、Active列の非零要素数がActiveブロックの行寸法の5%を越えた時点で、非零要素数の昇順に列を並べ変えるだけで、50%くらいのスピードアップをはかれます。じっさいにランダムに発生させた疎行列で、試して確認しました。

　さらにActive行の非零要素の演算を省略するために、Index配列を用意する手もあります（Active行の非零要素の列番号をおぼえておく）。ただしIndex配列を用いると、配列へのアクセス数は逆に増えるので、演算の省略効果とのトレードオフを考慮して使う必要があります。係数行列に対称性が期待できる場合は、Index配列の作成は格段に効率化されます。

　ガウス法は確かに大規模行列では遅いです。演算数は行列寸法nの3乗に比例します（密行列では）。疎行列であっても、nが5000を越えたら共役勾配法に切り変えたくなります。

　正定値対称に限らない共役勾配法はあったと記憶していますが、調べてみないとわかりません(^^;)。係数行列を「正定値対称部分＋残り」に分解するとか、そんな感じだったような・・・。

　分解すると言えば、優対角（対角成分付近の要素絶対値が大きい）なら、対角成分付近だけ考慮して残りは無視して解き、残差は繰り返し計算で補正する系統の解法もあります。

　あと固有値解析を利用する方法も。固有値，固有ベクトルの計算は、全部やったら直接解くより不経済ですが、最大もしくは最小固有値の10数個くらいだけが重要とわかってるケースです。10数個の固有値と固有ベクトルだけ求めて、固有ベクトルの重ね合わせで解を近似するとか。

　対称行列の固有値解析は、ハウスホルダー前処理付きスツルム・リュービル・バイセクションで固有値を求め（必要個数）、原点移動付き逆ベキ乗法で固有ベクトルを計算、が自分の時代は標準でした。逆ベキ乗法には、共役勾配法も使えます。またはサブスペース法でした。非対称なら、QR分解です。

　要するに、あの手この手を駆使します(^^;)。

回答No.1

f272

どういう解法が適しているのかは問題によって異なります。直接法(ガウスの消去法など)が最も速くて精度がよいなんていう状況もあるのです。
私がよく解く問題では代数的マルチグリッド法のバリエーションを使っていますが...

お礼

回答ありがとうございます。問題としてマトリックスの性質に期待しないという前提だとしたらどうなるでしょうか。代数的マルチグリッド法というのはマトリックスの性質を利用した解法でしょうか。私の立場としては、マトリックスＡとベクトルＢだけを与えてＡＸ＝Ｂが解けるという前提だけでやるという場合です。Ａ，Ｂとも乱数で発生させてもいいぐらいです。そのような状況での解法ということなのですが。ガウスの消去法しかないのでしょうか。