解く問題は -u''(x)=f(x)、u(0)=u(1)=0。厳密解 sin(kπx) を用い f(x)=(kπ)²sin(kπx) を与えています。N は 2^k+1 に丸めて使用します。
上段＝解 u(x)（青実線＝MG の数値解／灰色破線＝厳密解 sin(kπx)）／下段＝対数スケールでの残差 ‖r‖ の収束履歴（青＝MG、赤＝GS 単独）
1D ポアソン方程式を有限差分で離散化すると、内点 i に対して次の連立線形方程式 $A\mathbf{u}=\mathbf{f}$ が得られます。$A$ は対角 $2$・副対角 $-1$ の対称三重対角行列です。
細格子（格子幅 $h$）での離散化：
$$-\frac{u_{i-1}-2u_i+u_{i+1}}{h^2}=f_i$$
Gauss-Seidel 緩和（高周波誤差を除去）：
$$u_i^{(\text{new})}=\tfrac{1}{2}\bigl(u_{i-1}^{(\text{new})}+u_{i+1}^{(\text{old})}+h^2 f_i\bigr)$$
フル重み制限（fine→coarse）と線形補間（coarse→fine）：
$$r^{2h}_i=\tfrac{1}{4}r^{h}_{2i-1}+\tfrac{1}{2}r^{h}_{2i}+\tfrac{1}{4}r^{h}_{2i+1}$$
V サイクル全体（再帰）：
$$u\leftarrow \text{Smooth}\circ \text{Prolong}\circ V_{2h}\circ \text{Restrict}\circ \text{Smooth}(u)$$
滑らかな誤差成分は粗格子では「高周波」として扱われ、各レベルでスムーザが効率よく除去するため、収束因子は格子サイズに依存せず約 0.1 程度に保たれます。
マルチグリッド法シミュレーターとは
🙋
CAE のソルバーで「マルチグリッド前処理」ってよく聞くんですけど、結局これは何をしているんですか？普通の反復法と何が違うんでしょう？
🎓
いい質問だ。ざっくり言うと、Gauss-Seidel みたいな点反復は「ご近所さんとしか話せない」んだ。情報が 1 ステップで隣の格子点までしか伝わらない。だから滑らかな（低周波の）誤差は、ぐるっと届くのに何百反復もかかる。一方でマルチグリッドは粗格子に降りることで「遠くの情報を一気に運ぶ」。上のシミュレーターで V サイクル数を 1 → 5 と上げてみると、赤い GS が緩やかに落ちる横で、青の MG が桁単位で急降下するのが見えるよ。
🙋
なるほど！「GS 緩和回数」のスライダーは何を変えてるんですか？多いほど早く収束しそうな気がしますが。
🎓
そこが面白いところ。各レベルでスムージング回数を増やしても、MG の収束因子はほとんど変わらない。3 回でも 10 回でもほぼ一緒だ。理由は、スムーザの仕事は「高周波誤差を消すこと」だけで、低周波は粗格子側に任せてしまうからね。実務では計算コストとのバランスで 2〜3 回が定番だよ。シミュレーターでスムーザ回数を 1 と 10 で比べても、青の線の傾きはほぼ同じはずだ。
🙋
「厳密解の波数 k」を 1 にすると、解の形が単純なサイン半波になりますね。これを大きくすると…ぐにゃぐにゃに。
🎓
k は強制項 f(x) に含まれる空間周波数を変えている。重要な観察として、k を 1 〜 20 まで変えても MG の収束は安定している。これがマルチグリッドの最大の強みで、「全周波数の誤差を均等に潰せる」性質だ。一方 GS は低周波 k=1 のときが一番苦手で、収束が極端に遅くなる。シミュレーターで k=1 にして残差カードを比べてみて。
🙋
「細格子点数 N」を 257 にしたら、計算が一瞬で終わったのに残差はちゃんと落ちてる！普通は格子を細かくすると重くなりますよね？
🎓
これが MG の「最適複雑度」と呼ばれる性質だ。普通の反復法は格子幅 h を半分にすると収束反復数が約 4 倍になるが、MG は反復数が h に依存しない。つまり 1 反復のコストが O(N) で、それが定数回で終わるから全体も O(N)。1000 万点の問題でも数十秒で解けるから、現代の大規模 CAE ソルバーで標準になっているんだ。
よくある質問
FAS（非線形マルチグリッド）はどんな問題で使いますか？
FAS（Full Approximation Scheme）は粗格子で「誤差方程式」ではなく「解そのもの」を保持し、非線形作用素にも一貫した処理を与える枠組みです。ナビエ・ストークス方程式、レイノルズ平均乱流モデル、塑性問題、相変化を伴う熱伝導など、線形化が困難または高コストな問題で広く使われます。各レベルで非線形残差を直接計算し、粗格子から戻ってきた補正を陽に解に足し込む点が線形 MG と異なります。
AMG（代数マルチグリッド）と幾何マルチグリッドの違いは？
幾何マルチグリッドは「規則正しい格子」が前提で、レベルごとに点を半分にしていきます。一方 AMG は格子情報を一切使わず、係数行列 A だけから「強結合」関係を解析して疑似的な粗化を自動構築します。非構造メッシュの FEM、配管網、回路シミュレータなど幾何的階層を持たない大規模疎行列に直接適用でき、商用ソルバー（HYPRE BoomerAMG, Trilinos ML 等）で広く実装されています。
FEM ソルバーでマルチグリッドはどう使われますか？
構造解析や熱解析の大規模有限要素モデルでは、剛性行列 K に対する反復解法（共役勾配法 CG、GMRES）の前処理として MG / AMG が使われます。CG 単独だと条件数の悪化で収束が劇的に遅くなりますが、AMG 前処理を入れると数十反復で収束します。Ansys、Abaqus、COMSOL の「PCG with AMG」設定や、OpenFOAM の GAMG ソルバーが代表例です。
V サイクル以外にはどんなサイクルがありますか？
主要なバリエーションは W サイクル（粗格子で 2 回ずつ再帰）と F サイクル（V と W の中間）、そして FMG（Full Multigrid／ネステッド反復）です。W サイクルは粗格子コストの増加と引き換えに対流支配や強異方性問題で安定性が増します。FMG は最粗格子から解いて徐々に細格子に拡張する手法で、たった 1〜2 V サイクル分の追加コストで離散化誤差レベルまで収束させられる「最適な初期推定」を作れます。
実世界での応用
大規模 CFD ソルバー： OpenFOAM の GAMG（Geometric-Algebraic Multigrid）、ANSYS Fluent の AMG、Star-CCM+ など、現代の商用・オープンソース CFD はほぼ全て圧力ポアソン方程式の解法にマルチグリッドを採用しています。SIMPLE / PISO アルゴリズム内で毎タイムステップ解かれるポアソン方程式が全計算時間の 60〜80% を占めるため、ここを O(N) で解けるかどうかが全体性能を左右します。
構造解析の前処理： 線形弾性・熱伝導の大規模 FEM 問題では、剛性行列 K が対称正定値で AMG 前処理付き共役勾配法（PCG-AMG）が標準解法です。500 万自由度クラスの自動車車体モデルでも、AMG 前処理によって数十回の反復で収束します。Hypre、Trilinos ML、PETSc の AMG ライブラリが各種商用ソルバーのバックエンドとして組み込まれています。
気象・海洋シミュレーション： 地球規模の大気・海洋モデルでは、コリオリ力や静水圧近似により楕円型圧力方程式が現れ、これを毎ステップ高速に解く必要があります。WRF（気象研究予報）モデルや MITgcm 海洋モデルでは、球面格子上の幾何マルチグリッドや並列 AMG が使われ、数千〜数万コアの HPC 上で数日先の予報を実時間で計算します。
画像処理・ポアソン編集： マルチグリッドはコンピュータビジョン分野でも重要で、ポアソン画像編集（シームレスな貼り付け）、HDR トーンマッピング、ステレオ視差最適化、流体シミュレーションを用いた CG エフェクトなどで、巨大な疎行列を毎フレーム解く必要があり、マルチグリッドの速度がリアルタイム性を支えています。
よくある誤解と注意点
最も多い誤解は、「マルチグリッドはどんな問題でも魔法のように速い」と思い込む ことです。実際にはスムーザと粗化が問題に合っていないと収束しません。たとえば対流支配の問題（移流拡散方程式で Péclet 数が大きい場合）では、点 Gauss-Seidel が高周波誤差を消せず、収束因子が 1 に近づきます。このような問題ではブロック GS や line GS、あるいは半粗化（一方向のみの粗化）を使う必要があります。シミュレーターは純粋なポアソン方程式専用なので、収束因子が常に約 0.1 と理想的な振る舞いを示しますが、現実問題ではこのチューニングが MG 実装の腕の見せ所です。
次に多いのが、「スムージング回数を増やせば増やすほど良い」と考える ことです。シミュレーターでスムーザ回数を 1 から 10 まで動かしてみてください。MG の最終残差はほとんど改善しません。これはスムーザの役割が「高周波誤差除去のみ」で、すでに数回で除去済みの後はそれ以上やっても無駄だからです。実務では pre 2 回・post 2 回（合計 4 回）または各 3 回程度が定番で、増やすほど計算時間に対して効率が悪化します。ν=1 でも収束する MG は「効率が良い」と評価されます。
最後に、「マルチグリッドの収束が遅いときは V サイクルを増やせばよい」と単純に考える のも危険です。本来 MG は 5〜10 サイクルで離散化誤差レベル（O(h²)）まで落ちるべきもので、それ以上必要なら「何かがおかしい」サインです。よくある原因はスムーザと係数行列の不適合、境界条件の処理ミス、粗格子作用素の構成エラー（rediscretization vs Galerkin の混在）など。サイクル数を増やして力技で解こうとせず、収束因子（残差比 r_{n+1}/r_n）が 0.1〜0.2 程度に保たれているか確認することが正しい診断手順です。