反復法(連立1次方程式)

同義語:定常反復法Jacobi法ヤコビ法Gauss–Seidel法ガウス・ザイデル法SOR法逐次過緩和法Jacobi methodGauss–Seidel methodsuccessive over-relaxationstationary iterative method

概要

反復法(連立1次方程式)(iterative method for linear systems)とは、連立 1 次方程式 $Ax=b$ を、初期値から近似解の列を作って解く方法の総称である。$A=M-N$ と分けて $x_{k+1}=M^{-1}(Nx_k+b)$ とする定常反復法には Jacobi 法、Gauss–Seidel 法、SOR 法があり、どの右辺と初期値でも収束するための必要十分条件は、反復行列 $M^{-1}N$ のスペクトル半径が $1$ より小さいことである。行について狭義の対角優位な行列では Jacobi 法と Gauss–Seidel 法が収束し、Hermite 正定値行列では SOR 法の収束は緩和係数が $0< \omega< 2$ にあることと同値である。分解すると成分が埋まる大きな疎行列の方程式に使い、前処理としても使う。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 連立1次方程式, 固有値, スペクトル半径, 正定値行列

反復法(iterative method)とは、連立 1 次方程式 $Ax=b$ を、初期値 $x_0$ から近似解の列 $x_1,x_2,\dots$ を順に作って解く方法の総称である。掃き出し法 や LU分解 のような直接法が有限回の演算で解を出すのに対し、反復法は解に近づく列を作り、十分近づいたところで打ち切る。

何を計算するか

偏微分方程式を 差分法 で離散化すると、未知数が多く、1 行の非零成分が数個しかない疎行列の方程式が出る。LU分解 で解くと、消去の途中で $0$ だった成分が埋まり、記憶も手間も増える。そこで、行列の非零成分だけを使う計算を繰り返したい。
いちばん素朴な考えはこうである。第 $i$ 式を $x_i$ について解き、右辺に今の近似値を入れて新しい $x_i$ を作る。たとえば
$$ 4x_1-x_2=2,\qquad -x_1+3x_2=5 $$
なら $x_1\leftarrow(2+x_2)/4$、$x_2\leftarrow(5+x_1)/3$ を繰り返す。$(0,0)$ から始めると $(0.5,1.6667)$、$(0.9167,1.8333)$、$(0.9583,1.9722)$ と進み、解 $(1,2)$ に近づく。これが Jacobi 法である。
問いは 3 つある。どんな行列で収束するか。どれくらい速いか。どう止めるか。この記事では、$A=M-N$ と分けて作る 定常反復法 について、どの右辺と初期値でも収束するための必要十分条件が 反復行列のスペクトル半径が $1$ より小さいこと であることを証明し、対角優位な行列・Hermite 正定値行列・3 重対角行列での判定を与える。段ごとに部分空間を広げる方法は Krylov部分空間法 と 共役勾配法 が扱う。

定義と使える条件

以下、$\mathbb K$ は $\mathbb R$ または $\mathbb C$、$A\in M_n(\mathbb K)$、$b\in\mathbb K^n$ とする。スペクトル半径 $\rho(T)$ は、$T$ の複素固有値の絶対値の最大値である。

分離と定常反復法

$A=M-N$、$M$ は正則、という分け方を $A$ の 分離 という。$M$ は $My=c$ を速く解ける行列に選ぶ。$x_0\in\mathbb K^n$ から
$$ x_{k+1}:=Tx_k+c,\qquad T:=M^{-1}N=I-M^{-1}A,\qquad c:=M^{-1}b $$
で列を作る方法を 定常反復法 といい、$T$ を 反復行列 という。「定常」は $T$ と $c$ が段 $k$ によらないことを指す。

書き直すと $x_{k+1}=x_k+M^{-1}(b-Ax_k)$ である。すなわち、残差 $r_k:=b-Ax_k$ に $M^{-1}$ を掛けて修正する。また
$$ x=Tx+c\iff Mx=Nx+b\iff Ax=b $$
なので、列が収束すれば極限は $Ax=b$ の解である。$A$ が正則で $x^*:=A^{-1}b$、$e_k:=x_k-x^*$ とすると、$e_{k+1}=Te_k$、すなわち
$$ e_k=T^ke_0 $$
である。

Jacobi 法・Gauss–Seidel 法・SOR 法

$A$ の対角成分はすべて $0$ でないとし、$A=D+L+U$($D$ は対角部分、$L$ は狭義下三角部分、$U$ は狭義上三角部分)と書く。$\omega>0$ を 緩和係数 とする。$i=1,\dots,n$ の順に
$$ x^{\mathrm{GS}}_i:=\frac1{a_{ii}}\Bigl(b_i-\sum_{j< i}a_{ij}x^{(k+1)}_j-\sum_{j>i}a_{ij}x^{(k)}_j\Bigr),\qquad x^{(k+1)}_i:=(1-\omega)x^{(k)}_i+\omega\,x^{\mathrm{GS}}_i $$
と更新する方法を SOR 法(逐次過緩和法、successive over-relaxation)という。$\omega=1$ の場合を Gauss–Seidel 法 という。$x^{\mathrm{GS}}_i$ の式で右辺の $x^{(k+1)}_j$ を $x^{(k)}_j$ に替え、$\omega=1$ としたものを Jacobi 法 という。

Gauss–Seidel 法は新しく求めた成分をその場で使い、SOR 法は今の値からその更新先までの差の $\omega$ 倍だけ動かす。Jacobi 法は古い値だけを使うので、成分ごとに並列に計算できる。

