目次

　共役勾配法とは，$n$次正方行列$A$，$n$次元ベクトル$b$に対して，連立一次方程式$Ax=b$の近似解列$\left\{ x_n \right\}_{n=0}^{\infty}$を次のように生成する方法を指す．

Initialize $x_0$, and set $r_0=b-Ax_0$ and $p_0=r_0$.
for $k=0, 1, \dots$ do
 Update $\alpha_k = \frac{r_{k}^\top p_k}{p_k^{\top} Ap_k}$.
 Update $x_{k+1} = x_k + \alpha_k p_k$.
 Update $r_{k+1} = b - Ax_{k+1}$.
 Update $\beta_k = -\frac{r_{k+1}^\top Ap_k}{p_k^{\top} Ap_k}$.
 Update $p_{k+1} = r_{k+1} + \beta_k p_k$.
end

　本節では，係数行列$A$が正定値対称行列であるとする．このとき，連立一次方程式$Ax=b$には解が一意に存在することに注意して，次のような関数を考えよう： \begin{equation} \Phi (\xi) = \frac{1}{2}(\xi-x)^{\top}A(\xi-x). \end{equation} この関数は解$x$で唯一の最小値をとることに着目し，ここでは関数の最小化アルゴリズムから共役勾配法を構成 してみよう．

　最小化アルゴリズムといえば，最急降下法だろう．現在の解の候補$x_k$における目的関数の勾配を計算すると， \begin{equation} \nabla \Phi (x_k) = Ax_k - b = -r_k \end{equation} である．ただし，$r_k=b-Ax_k$は残差と呼ばれる．以上から，次の更新式が候補となる： \begin{equation} x_{k+1} = x_k + \alpha_k r_k. \end{equation} 実は，共役勾配法はこれを修正したものである．ということで，修正の方針について述べよう．共役勾配法における更新方向ベクトル$\{p_0, p_1, \dots \}$は，最急降下法における更新方向ベクトル$\{r_0, r_1, \dots\}$を，内積$(x,y)\mapsto x^\top Ay$に関して直交化したものである．

　Gram-Schmidtの正規直交化により，$p_0=r_0$および \begin{equation} p_{k+1} = r_{k+1} - \sum_{j=0}^{k}\frac{r_{k+1}^\top Ap_j}{p_j^{\top} Ap_j}p_j, \quad (k=0, 1, \dots) \end{equation} と定義する．このとき，右辺第２項の和の大部分が消え \begin{equation} p_{k+1} = r_{k+1} + \beta_k p_j, \quad \beta_k = -\frac{r_{k+1}^\top Ap_k}{p_k^{\top} Ap_k} \end{equation} となることを示すことができる．こうして得られる更新方向ベクトルを用いて，解を \begin{equation} x_{k+1} = x_k + \alpha_k p_k \end{equation} と更新すれば，共役勾配法における解の更新式が得られる．最後に，ステップサイズ$\alpha_k$を定める必要がある．これは \begin{equation} \alpha_k = \underset{\alpha > 0}{\mathrm{argmin}}\ \Phi (x_k + \alpha p_k) \end{equation} とするのが自然だろう．これを解くと \begin{equation} \alpha_k = \frac{r_{k}^\top p_k}{p_k^{\top} Ap_k} \end{equation} が得られる．以上で，共役勾配法のアルゴリズムが導出できた．

　非零ベクトル$v\in\mathbb{R}^n$，行列$A\in\mathbb{R}^{n\times n}$，自然数$m(\leq n)$に対して，$v, Av, A^2v, \dots, A^{m-1}v$が一次独立であるとき，集合 \begin{equation} K_m(A, v) = \mathrm{span} \left\{v, Av, A^2v, \dots, A^{m-1}v \right\} \end{equation} を行列$A$とベクトル$v$に関する$m$次のKrylov部分空間という．

　連立一次方程式$Ax=b$の初期近似解$x_0$と初期残差$r_0=b-Ax_0$に対して， \begin{equation} x_k = x_0 + z_k , \quad z_k\in K_k(A, r_0) \end{equation} のように近似解列を構成する方法を，Krylov部分空間法という．

　Krylov部分空間は次数が上がるごとに大きくなる．すなわち，$K_k(A, r_0) \subset K_{k+1}(A, r_0)$が成り立つため，反復するごとに近似解の範囲が広がる．

　係数行列$A\in\mathbb{R}^{n\times n}$を，正規乱数を成分とする正方行列$M$を用いて$A=M^\top M$と定義する．ただし，$n=2000$とする．下図に，共役勾配法の反復中における$\frac{\|r_k\|}{\|b\|}$の変化を示した．

　係数行列$A\in\mathbb{n\times n}$を次のような疎行列とする： \begin{equation} A = \begin{bmatrix} -1 & 2 & 1 & 0 & \cdots & 0 \\ 2 & -1 & 2 & 1 & \cdots & 0 \\ 1 & 2 & -1 & 2 & \cdots & 0 \\ 0 & 1 & 2 & -1 & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\ 0 & 0 & 0 & 1 & 2 & -1 \end{bmatrix}. \end{equation} ただし，$n=2000$とする．下図に，共役勾配法の反復中における$\frac{\|r_k\|}{\|b\|}$の変化を示した．