Krylov部分空間法(Krylov subspace method)とは、正則な行列 $A$ の連立 1 次方程式 $Ax=b$ を、初期残差 $r_0$ から作った部分空間 $\operatorname{span}\{r_0,Ar_0,\dots,A^{m-1}r_0\}$ に初期値を足した範囲で近似する反復法の総称である。行列とベクトルの積だけで計算できるので、大きな疎行列の方程式に使う。Arnoldi の手順で正規直交基底を作り、残差を最小にする GMRES や、残差の直交条件で解を決める FOM を計算し、丸めのない計算では $r_0$ の次数の段数で解に到達する。Hermite 正定値行列では誤差の $A$ ノルムが最小になり、収束は条件数で評価できる。
前提知識: 連立1次方程式, 固有値, Gram–Schmidtの直交化, 最小二乗法, 正定値行列
Krylov部分空間法(Krylov subspace method)とは、正則な $n$ 次正方行列 $A$ の連立 1 次方程式 $Ax=b$ を、初期値 $x_0$ と初期残差 $r_0=b-Ax_0$ から作った部分空間
$$
\mathcal K_m(A,r_0)=\operatorname{span}\{r_0,\ Ar_0,\ A^2r_0,\ \dots,\ A^{m-1}r_0\}
$$
に $x_0$ を足した範囲で近似する反復法の総称である。$\mathcal K_m(A,r_0)$ を Krylov 部分空間 という。
偏微分方程式の離散化から出る行列は、$n$ が $10^6$ を超えても 1 行に数個の成分しかない疎行列であることが多い。LU分解 で解くと、消去の途中で $0$ だった成分が埋まっていき、記憶も計算も膨らむ。一方、$A$ とベクトルの積 $x\mapsto Ax$ は、非零の成分の個数に比例する手間で計算できる。そこで「$A$ を掛ける」操作だけを使って解を作りたい。
手がかりは Cayley–Hamiltonの定理 である。$A$ が正則なら $A^{-1}$ は $A$ の $n-1$ 次以下の多項式で書けるので、解 $x^*=A^{-1}b$ は
$$
x^*=x_0+q(A)\,r_0\qquad(\deg q\le n-1)
$$
の形をしている。つまり $x^*$ は $x_0+\mathcal K_n(A,r_0)$ に入る。$m$ が $n$ よりずっと小さくても、$x_0+\mathcal K_m(A,r_0)$ の中によい近似があることを期待し、$m$ を $1$ ずつ増やしながら部分空間の中で最もよいものを取る。これが Krylov部分空間法である。
この記事では、Krylov 部分空間の基本性質、有限回で止まること、Arnoldi の手順、GMRES の最小残差の公式、Hermite 行列での 3 項の漸化式、条件数による収束の上界を証明する。計算の手順と数値例を示し、条件を外した反例を挙げる。
以下、$\mathbb K$ は $\mathbb R$ または $\mathbb C$、$A\in M_n(\mathbb K)$ とし、$\langle x,y\rangle:=y^*x$、$\|x\|:=\langle x,x\rangle^{1/2}$ とする($y^*$ は共役転置)。行列のノルムは、このノルムから定まる作用素ノルムとする。$e_j$ は標準基底のベクトルである。
$0$ でない $v\in\mathbb K^n$ と $m\ge1$ に対し、
$$
\mathcal K_m(A,v):=\operatorname{span}\{v,Av,\dots,A^{m-1}v\}
$$
を Krylov 部分空間 という。$p(A)v=0$ を満たす最高次の係数が $1$ の多項式 $p$ の次数の最小値を、$v$ の $A$ に関する 次数(grade)といい、$d(A,v)$ と書く。
$A$ の 最小多項式 $\psi$ は $\psi(A)v=0$ を満たすので、$d(A,v)\le\deg\psi\le n$ である。$A$ が対角化可能で、$v$ を固有空間の成分に $v=\sum_\lambda v_\lambda$ と分けると、$p(A)v=\sum_\lambda p(\lambda)v_\lambda$ だから、$d(A,v)$ は $v_\lambda\ne0$ となる相異なる固有値 $\lambda$ の個数に等しい。
$x_0\in\mathbb K^n$ を初期値、$r_0:=b-Ax_0\ne0$ とする。Krylov部分空間法 とは、各 $m\ge1$ で $x_m\in x_0+\mathcal K_m(A,r_0)$ を選ぶ反復法である。$r_m:=b-Ax_m$ を残差といい、代表的な選び方は次の 2 つである。
この定義は Saa03 第 6 章の冒頭(pp. 157–158)と §6.4(p. 165)、§6.5(p. 171)による。
使える条件。 この記事の公式と手順は、次の条件のもとで述べる。
| 方法 | 行列の条件 | $x_m$ の決め方 | 基底の漸化式 | 根拠 |
|---|---|---|---|---|
| GMRES | 正則 | 最小残差 | 全部の基底を使う | thm-kry-gmres |
| FOM | 正則で $H_m$ も正則 | Galerkin | 全部の基底を使う | prop-kry-fom |
| 共役勾配法 | Hermite 正定値 | Galerkin(誤差の $A$ ノルム最小) | 3 項 | thm-kry-energy |
| 共役残差法 | Hermite | 最小残差 | 3 項 | 証明しない:Saa03 §6.8・Algorithm 6.20(p. 203)。$r_j\ne0$ で $\langle Ar_j,r_j\rangle=0$ になると途中で止まる |
$V_m=(v_1,\dots,v_m)$ は thm-kry-arnoldi の正規直交基底の行列、$\beta:=\|r_0\|$、$d:=d(A,r_0)$、$e^{(m)}:=x^*-x_m$ とする。表の中のノルムは上で定めたものである。
| 公式 | 使える条件 | 根拠 |
|---|---|---|
| $\mathcal K_m(A,v)=\{p(A)v\mid\deg p\le m-1\}$ | なし | prop-kry-basic |
| $\dim\mathcal K_m(A,v)=\min\{m,d(A,v)\}$ | $v\ne0$ | prop-kry-basic |
| $x^*\in x_0+\mathcal K_m$ となる最小の $m$ は $d$ | $A$ 正則 | thm-kry-finite |
| $AV_m=V_{m+1}\overline H_m$、$V_m^*AV_m=H_m$ | $m< d(A,v_1)$ | thm-kry-arnoldi |
| GMRES:$x_m=x_0+V_my_m$、$y_m=\operatorname{argmin}_y\Vert\beta e_1-\overline H_my\Vert$ | $A$ 正則、$m< d$ | thm-kry-gmres |
| FOM:$H_my_m=\beta e_1$、$\Vert r_m\Vert=h_{m+1,m}\lvert e_m^{\mathsf T}y_m\rvert$ | $H_m$ 正則、$m< d$ | prop-kry-fom |
| $r_m=p_m(A)r_0$、$\deg p_m\le m$、$p_m(0)=1$ | $x_m\in x_0+\mathcal K_m$ | prop-kry-poly |
| $\Vert r_m\Vert\le\kappa_2(X)\min_p\max_i\lvert p(\lambda_i)\rvert\,\Vert r_0\Vert$(GMRES) | $A=X\Lambda X^{-1}$ | prop-kry-poly |
| $\Vert e^{(m)}\Vert_A\le2\rho^m\Vert e^{(0)}\Vert_A$、$\rho=\dfrac{\sqrt\kappa-1}{\sqrt\kappa+1}$ | $A$ Hermite 正定値、$1\le m\le d$ | thm-kry-cheb |
| $\Vert r^{(k+1)}\Vert^2\le(1-\mu^2/\Vert A\Vert^2)\Vert r^{(k)}\Vert^2$($r^{(k)}$ は再出発の $k$ 周目の残差) | $\operatorname{Re}\langle Ax,x\rangle\ge\mu\Vert x\Vert^2$、$\mu>0$ | prop-kry-restart |
$v\ne0$、$d=d(A,v)$ とする。
1 は線形結合 $\sum_{i< m}c_iA^iv$ を $p(t)=\sum_{i< m}c_it^i$ と読むだけである。
2 と 3:$v,Av,\dots,A^{m-1}v$ が線形従属であることは、$m-1$ 次以下の $0$ でない多項式 $p$ で $p(A)v=0$ となるものがあることと同じであり、これは $m-1\ge d$、すなわち $m>d$ と同値である。よって $m\le d$ で $\dim\mathcal K_m=m$ である。$d$ 次の最高次の係数が $1$ の多項式で $v$ を消すものの式から $A^dv\in\mathcal K_d$ なので、$A\mathcal K_d\subset\mathcal K_d$ であり、$m\ge d$ で $\mathcal K_m=\mathcal K_d$、次元は $d$ である。$\square$
(Saa03 Proposition 6.1・6.2、p. 158。)
$A$ を正則、$r_0\ne0$、$d=d(A,r_0)$ とする。解を $x^*=A^{-1}b$ とすると、$x^*\in x_0+\mathcal K_m(A,r_0)$ となる最小の $m$ はちょうど $d$ である。
$p(t)=t^d+c_{d-1}t^{d-1}+\cdots+c_1t+c_0$ を $p(A)r_0=0$ となる $d$ 次の多項式とする。$c_0\ne0$ である。実際、$c_0=0$ なら $p(t)=t\,g(t)$ と書け、$Ag(A)r_0=0$ と $A$ の正則性から $g(A)r_0=0$ となり、$\deg g=d-1$ が $d$ の最小性に反する。$p(A)r_0=0$ を
$$
r_0=-\frac1{c_0}A\bigl(A^{d-1}+c_{d-1}A^{d-2}+\cdots+c_1I\bigr)r_0
$$
と書き直して $A^{-1}$ を掛けると $A^{-1}r_0\in\mathcal K_d(A,r_0)$ である。$x^*-x_0=A^{-1}r_0$ なので $x^*\in x_0+\mathcal K_d$ である。
逆に $x^*-x_0=q(A)r_0$、$\deg q\le m-1$ とする。$A$ を掛けて $r_0=Aq(A)r_0$、すなわち $g(A)r_0=0$、$g(t):=1-tq(t)$ である。$g$ は定数項が $1$ で $0$ でない $m$ 次以下の多項式だから、$m\ge d$ である。$\square$
$r_0$ が少数の固有値の成分しか持たなければ $d$ は小さく、丸めのない計算では少ない段数で解に届く。
$\mathcal K_m$ の自然な基底 $v,Av,A^2v,\dots$ はすぐに平行に近づく。そこで Gram–Schmidtの直交化 で 1 段ごとに直交化する。
$v\ne0$ に対し $v_1:=v/\|v\|$ とし、$j=1,2,\dots$ について
$$
h_{ij}:=\langle Av_j,v_i\rangle\ (1\le i\le j),\qquad w_j:=Av_j-\sum_{i=1}^jh_{ij}v_i,\qquad h_{j+1,j}:=\|w_j\|
$$
と計算する。$h_{j+1,j}=0$ なら止まる。そうでなければ $v_{j+1}:=w_j/h_{j+1,j}$ として続ける。$m$ 段の $V_m:=(v_1,\dots,v_m)$、$h_{ij}$ を並べた $m\times m$ 行列 $H_m$($i>j+1$ の成分は $0$)、$H_m$ の下に行 $(0,\dots,0,h_{m+1,m})$ を足した $(m+1)\times m$ 行列 $\overline H_m$ を定める。
$v\ne0$、$d=d(A,v)$ とする。
$j\le d$ について、次の主張 $(\mathrm P_j)$ を示す:$v_1,\dots,v_j$ が定義され、$\mathcal K_j$ の正規直交基底であり、$v_j=cA^{j-1}v+u$($c\ne0$、$u\in\mathcal K_{j-1}$、ただし $\mathcal K_0=\{0\}$)と書ける。
$j=1$ は定義そのものである。$(\mathrm P_j)$ を仮定する。$w_j$ は $Av_j$ から $\mathcal K_j$ への直交射影を引いたものである。$Au\in\mathcal K_j$ なので $Av_j=cA^jv+Au$ から、$w_j=c\,(A^jv-\text{その }\mathcal K_j\text{ への射影})$ である。したがって $w_j=0$ と $A^jv\in\mathcal K_j$ は同値で、これは $\dim\mathcal K_{j+1}=\dim\mathcal K_j$ と同値である。prop-kry-basic の 2 と $j\le d$ により、これは $j=d$ と同値である。
$j< d$ なら $w_j\ne0$ で、$v_{j+1}=w_j/\|w_j\|$ は $v_1,\dots,v_j$ に直交する単位ベクトルであり、$\mathcal K_{j+1}$ に入り、$A^jv$ の係数は $c/\|w_j\|\ne0$ である。よって $(\mathrm P_{j+1})$ が成り立つ。これで 1 と 2 が示された。
$w_j$ の定義を書き直すと $Av_j=\sum_{i=1}^{j+1}h_{ij}v_i$($j< d$)である。これを列に並べたものが $AV_m=V_{m+1}\overline H_m$ である。$j=d$ では $w_d=0$ から $AV_d=V_dH_d$ である。左から $V_m^*$ を掛け、$V_m^*V_{m+1}=(I_m\ \ 0)$ を使うと $V_m^*AV_m=H_m$ である。$\square$
(Saa03 Proposition 6.4〜6.6、pp. 160–161。上の主張は、そこで使う次数の議論をまとめたものである。)
$H_m$ は $i>j+1$ の成分が $0$ の行列(上 Hessenberg 行列)で、$A$ を $\mathcal K_m$ に制限して $\mathcal K_m$ へ直交射影した写像の、基底 $V_m$ に関する表現行列である。
$A$ を正則、$r_0\ne0$、$\beta=\|r_0\|$、$d=d(A,r_0)$ とし、Arnoldi の手順を $v=r_0$ に適用する。
1:$x=x_0+V_my$ とおくと、$x$ は $x_0+\mathcal K_m$ 全体を動く(thm-kry-arnoldi の 2)。$r_0=\beta v_1=\beta V_{m+1}e_1$ と thm-kry-arnoldi の 3 により
$$
b-Ax=r_0-AV_my=V_{m+1}\bigl(\beta e_1-\overline H_my\bigr)
$$
である。$V_{m+1}$ の列は正規直交なので $\|b-Ax\|=\|\beta e_1-\overline H_my\|$ である。$V_{m+1}\overline H_m=AV_m$ の階数は、$A$ が正則で $V_m$ の列が独立なので $m$ であり、$\overline H_m$ の列は線形独立である。よって 最小二乗法 の問題の解 $y_m$ はただ 1 つで、$x_m$ もただ 1 つである。
2:$V_dH_d=AV_d$ の階数は $d$ だから $H_d$ は正則である。$y:=\beta H_d^{-1}e_1$ とおくと、$r_0=\beta V_de_1$ から $b-A(x_0+V_dy)=V_d(\beta e_1-H_dy)=0$ である。
3:$\mathcal K_m\subset\mathcal K_{m+1}$ なので、最小値を取る集合が広がり $\|r_{m+1}\|\le\|r_m\|$ である。$r_m=0$ なら $x^*\in x_0+\mathcal K_m$ なので、thm-kry-finite により $m\ge d$ である。$\square$
(Saa03 §6.5.1、(6.29)・(6.30)、p. 172。Arnoldi が止まることと解が得られることの同値は同書 Proposition 6.10、p. 179。)
$A$ を正則、$m< d$ とする。Galerkin 条件を満たす $x_m$ が存在するのは $H_m$ が正則のときに限り、そのとき $x_m=x_0+V_my_m$、$H_my_m=\beta e_1$ であって、
$$
r_m=-h_{m+1,m}\,(e_m^{\mathsf T}y_m)\,v_{m+1},\qquad\|r_m\|=h_{m+1,m}\,\lvert e_m^{\mathsf T}y_m\rvert
$$
である。
$x=x_0+V_my$ とすると、$r=V_{m+1}(\beta e_1-\overline H_my)=V_m(\beta e_1-H_my)-h_{m+1,m}(e_m^{\mathsf T}y)v_{m+1}$ である。右辺の第 2 項は $\mathcal K_m$ に直交するので、$r\perp\mathcal K_m$ は $H_my=\beta e_1$ と同値であり、そのとき $r$ は第 2 項に等しい。$H_m$ が正則なら $y$ はただ 1 つに決まる。
$H_m$ が特異なら解がないことを示す。$u^*H_m=0$ となる $u=(u_1,\dots,u_m)^{\mathsf T}\ne0$ を取る。$H_my=\beta e_1$ の解があれば、左から $u^*$ を掛けて $\beta\overline{u_1}=0$、すなわち $u_1=0$ である。$u^*H_m=0$ の第 $j$ 列($j=1,\dots,m-1$)は $\sum_{i\le j+1}\overline{u_i}h_{ij}=0$ であり、$m< d$ なので $h_{j+1,j}\ne0$ である。$j=1,2,\dots$ と順に見ると $u_2=\cdots=u_m=0$ となり、$u\ne0$ に反する。$\square$
(残差の式は Saa03 Proposition 6.7、p. 166。)
FOM の残差は単調に減るとは限らない(ex-kry-3x3)。
$A$ を正則とし、$x\in x_0+\mathcal K_m(A,r_0)$ とする。
1:$x=x_0+q(A)r_0$($\deg q\le m-1$)なら $b-Ax=r_0-Aq(A)r_0=p(A)r_0$、$p(t)=1-tq(t)$ である。逆に $p(0)=1$、$\deg p\le m$ なら $q(t):=(1-p(t))/t$ は $m-1$ 次以下の多項式である。
2:1 と最小残差条件から従う。
3:$p(A)=Xp(\Lambda)X^{-1}$ と $\|p(\Lambda)\|=\max_i\lvert p(\lambda_i)\rvert$ から $\|p(A)r_0\|\le\kappa_2(X)\max_i\lvert p(\lambda_i)\rvert\|r_0\|$ である。右辺の多項式について最小を取り、2 を使う。$\square$
(Saa03 Lemma 6.31・Proposition 6.32、p. 216。)
Krylov部分空間法の収束の問題は、「$0$ で値 $1$ を取り、固有値の上で小さい多項式」があるかどうかの問題に読み替えられる。
$A$ が Hermite 行列なら、$H_m$ は実対称な三重対角行列である。$\alpha_j:=h_{jj}$、$\gamma_j:=h_{j+1,j}$($j< d(A,v)$ で $\gamma_j>0$)、$\gamma_0v_0:=0$、$\gamma_{d(A,v)}v_{d(A,v)+1}:=0$ とおくと
$$
Av_j=\gamma_{j-1}v_{j-1}+\alpha_jv_j+\gamma_jv_{j+1}
$$
である。
$H_m=V_m^*AV_m$(thm-kry-arnoldi の 3)は Hermite 行列である。$i>j+1$ の成分が $0$ なので、$j>i+1$ の成分も $0$ である。対角成分は実数で、$h_{j,j+1}=\overline{h_{j+1,j}}=\gamma_j$ である。これを $Av_j=\sum_ih_{ij}v_i$ に入れる。$\square$
(Saa03 Theorem 6.19、p. 194。)したがって基底を全部覚えなくても次のベクトルが作れる。
$A$ が Hermite 正定値のとき $\|x\|_A:=\langle Ax,x\rangle^{1/2}$ はノルムである。
$A$ を Hermite 正定値、$m\le d=d(A,r_0)$、$e^{(m)}:=x^*-x_m$ とする。Galerkin 条件を満たす $x_m\in x_0+\mathcal K_m(A,r_0)$ はただ 1 つ存在し、それは $\|x^*-x\|_A$ を $x_0+\mathcal K_m$ の上で最小にするただ 1 つの点である。とくに $\|e^{(m+1)}\|_A\le\|e^{(m)}\|_A$ で、$x_d=x^*$ である。
$\langle y,z\rangle_A:=\langle Ay,z\rangle$ は内積である。$x\in x_0+\mathcal K_m$、$e:=x^*-x$ とすると $b-Ax=Ae$ なので、$z\in\mathcal K_m$ について $\langle b-Ax,z\rangle=\langle e,z\rangle_A$ である。よって Galerkin 条件は $e\perp_A\mathcal K_m$ と同値である。
$\Pi$ を $\mathcal K_m$ への $\langle\cdot,\cdot\rangle_A$ に関する直交射影とする。$x=x_0+z$($z\in\mathcal K_m$)と書くと $e=e^{(0)}-z$ であり、$e\perp_A\mathcal K_m$ は $z=\Pi e^{(0)}$ と同値である。これで存在と一意性が言える。さらに三平方の定理により
$$
\|e^{(0)}-z\|_A^2=\|e^{(0)}-\Pi e^{(0)}\|_A^2+\|\Pi e^{(0)}-z\|_A^2
$$
なので、最小値は $z=\Pi e^{(0)}$ のときだけ取る。単調性は $\mathcal K_m\subset\mathcal K_{m+1}$ から従う。$x_d=x^*$ は thm-kry-finite から従う。$\square$
prop-kry-lanczos で $H_m$ が三重対角になることを使うと、この $x_m$ は短い漸化式で更新できる。その手順が 共役勾配法 である(Saa03 §6.7、Algorithm 6.18、pp. 199–200)。
$A$ を Hermite 正定値、固有値を $0< \lambda_{\min}\le\cdots\le\lambda_{\max}$、$\kappa:=\lambda_{\max}/\lambda_{\min}$ とする。thm-kry-energy の $x_m$($1\le m\le d$)について
$$
\|e^{(m)}\|_A\le\min_{\substack{\deg p\le m\\p(0)=1}}\ \max_{i}\lvert p(\lambda_i)\rvert\ \|e^{(0)}\|_A\le2\rho^m\,\|e^{(0)}\|_A,\qquad\rho:=\frac{\sqrt\kappa-1}{\sqrt\kappa+1}
$$
である。
$e^{(m)}$ の形:prop-kry-poly の 1 と同じ計算で、$x\in x_0+\mathcal K_m$ の誤差は $x^*-x=A^{-1}p(A)r_0=p(A)e^{(0)}$ であり、$p$ は $p(0)=1$ の $m$ 次以下の多項式を動く。
$A$ の固有値 $\lambda_i$ の正規直交な固有ベクトル $u_i$ を取り(Hermite行列 の定理「ユニタリ対角化できる行列」)、$e^{(0)}=\sum_ic_iu_i$ と展開すると
$$
\|p(A)e^{(0)}\|_A^2=\sum_i\lambda_i\lvert p(\lambda_i)\rvert^2\lvert c_i\rvert^2\le\max_i\lvert p(\lambda_i)\rvert^2\ \|e^{(0)}\|_A^2
$$
である。thm-kry-energy の最小性から第 1 の不等式が従う。
第 2 の不等式。$\kappa=1$ なら $A=\lambda I$ で、$p(t)=1-t/\lambda$ により左辺の最小値は $0$ である。$\kappa>1$ とし、
$$
\tau(t):=\frac{\lambda_{\max}+\lambda_{\min}-2t}{\lambda_{\max}-\lambda_{\min}},\qquad\sigma:=\tau(0)=\frac{\kappa+1}{\kappa-1}>1
$$
とおく。$\tau$ は $[\lambda_{\min},\lambda_{\max}]$ を $[-1,1]$ へ写す。$T_m$ を第 1 種の Chebyshev多項式 とし、$p(t):=T_m(\tau(t))/T_m(\sigma)$ とおくと、$p(0)=1$、$\deg p=m$ であり、$[-1,1]$ で $\lvert T_m\rvert\le1$(同記事の定理「Chebyshev 多項式の基本性質」の 4)なので、$\max_i\lvert p(\lambda_i)\rvert\le1/T_m(\sigma)$ である。
$z:=\sigma+\sqrt{\sigma^2-1}>1$ とおくと $z^{-1}=\sigma-\sqrt{\sigma^2-1}$、$2\sigma=z+z^{-1}$ であり、同記事の命題「$x=z+\frac{1}{z}$ での値」の 2 により $2T_m(\sigma)=z^m+z^{-m}\ge z^m$ である。$\sigma^2-1=4\kappa/(\kappa-1)^2$ から
$$
z=\frac{\kappa+1+2\sqrt\kappa}{\kappa-1}=\frac{(\sqrt\kappa+1)^2}{(\sqrt\kappa-1)(\sqrt\kappa+1)}=\frac1\rho
$$
である。よって $1/T_m(\sigma)\le2\rho^m$ である。$\square$
(Saa03 Theorem 6.29、p. 214 と (6.128)、p. 215。)$\kappa$ が大きいと $\rho\approx1-2/\sqrt\kappa$ で、誤差を $1/10$ にする段数はおよそ $\sqrt\kappa$ に比例する(条件数)。これは最悪の場合の上界であり、固有値が固まっているときや $d$ が小さいときの実際の収束はずっと速い(ex-kry-poisson)。
GMRES は段数 $m$ とともに記憶が増える。そこで $m$ 段ごとに $x_m$ を新しい初期値にしてやり直す方法を GMRES($m$)(再出発 GMRES)という。やり直しの 1 周の始めの残差を $r^{(k)}$ と書く。
ある $\mu>0$ について、すべての $x$ で $\operatorname{Re}\langle Ax,x\rangle\ge\mu\|x\|^2$ とする。このとき $A$ は正則で、どの $m\ge1$ でも GMRES($m$) の残差は
$$
\|r^{(k+1)}\|^2\le\Bigl(1-\frac{\mu^2}{\|A\|^2}\Bigr)\|r^{(k)}\|^2
$$
を満たす。とくに $\|r^{(k)}\|\to0$ である。
$Ax=0$ なら $\mu\|x\|^2\le0$ なので $A$ は単射で、正則である。$r:=r^{(k)}\ne0$ とする。1 周の最小残差の候補に $x+\alpha r$ が入るので、$\|r^{(k+1)}\|^2\le\min_\alpha\|r-\alpha Ar\|^2=\|r\|^2-\lvert\langle r,Ar\rangle\rvert^2/\|Ar\|^2$ である。$\lvert\langle r,Ar\rangle\rvert\ge\operatorname{Re}\langle Ar,r\rangle\ge\mu\|r\|^2$、$\|Ar\|\le\|A\|\,\|r\|$ を入れる。$\square$
(主張は Saa03 Theorem 6.30、p. 216。)この上界は収束の保証であり、速さの目安にはならないことが多い(ex-kry-restart)。
入力は $x\mapsto Ax$ を計算する手続き、$b$、$x_0$、許容誤差 $\varepsilon$(たとえば $10^{-8}$)、再出発の長さ $m$ である。
解に至らない場合の検出。 $h_{j+1,j}=0$ なのに $r_j\ne0$ なら、thm-kry-arnoldi の 1 と thm-kry-gmres の 2 により $A$ は特異である。$R_j$ の対角成分が $0$ になる場合も同じである。残差が周を重ねても減らないときは、再出発で止まっている可能性がある(反例の表の $\mu>0$ を外した行)。
手間。 $j$ 段目は行列とベクトルの積が 1 回、内積とベクトルの和がそれぞれ $j$ 回である。$m$ 段で内積と和の手間は合計でおよそ $2m^2n$ 回の演算になり、$m+1$ 本の基底を覚える(Saa03 §6.4、p. 167)。これが再出発や短い漸化式が要る理由である。
| 行列の型 | 方法 | 根拠・注意 |
|---|---|---|
| Hermite 正定値 | 共役勾配法 | thm-kry-energy、thm-kry-cheb |
| Hermite で正定値でない | 共役残差法、全基底の GMRES | Galerkin 条件は解けないことがある(反例の表の正定値性を外した行)。同じ行の例では $\langle Ar_0,r_0\rangle=0$ で、共役残差法も 1 段目で $\beta_0$ が定まらず止まる |
| 一般で、記憶に余裕がある | GMRES | thm-kry-gmres |
| 一般で、記憶に余裕がない | GMRES($m$)、BiCGSTAB | 再出発で止まることがある。BiCGSTAB は Saa03 §7.4.2(p. 244)。この記事では証明しない |
前処理。 収束が遅いときは、$A$ に近く $Mz=c$ が速く解ける行列 $M$ を選び、$M^{-1}Ax=M^{-1}b$(左前処理)や $AM^{-1}u=b$、$x=M^{-1}u$(右前処理)に方法を適用する。前者は前処理後の残差 $M^{-1}(b-Ax)$ を見ることになり、後者は元の残差をそのまま見られる(Saa03 §9.3、pp. 282–284)。
$$
A=\begin{pmatrix}1&1&1\\0&1&1\\0&0&1\end{pmatrix},\qquad b=e_3,\qquad x_0=0.
$$
使う公式:thm-kry-arnoldi、thm-kry-gmres、prop-kry-fom。
答え:$v_1=e_3$、$v_2=\frac1{\sqrt2}(1,1,0)^{\mathsf T}$、$v_3=\frac1{\sqrt2}(1,-1,0)^{\mathsf T}$、$d=3$ で
$$
H_3=\begin{pmatrix}1&0&0\\\sqrt2&\frac32&-\frac12\\0&\frac12&\frac12\end{pmatrix}.
$$
| $m$ | GMRES の $x_m$ | $\Vert r_m\Vert $ の値 | FOM の $x_m$ | $\Vert r_m\Vert $ の値 |
|---|---|---|---|---|
| $1$ | $(0,0,\frac13)$ | $\frac{\sqrt6}3\approx0.8165$ | $(0,0,1)$ | $\sqrt2\approx1.4142$ |
| $2$ | $(-\frac12,-\frac12,\frac56)$ | $\frac{\sqrt6}6\approx0.4082$ | $(-\frac23,-\frac23,1)$ | $\frac{\sqrt2}3\approx0.4714$ |
| $3$ | $(0,-1,1)$ | $0$ | $(0,-1,1)$ | $0$ |
FOM の 1 段目の残差は $\|r_0\|=1$ より大きい。GMRES の残差は単調に減り、どちらも $m=3$ で $x^*=(0,-1,1)^{\mathsf T}$ に届く。
Arnoldi:$Av_1=(1,1,1)^{\mathsf T}$、$h_{11}=1$、$w_1=(1,1,0)^{\mathsf T}$、$h_{21}=\sqrt2$。$Av_2=\frac1{\sqrt2}(2,1,0)^{\mathsf T}$、$h_{12}=0$、$h_{22}=\frac32$、$w_2=\frac1{2\sqrt2}(1,-1,0)^{\mathsf T}$、$h_{32}=\frac12$。$Av_3=\frac1{\sqrt2}(0,-1,0)^{\mathsf T}$、$h_{13}=0$、$h_{23}=-\frac12$、$h_{33}=\frac12$、$w_3=0$。
GMRES の $m=1$:$\min_\alpha\|e_3-\alpha(1,1,1)^{\mathsf T}\|$ は $\alpha=\frac13$ で、$r_1=\frac13(-1,-1,2)^{\mathsf T}$。FOM の $m=1$:$H_1=(1)$ から $y_1=1$、$\|r_1\|=h_{21}\lvert y_1\rvert=\sqrt2$。FOM の $m=2$:$y=(1,-\frac{2\sqrt2}3)^{\mathsf T}$、$\|r_2\|=h_{32}\cdot\frac{2\sqrt2}3=\frac{\sqrt2}3$。
$A=\operatorname{diag}(1,2,2,3,3,3)$、$b=(1,1,1,1,1,1)^{\mathsf T}$、$x_0=0$ を GMRES で解く。
使う公式:def-kry-subspace の後の次数の説明、thm-kry-finite、prop-kry-poly の 2。
答え:相異なる固有値は $3$ 個なので $d=3$ である。$\|r_0\|=\sqrt6\approx2.4495$、$\|r_1\|=\sqrt{5/9}\approx0.74536$、$\|r_2\|=\sqrt{6/83}\approx0.26887$、$r_3=0$ である。$n=6$ でも 3 段で解 $x^*=(1,\frac12,\frac12,\frac13,\frac13,\frac13)^{\mathsf T}$ に届く。$m=3$ の残差多項式は $p(t)=(1-t)(1-\frac t2)(1-\frac t3)$ である。
$m=1$:$r_1=b-\alpha Ab$、$\alpha=\langle b,Ab\rangle/\|Ab\|^2=14/36=\frac7{18}$($\langle b,Ab\rangle=1+4+9=14$、$\|Ab\|^2=1+8+27=36$)で、$\|r_1\|^2=6-\frac{14^2}{36}=\frac59$。
$m=2$:$r_2=b-y_1Ab-y_2A^2b$ の最小二乗の解は $y_1=\frac{84}{83}$、$y_2=-\frac{19}{83}$ で、$r_2=\frac1{83}(18,-9,-9,2,2,2)^{\mathsf T}$、$\|r_2\|^2=\frac{498}{83^2}=\frac6{83}$。
$n=100$、$A=\operatorname{tridiag}(-1,2,-1)$(Dirichlet 境界の $-u''=1$ の差分)、$b=(1,\dots,1)^{\mathsf T}$、$x_0=0$ とする。解は $x^*_i=\frac12i(101-i)$ である。Galerkin 条件の $x_m$ を、倍精度で基底を再直交化して計算する。
使う公式:thm-kry-energy、thm-kry-cheb。
答え:固有値は $\lambda_k=2-2\cos\frac{k\pi}{101}$ なので $\kappa=\cot^2\frac{\pi}{202}\approx4133.64$、$\rho\approx0.969369$ である。$b$ は対称なので偶数番の固有ベクトルの成分が消え、$d=50$ である。
| $m$ | $10$ | $20$ | $30$ | $40$ | $49$ | $50$ |
|---|---|---|---|---|---|---|
| $\Vert e^{(m)}\Vert _A/\Vert e^{(0)}\Vert _A$ の値 | $0.71818$ | $0.46933$ | $0.25857$ | $0.09471$ | $0.00483$ | $10^{-13}$ 未満 |
| 上界 $2\rho^m$ | $1.46528$ | $1.07353$ | $0.78651$ | $0.57623$ | $0.43551$ | $0.42217$ |
図 1 の左に全体を示す。上界は正しいが、実際の収束は $d=50$ で打ち切られるので、上界よりずっと速い。
左:Poisson 行列の Galerkin 解の誤差の比と上界。右:非対称な三重対角行列での GMRES(100)、GMRES(30)、GMRES(5) の相対残差
$n=100$、$A=\operatorname{tridiag}(-1.5,\,2,\,-0.5)$(下の副対角が $-1.5$)、$b=(1,\dots,1)^{\mathsf T}$、$x_0=0$ とする。$\|r\|\le10^{-8}\|b\|$ までの Arnoldi の総段数を比べる。判定は手順 3 の $\lvert g_{j+1}\rvert$ で行い、数えるのは Arnoldi の中の行列とベクトルの積だけで、周の変わり目の残差の計算し直しは数えない。
使う公式:thm-kry-finite、prop-kry-restart。
答え:
| 再出発の長さ $m$ | $100$ | $50$ | $30$ | $10$ | $5$ | $2$ |
|---|---|---|---|---|---|---|
| 総段数 | $100$ | $403$ | $350$ | $190$ | $152$ | $183$ |
| 覚える基底の本数 | $100$ | $51$ | $31$ | $11$ | $6$ | $3$ |
$A$ の対称部分の最小固有値は $\mu\approx0.000967$、$\|A\|\approx3.99915$ で、prop-kry-restart の因子は $1$ との差が約 $5.9\times10^{-8}$ しかない。この例では、再出発しない GMRES は残差の減りが遅く、$n$ 段目でようやく解に届く(図 1 の右)。再出発の長さを長くすれば総段数が減るとも限らない。$A$ が正規行列でないので、固有値だけでは収束の様子は読めない。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $A$ が正則 | $A=\begin{pmatrix}0&1\\0&0\end{pmatrix}$、$b=e_1$、$x_0=0$ | $Ax=b$ は解 $x=e_2$ を持つが、$\mathcal K_m=\operatorname{span}\{e_1\}$ に解がない。Arnoldi は 1 段で止まるのに $r_1\ne0$(thm-kry-finite、thm-kry-gmres の 2) |
| Hermite 行列の正定値性 | $A=\operatorname{diag}(-1,1)$、$r_0=(1,1)^{\mathsf T}$ | $\kappa_2(A)=1$ なのに $\Vert r_1\Vert $ が $\Vert r_0\Vert $ のまま。$H_1=(0)$ で Galerkin 条件の解がない(thm-kry-energy、thm-kry-cheb) |
| Hermite 性 | $4$ 次の巡回置換行列 $Pe_j=e_{j+1}$($Pe_4=e_1$)、$b=e_1$、$x_0=0$ | $h_{14}=1\ne0$ で 3 項の漸化式にならない。GMRES の残差は $m=1,2,3$ で $\Vert r_m\Vert =1$ のまま(prop-kry-lanczos) |
| 対角化可能性($\kappa_2(X)$ の因子) | $A=\begin{pmatrix}1&1\\0&1\end{pmatrix}$、$b=e_2$、$x_0=0$ | 固有値は $1$ だけで $p(t)=1-t$ が固有値の上で $0$ だが、$\Vert r_1\Vert =\frac1{\sqrt2}\ne0$(prop-kry-poly の 3) |
| 再出発の収束の $\mu>0$ | $A=\begin{pmatrix}0&-1\\1&0\end{pmatrix}$、$r_0=e_1$ | GMRES(1) は永久に $r=e_1$ のまま。全基底の GMRES は $2$ 段で解く(prop-kry-restart) |
正則性:$Ae_1=0$ より $\mathcal K_m=\operatorname{span}\{e_1\}$、$d=1$ で、$\operatorname{span}\{e_1\}$ の点 $x$ は $Ax=0\ne b$ である。条件のうち正則性だけを満たさない。
正定値性:$\langle Ar_0,r_0\rangle=0$ なので $H_1=(0)$ である。$\|r_0-\alpha Ar_0\|^2=(1+\alpha)^2+(1-\alpha)^2$ は $\alpha=0$ で最小値 $2$ を取るので、$r_1=r_0$ である。$A$ は Hermite で、固有値が $0$ をはさむ点だけが正定値な場合と違う。
Hermite 性:$v_j=e_j$ で、$H_4=P$ である。$m\le3$ で $A\mathcal K_m=\operatorname{span}\{e_2,\dots,e_{m+1}\}$ は $e_1$ に直交するので、最小残差は $y=0$ で取り $r_m=e_1$ である。$m=4$ で $x^*=e_4$ を得る。$P$ は 正規行列 であり、prop-kry-poly の 3 と矛盾しない。固有値は $1$ の 4 乗根で、$3$ 次以下の多項式の 4 点での値の平均は定数項に等しいから、$p(0)=1$ なら $\max_i\lvert p(\lambda_i)\rvert\ge1$ である。
対角化可能性:$r_0=e_2$、$Ar_0=(1,1)^{\mathsf T}$、最小残差の $\alpha=\frac12$ で $r_1=\frac12(-1,1)^{\mathsf T}$ である。$A$ は対角化できないので、$\kappa_2(X)$ の因子ごと上界が意味を失う。
$\mu>0$:$\langle Ae_1,e_1\rangle=0$ で $\mu>0$ の条件だけを満たさない($A$ は正則)。$\|e_1-\alpha e_2\|$ は $\alpha=0$ で最小である。周ごとに同じ計算が繰り返される。$x^*=-e_2$ は $\mathcal K_2=\mathbb R^2$ に入る。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 高々 $n$ 段で解けるので直接法の代わりになる | $n$ 段の有限停止は丸めのない計算の話で、実用上は $n$ よりずっと少ない段数で打ち切る反復法として使う | thm-kry-finite の次数 $d$ は丸めがあると厳密には見えない |
| $h_{j+1,j}=0$ は解が得られない印である | $A$ が正則なら解に到達した合図である | thm-kry-gmres の 2 |
| 残差が小さいので誤差も小さい | $\Vert e\Vert/\Vert x^*\Vert\le\kappa(A)\Vert r\Vert/\Vert b\Vert$ までしか言えない | $e=A^{-1}r$、$\Vert b\Vert\le\Vert A\Vert\,\Vert x^*\Vert$。条件数 |
| 条件数が小さければ必ず速く収束する | 上界が成り立つのは Hermite 正定値のときである | 反例の表の正定値性を外した行 |
| 固有値が固まっていれば GMRES は速い | $A$ が正規行列でなければ、固有値だけでは決まらない | 反例の表の対角化可能性を外した行、ex-kry-restart |
| 再出発の長さは長いほどよい | 総段数は単調に減るとは限らない | ex-kry-restart |
| FOM の残差も単調に減る | 単調に減るのは GMRES の残差である。FOM は増えることがある | ex-kry-3x3 |
短い漸化式で書ける行列。 Hermite 行列では prop-kry-lanczos のように基底の漸化式が短い。一般の行列で、どの初期ベクトルでも Arnoldi の基底が短い漸化式で済むのは、最小多項式の次数が小さい場合と、$A$ が正規で $A^*$ が $A$ の次数の低い多項式で書ける場合に限られる(Faber–Manteuffel の定理。Saa03 Theorem 6.24、p. 208。この記事では証明しない)。非対称な行列で短い漸化式を保つには、BiCG などのように直交性を別の条件に替える(同書第 7 章)。
固有値の計算。 $H_m$ は $A$ を $\mathcal K_m$ に圧縮した行列なので、$H_m$ の固有値は $A$ の 固有値 の近似に使える。$A$ が Hermite なら、$H_m$ の固有値は $\mathcal K_m$ の上の Rayleigh商 の停留値である。
関連する手法。 数値線形代数 の直接法は密な行列に向き、Krylov部分空間法は疎な行列に向く。Jacobi 法などの定常反復(反復法(連立1次方程式))は、反復行列が段によらない方法で、Krylov部分空間法の前処理としても使う。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する