方法$M$反復行列 $T$使える条件
Richardson 法$\frac1\theta I$($\theta\ne0$)$I-\theta A$なし
Jacobi 法$D$$T_J=-D^{-1}(L+U)$$D$ が正則
Gauss–Seidel 法$D+L$$T_1=-(D+L)^{-1}U$$D$ が正則
SOR 法$\frac1\omega D+L$$T_\omega=(D+\omega L)^{-1}\bigl((1-\omega)D-\omega U\bigr)$$D$ が正則、$\omega>0$

SOR 法の行は、def-itm-methods の式を $a_{ii}x^{(k+1)}_i+\omega\sum_{j< i}a_{ij}x^{(k+1)}_j=(1-\omega)a_{ii}x^{(k)}_i-\omega\sum_{j>i}a_{ij}x^{(k)}_j+\omega b_i$ と書き直すと得られる。
使える条件。 反復法を使う場面の条件は次のとおりである。

  • (i) $A$ は正方行列で、解きたい方程式は $Ax=b$ の形をしている。
  • (ii) $Ax$ と $M^{-1}c$ の計算が、分解よりずっと安い(疎行列など)。
  • (iii) 反復行列について $\rho(T)< 1$ が成り立つ(thm-itm-rho)。これは行列と方法の組で決まり、行列だけでは決まらない(ex-itm-counter)。

公式の表

$\|\cdot\|$ は $\mathbb C^n$ のノルムとそれから定まる行列のノルムである。$\kappa$ は Hermite 正定値行列の最大固有値と最小固有値の比である。

公式使える条件根拠
$e_k=T^ke_0$$A$ 正則、$M$ 正則def-itm-splitting の後
どの $b,x_0$ でも収束 $\iff\rho(T)< 1$$M$ 正則thm-itm-rho
$\lim_{k\to\infty}\Vert T^k\Vert^{1/k}=\rho(T)$任意の $T$thm-itm-rho
$\Vert e_k\Vert\le\frac{\Vert T\Vert}{1-\Vert T\Vert}\Vert x_k-x_{k-1}\Vert$$\Vert T\Vert< 1$prop-itm-stop
Jacobi 法:$\Vert e_k\Vert_\infty\le q^k\Vert e_0\Vert_\infty$行について狭義の対角優位thm-itm-diag
SOR 法:$\Vert e_k\Vert_\infty\le(1-\omega(1-q))^k\Vert e_0\Vert_\infty$同じ、$0< \omega\le1$thm-itm-diag
$\rho(T_\omega)\ge\lvert1-\omega\rvert$$D$ 正則、$\omega>0$prop-itm-det
SOR 法が収束 $\iff0< \omega< 2$$A$ Hermite 正定値cor-itm-sor
$\rho(T_1)=\rho(T_J)^2$$A$ Hermite 正定値、3 重対角prop-itm-tridiag
$\omega_{\mathrm{opt}}=\dfrac2{1+\sqrt{1-\rho(T_J)^2}}$、$\rho(T_{\omega_{\mathrm{opt}}})=\omega_{\mathrm{opt}}-1$同じprop-itm-tridiag
Richardson 法:$\theta_{\mathrm{opt}}=\dfrac2{\lambda_{\min}+\lambda_{\max}}$、$\rho=\dfrac{\kappa-1}{\kappa+1}$$A$ Hermite 正定値ex-itm-poisson

主定理と証明

スペクトル半径による判定

次の補題が、固有値の情報とノルムの評価をつなぐ。

スペクトル半径に近いノルム

$T\in M_n(\mathbb C)$、$\varepsilon>0$ とする。$\mathbb C^n$ のノルム $\lvert\cdot\rvert_\varepsilon$ で、それから定まる行列のノルムについて $\lvert T\rvert_\varepsilon\le\rho(T)+\varepsilon$ となるものがある。

三角化して対角行列で縮める
証明を開く

Schur分解 の定理「Schur の三角化定理」により、ユニタリ行列 $Q$ と上三角行列 $R$ で $T=QRQ^*$ となるものがある。$R$ の対角成分は $T$ の固有値である。$\delta>0$ に対し $S:=\operatorname{diag}(1,\delta,\dots,\delta^{n-1})$ とおくと、$S^{-1}RS$ の $(i,j)$ 成分は $\delta^{j-i}R_{ij}$ である。よって $\delta$ を十分小さく取ると、対角より上の成分の絶対値の各行の和が $\varepsilon$ 以下になり、$\|S^{-1}RS\|_\infty\le\rho(T)+\varepsilon$ となる。$\lvert x\rvert_\varepsilon:=\|S^{-1}Q^*x\|_\infty$ と定めると、これはノルムであり、$\lvert Tx\rvert_\varepsilon=\|S^{-1}RS\,S^{-1}Q^*x\|_\infty\le(\rho(T)+\varepsilon)\lvert x\rvert_\varepsilon$ である。$\square$

定常反復法の収束の判定

$A=M-N$、$M$ を正則、$T=M^{-1}N$ とする。次の 2 つは同値である。

  1. どの $b$ とどの初期値 $x_0$ についても、列 $x_k$ は収束する。
  2. $\rho(T)< 1$ である。
    このとき $A$ は正則で、極限は $A^{-1}b$ である。また、任意の $T$ と $\mathbb C^n$ の任意のノルムについて $\lim_{k\to\infty}\|T^k\|^{1/k}=\rho(T)$ である。
