next up previous
Next: 3 ツリー法の原理 Up: 計算天文学 II 第10回 データ構造とアルゴリズム(1) Previous: 1 データ構造

2 重力多体問題

対象となる問題は、重力多体問題である。これはつまり沢山の質点がお互いに 重力で引き合って運動するというもので、星団、銀河等の基本的なモデルである。

運動方程式は

\begin{displaymath}
{d^2 \mbox{\boldmath$x$}_i \over dt^2} = - \sum_{j\ne i, 1\...
...er \vert\mbox{\boldmath$x$}_j - \mbox{\boldmath$x$}_i\vert^3},
\end{displaymath} (1)

である。 $\mbox{\boldmath$x$}_i, m_i$ はそれぞれ粒子$i$ の位置、質量であり、 $G$は重力定数である。

これをそのまま数値計算してもいいが、2つの粒子が近付いた時に重力が発散 するという問題がある。銀河のシミュレーションの場合には、実際の星の数は $10^{10}$個以上と非常に多いのに、それを多い場合でもせいぜい100万程度の 数の粒子で表すので、粒子が重い分この問題がおきやすくなっている。この発 散をまともに扱うには、粒子毎に時間刻みを変更するような特別な工夫が必要 になる。

発散 を避けるために、ポテンシャルとして純粋な $-Gm/r$ ではなくて、

\begin{displaymath}
\phi = -\frac{Gm}{\sqrt{r^2 + \epsilon^2}}
\end{displaymath} (2)

というふうに $r=0$ で有限になるようにしたものを使うのが普通である。 $\epsilon$ は定数で、計算結果に影響しないように十分小さくとる。

このようにポテンシャルをなまらしたときには、時間積分は簡単になって一定 刻みでやればいい。

実際に沢山の粒子を使う上で問題になるのが、運動方程式の右辺の計算量であ る。一つの粒子への力を計算するのに他の全部からの力を計算しないといけな いので、粒子が $N$ 個あれば 1 ステップ当たりの計算量は $N^2$ になる。

これをもうちょっとうまくやろうというのが、次に説明するツリー法というも のである。



Jun Makino
平成16年1月17日