# 定常反復法：Jacobi 法・Gauss–Seidel 法・SOR 法の収束と最適な緩和係数
> 行列の分割による定常反復が収束する条件 ρ(M⁻¹N) < 1 を示し、対角優位・正定値での Jacobi 法・Gauss–Seidel 法・SOR 法の収束、Kahan の必要条件、Young の定理と最適な緩和係数、離散 Laplace 方程式での収束率を証明する。
> https://rikai.mugen-giken.com/mathematics/numerical-linear-algebra/stationary-iterative-methods
## 0. この記事の要点
大きな連立方程式を、一度に解くのではなく「いまの答えの見積もりを少しずつ直す」操作の繰り返しで解く方法を扱います。たとえば 2 つの未知数 $x_1$, $x_2$ があるとき、$x_2$ の今の値から $x_1$ を計算し直し、その $x_1$ から $x_2$ を計算し直す、という往復です。この記事を読むと、そうした繰り返しがいつ正しい答えに近づくのか、近づく速さは何で決まるのか、更新の幅をどう選ぶと速くなるのかが分かります。
- 連立一次方程式 $A\boldsymbol{x} = \boldsymbol{b}$ の係数行列を $A = M - N$ と分け、$M\boldsymbol{x}_{k+1} = N\boldsymbol{x}_k + \boldsymbol{b}$ を繰り返すのが**定常反復法**です。任意の初期値で収束することと、反復行列の[スペクトル半径](/mathematics/numerical-linear-algebra/norms-and-conditioning#def-spectral-radius)（固有値の絶対値の最大）が $\rho(M^{-1}N) < 1$ であることは同値で、1 回あたり誤差はおよそ $\rho$ 倍になります。
- 狭義対角優位（各行で対角成分が他の成分の絶対値の和より大きいこと）なら Jacobi 法と Gauss–Seidel 法は収束します。[正定値](/mathematics/linear-algebra/spectral-theorem#def-positive-definite) Hermite 行列なら、SOR 法は $0 < \omega < 2$ で収束します（Ostrowski–Reich）。逆に、どんな行列でも $\rho(\mathcal{L}_\omega) \ge |\omega - 1|$ なので、$0 < \omega < 2$ は収束に必要です（Kahan）。
- **矛盾なく順序づけられた**行列（未知数の番号づけが、隣り合う未知数の間で規則正しく上下する行列。§4 で定義します）、たとえば三重対角行列や、格子の自然な順序・赤黒順序（格子点を市松模様に塗り分け、赤の点を先に並べる順序）の離散 Laplace 行列では、Jacobi 法の固有値 $\mu$ と SOR 法の固有値 $\lambda$ が $(\lambda + \omega - 1)^2 = \lambda\omega^2\mu^2$ で結ばれます（Young の定理）。ここから $\rho_{\mathrm{GS}} = \rho_{\mathrm{J}}^2$ と最適な緩和係数 $\omega_{\mathrm{opt}} = 2/(1 + \sqrt{1 - \rho_{\mathrm{J}}^2})$ が出ます。
- 離散 Laplace 方程式（格子幅 $h$）では $\rho_{\mathrm{J}} = \cos\pi h$ で、10 桁縮めるのに必要な反復回数は Jacobi 法・Gauss–Seidel 法で $h^{-2}$、最適 SOR 法で $h^{-1}$ に比例します。
- この遅さが、[Krylov 部分空間](/mathematics/numerical-linear-algebra/lanczos-and-conjugate-gradient#def-krylov)法（[共役勾配法](/mathematics/numerical-linear-algebra/lanczos-and-conjugate-gradient)）と前処理、多重格子法へ進む理由です。
## 1. 動機
偏微分方程式を差分法で離散化すると、未知数が $10^6$ を超える疎な連立一次方程式が現れます。Gauss 消去は fill-in（もとは $0$ だった成分が消去の途中で非零になること）のためにメモリも演算量も膨らみますが、行列とベクトルの積や「各未知数を隣接する値から更新する」操作なら、非零成分の個数に比例する手間で済みます。
Laplace 方程式 $-\Delta u = f$ の 5 点差分では、各格子点の値は「上下左右の値の平均 $+\ h^2f/4$」です。この関係を、いまの近似値を右辺に入れて左辺を更新する、という形で繰り返すのが Jacobi 法です。更新した値をすぐ使えば Gauss–Seidel 法、更新幅を $\omega$ 倍に伸ばせば SOR 法（逐次過緩和法）になります。
本章の問いは 3 つです。いつ収束するか。どれくらいの速さか。$\omega$ をどう選べばよいか。答えはすべて**反復行列のスペクトル半径**で書けます。スペクトル半径と行列の冪の関係は [行列のノルムと線形方程式の条件数](/mathematics/numerical-linear-algebra/norms-and-conditioning) の結果を使い、固有値の計算は [冪乗法・逆反復の章](/mathematics/numerical-linear-algebra/power-and-inverse-iteration) と同じく固有ベクトルでの展開が基本になります。
## 2. 分割と定常反復
$A \in \mathbb{C}^{n\times n}$ を正則とする。$A = M - N$（$M$ は正則）を $A$ の**分割**という。$\boldsymbol{x}_0 \in \mathbb{C}^n$ から
$$
M\boldsymbol{x}_{k+1} = N\boldsymbol{x}_k + \boldsymbol{b},\qquad\text{すなわち}\qquad \boldsymbol{x}_{k+1} = G\boldsymbol{x}_k + M^{-1}\boldsymbol{b},\quad G = M^{-1}N
$$
で $\boldsymbol{x}_k$ を作る反復を**定常反復**、$G$ を**反復行列**という。
「定常」とは、$G$ と $M^{-1}\boldsymbol{b}$ が $k$ によらないことを指します。$M$ は「$M\boldsymbol{y} = \boldsymbol{c}$ が安く解ける」ように選びます。$A$ の対角部分を $D$、狭義下三角部分の符号を変えたものを $L$、狭義上三角部分の符号を変えたものを $U$ として $A = D - L - U$ と書くと、代表的な 3 つの方法は次の分割です（$D$ は正則、つまり対角成分はすべて $0$ でないとする）。
| 方法 | $M$ | 反復行列 |
|---|---|---|
| Jacobi 法 | $D$ | $G_{\mathrm{J}} = D^{-1}(L + U)$ |
| Gauss–Seidel 法 | $D - L$ | $G_{\mathrm{GS}} = (D - L)^{-1}U$ |
| SOR 法（緩和係数 $\omega \ne 0$） | $\omega^{-1}D - L$ | $\mathcal{L}_\omega = (D - \omega L)^{-1}\bigl((1 - \omega)D + \omega U\bigr)$ |
Gauss–Seidel 法は $\omega = 1$ の SOR 法です。成分で書くと、Gauss–Seidel 法は $i = 1, 2, \ldots, n$ の順に
$$
x_i^{(k+1)} = \frac{1}{a_{ii}}\Bigl(b_i - \sum_{ji}a_{ij}x_j^{(k)}\Bigr)
$$
と、更新済みの成分をすぐに使います。SOR 法はこの右辺を $\tilde{x}_i$ として $x_i^{(k+1)} = (1 - \omega)x_i^{(k)} + \omega\tilde{x}_i$ とします。$D - L$ と $D - \omega L$ は対角成分が $0$ でない下三角行列で、行列式は対角成分の積（