誤差は $T$ の冪で動く

2 ⇒ 1。$\rho(T)< 1$ なら $1$ は $T$ の固有値でないので $I-T$ は正則であり、$A=M(I-T)$ も正則である。$x^*=A^{-1}b$ とする。$\varepsilon>0$ を $q:=\rho(T)+\varepsilon< 1$ となるように取り、lem-itm-norm のノルムを使うと、$\lvert e_k\rvert_\varepsilon=\lvert T^ke_0\rvert_\varepsilon\le q^k\lvert e_0\rvert_\varepsilon\to0$ である。$\mathbb C^n$ のノルムはどれも定数倍で比べられるので、$x_k\to x^*$ である。
1 ⇒ 2。列の極限 $x$ は $x=Tx+c$、すなわち $Ax=b$ を満たす。$b$ は任意なので $A$ は全射で、正則である。$b=0$ とすると解は $0$ だけなので、すべての $y\in\mathbb K^n$ について $T^ky\to0$ である。$\mathbb K=\mathbb R$ のときも、$v=v'+iv''$($v',v''\in\mathbb R^n$)について $T^kv=T^kv'+iT^kv''\to0$ なので、すべての $v\in\mathbb C^n$ について $T^kv\to0$ である。$T$ の固有値 $\lambda$ の固有ベクトル $v$ を取ると $\lambda^kv\to0$ なので $\lvert\lambda\rvert< 1$ である。
極限の式。$\lambda$ を $\lvert\lambda\rvert=\rho(T)$ の固有値、$v$ を固有ベクトルとすると、$\|T^kv\|=\rho(T)^k\|v\|$ なので $\rho(T)^k\le\|T^k\|$ である。逆に、$\varepsilon>0$ について lem-itm-norm のノルムと $\|\cdot\|$ を比べる定数を $C$ とすると、$\|T^k\|\le C\lvert T^k\rvert_\varepsilon\le C(\rho(T)+\varepsilon)^k$ である。$k$ 乗根を取って $k\to\infty$、次に $\varepsilon\to0$ とする。$\square$

(主張は Saa03 Theorem 4.1、p. 115。極限の式は同書 §4.2.1、p. 116 の大域的な収束因子の式。)したがって、$\rho(T)$ が $1$ に近いほど遅い。誤差を $\varepsilon$ 倍にする段数はおよそ $\ln\varepsilon/\ln\rho(T)$ である。ただしこれは $k$ が大きいときの目安であり、途中では誤差が増えることもある(ex-itm-counter)。
実際に止めるには、$\|T\|< 1$ のとき次の評価が使える。

隣り合う反復の差による誤差の評価

$\mathbb C^n$ のあるノルムについて $\|T\|< 1$ とする。このとき $\|e_k\|\le\|T\|^k\|e_0\|$ であり、
$$ \|e_k\|\le\frac{\|T\|}{1-\|T\|}\,\|x_k-x_{k-1}\|\qquad(k\ge1) $$
である。

三角不等式を 1 回使う

$\rho(T)\le\|T\|< 1$ なので $A$ は正則である(thm-itm-rho)。$e_k=Te_{k-1}$ から第 1 の式が出る。$e_{k-1}=e_k-(x_k-x_{k-1})$ なので $\|e_k\|\le\|T\|\,\|e_{k-1}\|\le\|T\|\bigl(\|e_k\|+\|x_k-x_{k-1}\|\bigr)$ である。$\|e_k\|$ について解く。$\square$

倍率 $\|T\|/(1-\|T\|)$ は $\|T\|$ が $1$ に近いと大きい。ex-itm-poisson の Jacobi 法なら、Euclid ノルムで約 $89$ 倍である。反復の差が小さいだけでは誤差が小さいとは言えない。

対角優位な行列

$A$ が 行について狭義の対角優位 であるとは、すべての $i$ で $\lvert a_{ii}\rvert>\sum_{j\ne i}\lvert a_{ij}\rvert$ であることをいう。

対角優位な行列での収束

$A$ を行について狭義の対角優位とし、
$$ q:=\max_i\frac{\sum_{j\ne i}\lvert a_{ij}\rvert}{\lvert a_{ii}\rvert}< 1 $$
とおく。このとき $A$ は正則で、どの初期値からも、Jacobi 法の誤差は $\|e_k\|_\infty\le q^k\|e_0\|_\infty$ を満たし、SOR 法の誤差は $0< \omega\le1$ で
$$ \|e_k\|_\infty\le\bigl(1-\omega(1-q)\bigr)^k\|e_0\|_\infty $$
を満たす。とくに Gauss–Seidel 法の誤差は $\|e_k\|_\infty\le q^k\|e_0\|_\infty$ を満たす。

最大の成分で評価する

