ベレの方法

ベレの方法（ベレのほうほう、）は、ニュートンの運動方程式を数値積分する手法の一つ。ベレのアルゴリズム、ベレ法、ベルレ積分法()、ベルレの方法などの呼び方もある。分子動力学法における粒子の軌跡（トラジェクトリ）のシミュレーションやコンピュータグラフィックスに頻繁に用いられる。1791年にジャン＝バティスト・ジョゼフ・ドランブルが用いたのが最初で、その後も何回も再発見されているが、1960年代にが分子動力学法に用いてから広く使われるようになった。1909年にハレー彗星の軌道を計算するためにフィリップ・コーウェルとアンドリュー・クロンメリンにより用いられたり、1907年に磁場中の荷電粒子のトラジェクトリを研究するためににより用いられたりしている（そのため、Störmerの方法という異称もある）。この手法の特徴として、数値的安定性が高く、時間反転対称性を持つことや位相空間上のシンプレクティック形式を保存するなど物理系において重要な性質を持つうえ、オイラー法と比べてもほとんど計算コストが増えないことが挙げられる。
基本.
formula_1の形の2階微分方程式を初期条件formula_2およびformula_3のもとで、formula_4をステップサイズとして、formula_5における数値的近似解formula_6は、下のようなアルゴリズムで求めることができる。
運動方程式.
保存系におけるニュートンの運動方程式は
もしくは粒子毎に
と表わされる。ここで、
この等式は、相互作用する分子群や惑星の軌道などさまざまな物理系が、さまざまなポテンシャル関数を決めたときどのように時間発展するかを記述するために用いることができる。
右辺に質量を移し、粒子系の構造を忘れることにすると、上の式は以下のように単純化することができる。
位置に依存する加速度を表す適切なベクトル値関数"A"を使用します。通常、も与えられます。ここで、ベクトル値関数は位置依存加速度をあらわす。通常は、初期位置formula_14および初速度formula_15も所与である。
ベレ積分（速度なし）.
この初期値問題を離散化し、数値的に解くため、タイムステップformula_4を選び、サンプル点列formula_17を考える。このとき、問題は厳密解formula_18をよく近似する点群列formula_19をもとめることに帰着する。
オイラー法が1階微分方程式中の1次微分を前進差分近似するのに対し、ベレ積分は2次微分を中心差分近似すると見ることができる。
「Störmerの方法」で用いられる形式の「ベレ積分」は、 この式を用い、速度を使わずに以前の2つの位置から次の座標を与える。
離散化誤差.
このアルゴリズムは本質的に時間反転対称性を持ち、離散化の際に奇数次の項が消え、formula_22について3次の項がなくなるため、局所誤差の大きさを低減することができる。局所誤差は厳密解formula_23を代入し、formula_24におけるテイラー展開からformula_25をそれぞれ計算することにより定量できる。
ここで、formula_27は位置、formula_28は速度、formula_29は加速度、formula_30は躍度である。
これら2つの級数を足し合わせると、以下の式を得る。
この式から、テイラー展開の1次および3次の項がうち消しあい、ベレ積分の精度が単なるテイラー展開よりも1次高くなっていることがわかる。
ここで、加速度formula_32は厳密解を用いて計算されているが、逐次計算時には中心座標を用いてformula_33のように計算されることに注意が必要である。大域誤差を計算する際には、この厳密解と近似解列との差は消えず、大域誤差に寄与する。
シンプルな例.
局所誤差と大域誤差との関係について洞察を得るため、厳密解と近似解が陽に書き下せるシンプルな例を考えてみる。このような例として標準的なものとして指数関数があげられる。
を定数として、線形微分方程式formula_34を考える。この方程式の厳密解はformula_35およびformula_36である。
この微分方程式にStörmerの方法を適用すると、以下の線形漸化式を得る。
もしくは
これは特性多項式の根を求めること、すなわちformula_39の解を求めることにより解くことができ、以下の根が得られる。
上の線形漸化式のbasis solutionsはformula_41およびformula_42である。これらを厳密解と比較するため、テイラー展開すると以下を得る。
この級数の指数関数formula_44との商はformula_45となるため、以下のように書ける。
ここから、最初のbasis solutionの誤差は以下のように算出される。
したがって、局所離散化誤差は4次以上となるが、微分方程式が2階のため、大域誤差は2次で、時間的に指数的に増加する定数項をもつ。
逐次計算の開始.
ベルレ法の最初のステップ、formula_48、formula_49で、formula_50を計算するためにはformula_51における位置ベクトルformula_52が必要となる。初期条件はformula_53に対してのみ所与なので、一見これは問題をはらんでいるようにみえる。しかし、加速度formula_54は既知であるため、最初のステップは2次までのテイラー展開を用いて計算することができる。
この最初のステップの誤差はformula_56である。しかし、シミュレーションは長い時間、何ステップにもわたって行われ、時刻formula_57におけるトータルの誤差は、formula_19とformula_18との距離およびformula_60とformula_61との比の両方でオーダーformula_62であり、最初のステップにおける誤差は無視できる。さらに言えば、この2次の大域誤差を得るためには初期誤差は最低でも3次である必要がある。
非一様なタイムステップ.
Störmer–Verlet法の弱点として、タイムステップformula_22が変化すると微分関数の近似解を与えなくなってしまう点である。この弱点は次の式を使うことにより修正できる。
より厳密な導出は、formula_65における2次までのテイラー展開にformula_66とformula_67を代入し、formula_68を消去して以下を得る。
したがって、次の式を得る。
速度の計算：Störmer–Verlet法.
基本的なStörmer方程式は速度を陽に与えないが、運動エネルギーなど特定の物理量を計算するためには速度が必要となる。このことは分子動力学法において、時刻formula_71における運動エネルギーや瞬時温度を時刻formula_72における位置を計算するまで計算できないという技術的な問題をひきおこす。この欠点は速度ベレ法を用いるか、平均値の定理を用いて以下のように位置から速度を推定することで対処することができる。
ここで、この速度項は時刻ではなく時刻formula_71の速度であり、位置項の1ステップ後ろである。このことはformula_75はformula_76の2次近似であることを意味する。同じ議論として、タイムステップを半分formula_77にしたformula_78はformula_79の2次近似である。
精度を犠牲にすれば、時刻における速度を次のように近似することもできる。
速度ベルレ法.
関連する、より広く用いられているアルゴリズムとして速度ベルレ法があげられる。この手法はリープ・フロッグ法に似ているが、同時刻の位置と速度を計算する点（リープ・フロッグ法では名前の含意するとおり計算しない）で違う。速度ベルレ法とベルレ法は似ているが、陽に速度を扱い、初期ステップにおける速度を明示的に解く点で異なる。
速度ベルレ法とベルレ法の誤差は同じオーダーであることは示すことができる。ベルレ法では2時刻における位置を記憶しておく必要があるため、1時刻における位置と速度を記憶する速度ベルレ法の法がメモリ消費量が多いとは限らない。
半ステップ速度計算を省く場合、以下のように簡略化される。
ただし、加速度formula_86がformula_85のみに依存し、formula_94に依存しないことを前提としている。
速度ベルレ法は、長期的にはリープ・フロッグ法と同様によりもオーダー1つ分良い近似である。速度の時刻が半ステップずれる以外は殆ど同じである。このことは上述のループのステップ3から初めて、ステップ2と4を組み合わせればステップ1における加速度項は取り除けることに注意すればすぐに証明することができる。唯一の違いは、速度ベルレ法のける中間速度が半陰的オイラー法における最終速度として扱われることである。
オイラー法の大域誤差はオーダーは1であるのに対して、速度ベルレ法の大域誤差のオーダーは中点法と同じく2である。加えて、もし加速度が保存力もしくはから定まる場合、エネルギーの近似値は厳密解における一定値のエネルギーのまわりを振動し、大域誤差は半陰的オイラー法ではオーダー1、速度ベルレ法およびリープ・フロッグ法ではオーダー2の範囲に収まる。系の運動量や角運動量などのシンプレクティック数値積分法で保存されるその他の量についても同じことが言える。
速度ベルレ法は、のとした特殊例である。
アルゴリズムの表現.
速度ベルレ法は3Dアプリケーション一般に有用なアルゴリズムであり、以下のようなC++実装により一般的に解ける。加速度の向きの変化をデモするため、簡略化された抗力を作用させているが、加速度が一定でない場合にのみ必要となる。
struct Body
 Vec3d pos { 0.0, 0.0, 0.0 };
 Vec3d vel { 2.0, 0.0, 0.0 }; // x軸正方向に 2 m/s
 Vec3d acc { 0.0, 0.0, 0.0 }; // 加速度の初期値は0
 double mass = 1.0; // 1kg
 double drag = 0.1; // rho*C*Area - 例示のための簡略化された抗力
 * Update pos and vel using "Velocity Verlet" integration
 * @param dt DeltaTime / time step [eg: 0.01]
 void update(double dt)
 Vec3d new_pos = pos + vel*dt + acc*(dt*dt*0.5);
 Vec3d new_acc = apply_forces(); // 加速度が一定の場合は不要
 Vec3d new_vel = vel + (acc+new_acc)*(dt*0.5);
 pos = new_pos;
 vel = new_vel;
 acc = new_acc;
 Vec3d apply_forces() const
 Vec3d grav_acc = Vec3d{0.0, 0.0, -9.81 }; // Z軸負方向に 9.81m/s^2
 Vec3d drag_force = 0.5 * drag * (vel * abs(vel)); // D = 0.5 * (rho * C * Area * vel^2)
 Vec3d drag_acc = drag_force / mass; // a = F/m
 return grav_acc - drag_acc;
};
誤差項.
ベルレ法の局所位置誤差は上述のとおりformula_95、局所速度誤差はformula_96である。
しかし、大域位置誤差はformula_96、大域速度誤差はformula_96である。これは次のように導出できる。
および
より以下が導かれる。
同様に繰り返せば、以下を得る。
この数列の一般項は以下のように得られる。
大域位置誤差はformula_106としたときの位置formula_107の誤差であるから、次を得る。
したがって、時間間隔を一定とした場合の大域（累積）誤差は以下のオーダーとなる。
ベルレ法では速度は位置に依存して非累積的に算出されるため、大域速度誤差のオーダーもformula_96となる。
分子動力学シミュレーションでは通常、局所誤差よりも大域誤差のほうがはるかに重要であるため、ベルレ法はオーダー2の積分アルゴリズムとみなされる。
拘束.
拘束条件下にある多粒子系は、ベルレ法を用いるほうがオイラー法よりも単純に解くことができる。質点間の拘束条件はたとえば距離を特定値に拘束したり引力を印加したりする条件が考えられるが、粒子間をばねで繋いだと考えることができる。無限に硬いばねを用いれば、このモデルはベルレ法で解くことができる。
一次元の場合、番目の質点の時刻における、拘束されない位置をformula_111、実際の位置をformula_112とすると、これらの間の関係は以下のようなアルゴリズムで得ることができる。
ベルレ法は位置を直接力に関係づけるため、速度を用いて問題を解くよりも使いやすい。
しかし、各粒子に複数の拘束条件が課される場合、問題が起きる。この問題を解決するには、シミュレーションのタイムステップを小さくしたり、タイムステップごとに決まったステップ数の拘束緩和を行ったり、残差が特定の値を下回るまで拘束を緩和する、などの方法でシミュレーションを実装する。
拘束条件を1次までで局所近似する場合、これはガウス＝ザイデル法と同等となる。行列が小さい場合、LU分解の方が速いことが知られている。大きな系もクラスター（例:ラグドール=クラスター）に分解できることがある。クラスター内ではLU分解を用い、クラスター間にはガウス＝ザイデル法を用いればよい。行列のコードを再利用し、力の位置への依存性を1次局所近似することにより、ベルレ積分をより暗黙的にすることができる。
SuperLUを始めとした、疎行列を用いて複雑な問題を解くための洗練されたも存在する。また、例えば音波を形成することなく力を布を伝わらせるなどの特殊化された問題を取り扱うための特殊な技法もある。
を解くには、を扱えるアルゴリズムを用いる必要がある。
衝突応答.
衝突に応答する一つの方法として、ペナルティに基く方法が挙げられる。この方法では基本的に衝突した点に力を加える。問題は、加える力をどのように決めるかである。力が強すぎると物体は不安定になり、弱すぎると互いに貫通してしまう。衝突に応答する別の方法としては投影法があり、衝突した物体を最小の移動距離で相手の物体の内部から出すように動かすことで衝突に応答する。
ベルレ法では、後者の方法で衝突した場合の速度が自動的に決定する。しかし、このことは衝突の物理が自動的に満たされる(すなわち運動量の変化が現実的なものとなる)ことを意味しない。速度項を暗黙的に変化させる代わりに、衝突した物体の最終速度を陽に（直前のタイムステップにおいて記録された位置を変化させることにより）制御する必要がある。
新しい速度を決める最も単純な方法として、完全弾性衝突もしくは完全非弾性衝突を仮定することが挙げられる。より複雑な制御方法では、反発係数を用いることもある。