ガウス・ザイデル法

ガウス・ザイデル法は、離散化で現れる疎な連立一次方程式 $A\mathbf{x}=\mathbf{b}$ を、逐次更新の反復で解に近づける手法である。更新済みの成分をすぐに次の計算へ反映できるため、ヤコビ法より少ない反復で収束しやすい一方、計算順序と並列化に注意が要る。

参考ドキュメント

• ガウス＝ザイデル法（日本語Wikipedia） https://ja.wikipedia.org/wiki/ガウス＝ザイデル法
• R. Barrett et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods（Netlib, PDF） https://www.netlib.org/templates/templates.pdf
• 多重格子法の講義資料（緩和演算子としての Gauss-Seidel に言及、東京大学） https://www.cc.u-tokyo.ac.jp/events/lectures/04/kosyu-20090312-mm.pdf

1. 離散化が生む線形方程式

有限差分法・有限要素法・有限体積法などで、拡散・静電ポテンシャル・弾性・磁気スカラーポテンシャル等の場の方程式を離散化すると、未知ベクトル $\mathbf{x}$（格子点の未知量、節点変位、電位、補正量など）が線形方程式として現れる。

代表例：均一媒質のポアソン方程式

$$-{\mathrm{\nabla }}^2\varphi (\mathbf{r})=\frac{\rho (\mathbf{r})}{\epsilon }$$

3 次元の等間隔格子（格子幅 $h$）で 7 点差分を用いると、各格子点 $(i,j,k)$ の更新式は

$${\varphi }_{i,j,k}^{(\mathrm{new})}=\frac{1}{6}({\varphi }_{i+1,j,k}+{\varphi }_{i-1,j,k}+{\varphi }_{i,j+1,k}+{\varphi }_{i,j-1,k}+{\varphi }_{i,j,k+1}+{\varphi }_{i,j,k-1}+h^2\frac{{\rho }_{i,j,k}}{\epsilon })$$

の形に落ち、全格子点をまとめると $A\mathbf{x}=\mathbf{b}$（疎行列）になる。

2. 逐次更新で「その場で上書き」する

2.1 反復法

$A\mathbf{x}=\mathbf{b}$ の未知数を $x_1,\dots ,x_n$ とし、$k$ 回目の近似を ${\mathbf{x}}^{(k)}$ とする。ガウス・ザイデル法の成分更新は

$$x_i^{(k+1)}=\frac{1}{a_{ii}}(b_i-\sum _{j<i}{a}_{ij}{x}_j^{(k+1)}-\sum _{j>i}{a}_{ij}{x}_j^{(k)})(i=1,\dots ,n)$$

である。ここで $j<i$ の項に $x_j^{(k+1)}$（更新済みの最新値）が入る点が本質である。

2.2 行列分割（matrix splitting）

係数行列を

$$A=D+L+U$$

（$D$：対角、$L$：狭義下三角、$U$：狭義上三角）と分けると、

$$(D+L){\mathbf{x}}^{(k+1)}=\mathbf{b}-U{\mathbf{x}}^{(k)}$$

となる。すなわち、反復行列 $T_{\mathrm{GS}}$ と定数項 $\mathbf{c}$ は

$${\mathbf{x}}^{(k+1)}=T_{\mathrm{GS}}{\mathbf{x}}^{(k)}+\mathbf{c},T_{\mathrm{GS}}=-(D+L{)}^{-1}U,\mathbf{c}=(D+L{)}^{-1}\mathbf{b}$$

である。上書き更新ゆえに、追加の作業ベクトルが不要になりやすい点が利点となる。

3. 収束条件

3.1 収束判定の基本

誤差 ${\mathbf{e}}^{(k)}={\mathbf{x}}^{(k)}-{\mathbf{x}}^{\ast }$（真の解 ${\mathbf{x}}^{\ast }$）は

$${\mathbf{e}}^{(k+1)}=T_{\mathrm{GS}}{\mathbf{e}}^{(k)}$$

を満たす。したがって

$$\rho (T_{\mathrm{GS}})<1$$

（スペクトル半径が 1 未満）なら収束する。

3.2 代表的な十分条件

一般に、次の条件はよく使われる十分条件である。

• 厳密対角優位（strict diagonal dominance）$$|a_{ii}|>\sum _{j\ne i}|a_{ij}|(\mathrm{\forall }i)$$
• 対称正定値（symmetric positive definite; SPD）$$A=A^{\mathrm{\top }},{\mathbf{z}}^{\mathrm{\top }}A\mathbf{z}>0(\mathrm{\forall }\mathbf{z}\ne \mathbf{0})$$

ポアソン型方程式の離散化や、弾性の剛性行列（境界条件が適切な場合）は SPD 構造を持ちやすく、ガウス・ザイデル法が安定に働く典型例である。

3.3 エネルギー最小化

SPD 行列 $A$ に対して

$$f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^{\mathrm{\top }}A\mathbf{x}-{\mathbf{b}}^{\mathrm{\top }}\mathbf{x}$$

を考えると、$\mathrm{\nabla }f=A\mathbf{x}-\mathbf{b}$ であり、最小化条件 $\mathrm{\nabla }f=\mathbf{0}$ が $A\mathbf{x}=\mathbf{b}$ に一致する。ガウス・ザイデル法は、座標ごとの最小化（coordinate descent）に近い逐次更新として解釈でき、反復が進むほど $f(\mathbf{x})$ が減少しやすい、という見通しが得られる。

4. ヤコビ法との違いと更新順序の意味

4.1 ヤコビ法との対比

ヤコビ法は

$$x_i^{(k+1)}=\frac{1}{a_{ii}}(b_i-\sum _{j\ne i}{a}_{ij}{x}_j^{(k)})$$