Jacobi 法。$T_J$ の $(i,j)$ 成分は $j\ne i$ で $-a_{ij}/a_{ii}$、$j=i$ で $0$ なので、$\|T_J\|_\infty=q< 1$ である。よって prop-itm-stop が使え、$A$ も正則である。
SOR 法。$e':=T_\omega e$ とおくと、def-itm-methods で $b=0$ とした式から
$$ e'_i=(1-\omega)e_i-\omega\sum_{j< i}\frac{a_{ij}}{a_{ii}}e'_j-\omega\sum_{j>i}\frac{a_{ij}}{a_{ii}}e_j $$
である。$\alpha_i:=\sum_{j< i}\lvert a_{ij}/a_{ii}\rvert$、$\beta_i:=\sum_{j>i}\lvert a_{ij}/a_{ii}\rvert$ とおくと $\alpha_i+\beta_i\le q$ である。$\lvert e'_i\rvert=\|e'\|_\infty$ となる $i$ を取ると、$1-\omega\ge0$ に注意して
$$ \|e'\|_\infty\le(1-\omega+\omega\beta_i)\|e\|_\infty+\omega\alpha_i\|e'\|_\infty $$
である。$1-\omega\alpha_i>0$ なので、$q_\omega:=1-\omega(1-q)$ として $1-\omega+\omega\beta_i\le q_\omega(1-\omega\alpha_i)$ を示せばよい。右辺から左辺を引くと
$$ \omega(q-\alpha_i-\beta_i)+\omega^2\alpha_i(1-q)\ge0 $$
である。よって $\|T_\omega e\|_\infty\le q_\omega\|e\|_\infty$ である。$\square$

(Jacobi 法と Gauss–Seidel 法の収束は Saa03 Theorem 4.9、pp. 121–122。そこでは、対角優位の不等式で等号を許し 1 行以上で狭義で、行列が既約である場合も扱う。この記事ではその場合を証明しない。)

Hermite 正定値行列

Hermite 正定値行列 $A$ では、$\|x\|_A:=(x^*Ax)^{1/2}$ というノルムで誤差を測ると、分離の条件が見やすくなる。

$A$ ノルムで縮む分離

$A$ を Hermite 行列、$A=M-N$、$M$ を正則とし、$P:=M+M^*-A$ が正定値であるとする。このとき
$$ \rho(M^{-1}N)< 1\iff A\text{ は正定値} $$
である。$A$ が正定値なら、$x\ne0$ で $\|Tx\|_A< \|x\|_A$ である。

1 段の減少量を計算する

$x\in\mathbb C^n$ について $y:=M^{-1}Ax$ とおくと $Tx=x-y$、$Ax=My$ である。$A$ が Hermite なので
$$ (x-y)^*A(x-y)=x^*Ax-x^*Ay-y^*Ax+y^*Ay=x^*Ax-y^*M^*y-y^*My+y^*Ay $$
すなわち、次の恒等式が成り立つ。
$$ (Tx)^*A(Tx)=x^*Ax-y^*Py $$
$A$ が正定値のとき。$x\ne0$ なら $Ax\ne0$ なので $y\ne0$ であり、恒等式から $\|Tx\|_A< \|x\|_A$ である。$Tx=\lambda x$($x\ne0$)を入れると $\lvert\lambda\rvert^2\|x\|_A^2< \|x\|_A^2$ なので、$\lvert\lambda\rvert< 1$ である。
$\rho(T)< 1$ のとき。$I-T=M^{-1}A$ は正則なので $A$ は正則である。$A$ が正定値でないとすると、$x_0\ne0$ で $x_0^*Ax_0\le0$ となるものがある。$x_k:=T^kx_0$、$\phi_k:=x_k^*Ax_k$ とおく。恒等式により $\phi_k$ は増えず、$y=M^{-1}Ax_0\ne0$ なので $\phi_1< \phi_0\le0$ である。一方 $\rho(T)< 1$ なので $x_k\to0$、$\phi_k\to0$ である。これは矛盾である。$\square$

分離の条件 $P$ は、方法ごとに次のようになる。$A$ は Hermite 行列なので $U=L^*$ である。

方法$P=M+M^*-A$$P$ が正定値になる条件
Jacobi 法$2D-A$行列ごとに確かめる(ex-itm-jacobi-spd)
Gauss–Seidel 法$D$$D$ の対角成分がすべて正
SOR 法$(\frac2\omega-1)D$$D$ の対角成分がすべて正で $0< \omega< 2$
行列式による下界

$A$ の対角成分がすべて $0$ でなく、$\omega>0$ なら、$\rho(T_\omega)\ge\lvert1-\omega\rvert$ である。とくに $\omega\ge2$ の SOR 法は、収束しない $b,x_0$ を持つ。

固有値の積を見る

$D+\omega L$ は対角成分が $D$ と同じ下三角行列、$(1-\omega)D-\omega U$ は対角成分が $(1-\omega)D$ の上三角行列なので、$\det T_\omega=(1-\omega)^n$ である。これは固有値の積なので、絶対値の最大のものは $\lvert1-\omega\rvert$ 以上である。後半は thm-itm-rho による。$\square$

Hermite 正定値行列での SOR 法

$A$ を Hermite 行列で対角成分がすべて正とし、$0< \omega< 2$ とする。このとき、SOR 法がどの $b,x_0$ でも収束することと、$A$ が正定値であることは同値である。とくに、$A$ が Hermite 正定値なら、SOR 法が収束することと $0< \omega< 2$ は同値であり、Gauss–Seidel 法はつねに収束する。

分離の条件を当てはめる

$M=\frac1\omega D+L$ について、$U=L^*$ と $A=D+L+L^*$ から $P=(\frac2\omega-1)D$ であり、これは正定値である。thm-itm-energy と thm-itm-rho から前半が従う。$A$ が正定値なら対角成分は正なので、後半は前半と prop-itm-det から従う。$\square$

(主張は Saa03 Theorem 4.10、p. 122。)

3 重対角行列と最良の緩和係数

