反復法(連立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$ にあることと同値である。分解すると成分が埋まる大きな疎行列の方程式に使い、前処理としても使う。
反復法(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
$$
である。
$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$ と書き直すと得られる。
使える条件。 反復法を使う場面の条件は次のとおりである。
$\|\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 つは同値である。
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)
$$
である。
$\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 正定値行列 $A$ では、$\|x\|_A:=(x^*Ax)^{1/2}$ というノルムで誤差を測ると、分離の条件が見やすくなる。
$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$ である。
$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$
$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。)
$\omega$ をうまく選ぶと SOR 法は大幅に速くなる。差分法 の 1 次元の行列のような 3 重対角行列では、$T_\omega$ の固有値が $T_J$ の固有値で決まり、最良の $\omega$ が式で書ける。
$A$ を Hermite 正定値な 3 重対角行列とし、$\bar\mu:=\rho(T_J)$、$0< \omega< 2$ とする。
$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}$ である。
| 行列の型 | 方法 | 根拠・注意 |
|---|---|---|
| 行について狭義の対角優位 | Jacobi 法、Gauss–Seidel 法 | thm-itm-diag。上界 $q$ は実際より悪いことが多い |
| Hermite 正定値、3 重対角に近い | SOR 法($\omega_{\mathrm{opt}}$ の近く) | cor-itm-sor、prop-itm-tridiag |
| Hermite 正定値、大きな疎行列 | 共役勾配法 を第一に考える | 段数の目安が $\kappa$ でなく $\sqrt\kappa$ に比例する。定常反復法は前処理に回す |
| 一般の大きな疎行列 | Krylov部分空間法 | 定常反復法は収束の保証がないことが多い |
$$
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$ である。
$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)。
$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 法のスペクトル半径と緩和係数
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$ を少し小さく見積もるほうが、少し大きく見積もるより損が大きい。
$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 法とは別の方法である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する