であり、右辺がすべて古い値 $x^{(k)}$ で構成される。よって成分ごとに独立に計算でき、並列化しやすいが、収束は遅くなりやすい。

ガウス・ザイデル法は「更新したら即使う」ため、反復 1 回あたりの誤差減衰が強いことが多いが、逐次依存が生じる。

4.2 順序依存と再番号付け

ガウス・ザイデル法は未知数の更新順序（行・列の並び）で反復の挙動が変わりうる。疎行列をグラフとして見たとき、近い未知数が近い順序になるように並べ替える（帯幅削減、領域分割に沿った順序など）と、収束が改善する場合がある。

5. 緩和と対称ガウス・ザイデル

5.1 緩和（SOR：successive over-relaxation）

ガウス・ザイデル法に緩和係数 $\omega$ を導入した SOR 法は、更新を

$$x_i^{(k+1)}=(1-\omega )x_i^{(k)}+\frac{\omega }{a_{ii}}(b_i-\sum _{j<i}{a}_{ij}{x}_j^{(k+1)}-\sum _{j>i}{a}_{ij}{x}_j^{(k)})$$

とする。$0<\omega <1$ はアンダーリラックス、$1<\omega <2$ はオーバーリラックスであり、適切な $\omega$ を選べば収束が加速する場合がある。$\omega =1$ はガウス・ザイデル法に一致する。

5.2 対称ガウス・ザイデル（SGS）

前進（forward）ガウス・ザイデルと後退（backward）ガウス・ザイデルを連続して行うものが対称ガウス・ザイデルである。SPD 問題に対する前処理（例：共役勾配法の前処理）として用いられることがある。

6. 注意点

6.1 残差による停止

残差を

$${\mathbf{r}}^{(k)}=\mathbf{b}-A{\mathbf{x}}^{(k)}$$

とし、例えば

$$\frac{\parallel {\mathbf{r}}^{(k)}{\parallel }_2}{\parallel \mathbf{b}{\parallel }_2}<\epsilon$$

や

$$\frac{\parallel {\mathbf{x}}^{(k)}-{\mathbf{x}}^{(k-1)}{\parallel }_2}{\parallel {\mathbf{x}}^{(k)}{\parallel }_2}<\epsilon$$

で停止する。ポアソン系では、残差の空間分布が局所的に残ることがあり、ノルムだけでなく最大値 $\parallel \mathbf{r}{\parallel }_{\mathrm{\infty }}$ を併用する場合もある。

6.2 収束が遅い・不安定になる典型

• 行列が強く非対角支配である、または条件数が大きい
• 非対称・非正定値で、反復行列のスペクトル半径が 1 に近い
• 更新順序が疎行列構造と相性が悪い
• 初期値が物理的に不適切である（境界条件・ゲージ条件の扱いなど）

この場合、前処理、再番号付け、SOR、Krylov 法（CG, GMRES など）への移行、あるいは多重格子の導入が検討対象になる。

7. 多重格子法におけるガウス・ザイデル

多重格子法では「粗い格子で低周波誤差を補正し、細かい格子で高周波誤差を減衰させる」という役割分担がある。ガウス・ザイデル法は反復 1〜数回で高周波成分の誤差を効率よく減衰させやすく、緩和演算子（smoother）として頻用される。

概念的には、細格子で

$$\mathbf{x}\leftarrow \mathrm{Smooth}(\mathbf{x})$$

を数回行い、残差を粗格子に移して補正量を計算し、再び細格子へ戻す。ここで $\mathrm{Smooth}$ の代表がガウス・ザイデルである。

8. 並列化の工夫

逐次依存は並列化の障害であるが、格子型問題では「同じ色どうしは互いに依存しない」ように塗り分けると並列更新が可能になる。

• 赤黒ガウス・ザイデル（2-color）
  • 2 次元・3 次元格子のチェッカーボード分割で、赤点を一斉更新 → 黒点を一斉更新の順に行う
• マルチカラー（graph coloring）
  • 一般疎行列でも、隣接しない未知数が同じ色になるように彩色して並列化する
• ブロック・ガウス・ザイデル
  • 変数をブロックにまとめて更新し、ブロック内部は小さな直接法や局所反復で解く

これらは、多重格子の並列 smoother としても重要な設計点になる。

9. 本手法の位置づけ

手法	更新の特徴	並列性	収束の傾向	代表的な使いどころ
ヤコビ法	全成分を古い値で計算し一斉更新	高い	遅め	前処理、GPU向け、最初の粗い反復
ガウス・ザイデル法	更新済みを即利用して逐次更新	低い（工夫で改善）	速めになりやすい	ポアソン系、緩和、smoother
SOR 法	GS に緩和係数 $\omega$ を導入	低い（工夫で改善）	条件次第で加速	反復加速、古典的 PDE 解法
Krylov 法（CG/GMRES 等）	残差空間を用いた非定常反復	中〜高	良い（前処理依存）	大規模疎行列の主力

ガウス・ザイデル法は「単体で最後まで収束させる」だけでなく、「より大きな解法の部品として組み込む」位置づけでも重要である。

まとめ

• ガウス・ザイデル法は、$A\mathbf{x}=\mathbf{b}$ を逐次上書き更新で解に近づける基本反復法である。更新済みの値をそのまま使うため、ヤコビ法より収束が速いことが多い。
• 収束は反復行列のスペクトル半径 $\rho (T_{\mathrm{GS}})<1$ に支配され、厳密対角優位や SPD は代表的な十分条件である。
• 多重格子法では高周波誤差を減衰させる緩和（smoother）として重要であり、赤黒・マルチカラー・ブロック化で並列性を補う設計が有効である。