$\omega$ をうまく選ぶと SOR 法は大幅に速くなる。差分法 の 1 次元の行列のような 3 重対角行列では、$T_\omega$ の固有値が $T_J$ の固有値で決まり、最良の $\omega$ が式で書ける。

3 重対角行列での SOR 法の固有値

$A$ を Hermite 正定値な 3 重対角行列とし、$\bar\mu:=\rho(T_J)$、$0< \omega< 2$ とする。

  1. $T_J$ の固有値は実数で、$\mu$ が固有値なら $-\mu$ も固有値であり、$\bar\mu< 1$ である。
  2. $\lambda\ne0$ が $T_\omega$ の固有値であることは、$T_J$ のある固有値 $\mu$ について $(\lambda+\omega-1)^2=\omega^2\mu^2\lambda$ となることと同値である。
  3. $\omega_{\mathrm{opt}}:=\dfrac2{1+\sqrt{1-\bar\mu^2}}$ とおくと、
    $$ \rho(T_\omega)=\begin{cases}\Bigl(\dfrac{\omega\bar\mu+\sqrt{\omega^2\bar\mu^2-4(\omega-1)}}2\Bigr)^2&(0< \omega\le\omega_{\mathrm{opt}})\\[2ex]\omega-1&(\omega_{\mathrm{opt}}\le\omega< 2)\end{cases} $$
    である。とくに $\rho(T_1)=\bar\mu^2$ であり、$\rho(T_\omega)$ は $\omega=\omega_{\mathrm{opt}}$ でただ 1 つの最小値 $\omega_{\mathrm{opt}}-1$ を取る。
対角行列の相似で $L$ と $U$ の重みを移す
証明を開く

$t\ne0$ に対し $S:=\operatorname{diag}(1,t,\dots,t^{n-1})$ とおくと、$A$ が 3 重対角なので $S^{-1}(aD+bL+cU)S=aD+\frac btL+ctU$ である。よって $f(a,b,c):=\det(aD+bL+cU)$ について $f(a,b,c)=f(a,b/t,ct)$ であり、$bc\ne0$ で $s^2=bc$ なら $t=b/s$ として $f(a,b,c)=f(a,s,s)$ である。

1:$t=-1$ の相似で $L+U$ と $-(L+U)$ は相似であり、$T_J=-D^{-1}(L+U)$ の固有値は $0$ について対称である。$D$ の対角成分は正なので、$T_J$ は Hermite 行列 $H:=-D^{-1/2}(L+U)D^{-1/2}$ と相似で、固有値は実数である。$D^{-1/2}AD^{-1/2}=I-H$ は正定値なので $H$ の固有値は $1$ より小さく、対称性から $-1$ より大きい。

2:$D+\omega L$ は正則なので、$\lambda$ が $T_\omega$ の固有値であることは $\det\bigl((\lambda+\omega-1)D+\omega\lambda L+\omega U\bigr)=0$ と同値である。$\lambda\ne0$ とし、$\sqrt\lambda$ を平方根の 1 つとする。$s=\omega\sqrt\lambda$ として上の等式を使うと、この行列式は $s^n\det(\mu D+L+U)$ に等しい。ここで $\mu:=(\lambda+\omega-1)/(\omega\sqrt\lambda)$ である。$\det(\mu D+L+U)=\det D\,\det(\mu I-T_J)$ なので、条件は $\mu$ が $T_J$ の固有値であることである。1 の対称性により、平方根の取り方によらず、これは 2 の式と同値である。

3:$\lambda\ne0$ の固有値は、$\mu\ge0$ を $T_J$ の固有値として、$q_\mu(s):=s^2-\omega\mu s+\omega-1$ の $0$ でない根 $s$ の平方である($\pm s$ の両方の場合を、$\mu$ と $-\mu$ で尽くす)。$\Delta(\mu):=\omega^2\mu^2-4(\omega-1)$ とおく。$\omega=1$ なら根は $0,\mu$ で、$\rho(T_1)=\bar\mu^2$ である。

$\Delta(\mu)\ge0$ なら根は実数で、絶対値が大きいほうは $s_+(\mu):=\frac12(\omega\mu+\sqrt{\Delta(\mu)})$ であり、これは $\mu$ について増加する。$\Delta(\mu)< 0$ なら根は共役な複素数で、$\lvert s\rvert^2=\omega-1$ である(このとき $\omega>1$)。$\omega>1$ で $\Delta(\mu)\ge0$ なら $s_+(\mu)^2\ge s_+s_-=\omega-1$ である。よって $\Delta(\bar\mu)\ge0$ なら $\rho(T_\omega)=s_+(\bar\mu)^2$、$\Delta(\bar\mu)< 0$ なら $\rho(T_\omega)=\omega-1$ である。$\Delta(\bar\mu)=0$ の根は $\omega=2/(1\pm\sqrt{1-\bar\mu^2})$ で、$0< \omega< 2$ の範囲では $\Delta(\bar\mu)\ge0\iff\omega\le\omega_{\mathrm{opt}}$ である。これで式が示された。

$\omega< \omega_{\mathrm{opt}}$ で $s:=s_+(\bar\mu)$ を $\omega$ で微分すると、$q_{\bar\mu}(s)=0$ から $\sqrt{\Delta}\,s'=\bar\mu s-1$ である。cor-itm-sor により $s< 1$ で、$\bar\mu< 1$ なので $s'< 0$ である。$\omega\ge\omega_{\mathrm{opt}}$ で $\omega-1$ は増加する。$\omega=\omega_{\mathrm{opt}}$ では $\Delta=0$ で両方の式の値が一致する。$\square$

