マルチグリッド法

なぜ普通の反復法は格子を細かくすると遅くなるのか

偏微分方程式（例えばポアソン方程式）を有限差分法・有限要素法で離散化すると、巨大な連立一次方程式 A x = b が得られます。ヤコビ法やガウス・ザイデル法、SOR（逐次過緩和法）といった古典的な反復法は、実装が単純で1回の反復コストも軽いという利点がありますが、決定的な弱点があります。誤差に含まれる周波数成分ごとに減衰速度がまったく違うという点です。

これらの反復法は局所的な情報（隣接格子点との差分）だけを使って値を更新するため、細かく振動する高周波誤差は数回の反復で急速に消えます。ところが、格子全体にゆったり広がる低周波誤差は、1回の更新では隣の点にしか情報が伝わらないため、収束するまでに格子点数に比例した反復回数が必要になります。格子を細かくする（分割数を増やす）と低周波成分がより「低周波」寄りになり、収束に必要な反復回数はさらに増加します。結果として、必要な反復回数は格子間隔 h の逆数の2乗程度で増え、全体の計算量はO(N^2)に達することもあります（Nは未知数の総数）。

発想の転換 ── 低周波誤差を粗い格子で高周波にする

マルチグリッド法の核心は次の一点に尽きます。ある格子上で低周波に見える誤差成分は、より粗い（間隔が広い）格子上に移すと相対的に高周波成分になる。 格子点の間隔を2倍に粗くすれば、元の格子で波長が長かった誤差も、粗い格子の点間隔に対しては相対的に短い波長として観測されます。つまり、粗い格子でスムーザーを使えば、細かい格子では手こずっていた低周波誤差を効率よく減衰できるのです。

この考えに基づき、マルチグリッド法は次の手順を再帰的に組み合わせます。

2格子（Two-Grid）法の基本手順

1. 前平滑化（pre-smoothing）
   細かい格子でヤコビ法/ガウス・ザイデル法を数回適用し、高周波誤差を除去する

2. 残差の計算
   r = b - A x  （現在の近似解 x の残差を求める）

3. 制限（restriction）
   残差 r を粗い格子へ転送する: r_coarse = R * r
   （Rは制限作用素、例えば単純平均や重み付き平均を使う）

4. 粗い格子での求解
   粗い格子上の誤差方程式 A_coarse * e_coarse = r_coarse を解く
   （粗い格子でも同じ問題が小さいサイズで現れるので再帰できる）

5. 補間（prolongation / interpolation）
   粗い格子で得た誤差 e_coarse を細かい格子へ戻す: e = P * e_coarse
   （Pは補間作用素、例えば線形補間）

6. 補正
   x = x + e

7. 後平滑化（post-smoothing）
   再度スムーザーを数回適用し、補間で生じた高周波の粗さを除去する

ステップ4で「粗い格子上の誤差方程式」を厳密に解く代わりに、粗い格子自体をさらに粗い格子へ制限してこの手順を繰り返すと、格子解像度のピラミッドを降りていく再帰構造になります。最も粗い格子（数点〜十数点程度）まで到達したら、そこでは直接法（LU分解など）で厳密に解いてしまえます。小さい問題なので直接法のコストも無視できます。

V-サイクルとW-サイクル

前述の「細かい→粗い→細かい」という1往復を、格子レベルの数だけ再帰的に繰り返す構成をVサイクルと呼びます。最も細かい格子から出発し、順に粗い格子へ降りていき、最粗格子で厳密に解いてから、通ってきた経路を逆順にたどって細かい格子へ戻る様子が、レベルを縦軸に取ると英字のVの字型を描くことに由来します。

V-サイクル（4レベルの例、L0が最細、L3が最粗）

L0 →(平滑化・制限)→ L1 →(平滑化・制限)→ L2 →(平滑化・制限)→ L3(厳密求解)
                                                                  |
L0 ←(補間・平滑化)← L1 ←(補間・平滑化)← L2 ←(補間・平滑化)← 戻る

Wサイクルは、各粗い格子レベルに滞在する回数を増やし、1つ粗いレベルを2回訪問してから次に戻る構成です。図示するとアルファベットのWのような形になります。Wサイクルは低周波誤差の除去をより念入りに行うため、非常に悪条件な問題（係数が大きく変化する、格子が歪んでいるなど）で収束が安定しやすい一方、1サイクルあたりの計算コストはVサイクルより増えます。実務では、まずVサイクルを試し、収束が思わしくない場合にWサイクルやサイクル数を増やす選択をすることが多いです。

なぜO(N)に近づけるのか

古典的な反復法が格子を細かくするほど遅くなるのに対し、マルチグリッド法の1回のVサイクルにかかる計算量を見積もってみます。最も細かい格子の点数をNとすると、1つ粗いレベルは次元数に応じて点数がおよそ半分〜4分の1になります（1次元ならおよそ1/2、2次元ならおよそ1/4）。各レベルでの作業量（平滑化・残差計算・制限・補間）はそのレベルの点数に比例するため、全レベルの作業量を合計すると等比数列になります。

2次元問題での作業量の見積もり

  レベルL0（最細, 点数N）の作業量: c * N
  レベルL1（点数 N/4）の作業量:    c * N/4
  レベルL2（点数 N/16）の作業量:   c * N/16
  ...

  合計 = c * N * (1 + 1/4 + 1/16 + ...) = c * N * (4/3)
       → Nに比例する定数倍 → O(N)

等比級数が収束するため、レベル数（≒格子を粗くできる回数、log N のオーダー）にほとんど依存せず、合計コストは最も細かい格子の点数Nの定数倍で頭打ちになります。さらに重要なのは、Vサイクル1回あたりの誤差減衰率が、格子を細かくしても（Nを大きくしても）ある一定値（実装によりおよそ0.1〜0.2程度）より悪化しないという収束理論の結果です。これは、各レベルのスムーザーが自分のレベルで受け持つ周波数帯の誤差をきちんと減衰させ、その帯域を外れた誤差は別のレベルが担当するという役割分担が成立するためで、格子間隔hに依存しない収束率（メッシュに依存しない収束、mesh-independent convergence）が理論的に保証される点が、他の反復法との決定的な違いです。誤差を実用上十分な精度まで落とすのに必要なVサイクル回数はNに依存せず一定（多くの場合数回〜十数回程度）で済むため、全体の計算量はO(N)を維持できます。

対照的に、ヤコビ法・ガウス・ザイデル法はおよそO(N^2)、共役勾配法（前処理なし）はおよそO(N^1.5)の計算量になることが多く、格子が細かくなるほど（Nが大きくなるほど）マルチグリッド法との差は開いていきます。

まとめ

• 古典的な反復法（ヤコビ法、ガウス・ザイデル法など）は高周波誤差はすぐ消すが低周波誤差の減衰が遅く、格子を細かくするほど収束に必要な反復回数が増える。
• マルチグリッド法は、低周波誤差を粗い格子に制限すると相対的に高周波になる性質を利用し、平滑化・残差の制限・粗格子での求解・補間・補正を再帰的に繰り返す。
• Vサイクルは各レベルを1往復、Wサイクルは粗いレベルをより念入りに訪問する構成で、悪条件な問題ほどWサイクルが有利になりやすい。
• 各レベルの作業量が等比数列で減っていくため合計コストは最も細かい格子の点数Nの定数倍にとどまり、かつメッシュに依存しない収束率が理論的に保証されるため、全体としてO(N)に近い計算量を達成できる。
• 係数の不均質性や非構造格子が強い問題では、幾何マルチグリッドでなく行列構造から粗格子階層を構築する代数的マルチグリッド（AMG）が使われる。