Krylov部分空間法

同義語:クリロフ部分空間法Krylov subspace method

概要

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$ ノルムが最小になり、収束は条件数で評価できる。

$$\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次方程式, 固有値, 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$ は標準基底のベクトルである。

Krylov 部分空間と次数

$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$ の個数に等しい。

Krylov 部分空間上の 2 つの条件

$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 つである。

  1. Galerkin 条件:$r_m\perp\mathcal K_m(A,r_0)$。一般の行列でこれを解く方法を FOM(full orthogonalization method)という。
  2. 最小残差条件:$\|r_m\|=\min\{\|b-Ax\|\mid x\in x_0+\mathcal K_m(A,r_0)\}$。一般の行列でこれを解く方法を GMRES(generalized minimal residual method)という。

この定義は Saa03 第 6 章の冒頭(pp. 157–158)と §6.4(p. 165)、§6.5(p. 171)による。
使える条件。 この記事の公式と手順は、次の条件のもとで述べる。

  • (i) $A$ は正方行列で正則である。
  • (ii) $x\mapsto Ax$ の計算が速い(疎行列、高速 Fourier 変換で掛けられる行列など)。
  • (iii) 手法ごとの条件:次の表の「行列の条件」の列。
    方法行列の条件$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

主定理と証明

部分空間の基本性質と有限停止

Krylov 部分空間の基本性質

$v\ne0$、$d=d(A,v)$ とする。

  1. $\mathcal K_m(A,v)=\{p(A)v\mid p\text{ は }m-1\text{ 次以下の多項式}\}$ である。
  2. $\dim\mathcal K_m(A,v)=\min\{m,d\}$ である。
  3. $A\mathcal K_d(A,v)\subset\mathcal K_d(A,v)$ であり、$m\ge d$ で $\mathcal K_m(A,v)=\mathcal K_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$ は小さく、丸めのない計算では少ない段数で解に届く。

Arnoldi の手順

$\mathcal K_m$ の自然な基底 $v,Av,A^2v,\dots$ はすぐに平行に近づく。そこで Gram–Schmidtの直交化 で 1 段ごとに直交化する。

Arnoldi の手順

$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$ を定める。

Arnoldi の関係式

$v\ne0$、$d=d(A,v)$ とする。

  1. 手順はちょうど $j=d$ の段で止まる。
  2. $1\le m\le d$ で、$v_1,\dots,v_m$ は $\mathcal K_m(A,v)$ の正規直交基底である。
  3. $m< d$ で $AV_m=V_{m+1}\overline H_m$、$m=d$ で $AV_d=V_dH_d$ である。どの $m\le d$ でも $V_m^*AV_m=H_m$ である。
段数についての帰納法

$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$ に関する表現行列である。

GMRES と FOM の公式

GMRES の公式と単調性

$A$ を正則、$r_0\ne0$、$\beta=\|r_0\|$、$d=d(A,r_0)$ とし、Arnoldi の手順を $v=r_0$ に適用する。

  1. $m< d$ で $\overline H_m$ の列は線形独立であり、最小残差条件を満たす $x_m$ はただ 1 つで、
    $$ x_m=x_0+V_my_m,\qquad y_m=\operatorname*{argmin}_{y\in\mathbb K^m}\|\beta e_1-\overline H_my\|,\qquad\|r_m\|=\min_y\|\beta e_1-\overline H_my\| $$
    である。ここで $e_1\in\mathbb K^{m+1}$ である。
  2. $m=d$ で $H_d$ は正則であり、$x_d=x_0+\beta V_dH_d^{-1}e_1=x^*$ である。
  3. $\|r_{m+1}\|\le\|r_m\|$ であり、$r_m=0$ となるのは $m=d$ のときに限る($m\le d$ の範囲で)。
正規直交な列で問題を小さくする

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。)

FOM の公式

$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. $b-Ax=p(A)r_0$ となる $m$ 次以下の多項式 $p$ で $p(0)=1$ を満たすものがある。逆に、そのような $p$ はどれも、$x_0+\mathcal K_m$ の点 $x$ の残差として現れる。
  2. GMRES の残差は $\|r_m\|=\min\{\|p(A)r_0\|\mid\deg p\le m,\ p(0)=1\}$ を満たす。
  3. $A=X\Lambda X^{-1}$、$\Lambda=\operatorname{diag}(\lambda_1,\dots,\lambda_n)$ と対角化できるなら、$\kappa_2(X):=\|X\|\,\|X^{-1}\|$ として
    $$ \|r_m\|\le\kappa_2(X)\,\min_{\substack{\deg p\le m\\p(0)=1}}\ \max_{1\le i\le n}\lvert p(\lambda_i)\rvert\ \|r_0\| $$
    である。$A$ が 正規行列 なら $X$ をユニタリに取れて $\kappa_2(X)=1$ である。