(固有値の関係は、より一般の「整合順序の行列」について Saa03 Theorem 4.16、p. 126、$\omega_{\mathrm{opt}}$ の式は同書 (4.47)、p. 127。ここでは 3 重対角の場合に限って示した。)

計算の手順

入力は $A$、$b$、初期値 $x_0$(よい近似がなければ $0$)、許容誤差 $\varepsilon$(たとえば $10^{-8}$)、反復の上限 $k_{\max}$ である。

  1. 方法を選ぶ:下の表で分離を決める。SOR 法なら $\omega$ も決める。
  2. 対角成分を確かめる:$a_{ii}=0$ の行があれば、行を入れ替えて対角成分を $0$ でなくする。
  3. 1 段を計算する:def-itm-methods の式で $i=1,\dots,n$ の順に更新する。和は非零成分だけを取る。Jacobi 法は新旧 2 本のベクトルを持ち、Gauss–Seidel 法と SOR 法は 1 本を上書きする。
  4. 止める判定:残差 $r_k=b-Ax_k$ を計算し、$\|r_k\|\le\varepsilon\|b\|$ なら止める。このとき相対誤差は $\kappa(A)\varepsilon$ 以下である(数値線形代数 の系「残差による誤差の評価」)。$k=k_{\max}$ でも止める。
  5. 収束の様子を見る:比 $\|x_{k+1}-x_k\|/\|x_k-x_{k-1}\|$ を記録する。一定の値に落ち着くなら、それが $\rho(T)$ の目安である(thm-itm-rho の後の段落。途中で増える場合があるので、$k$ が大きいところで見る)。
  6. 失敗の検出:比が $1$ 以上のまま続く、または $\|r_k\|$ が増え続けるなら、$\rho(T)\ge1$ を疑い、別の方法に替える。
    1 段の手間は、どの方法も非零成分の個数の定数倍である。列 $x_k$ が収束しても丸め誤差で $\|r_k\|$ が頭打ちになるので、$\varepsilon$ は 条件数 と丸めの単位の積より大きく取る。
    行列の型方法根拠・注意
    行について狭義の対角優位Jacobi 法、Gauss–Seidel 法thm-itm-diag。上界 $q$ は実際より悪いことが多い
    Hermite 正定値、3 重対角に近いSOR 法($\omega_{\mathrm{opt}}$ の近く)cor-itm-sor、prop-itm-tridiag
    Hermite 正定値、大きな疎行列共役勾配法 を第一に考える段数の目安が $\kappa$ でなく $\sqrt\kappa$ に比例する。定常反復法は前処理に回す
    一般の大きな疎行列Krylov部分空間法定常反復法は収束の保証がないことが多い

例題

非対称な 3 次の行列

$$ A=\begin{pmatrix}4&-2&1\\-1&5&-2\\1&-1&3\end{pmatrix},\qquad b=\begin{pmatrix}3\\2\\3\end{pmatrix},\qquad x_0=0 $$
とする。解は $x^*=(1,1,1)^{\mathsf T}$ である。
使う公式:def-itm-methods、thm-itm-diag。行の比は $\frac34,\frac35,\frac23$ なので $q=\frac34$ である。
答え:

$k$Jacobi 法の $x_k$Gauss–Seidel 法の $x_k$
$1$$(\frac34,\frac25,1)$$(\frac34,\frac{11}{20},\frac{14}{15})$
$2$$(\frac7{10},\frac{19}{20},\frac{53}{60})$$(\frac{19}{24},\frac{559}{600},\frac{157}{150})$

$\|e_{10}\|_\infty$ は Jacobi 法で約 $4.2941\times10^{-3}$、Gauss–Seidel 法で約 $2.3343\times10^{-6}$、$\omega=0.9$ の SOR 法で約 $2.3027\times10^{-5}$ である。thm-itm-diag の上界は、前の 2 つが $q^{10}\approx0.05631$、$\omega=0.9$ が $(1-0.9\cdot\frac14)^{10}\approx0.07817$ で、どれも実際より大きい。$\rho(T_J)\approx0.66484$、$\rho(T_1)\approx0.25820$ である。

差分の Poisson 行列

$n=20$、$A=\operatorname{tridiag}(-1,2,-1)$(両端 $0$ の境界条件での $-u''=f$ の差分)、$b=(1,\dots,1)^{\mathsf T}$、$x_0=0$ とする。$\|r_k\|_2\le10^{-8}\|b\|_2$ までの段数を比べる。
使う公式:thm-itm-rho、prop-itm-tridiag。
答え:$\rho(T_J)=\cos\frac\pi{21}\approx0.98883$、$\omega_{\mathrm{opt}}=\frac2{1+\sin(\pi/21)}\approx1.74058$ である。

方法Jacobi 法Gauss–Seidel 法SOR 法($\omega=1.5$)SOR 法($\omega_{\mathrm{opt}}$)
$\rho(T)$$0.98883$$0.97779$$0.93169$$0.74058$
段数$1633$$818$$263$$78$

Gauss–Seidel 法の段数は Jacobi 法の約半分で、これは $\rho(T_1)=\rho(T_J)^2$ に対応する。$\omega_{\mathrm{opt}}$ の SOR 法は 1 段の手間がほぼ同じで、段数は $20$ 分の $1$ 以下である(図 1)。

固有値の計算と Richardson 法を開く

