共役勾配法(conjugate gradient method)とは、Hermite 正定値行列 $A$ の連立 1 次方程式 $Ax=b$ を、残差と探索方向の短い漸化式で解く反復法である。残差は互いに直交し、探索方向は $A$ について互いに共役で、各段の近似解は、初期値に Krylov 部分空間を足した範囲で誤差の $A$ ノルムを最小にする。丸めのない計算では初期残差の次数の段数で解に届き、$m$ 段後の $A$ ノルムの誤差は、条件数 $\kappa$ から定まる $\rho=(\sqrt\kappa-1)/(\sqrt\kappa+1)$ を用いて初期の誤差の $2\rho^m$ 倍以下になる。大きな疎行列の方程式に使い、前処理と組み合わせて収束を速める。
前提知識: 正定値行列, 反復法(連立1次方程式), Krylov部分空間法, 条件数
共役勾配法(conjugate gradient method、CG 法)とは、Hermite 正定値行列 $A$ の連立 1 次方程式 $Ax=b$ を、残差と探索方向の短い漸化式で解く反復法である。1 段の手間は行列とベクトルの積 1 回、内積 2 回、ベクトルの和 3 回で、覚えるベクトルも 4 本で済むのに、各段の近似解は、初期値に Krylov 部分空間を足した範囲で誤差の $A$ ノルムを最小にする。
$A$ が Hermite 正定値のとき、$Ax=b$ を解くことは 2 次関数
$$
f(x):=\tfrac12x^*Ax-\operatorname{Re}(x^*b)
$$
の最小化と同じである。実際、$x^{\star}:=A^{-1}b$ とすると $f(x)-f(x^{\star})=\frac12(x-x^{\star})^*A(x-x^{\star})$ である。$f$ が最も急に下がる方向は残差 $r=b-Ax$ なので、まず思いつくのは、$r$ の方向に下れるだけ下ることの繰り返し(最急降下法)である。しかしこれは、等高線が細長い楕円のときジグザグに進み、$A=\operatorname{diag}(1,10)$ のような 2 次の行列でも、初期値によっては有限回で止まらない(反例の表の共役性の行)。
原因は、前の段で最小にした方向の成果を、次の段で失わせることにある。そこで探索方向を「$A$ について直交する」ように選ぶ。すると各段の最小化が前の段の成果を失わせず、$m$ 段後の近似解は、$m$ 次元の部分空間に初期値を足した範囲全体での最小点になる。
Galerkin 条件の解が $A$ ノルムの最小点であること、誤差の上界 $2\rho^m$、Lanczos の 3 項の漸化式は Krylov部分空間法 で証明した。この記事は、その解を計算する 漸化式と手順 を与える。漸化式が Galerkin 解を与えること(thm-cg-main)を証明し、1 段の誤差の減り方、前処理、止め方を述べる。
以下、$\mathbb K$ は $\mathbb R$ または $\mathbb C$、$A\in M_n(\mathbb K)$ は Hermite 正定値、$b\in\mathbb K^n$ とする。$\langle x,y\rangle:=y^*x$、$\|x\|:=\langle x,x\rangle^{1/2}$、$\|x\|_A:=\langle Ax,x\rangle^{1/2}$ とする。解を $x^{\star}:=A^{-1}b$ と書き、$k$ 段目の誤差を $e_k:=x^{\star}-x_k$ と書く(Krylov部分空間法 の $e^{(k)}$ と同じ符号である)。
$p,q\in\mathbb K^n$ が $\langle Ap,q\rangle=0$ を満たすとき、$p$ と $q$ は $A$ について 共役 である($A$ 直交ともいう)。$A$ が単位行列なら、これは直交と同じである。
$0$ でないベクトルが互いに共役なら線形独立である。実際、$\sum_ic_ip_i=0$ と $Ap_j$ の内積を取ると $c_j\langle Ap_j,p_j\rangle=0$ で、正定値性から $c_j=0$ である。
$x_0\in\mathbb K^n$ を初期値とし、$r_0:=b-Ax_0$、$p_0:=r_0$ とする。$k=0,1,2,\dots$ について、$r_k\ne0$ である間
$$
\alpha_k:=\frac{\langle r_k,r_k\rangle}{\langle Ap_k,p_k\rangle},\qquad x_{k+1}:=x_k+\alpha_kp_k,\qquad r_{k+1}:=r_k-\alpha_kAp_k,
$$
$$
\beta_k:=\frac{\langle r_{k+1},r_{k+1}\rangle}{\langle r_k,r_k\rangle},\qquad p_{k+1}:=r_{k+1}+\beta_kp_k
$$
と計算する。この手順を 共役勾配法 という。$p_k$ を 探索方向 という。
帰納法で $r_k=b-Ax_k$ である($b-Ax_{k+1}=b-Ax_k-\alpha_kAp_k$)。$\alpha_k$ は正、$\beta_k$ は $0$ 以上の実数である。分母が $0$ にならないことは thm-cg-main で示す。
使える条件。
$d$ は $r_0$ の $A$ に関する次数、すなわち $p(A)r_0=0$ となる最高次の係数が $1$ の多項式の次数の最小値である。$r_0$ を固有空間の成分に分けたとき、$0$ でない成分を持つ相異なる固有値の個数に等しい。$\kappa:=\lambda_{\max}/\lambda_{\min}$、$\rho:=(\sqrt\kappa-1)/(\sqrt\kappa+1)$ とする。
| 公式 | 使える条件 | 根拠 |
|---|---|---|
| $\langle r_i,r_j\rangle=0$、$\langle Ap_i,p_j\rangle=0$($i\ne j$) | $r_0\ne0$ | thm-cg-main |
| $\operatorname{span}\{r_0,\dots,r_{m-1}\}=\operatorname{span}\{p_0,\dots,p_{m-1}\}=\mathcal K_m(A,r_0)$ | $1\le m\le d$ | thm-cg-main |
| $\Vert e_m\Vert_A=\min\{\Vert x^{\star}-x\Vert_A\mid x\in x_0+\mathcal K_m(A,r_0)\}$ | $m\le d$ | thm-cg-main |
| $r_d=0$ で、$k< d$ では $r_k\ne0$ | 丸めのない計算 | thm-cg-main |
| $\Vert e_k\Vert_A^2-\Vert e_{k+1}\Vert_A^2=\alpha_k\Vert r_k\Vert^2$ | $k< d$ | prop-cg-decrease |
| $\Vert e_{k+1}\Vert< \Vert e_k\Vert$ | $k< d$ | prop-cg-euclid |
| $\Vert e_m\Vert_A\le2\rho^m\Vert e_0\Vert_A$ | $1\le m\le d$ | Krylov部分空間法 |
| $\Vert e_{s+m}\Vert_A\le2\tilde\rho^{\,m}\Vert e_0\Vert_A$ | 外れ値の固有値が $s$ 個 | cor-cg-outlier |
| $\Vert e_m\Vert_A\le2\rho_M^m\Vert e_0\Vert_A$ | 前処理 $M$ が Hermite 正定値 | prop-cg-pcg |
$r_0\ne0$、$d:=d(A,r_0)$ とする。def-cg-method の漸化式は $k< d$ で分母が $0$ にならずに定まり、$0\le m\le d$ で次が成り立つ。
$m=0$ では $\mathcal K_0=\{0\}$ で、1〜3 は空な主張である。$m< d$ とし、$m$ まで 1〜3 が成り立つとして $m+1$ の場合を示す。
$r_m\ne0$ と分母。 3 と $x_{j+1}-x_j=\alpha_jp_j$ から $x_m\in x_0+\mathcal K_m$ である。$r_m=0$ なら $x^{\star}=x_m\in x_0+\mathcal K_m$ となるが、Krylov部分空間法 の定理「有限回で解に到達すること」により $x^{\star}\in x_0+\mathcal K_m$ となる最小の $m$ は $d$ なので、$m< d$ に反する。よって $r_m\ne0$ である。$m=0$ なら $p_0=r_0\ne0$ である。$m\ge1$ なら、$p_m=r_m+\beta_{m-1}p_{m-1}$ で、1 と 3 から $r_m\perp p_{m-1}$ なので $\|p_m\|^2=\|r_m\|^2+\beta_{m-1}^2\|p_{m-1}\|^2>0$ である。よって $\langle Ap_m,p_m\rangle>0$ で $\alpha_m$ は定まり、同じ直交性から
$$
\langle r_m,p_m\rangle=\|r_m\|^2,\qquad\text{すなわち}\qquad\alpha_m=\frac{\langle r_m,p_m\rangle}{\langle Ap_m,p_m\rangle}
$$
である。$\beta_m$ も定まる。
3 の $m+1$ の場合。 $m\ge1$ なら $r_m=r_{m-1}-\alpha_{m-1}Ap_{m-1}$ と $p_{m-1}\in\mathcal K_m$ から $r_m\in\mathcal K_{m+1}$ である($m=0$ なら $r_0\in\mathcal K_1$)。$r_m\ne0$ は $\mathcal K_m=\operatorname{span}\{r_0,\dots,r_{m-1}\}$ に直交するので、$r_m\notin\mathcal K_m$ である。Krylov部分空間法 の命題「Krylov 部分空間の基本性質」により $\dim\mathcal K_{m+1}=m+1$ なので、$\operatorname{span}\{r_0,\dots,r_m\}=\mathcal K_{m+1}$ である。$p_m-r_m\in\operatorname{span}\{p_0,\dots,p_{m-1}\}$ なので、$p$ の張る空間も同じである。
1 の $m+1$ の場合。 $j< m$ なら、$\langle r_{m+1},p_j\rangle=\langle r_m,p_j\rangle-\alpha_m\langle Ap_m,p_j\rangle=0$ である(1 と 3 と 2 による)。$j=m$ なら、上の $\alpha_m$ の式から $\langle r_{m+1},p_m\rangle=\langle r_m,p_m\rangle-\alpha_m\langle Ap_m,p_m\rangle=0$ である。よって $r_{m+1}$ は $\mathcal K_{m+1}$ に直交し、1 が成り立つ。
2 の $m+1$ の場合。 $m+1< d$ とする。$A$ が Hermite なので、$j\le m$ について
$$
\langle Ap_{m+1},p_j\rangle=\langle r_{m+1},Ap_j\rangle+\beta_m\langle Ap_m,p_j\rangle
$$
である。$j< m$ なら、$Ap_j\in\mathcal K_{j+2}\subset\mathcal K_{m+1}$ なので第 1 項は $0$ で、第 2 項は 2 により $0$ である。$j=m$ なら、$Ap_m=(r_m-r_{m+1})/\alpha_m$ と $r_{m+1}\perp r_m$ から $\langle r_{m+1},Ap_m\rangle=-\|r_{m+1}\|^2/\alpha_m$ である。一方 $\beta_m\langle Ap_m,p_m\rangle=\frac{\|r_{m+1}\|^2}{\|r_m\|^2}\cdot\frac{\|r_m\|^2}{\alpha_m}=\|r_{m+1}\|^2/\alpha_m$ である。和は $0$ である。
4。 $x_m\in x_0+\mathcal K_m$ は上で見た。$r_m\perp\mathcal K_m$ は 1 と 3 である。これは Galerkin 条件なので、Krylov部分空間法 の定理「Galerkin 条件と $A$ ノルムの最小化」により $x_m$ は最小点であり、$x_d=x^{\star}$ である。$\square$
(漸化式は Saa03 §6.7.1、Algorithm 6.18、pp. 199–200、直交性と共役性は同書 Proposition 6.20、p. 198。そこでは Lanczos の手順の $LU$ 分解から導く。上の証明は漸化式から直接の帰納法で示したものである。)
$p_{k+1}$ は $r_{k+1}$ から $p_k$ の成分を $A$ 直交に引いたものであり、$p_0,\dots,p_{k-1}$ の成分を引く必要がないのは、$A$ が Hermite で $r_{k+1}$ が $\mathcal K_{k+1}$ に直交するからである。これが短い漸化式の理由である。$A$ が Hermite でないと、この段が通らない(反例の表の Hermite 性の行)。
$k< d$ とする。$\alpha_k$ は $t\in\mathbb R$ の関数 $\|e_k-tp_k\|_A^2$ を最小にする値であり、
$$
\|e_k\|_A^2-\|e_{k+1}\|_A^2=\alpha_k\|r_k\|^2
$$
である。とくに $\|e_0\|_A^2=\sum_{k=0}^{d-1}\alpha_k\|r_k\|^2$ である。
$Ae_k=r_k$ なので、thm-cg-main の証明の $\langle r_k,p_k\rangle=\|r_k\|^2$ を使うと
$$
\|e_k-tp_k\|_A^2=\|e_k\|_A^2-2t\|r_k\|^2+t^2\langle Ap_k,p_k\rangle
$$
である。これは $t=\|r_k\|^2/\langle Ap_k,p_k\rangle=\alpha_k$ で最小になり、最小値は $\|e_k\|_A^2-\alpha_k\|r_k\|^2$ である。$e_{k+1}=e_k-\alpha_kp_k$ なので式が従う。$e_d=0$ なので和の式が出る。$\square$
$\alpha_k\|r_k\|^2$ は手元の量なので、この式は誤差の見積もりに使える。$k+s\le d$ なら $\|e_k\|_A^2\ge\sum_{j=k}^{k+s-1}\alpha_j\|r_j\|^2$ で、差は $\|e_{k+s}\|_A^2$ である。
$k< d$ なら $\|e_{k+1}\|< \|e_k\|$ である。また $j\le d-1$ について
$$
p_j=\|r_j\|^2\sum_{i=0}^j\frac{r_i}{\|r_i\|^2}
$$
である。
$p$ の式は、$j=0$ で明らかで、$p_{j+1}=r_{j+1}+\frac{\|r_{j+1}\|^2}{\|r_j\|^2}p_j$ から帰納法で従う。$r_i$ の直交性から、$j,l\le d-1$ について $\langle p_j,p_l\rangle=\|r_j\|^2\|r_l\|^2\sum_{i\le\min(j,l)}\|r_i\|^{-2}>0$ である。$e_{k+1}=\sum_{j=k+1}^{d-1}\alpha_jp_j$($e_d=0$ による)なので、$\langle e_{k+1},p_k\rangle\ge0$ である。$e_k=e_{k+1}+\alpha_kp_k$ から $\|e_k\|^2=\|e_{k+1}\|^2+2\alpha_k\langle e_{k+1},p_k\rangle+\alpha_k^2\|p_k\|^2>\|e_{k+1}\|^2$ である。$\square$
誤差の $A$ ノルムと Euclid ノルムは単調に減るが、残差のノルム $\|r_k\|$ は単調に減るとは限らない(ex-cg-residual)。
$v_1,v_2,\dots$ を $v=r_0$ から作った Lanczos のベクトルとし、Krylov部分空間法 の命題「Lanczos の 3 項の漸化式」の対角成分を $a_j$、副対角成分を $\gamma_j$ と書く。$k< d$ で
$$
r_k=(-1)^k\|r_k\|\,v_{k+1}
$$
であり、$a_1=\dfrac1{\alpha_0}$、$a_{k+1}=\dfrac1{\alpha_k}+\dfrac{\beta_{k-1}}{\alpha_{k-1}}$($k\ge1$)、$\gamma_{k+1}=\dfrac{\sqrt{\beta_k}}{\alpha_k}$($k+1< d$)である。
$r_k$ と $v_{k+1}$ はどちらも $\mathcal K_{k+1}$ の元で $\mathcal K_k$ に直交する。この直交補空間は 1 次元なので、$r_k=c\|r_k\|v_{k+1}$($\lvert c\rvert=1$)である。$A^kr_0$ の係数を見る。漸化式から $r_k$ の係数は $r_{k-1}$ の係数の $-\alpha_{k-1}$ 倍なので符号は $(-1)^k$ である。$v_{k+1}$ の係数は、Arnoldi の手順が正の数で割るだけなので正である。よって $c=(-1)^k$ である。
$k\ge1$ とする。$Ap_k=Ar_k+\beta_{k-1}Ap_{k-1}$ に $Ap_j=(r_j-r_{j+1})/\alpha_j$ を入れると $Ar_k=-\frac1{\alpha_k}r_{k+1}+\bigl(\frac1{\alpha_k}+\frac{\beta_{k-1}}{\alpha_{k-1}}\bigr)r_k-\frac{\beta_{k-1}}{\alpha_{k-1}}r_{k-1}$ である。$r_j$ を $v_{j+1}$ で書き直し、$\|r_{k+1}\|/\|r_k\|=\sqrt{\beta_k}$ を使って 3 項の漸化式と比べる。$k=0$ は $Ar_0=(r_0-r_1)/\alpha_0$ を使う。$\square$
(Saa03 (6.99)・(6.102)・(6.103)、pp. 202–203。)$\gamma$ と $a$ からなる 3 重対角行列の固有値は $A$ の固有値の近似になるので、共役勾配法の係数から $\kappa$ を見積もれる(同書 §6.7.3、pp. 201–202)。
$\|e_m\|_A\le2\rho^m\|e_0\|_A$($\rho=(\sqrt\kappa-1)/(\sqrt\kappa+1)$)は Krylov部分空間法 の定理「条件数による収束の上界」である。同じ定理の途中の不等式
$$
\|e_m\|_A\le\min_{\substack{\deg p\le m\\p(0)=1}}\ \max_i\lvert p(\lambda_i)\rvert\ \|e_0\|_A
$$
は、固有値の分布そのものを見ている。固有値が固まっているときは上界よりずっと速い。
$0< a< b$ とし、$A$ の相異なる固有値のうち $s$ 個は $b$ より大きく、残りはすべて $[a,b]$ に入るとする。$\tilde\kappa:=b/a$、$\tilde\rho:=(\sqrt{\tilde\kappa}-1)/(\sqrt{\tilde\kappa}+1)$ とすると、$m\ge1$、$s+m\le d$ で
$$
\|e_{s+m}\|_A\le2\tilde\rho^{\,m}\|e_0\|_A
$$
である。
$\mu_1,\dots,\mu_s$ を外れ値の固有値とする。Krylov部分空間法 の定理「条件数による収束の上界」の証明の多項式を $\lambda_{\min},\lambda_{\max}$ を $a,b$ に替えて作ったものを $g$ とする。$g(0)=1$、$\deg g=m$ で、$[a,b]$ で $\lvert g\rvert\le2\tilde\rho^{\,m}$ である($a< b$ なので $\tilde\kappa>1$ である)。$p(t):=g(t)\prod_{i=1}^s(1-t/\mu_i)$ とおくと、$p(0)=1$、$\deg p=s+m$ である。外れ値の固有値で $p=0$ であり、$[a,b]$ では各因子の絶対値が $1$ 以下なので $\lvert p\rvert\le2\tilde\rho^{\,m}$ である。上の不等式に入れる。$\square$
$\kappa$ が大きいときは、$A$ に近く $Mz=c$ が速く解ける Hermite 正定値行列 $M$ を選ぶ。$M^{-1}A$ は一般に Hermite でないが、次の手順は Hermite 性を保って共役勾配法を当てたものになる。
$M$ を Hermite 正定値行列とする。$r_0:=b-Ax_0$、$z_0:=M^{-1}r_0$、$p_0:=z_0$ とし、$k=0,1,\dots$ について
$$
\alpha_k:=\frac{\langle r_k,z_k\rangle}{\langle Ap_k,p_k\rangle},\quad x_{k+1}:=x_k+\alpha_kp_k,\quad r_{k+1}:=r_k-\alpha_kAp_k,\quad z_{k+1}:=M^{-1}r_{k+1},
$$
$$
\beta_k:=\frac{\langle r_{k+1},z_{k+1}\rangle}{\langle r_k,z_k\rangle},\quad p_{k+1}:=z_{k+1}+\beta_kp_k
$$
と計算する。これを 前処理付き共役勾配法 といい、$M$ を 前処理行列 という。
$M=LL^*$($L$ は正則)とし、$\hat A:=L^{-1}AL^{-*}$ とする。def-cg-pcg の $x_k$ について、$u_k:=L^*x_k$ は $\hat Au=L^{-1}b$ に初期値 $u_0$ から def-cg-method の共役勾配法を当てた列である。したがって、$\hat r_0:=L^{-1}r_0$ の $\hat A$ に関する次数を $\hat d$ とすると、$1\le m\le\hat d$ で $x_m$ は $x_0+\mathcal K_m(M^{-1}A,z_0)$ の上で $\|x^{\star}-x\|_A$ を最小にする点である。さらに $M^{-1}A$ の固有値は正で、その最大と最小の比を $\kappa_M$ とし $\rho_M:=(\sqrt{\kappa_M}-1)/(\sqrt{\kappa_M}+1)$ とすると、$\|e_m\|_A\le2\rho_M^m\|e_0\|_A$ である。
$k\ge1$ でも $\hat r_k:=L^{-1}r_k$ とおき、$\hat p_k:=L^*p_k$ とおく。$z_k=L^{-*}\hat r_k$ なので $\langle r_k,z_k\rangle=\|\hat r_k\|^2$ であり、$\langle Ap_k,p_k\rangle=\langle\hat A\hat p_k,\hat p_k\rangle$ である。$u_{k+1}=u_k+\alpha_k\hat p_k$、$\hat r_{k+1}=\hat r_k-\alpha_k\hat A\hat p_k$、$\hat p_{k+1}=L^*z_{k+1}+\beta_k\hat p_k=\hat r_{k+1}+\beta_k\hat p_k$ である。$\hat p_0=L^*z_0=\hat r_0$、$\hat r_0=L^{-1}b-\hat Au_0$ なので、これは $\hat A$ の共役勾配法そのものである。
$\hat A$ は Hermite 正定値である。$\|u-u'\|_{\hat A}=\|L^{-*}(u-u')\|_A$ なので、$\hat A$ についての最小性は $x$ についての $A$ ノルムの最小性である。部分空間は $L^{-*}\mathcal K_m(\hat A,\hat r_0)=\mathcal K_m(L^{-*}L^{-1}A,L^{-*}L^{-1}r_0)=\mathcal K_m(M^{-1}A,z_0)$ である。$M^{-1}A=L^{-*}\hat AL^*$ は $\hat A$ と相似なので、固有値は同じである。上界は Krylov部分空間法 の定理「条件数による収束の上界」を $\hat A$ に当てる($m>\hat d$ では誤差は $0$ である)。$\square$
(Saa03 Algorithm 9.1、p. 277 と、同じ頁から p. 278 の議論。)$M=A$ なら $\kappa_M=1$ だが $M^{-1}$ の計算が解くことそのものになる。実用の選び方は、対角行列 $M=D$、Gauss–Seidel 型の $M=(D+L)D^{-1}(D+L)^*$($A=D+L+L^*$)、不完全 Cholesky 分解などである。定常反復法の $M$(反復法(連立1次方程式) の定義「分離と定常反復法」)のうち Hermite 正定値なものがそのまま使える。
入力は $x\mapsto Ax$ を計算する手続き、$b$、初期値 $x_0$(よい近似がなければ $0$)、許容誤差 $\varepsilon$(たとえば $10^{-8}$)、反復の上限 $k_{\max}$ である。
失敗の検出。 手順 6 の残差が漸化式の $r$ と食い違うときは、丸めで $r$ が真の残差からずれている。$x$ から手順 1 をやり直す。
| 状況 | やること | 根拠 |
|---|---|---|
| 固有値が少数の塊に分かれる | そのまま使う。塊が十分に狭ければ、段数はおよそ塊の数で済む | ex-cg-few |
| $\kappa$ が大きい | 前処理を入れる | prop-cg-pcg、ex-cg-precond |
| $n$ 段で止まらない | 異常ではない。丸めで有限停止は失われる | ex-cg-rounding |
| $A$ が Hermite でない | Krylov部分空間法 の GMRES などを使う | 反例の表の Hermite 性の行 |
$A=\operatorname{tridiag}(-1,2,-1)$($n=3$)、$b=(1,0,0)^{\mathsf T}$、$x_0=0$ とする。解は $x^{\star}=(\frac34,\frac12,\frac14)^{\mathsf T}$ である。
使う公式:def-cg-method、prop-cg-decrease。
答え:
| $k$ | $x_k$ | $r_k$ | $p_k$ | $\alpha_k$ | $\beta_k$ | $\Vert e_k\Vert_A^2$ の値 |
|---|---|---|---|---|---|---|
| $0$ | $(0,0,0)$ | $(1,0,0)$ | $(1,0,0)$ | $\frac12$ | $\frac14$ | $\frac34$ |
| $1$ | $(\frac12,0,0)$ | $(0,\frac12,0)$ | $(\frac14,\frac12,0)$ | $\frac23$ | $\frac49$ | $\frac14$ |
| $2$ | $(\frac23,\frac13,0)$ | $(0,0,\frac13)$ | $(\frac19,\frac29,\frac13)$ | $\frac34$ | — | $\frac1{12}$ |
| $3$ | $(\frac34,\frac12,\frac14)$ | $0$ | — | — | — | $0$ |
3 段で解に届く($A$ の固有値は相異なり、$r_0$ はどの固有ベクトルの成分も持つので $d=3$)。$\|e_k\|_A^2$ の減少は $\frac12,\frac16,\frac1{12}$ で、$\alpha_k\|r_k\|^2$ に等しい。
$Ap_0=(2,-1,0)^{\mathsf T}$ なので $\langle Ap_0,p_1\rangle=\frac12-\frac12=0$ である。残差は互いに直交している。prop-cg-lanczos の式から $a_1=2$、$a_2=\frac32+\frac12=2$、$\gamma_1=\sqrt{1/4}/\frac12=1$ で、$r_0$ から作った Lanczos の 3 重対角行列は、$A$ の副対角の $-1$ を $1$ に替えた $\operatorname{tridiag}(1,2,1)$ である($v_2=(0,-1,0)^{\mathsf T}$ なので副対角の符号が変わる)。
(a) $n=6$、$A=I+\mathbf 1\mathbf 1^{\mathsf T}$($\mathbf 1$ は成分がすべて $1$ のベクトル)、$b=(1,0,\dots,0)^{\mathsf T}$、$x_0=0$ とする。(b) $A$ を対角行列とし、固有値を $[1,2]$ の等間隔の $100$ 個($1+i/99$)と外れ値 $100,1000,10000$ の計 $103$ 個、$b=\mathbf 1$、$x_0=0$ とする。
使う公式:thm-cg-main、cor-cg-outlier。
答え:(a) 固有値は $1,7$ の 2 種類なので $d=2$ で、$\alpha_0=\frac12$、$\beta_0=\frac54$、$\alpha_1=\frac27$ として 2 段で $x_2=x^{\star}=(\frac67,-\frac17,\dots,-\frac17)^{\mathsf T}$ に届く。
(b) $\kappa=10^4$ で $\rho\approx0.98020$、$\tilde\kappa=2$ で $\tilde\rho\approx0.17157$ である。十分な桁数(80 桁)の計算で
| $m$ | $5$ | $10$ | $15$ |
|---|---|---|---|
| $\Vert e_m\Vert_A/\Vert e_0\Vert_A$ の値 | $0.034977$ | $5.6441\times10^{-6}$ | $8.6744\times10^{-10}$ |
| 上界 $2\tilde\rho^{\,m-3}$ | $0.058875$ | $8.7533\times10^{-6}$ | $1.3014\times10^{-9}$ |
| 上界 $2\rho^m$ | $1.8097$ | $1.6375$ | $1.4816$ |
である。条件数は $10^4$ でも、外れ値 3 個を除いた $\tilde\kappa$ の速さで収束する。倍精度では丸めのために遅れ、同じ比は $m=15$ で $9.6201\times10^{-7}$ である。
$A=\operatorname{diag}(1,2,20)$、$b=(1,1,1)^{\mathsf T}$、$x_0=0$ とする。
使う公式:prop-cg-decrease、prop-cg-euclid。
答え:
| $k$ | $0$ | $1$ | $2$ | $3$ |
|---|---|---|---|---|
| $\Vert r_k\Vert$ の値 | $1.73205$ | $1.97240$ | $0.44384$ | $0$ |
| $\Vert e_k\Vert_A$ の値 | $1.24499$ | $1.07643$ | $0.38064$ | $0$ |
| $\Vert e_k\Vert$ の値 | $1.11915$ | $0.94826$ | $0.34490$ | $0$ |
$\alpha_0=\frac3{23}$ で、$r_1=(\frac{20}{23},\frac{17}{23},-\frac{37}{23})^{\mathsf T}$ である。誤差のノルムは減るが、残差は 1 段目に増える。
$N\times N$ の格子の 5 点差分の行列 $A$(対角 $4$、隣 $-1$、$n=N^2$)、$b=\mathbf 1$、$x_0=0$ とする。$\|r_k\|\le10^{-8}\|b\|$ までの段数を比べる。計算は倍精度である。
使う公式:thm-cg-main、Krylov部分空間法 の定理「条件数による収束の上界」。
答え:
| $N$ | $n$ | $\kappa$ | $\sqrt\kappa$ | 共役勾配法の段数 | $\omega=\frac2{1+\sin(\pi/(N+1))}$ の SOR 法の段数 | Jacobi 法の段数の目安 |
|---|---|---|---|---|---|---|
| $15$ | $225$ | $103.09$ | $10.15$ | $27$ | $60$ | $949$ |
| $31$ | $961$ | $414.35$ | $20.36$ | $58$ | $121$ | $3816$ |
| $63$ | $3969$ | $1659.4$ | $40.74$ | $118$ | $244$ | $15283$ |
共役勾配法の段数は $\sqrt\kappa$ にほぼ比例して増え、$\kappa$ にほぼ比例する Jacobi 法の目安 $\ln10^{-8}/\ln\cos\frac\pi{N+1}$ よりずっと少ない。固有値は $\lambda=4-2\cos\frac{i\pi}{N+1}-2\cos\frac{j\pi}{N+1}$($1\le i,j\le N$)である。$\omega$ の値を知らなくても使えることが、SOR 法に対する利点である。
$n=200$、$S=\operatorname{diag}(s_1,\dots,s_n)$、$s_i=10^{3(i-1)/199}$、$A=S\operatorname{tridiag}(-1,2.01,-1)S$、$b=\mathbf 1$、$x_0=0$ とする。$\|r_k\|\le10^{-8}\|b\|$ までの段数を倍精度で比べる。
使う公式:prop-cg-pcg。
答え:
| 前処理 | $\kappa_M$ | 段数 |
|---|---|---|
| なし($M=I$) | $7.66\times10^7$ | 約 $6150$ |
| $M=D$ | $391.41$ | $200$ |
| $M=(D+L)D^{-1}(D+L)^{\mathsf T}$ | $49.56$ | $70$ |
対角行列だけで $\kappa$ が約 $20$ 万分の 1 になる。前処理なしの段数は $n$ を超える。これは丸めのためである(図 1 の右)。
$n=48$ とし、対角行列 $A$ の固有値を $\lambda_i=0.1+\frac{i-1}{47}\cdot999.9\cdot0.8^{48-i}$、$b=\mathbf 1$、$x_0=0$ とする。
使う公式:thm-cg-main。固有値は相異なり $b$ はすべての固有ベクトルの成分を持つので $d=48$ である。
答え:$\|e_k\|_A/\|e_0\|_A$ が次の値以下になる段数は次のとおりである。
| しきい値 | 十分な桁数(120 桁) | 倍精度 |
|---|---|---|
| $10^{-6}$ | $41$ | $103$ |
| $10^{-10}$ | $45$ | $140$ |
倍精度の段数は演算の書き方で数段変わり、$k=48$ の比は約 $0.03$ で、解に届かない(図 1 の左)。漸化式の直交性が丸めで失われ、同じ部分空間の探索をやり直すためである。残差を毎段すべての前の残差に直交化し直すと、倍精度でも $41$ 段、$45$ 段になるが、短い漸化式の利点は失われる。
左:48 次の対角行列での誤差の比(120 桁の計算と倍精度)。右:200 次の行列での前処理の効果
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| Hermite 性 | $A=\begin{pmatrix}1&1\\-1&1\end{pmatrix}$、$b=(1,0)^{\mathsf T}$、$x_0=0$ | 分母は正だが、$x_2=(\frac32,\frac12)^{\mathsf T}\ne x^{\star}=(\frac12,\frac12)^{\mathsf T}$、$\langle r_2,r_0\rangle=-1\ne0$(thm-cg-main) |
| 正定値性 | $A=\operatorname{diag}(-1,1)$、$b=(1,1)^{\mathsf T}$、$x_0=0$ | $A$ は正則な Hermite 行列だが $\langle Ap_0,p_0\rangle=0$ で $\alpha_0$ が定まらない |
| 探索方向の共役性 | $\beta_k=0$ に替える(最急降下法)。$A=\operatorname{diag}(1,10)$、$b=0$、$x_0=(10,1)^{\mathsf T}$ | 2 段で止まらず、各段で $\Vert e\Vert_A$ がちょうど $\frac9{11}$ 倍になる(共役勾配法は 2 段で $0$) |
| 丸めのない計算 | ex-cg-rounding | $d$ 段で解に届くこと(thm-cg-main) |
| 前処理行列の正定値性 | $A=I$、$b=(1,1)^{\mathsf T}$、$x_0=0$、$M=\operatorname{diag}(1,-1)$ | $\langle r_0,z_0\rangle=0$ で $\alpha_0=0$、$x_1=x_0$ のままで $\beta_0$ が定まらない |
Hermite 性:$A$ の対称部分は $I$ なので $\langle Ap,p\rangle=\|p\|^2>0$ で漸化式は動く。$\alpha_0=1$、$x_1=(1,0)^{\mathsf T}$、$r_1=(0,1)^{\mathsf T}$、$\beta_0=1$、$p_1=(1,1)^{\mathsf T}$、$Ap_1=(2,0)^{\mathsf T}$、$\alpha_1=\frac12$、$x_2=(\frac32,\frac12)^{\mathsf T}$、$r_2=(-1,1)^{\mathsf T}$ である。$\|r_2\|=\sqrt2>\|r_0\|=1$ である。$\mathcal K_2=\mathbb R^2$ なので Galerkin 解は $x^{\star}$ だが、漸化式はそれを与えない。
正定値性:$\langle Ar_0,r_0\rangle=-1+1=0$ である。条件のうち正定値性だけが成り立たない($A$ は Hermite で、固有値は $\pm1$)。
共役性:$x^{\star}=0$ である。$x_0=(10,1)^{\mathsf T}$ で $r_0=-(10,10)^{\mathsf T}$、最小化の段は $\alpha=\frac2{11}$ で、$x_1=(\frac{90}{11},-\frac9{11})^{\mathsf T}$ となる。これは $\frac9{11}$ 倍して第 2 成分の符号を変えたものなので、以後も同じ比で進む。$\kappa=10$ で $\frac{\kappa-1}{\kappa+1}=\frac9{11}$ である。
前処理行列:$z_0=(1,-1)^{\mathsf T}$、$\langle r_0,z_0\rangle=1-1=0$ である。$p_0=z_0$、$\langle Ap_0,p_0\rangle=2$ なので $\alpha_0=0$ である。$A$ と $r_0$ は問題がなく、$M$ が不定であることだけが原因である。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 残差は単調に減る | 単調に減るのは $\Vert e_k\Vert_A$ と $\Vert e_k\Vert$ である | ex-cg-residual |
| $n$ 段で必ず解ける | 丸めのない計算の話である。実際には $n$ より前で打ち切ることも、$n$ を超えることもある | ex-cg-rounding |
| 収束の速さは $\kappa$ だけで決まる | $2\rho^m$ は最悪の場合の上界で、固有値の分布で速くなる | ex-cg-few |
| 非対称な行列にそのまま使う | Hermite 性がないと直交性も停止も成り立たない。GMRES などを使う | 反例の表の 1 行目 |
| $M^{-1}A$ をそのまま def-cg-method に入れる | $M^{-1}A$ は一般に Hermite でない。def-cg-pcg を使う | prop-cg-pcg |
| 前処理付きでも $\alpha_k$ の分子を $\langle r_k,r_k\rangle$ とする | 分子は $\langle r_k,z_k\rangle$ である | def-cg-pcg |
正規方程式。 Hermite でない正則な $A$ には、$A^*Ax=A^*b$ に共役勾配法を当てる方法がある(Saa03 §8.3.1、Algorithm 8.4、p. 266)。ただし条件数は $\kappa_2(A)^2$ になる(最小二乗法 の命題「正規方程式の条件数」)。
歴史。 共役勾配法は Lanczos と、Hestenes と Stiefel が、別々に異なる形で導入した(同書第 6 章の末尾の注、p. 226)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する