多項式に読み替える
証明を開く

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$ を取り、固有値の上で小さい多項式」があるかどうかの問題に読み替えられる。

Hermite 行列の場合

Lanczos の 3 項の漸化式

$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} $$
である。

Hermite かつ Hessenberg
証明を開く

$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}$ はノルムである。

Galerkin 条件と $A$ ノルムの最小化

$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^*$ である。

$A$ 内積での直交射影

$\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} $$
である。

Chebyshev 多項式を試す

$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$ である。

1 段だけで得られる減少
証明を開く

$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)。

計算の手順

GMRES($m$) の手順

入力は $x\mapsto Ax$ を計算する手続き、$b$、$x_0$、許容誤差 $\varepsilon$(たとえば $10^{-8}$)、再出発の長さ $m$ である。

  1. 準備:$r_0=b-Ax_0$、$\beta=\|r_0\|$、$v_1=r_0/\beta$ とする。$\beta\le\varepsilon\|b\|$ なら止まる。
  2. Arnoldi の 1 段($j=1,2,\dots$):$w\leftarrow Av_j$ とし、$i=1,\dots,j$ の順に $h_{ij}\leftarrow\langle w,v_i\rangle$、$w\leftarrow w-h_{ij}v_i$ と更新する(修正 Gram–Schmidt。def-kry-arnoldi と丸めのない計算では同じ結果になる)。$h_{j+1,j}\leftarrow\|w\|$ とする。
  3. 最小二乗の更新(thm-kry-gmres):$\overline H_j$ を Givens 回転で上三角にする。前の段の回転を新しい列に掛け、1 回の回転を足すだけでよい。$Q_j\overline H_j$ の上の $j$ 行を $R_j$、$Q_j\beta e_1=(g_1,\dots,g_{j+1})^{\mathsf T}$ とすると、$Q_j$ がユニタリなので $\|r_j\|=\lvert g_{j+1}\rvert$ である。
  4. 止める判定:$\lvert g_{j+1}\rvert\le\varepsilon\|b\|$ または $h_{j+1,j}=0$ なら手順 6 へ。
  5. 次の段:$h_{j+1,j}\ne0$ なら $v_{j+1}=w/h_{j+1,j}$ とする。$j< m$ なら手順 2 へ戻る。
  6. 解の更新:$R_jy=(g_1,\dots,g_j)^{\mathsf T}$ を解き、$x\leftarrow x_0+V_jy$ とする。
  7. 確かめ:$r=b-Ax$ を計算し直す。$\|r\|\le\varepsilon\|b\|$ なら終わる。そうでなければ $x_0\leftarrow x$ として手順 1 へ戻る(反復の上限を決めておく)。

解に至らない場合の検出。 $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 で正定値でない共役残差法、全基底の GMRESGalerkin 条件は解けないことがある(反例の表の正定値性を外した行)。同じ行の例では $\langle Ar_0,r_0\rangle=0$ で、共役残差法も 1 段目で $\beta_0$ が定まらず止まる
一般で、記憶に余裕があるGMRESthm-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)。

例題

非対称な 3 次の行列の GMRES と FOM

$$ 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}$。

差分の Poisson 行列

$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) の相対残差 左: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部分空間法の前処理としても使う。

関連項目

参考文献

[1]
Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003, 第 6 章(pp. 157–158、§6.4 p. 165、p. 167、§6.5 p. 171–172)、Proposition 6.1・6.2(p. 158)、Proposition 6.4〜6.6(pp. 160–161)、Proposition 6.7(p. 166)、Proposition 6.10(p. 179)、Theorem 6.19(p. 194)、Algorithm 6.18(pp. 199–200)、§6.8(p. 203)、Theorem 6.24(p. 208)、Theorem 6.29(p. 214)、(6.128)(p. 215)、Theorem 6.30・Lemma 6.31・Proposition 6.32(p. 216)、§7.4.2(p. 244)、§9.3(pp. 282–284)

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