$T_J=\frac12\operatorname{tridiag}(1,0,1)$ である。$v^{(k)}_j:=\sin\frac{jk\pi}{21}$($k=1,\dots,20$)とおくと、加法定理から $\frac12(v^{(k)}_{j-1}+v^{(k)}_{j+1})=\cos\frac{k\pi}{21}\,v^{(k)}_j$ で、$v^{(k)}_0=v^{(k)}_{21}=0$ なので、これらが $20$ 個の固有値 $\cos\frac{k\pi}{21}$ を与える。$A=2(I-T_J)$ の固有値は $2-2\cos\frac{k\pi}{21}$ で、$\lambda_{\min}\approx0.022338$、$\lambda_{\max}\approx3.97766$、$\kappa\approx178.06$ である。

Hermite 正定値な $A$ の Richardson 法では $T=I-\theta A$ の固有値は $1-\theta\lambda$ であり、$\rho(T)=\max\{\lvert1-\theta\lambda_{\min}\rvert,\lvert1-\theta\lambda_{\max}\rvert\}$ である。収束するのは $0< \theta< 2/\lambda_{\max}$ のときで、最小は $1-\theta\lambda_{\min}=\theta\lambda_{\max}-1$、すなわち $\theta=2/(\lambda_{\min}+\lambda_{\max})$ のとき $\rho=(\kappa-1)/(\kappa+1)$ である(Saa03 Example 4.1、pp. 116–118)。この行列では $\lambda_{\min}+\lambda_{\max}=4$ なので $\theta=\frac12$ で、Jacobi 法と一致する。$\omega_{\mathrm{opt}}$ の $T_\omega$ は対角化できず、誤差に $k\rho^k$ の形の項が出るので、段数 $78$ は目安 $\ln10^{-8}/\ln\rho\approx61$ より多い。

左:Poisson 行列(n=20)の相対残差と段数。右:SOR 法のスペクトル半径と緩和係数 左:Poisson 行列(n=20)の相対残差と段数。右:SOR 法のスペクトル半径と緩和係数

緩和係数とスペクトル半径

ex-itm-poisson の行列で $\rho(T_\omega)$ を比べる。
使う公式:prop-itm-tridiag の 3。
答え:

$\omega$$0.5$$1$$1.25$$1.5$$1.7$$1.74058$$1.8$$1.9$
$\rho(T_\omega)$$0.99258$$0.97779$$0.96288$$0.93169$$0.84791$$0.74058$$0.8$$0.9$

$\omega_{\mathrm{opt}}$ の左で急に下がり、右は傾き $1$ の直線で上がる(図 1 の右)。$\omega$ を少し小さく見積もるほうが、少し大きく見積もるより損が大きい。

正定値でも Jacobi 法は発散する

$a\in\mathbb R$ として、対角成分が $1$、それ以外の成分がすべて $a$ の 3 次の行列 $A_a$ を考える。
使う公式:thm-itm-rho、cor-itm-sor、thm-itm-energy。
答え:$A_a$ の固有値は $1+2a,1-a,1-a$ なので、$a=0.6$ で $A_{0.6}$ は正定値である(固有値 $2.2,0.4,0.4$)。$T_J=I-A_a$ の固有値は $-2a,a,a$ なので $\rho(T_J)=1.2$ で、Jacobi 法は収束しない。一方 Gauss–Seidel 法は cor-itm-sor により収束する($\rho(T_1)\approx0.46476$)。Jacobi 法の $P=2D-A_{0.6}=2I-A_{0.6}$ の固有値は $-0.2,1.6,1.6$ で正定値でないので、thm-itm-energy とは矛盾しない。

使える条件と反例

外す条件反例成り立たなくなること
対角成分が $0$ でない$A=\begin{pmatrix}0&1\\1&0\end{pmatrix}$$A$ は正則だが Jacobi 法・SOR 法の式が定義できない(行を入れ替えると $I$)
対角優位の「狭義」(thm-itm-diag)$A=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$等号の対角優位だが $A$ は特異で、$\rho(T_J)=1$
対角優位(thm-itm-diag)$A=\begin{pmatrix}1&2\\2&1\end{pmatrix}$$A$ は正則だが $\rho(T_J)=2$ で Jacobi 法は発散
Hermite 性(cor-itm-sor)$A=\begin{pmatrix}1&-2\\2&1\end{pmatrix}$、$\omega=1$$\frac12(A+A^{\mathsf T})=I$ は正定値だが $\rho(T_1)=4$
正定値性(cor-itm-sor)$A=\begin{pmatrix}1&2\\2&1\end{pmatrix}$、$\omega=1$対角成分は正の Hermite 行列だが $\rho(T_1)=4$
$\omega< 2$(cor-itm-sor)$A=\begin{pmatrix}2&-1\\-1&2\end{pmatrix}$、$\omega=2$Hermite 正定値だが $\rho(T_2)=1$ で収束しない
$P$ の正定値性(thm-itm-energy)$A_{0.6}$ の Jacobi 法(ex-itm-jacobi-spd)$A$ は正定値だが $\rho(T_J)=1.2$
3 重対角(prop-itm-tridiag)$A_{0.4}$(ex-itm-jacobi-spd の行列)Hermite 正定値だが $\rho(T_1)\approx0.25298$、$\rho(T_J)^2=0.64$
反例の確認
確認の計算を開く

2 行目:$A$ の行の和は $0$ で特異である。$T_J=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ の固有値は $\pm1$ である。

