Next: 4 練習 Up: 計算天文学 II 第4回楕円型方程式 Previous: 2 線形方程式と反復法

3 もっと高度な解法

天文等で出てくるポアソン方程式の場合には、特にうまく $\omega$ を決められれば SOR で非常にうまくいくことが多い。が、まあ、世の中はそういう問題ばかりでもないので、それ以外の方法を紹介だけしておく。

3.1 ADI

ADI は alternating direction implicit の略である。ここでの基本的な考察は、「3重対角なら簡単に解ける」ということである。これを使って、方向と方向を交代で解いているうちになんとかなって欲しいというのが ADI の考え方ということになる。

もうちょっとちゃんと書いてみると、例えば方向に解くときには、

$\begin{displaymath} \frac{u_{i,j+1}^{new}+u_{i,j-1}^{new}-2u_{ij}^{new}+u_{i+1,j}+u_{i-1,j}-2u_{ij}} {\Delta x^2} = \rho_{ij} \end{displaymath}$

(14)

となる。ここで、 new とつけたのが更新後の値で、これを

から順に解いていく。

方向が終ったら次は

方向をやる。

ただし、実際に使う上では、 SOR と同じように、修正量の補正をしたほうが収束が速い。 SOR とは逆に修正量をすこし減らす必要があり、どれくらい減らすべきかを決めるのにはまたややこしい理屈がいる。

ただし、適当に修正量を決めても最適な SOR よりも遅くはない程度で収束するという利点がある。

3.2 共役勾配法

共役勾配法は、実は、現在大規模な行列を解くのにはもっとも広く使われている方法である。これは、特にいろいろな前処理と組み合わせることで、例えば拡散方程式の定常問題で拡散係数が空間に強く依存する場合にも収束させられるとか、刻みを場所によって変えるような高度な方法でも同様になんとかできるとかいう利点があるからである。

しかし、これは安直にプログラムを書いただけではこれまでの紹介してきた方法に比べて速くなくて、いろいろ高度な変形をして初めて速くなる。また、ほとんど共役勾配法だけについて議論した良い教科書がいくつもあるので、ここでは省略する。ここでは、とりあえずそういう名前のものがあるということくらいをちょっと憶えておいてほしい。

とはいえ、極めて重要な方法ではあるので、これについては、もうちょっと数学的な準備をした後でもう一度やることにする。

ポアソン方程式を解く方法の一つで、応用上は重要なのはフーリエ変換を使った方法である。いま、固定境界をやめて周期境界条件でいいことにすると、ポアソン方程式の場合、 $\rho$ をフーリエ級数展開して、出てきた係数に $1/k^2$ ( は波数)を掛けてから逆フーリエ変換すればポアソン方程式の解になっているわけである。固定境界なら $\sin$ 関数だけで展開すればよい。フーリエ変換の計算量は多次元でも格子点の総数をとして $O(n\log n)$ の程度なので、これは反復法でいうと回数がせいぜい $\log n$ で済むということに相当する。