3 行目:$\lvert a_{ii}\rvert=1< 2$ である。$T_J=\begin{pmatrix}0&-2\\-2&0\end{pmatrix}$ の固有値は $\pm2$ である。

4 行目:$A=\begin{pmatrix}1&-a\\a&1\end{pmatrix}$ について $T_1=\begin{pmatrix}0&a\\0&-a^2\end{pmatrix}$ である。$a=2$ で固有値は $0,-4$ である。

5 行目:$A$ の固有値は $3,-1$ である。$T_1=\begin{pmatrix}0&-2\\0&4\end{pmatrix}$ である。

6 行目:prop-itm-det により $\rho(T_2)\ge1$ である。実際 $T_2=\begin{pmatrix}-1&1\\-1&0\end{pmatrix}$ の固有値は $\lambda^2+\lambda+1=0$ の根で、絶対値は $1$ である。

8 行目:$a=0.4$ の $A_a$ は固有値 $1.8,0.6,0.6$ で正定値である。$T_J$ の固有値は $-0.8,0.4,0.4$ で $0$ について対称でない。3 重対角という条件だけを外している。

行列と方法の組で決まること。 $B_1=\begin{pmatrix}1&2&-2\\1&1&1\\2&2&1\end{pmatrix}$ は $T_J^3=0$ なので $\rho(T_J)=0$ で Jacobi 法は有限回で解に届くが、$T_1$ の固有多項式は $\lambda(\lambda-2)^2$ で $\rho(T_1)=2$ である。$B_2=\begin{pmatrix}2&-1&1\\2&2&2\\-1&-1&2\end{pmatrix}$ では逆に、$T_J$ の固有多項式は $\lambda^3+\frac54\lambda$ で $\rho(T_J)=\frac{\sqrt5}2$、$T_1$ の固有多項式は $\lambda(\lambda+\frac12)^2$ で $\rho(T_1)=\frac12$ である。
$\|T\|\ge1$ でも収束すること。 $T=\begin{pmatrix}0.9&1\\0&0.9\end{pmatrix}$ は $\rho(T)=0.9$ だが $\|T\|_\infty=1.9$ である。$\|T^k\|_\infty$ は $k=9$ で最大値 $4.2616$ を取ってから減り、$k=100$ で約 $0.003$ になる。

よくある誤り

誤り正しくはなぜ
Jacobi 法は正則な行列ならいつも収束する$\rho(T_J)< 1$ が必要十分であるthm-itm-rho、反例の表の 3 行目
正定値なら Jacobi 法も収束する正定値で保証されるのは Gauss–Seidel 法と SOR 法であるex-itm-jacobi-spd
Gauss–Seidel 法は Jacobi 法より必ず速い一方だけが収束する行列があるex-itm-counter の $B_1,B_2$
$\Vert T\Vert\ge1$ の方法は収束しない$\rho(T)< 1$ なら収束する。ノルムの条件は十分条件であるex-itm-counter
反復の差が小さいので解は正確である倍率 $\Vert T\Vert/(1-\Vert T\Vert)$ が掛かる。$\rho(T)=0.99$ なら誤差を $\frac1{10}$ にするのに約 $229$ 段かかるprop-itm-stop
$\omega$ は大きいほどよい$\omega_{\mathrm{opt}}$ を超えると $\rho=\omega-1$ で悪くなり、$\omega\ge2$ では収束しないprop-itm-tridiag、prop-itm-det

補足

Krylov 部分空間との関係。 $x_{k+1}=x_k+M^{-1}r_k$ を繰り返すと、$x_k-x_0$ は $M^{-1}A$ と $M^{-1}r_0$ の Krylov部分空間法 の部分空間 $\mathcal K_k(M^{-1}A,M^{-1}r_0)$ に入る。定常反復法はその中の決まった 1 点を取り、Krylov部分空間法はその中で最もよい点を取る。これが、定常反復法をそのまま使うより、前処理 $M$ として使うことが多い理由である。$M^{-1}Ax=M^{-1}b$ を前処理された方程式という(Saa03 §4.1.2、p. 113)。
ブロック化と正則分離。 成分の代わりに未知数の組ごとに更新するブロック Jacobi 法・ブロック Gauss–Seidel 法がある(Saa03 §4.1.1、p. 108)。また、$M^{-1}$ と $N$ の成分がすべて非負である分離について、$\rho(M^{-1}N)< 1$ は「$A$ が正則で $A^{-1}$ の成分がすべて非負」と同値である(同書 Theorem 4.4、p. 118。この記事では証明しない)。
平滑化。 Jacobi 法や Gauss–Seidel 法は、誤差の振動の速い成分を速く減らす。この性質を使う方法が 多重格子法 である(Saa03 第 13 章、p. 423 から)。
語の注意。 固有値を計算する「Jacobi 法」(Jacobiの固有値法。直交行列で対称行列を対角化していく)は、この記事の Jacobi 法とは別の方法である。

関連項目

参考文献

[1]
Yousef Saad, Iterative Methods for Sparse Linear Systems, SIAM, 2003, §4.1.1(p. 108)、§4.1.2(p. 113)、Theorem 4.1(p. 115)、§4.2.1(p. 116)、Example 4.1(pp. 116–118)、Theorem 4.4(p. 118)、Theorem 4.9(pp. 121–122)、Theorem 4.10(p. 122)、Theorem 4.16(p. 126)、(4.47)(p. 127)、第 13 章(p. 423〜)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する