はじめに

線形方程式 $A\boldsymbol{x}=\boldsymbol{b}$ は工学の様々な分野で登場するため、これをコンピュータで計算する手法は盛んに研究されてきました。そういった手法の一種として頻繁に用いられるのが共役勾配法（CG法）です。前回の記事では、CG法の前提として変分原理、反復法、最急降下法の解説を行いました。この記事では、いよいよCG法の解説を行います。

前回のおさらい

まず、前回の記事を簡単におさらいしておきます。まだお読みでない方はこちらからどうぞ。

解きたい線形方程式は次式で表されます。

A\boldsymbol{x}=\boldsymbol{b} \tag{1}

これを解くために、関数 $f(\boldsymbol{x})$ を次式で定義しました。

f(\boldsymbol{x}) \equiv \frac{1}{2}(\boldsymbol{x}, A\boldsymbol{x})-(\boldsymbol{b}, \boldsymbol{x}) \tag{2}

すると、（1）の解は関数 $f(\boldsymbol{x})$ を最小とする $\boldsymbol{x}$ として与えられます。

そのような $\boldsymbol{x}$ を求めるために、反復法を用いるのでした。反復法では、第 $k$ ステップの $\boldsymbol{x}_k$ に対し、第 $k+1$ ステップの $\boldsymbol{x}_{k+1}$ を次式で定めます。

\boldsymbol{x}_{k+1} = \boldsymbol{x}_k + \alpha_k\boldsymbol{p}_k \tag{3}

$\boldsymbol{p}_k$ は「修正方向ベクトル」、$\alpha_k$ は「修正量」です。

更に、

\alpha_k = \frac{(\boldsymbol{r}_k, \boldsymbol{p}_k)}{(A\boldsymbol{p}_k, \boldsymbol{p}_k)} \tag{4}

と求まったのでした。なお、残差 $\boldsymbol{r}_k$ は

\boldsymbol{r}_k \equiv 0 - f'(\boldsymbol{x}_k) = \boldsymbol{b} - A\boldsymbol{x}_k \tag{5}

と定義されます。

さて、$\alpha_k$ は求まりましたが、$\boldsymbol{p}_k$　はどうしたらいいのでしょうか？それを与えるのが最急降下法やCG法です。

共役方向法

次の式は、修正方向ベクトル $\boldsymbol{p}_k$ を決める上で重要な定理です。

(\boldsymbol{s}_{k+1}, A\boldsymbol{p}_k) = 0 \tag{6}

ここで、$\boldsymbol{s}_k$ は次のように定義されるベクトルです。

\begin{align}
\boldsymbol{s}_k &\equiv \boldsymbol{x}_\text{ans} - \boldsymbol{x}_k \\
&= A^{-1}\boldsymbol{b} - \boldsymbol{x}_k \tag{7}
\end{align}

$\boldsymbol{s}_k$ は真の解と現在の解の差を表すので、「誤差ベクトル」と呼ぶことにします。

式（6）の証明をしておきます。

\begin{align}
(\boldsymbol{s}_{k+1}, A\boldsymbol{p}_k)
&= (A\boldsymbol{s}_{k+1}, \boldsymbol{p}_k) \qquad (\because Aは対称行列) \\
&= (\boldsymbol{b} - A\boldsymbol{x}_{k+1}, \boldsymbol{p}_k) \qquad (\because \boldsymbol{s}_{k+1} = A^{-1}\boldsymbol{b} - \boldsymbol{x}_{k+1}) \\
&= (\boldsymbol{r}_{k+1}, \boldsymbol{p}_k) \tag{8}
\end{align}

ここで、

\begin{align}
\left\{
\begin{array}{}
\boldsymbol{r}_k &= \boldsymbol{b} - A\boldsymbol{x}_k \\
\boldsymbol{r}_{k+1} &= \boldsymbol{b} - A\boldsymbol{x}_{k+1}
\end{array}
\right. \\
\therefore \boldsymbol{r}_{k+1} = \boldsymbol{r}_k - \alpha_kA\boldsymbol{p}_k \tag{9}
\end{align}

ですから、

\begin{align}
(\boldsymbol{r}_{k+1}, \boldsymbol{p}_k) &= (\boldsymbol{r}_k, \boldsymbol{p}_k) - \alpha_k(A\boldsymbol{p}_k, \boldsymbol{p}_k) \\
&= 0 \qquad \Biggl( \because \alpha_k = \frac{(\boldsymbol{r}_k, \boldsymbol{p}_k)}{(A\boldsymbol{p}_k, \boldsymbol{p}_k)} \Biggr) \tag{10}
\end{align}

となります。

以上が数学的な証明ですが、直感的な説明もしておきます。修正量 $\alpha_k$ は、修正方向ベクトル $\boldsymbol{p}_k$ の方向で関数 $f$ が最小となる位置 $x_{k+1}$ に移動させるための修正量です。従って、移動後の残差 $r_{k+1}$ に $\boldsymbol{p}_k$ の方向は含まれず、両者は直交します。そのため、式(10）はゼロとなるのです。

さて、証明が済んだところで、式（6）の意味を考えます。これは、第 $k+1$ ステップの解が $\boldsymbol{x}_{k+1} = \boldsymbol{x}_k + \alpha_k\boldsymbol{p}_k \qquad \Bigl( \alpha_k = \frac{(\boldsymbol{r}_k, \boldsymbol{p}_k)}{(A\boldsymbol{p}_k, \boldsymbol{p}_k)} \Bigr)$ で得られたのであれば、前回の修正方向ベクトル $\boldsymbol{p}_k$ がどのような方針で決められたものであっても、誤差ベクトル $\boldsymbol{s}_{k+1}$（すなわち、$\boldsymbol{x}_{k+1}$ から見た厳密解の方向）は $A\boldsymbol{p}_k$ と直交方向にあることを示します。従って、第 $k+1$ ステップの修正方向ベクトル $\boldsymbol{p}_{k+1}$ は、$A\boldsymbol{p}_k$ と直交する方向を選べばよいことが分かります。

まず、$\boldsymbol{x}_0$ と $\boldsymbol{p}_0$ を任意に与え、$\boldsymbol{x}_1$ を求めます。解は $A\boldsymbol{p}_0$ と直交する方向にあるので、「$\boldsymbol{p}_1$ の候補として（任意に）選んだベクトル」$\boldsymbol{t}_1$ から $A\boldsymbol{p}_0$ の成分を除去したベクトルを $\boldsymbol{p}_1$ としましょう。

\boldsymbol{p}_1 = \boldsymbol{t}_1 - \frac{(\boldsymbol{t}_1, A\boldsymbol{p}_0)}{(\boldsymbol{p}_0, A\boldsymbol{p}_0)}\boldsymbol{p}_0 \tag{11}

試しに $(\boldsymbol{p}_1, A\boldsymbol{p}_0)$ を計算してみると（ゼロになるはずです）、この式の形が納得いただけると思います。ちなみに、これは「Gram-Schmidtの直交化」と呼ばれるものですね。

次に、$\boldsymbol{p}_2$ について検討します。$\boldsymbol{x}_3$ は $\boldsymbol{x}_1$ から見ると $A\boldsymbol{p}_0$ に垂直な方向にあるので、

\begin{align}
(\boldsymbol{x}_3 - \boldsymbol{x}_1, A\boldsymbol{p}_0) &= 0 \\
(\alpha_1\boldsymbol{p}_1 + \alpha_2\boldsymbol{p}_2, A\boldsymbol{p}_0) &= 0 \\
(\boldsymbol{p}_2, A\boldsymbol{p}_0) &= 0 \qquad (\because (\boldsymbol{p}_1, A\boldsymbol{p}_0) = 0) \tag{12}
\end{align}

となります。つまり、$\boldsymbol{p}_2$ は $A\boldsymbol{p}_0$ と $A\boldsymbol{p}_1$ の両方に直交するベクトルです。従って、こちらも任意に選んだベクトル $\boldsymbol{t}_2$ を用意して、

\boldsymbol{p}_2 = \boldsymbol{t}_2
- \frac{(\boldsymbol{t}_2, A\boldsymbol{p}_1)}{(\boldsymbol{p}_1, A\boldsymbol{p}_1)}\boldsymbol{p}_1
- \frac{(\boldsymbol{t}_2, A\boldsymbol{p}_0)}{(\boldsymbol{p}_0, A\boldsymbol{p}_0)}\boldsymbol{p}_0 \tag{13}

と求められます。これも、Gram-Schmidtの直交化です。

以上を一般化すると、任意のベクトル $\boldsymbol{t}_{k+1}$ を用いて、

\boldsymbol{p}_{k+1} = \boldsymbol{t}_{k+1} - \sum_{i=0}^k \frac{(\boldsymbol{t}_{k+1}, A\boldsymbol{p}_i)}{(\boldsymbol{p}_i, A\boldsymbol{p}_i)}\boldsymbol{p}_i \tag{14}

とすればよいことが分かります。つまり、$\boldsymbol{p}_{k+1}$ は $A\boldsymbol{p}_0$ ～ $A\boldsymbol{p}_k$ の全てと直交する方向ベクトルとすればよいわけです。これを式にしておくと、

(\boldsymbol{p}_{k+1}, A\boldsymbol{p}_i) = 0 \qquad (i \le k) \tag{15}

となります。

前回の記事で、次のように述べました。

最急降下法は実はそれほど速くないのです。なぜなら、各反復での修正方向として「最急降下」方向を取るという戦略は、過去の反復の際の修正方向データを使っていないからです。

式（14）を用いれば、この問題点を見事克服できていることがお分かりいただけるかと思います。

ここで、$(\boldsymbol{p}_i, A\boldsymbol{p}_j) = 0$ すなわち $\boldsymbol{p}_i^\top A \boldsymbol{p}_j = 0$ が成り立つとき、「$\boldsymbol{p}_i$ と $\boldsymbol{p}_j$ は $A$ に関して共役である」といいます。このことから、式（14）のように $\boldsymbol{p}_k$ を定める方法を、「共役方向法」と呼びます。

共役勾配法（CG法）

いよいよ集大成です！大変でしたね...
もうひと踏ん張り、頑張りましょう！

共役方向法で登場するベクトル $\boldsymbol{t}$ としては任意のベクトルが与えられますが、計算が楽になるような $\boldsymbol{t}$ を用いた方が嬉しいですね。この $\boldsymbol{t}$ として残差ベクトル $\boldsymbol{r}$ を採用するのが、共役勾配法（Conjugate Gradient法：CG法）です。そうするとなぜ計算が楽になるのでしょうか？

後程証明しますが、

(\boldsymbol{r}_{k+1}, A\boldsymbol{p}_i) = 0 \qquad (i \leq k-1) \tag{16}

が成り立ちます。すなわち、式（14）のシグマのうち、$i=0$ から $i=k-1$ までの全ての項はゼロとなるので、式（14）は次のように簡略化されます。

\begin{align}
\boldsymbol{p}_{k+1}
&= \boldsymbol{r}_{k+1} - \frac{(\boldsymbol{r}_{k+1}, A\boldsymbol{p}_k)}{(\boldsymbol{p}_k, A\boldsymbol{p}_k)}\boldsymbol{p}_k \\
&= \boldsymbol{r}_{k+1} + \beta_k \boldsymbol{p}_k \qquad \Biggl(\beta_k \equiv -\frac{(\boldsymbol{r}_{k+1}, A\boldsymbol{p}_k)}{(\boldsymbol{p}_k, A\boldsymbol{p}_k)}\Biggr)\tag{17}
\end{align}

この式を用いれば、過去全ての $\boldsymbol{p}$ を保存する必要がなくなり、計算リソースの削減につながります。

なお、一番最初の方向ベクトルである $\boldsymbol{p}_0$ については、最急降下法と同様に

\boldsymbol{p}_0 = \boldsymbol{r}_0 \tag{18}

とします。

ここで、

\begin{align}
\alpha_k &= \frac{(\boldsymbol{r}_k, \boldsymbol{p}_k)}{(A\boldsymbol{p}_k, \boldsymbol{p}_k)} \\
\beta_k &= -\frac{(\boldsymbol{r}_{k+1}, A\boldsymbol{p}_k)}{(\boldsymbol{p}_k, A\boldsymbol{p}_k)} \tag{19}
\end{align}

でしたが、これらは次のように簡略化できます。

\begin{align}
\alpha_k &= \frac{(\boldsymbol{r}_k, \boldsymbol{r}_k)}{(A\boldsymbol{p}_k, \boldsymbol{p}_k)} \\
\beta_k &= \frac{(\boldsymbol{r}_{k+1}, \boldsymbol{r}_{k+1})}{(\boldsymbol{r}_k, \boldsymbol{r}_k)} \tag{20}
\end{align}

これも、後程証明することにします。

計算手順

CG法の計算手順は以下の通りです。

$\boldsymbol{x}_0$ を適当に選ぶ。
$\boldsymbol{r}_0 = \boldsymbol{b} - A\boldsymbol{x}_0$
$\boldsymbol{p}_0 = \boldsymbol{r}_0$
$k = 0$
ループ開始
$\alpha_k = \frac{(\boldsymbol{r}_k, \boldsymbol{r}_k)}{(A\boldsymbol{p}_k, \boldsymbol{p}_k)}$
$\boldsymbol{x}_{k+1} = \boldsymbol{x}_k + \alpha_k\boldsymbol{p}_k $
$\boldsymbol{r}_{k+1} = \boldsymbol{r}_k - \alpha_kA\boldsymbol{p}_k$
$ \beta_k = \frac{( \boldsymbol{r} _{k+1}, \boldsymbol{r} _{k+1} )}{( \boldsymbol{r} _k, \boldsymbol{r} _k )}$
$\boldsymbol{p} _{k+1} = \boldsymbol{r} _{k+1} + \beta_k \boldsymbol{p} _k $
収束判定 → 未収束なら $k=k+1$ として6.へ。
ループ終了

なお、残差 $\boldsymbol{r}$ の本来の定義は式（5）ですが、計算の簡略化のために式（9）の関係を用いています。

CG法の解説は以上で終了です！！お疲れ様でした。

以下では、証明をすっ飛ばした式を証明していきます。数学チックになってしまうので、気になる方が気になる部分を見て頂いたらいいと思います。

式（16）の証明

では、最後に式（16）の証明に取り掛かりましょう。まず、残差 $\boldsymbol{r}$ に関する次の定理を用います。

(\boldsymbol{r}_{k+1}, \boldsymbol{r}_i) = 0 \qquad (i \le k) \tag{21}

これは今後いろんなところで登場する重要な定理で、「残差の直交性」などと呼ばれます。もちろん後程証明しますが、今はとりあえずそんなもんかぁと思っていただけたら良いと思います。私は、$\alpha$ を上手く決めたおかげである方向への探索は1度で済むから、残差は直交するのかなぁって感覚的には理解してます（正しいかは分かりません）。

さて、残差 $r$ は、式（9）で示したように次の漸化式を満たします。

\boldsymbol{r}_{i+1} = \boldsymbol{r}_i - \alpha_iA\boldsymbol{p}_i \tag{22}

となります。この式と $\boldsymbol{r}_{k+1}$ の内積を取ると、

(\boldsymbol{r}_{k+1}, \boldsymbol{r}_{i+1}) = (\boldsymbol{r}_{k+1}, \boldsymbol{r}_i) - \alpha_i(\boldsymbol{r}_{k+1}, A\boldsymbol{p}_i) \\\tag{23}

と求まり、$i\le k-1$とすれば、式（16）より、この式の左辺と右辺第一項はゼロになるので、式（16）が求まります。

(\boldsymbol{r}_{k+1}, A\boldsymbol{p}_i) = 0 \qquad (i \leq k-1) \tag{24}

α と β に関する式（20）の証明

続いては、$\alpha_k$ と $\beta_k$ の変形をした式（20）の証明を行います。目標は、

\begin{align}
\alpha_k &= \frac{(\boldsymbol{r}_k, \boldsymbol{p}_k)}{(A\boldsymbol{p}_k, \boldsymbol{p}_k)} \\
\beta_k &= -\frac{(\boldsymbol{r}_{k+1}, A\boldsymbol{p}_k)}{(\boldsymbol{p}_k, A\boldsymbol{p}_k)} \tag{25}
\end{align}

を次の式に変形することです。

\begin{align}
\alpha_k &= \frac{(\boldsymbol{r}_k, \boldsymbol{r}_k)}{(A\boldsymbol{p}_k, \boldsymbol{p}_k)} \\
\beta_k &= \frac{(\boldsymbol{r}_{k+1}, \boldsymbol{r}_{k+1})}{(\boldsymbol{r}_k, \boldsymbol{r}_k)} \tag{26}
\end{align}

まずは $\alpha_k$ の分子を変形します。

\begin{align}
(\boldsymbol{r}_k, \boldsymbol{p}_k)
&= (\boldsymbol{r}_k, \boldsymbol{r}_k + \beta_{k-1}\boldsymbol{p}_{k-1}) \\
&= (\boldsymbol{r}_k, \boldsymbol{r}_k,) + \beta_{k-1}(\boldsymbol{r}_k, \boldsymbol{p}_{k-1}) \tag{27}
\end{align}

ここで、式（10）より、この式の右辺第二項はゼロとなるので、

(\boldsymbol{r}_k, \boldsymbol{p}_k) = (\boldsymbol{r}_k, \boldsymbol{r}_k) \tag{28}

となり、

\alpha_k = \frac{(\boldsymbol{r}_k, \boldsymbol{p}_k)}{(A\boldsymbol{p}_k, \boldsymbol{p}_k)} = \frac{(\boldsymbol{r}_k, \boldsymbol{r}_k)}{(A\boldsymbol{p}_k, \boldsymbol{p}_k)}  \tag{29}

が示せました。

続いて $\beta_k$ の変形に移ります。式（9）より、

\begin{align}
\boldsymbol{r}_{k+1} &= \boldsymbol{r}_k - \alpha_kA\boldsymbol{p}_k \\
\therefore A\boldsymbol{p}_k &= \frac{1}{\alpha_k}(\boldsymbol{r}_k - \boldsymbol{r}_{k+1}) \tag{30}
\end{align}

と求まります。これを用いると、$\beta_k$ の分子が次のように変形できます。

\begin{align}
(\boldsymbol{r}_{k+1}, A\boldsymbol{p}_k)
&= \frac{1}{\alpha_k}(\boldsymbol{r}_{k+1}, \boldsymbol{r}_k - \boldsymbol{r}_{k+1}) \\
&= \frac{(\boldsymbol{r}_{k+1}, \boldsymbol{r}_k)}{\alpha_k} - \frac{(\boldsymbol{r}_{k+1}, \boldsymbol{r}_{k+1})}{\alpha_k} \\
&= -\frac{(\boldsymbol{r}_{k+1}, \boldsymbol{r}_{k+1})}{\alpha_k} \qquad (\because 残差の直交性（21）) \tag{31}
\end{align}

これを式（25）の $\beta_k$ に代入すると、

\begin{align}
\beta_k &= \frac{1}{\alpha_k}\frac{(\boldsymbol{r}_{k+1}, \boldsymbol{r}_{k+1})}{(\boldsymbol{p}_k, A\boldsymbol{p}_k)} \\
&= \frac{(\boldsymbol{r}_{k+1}, \boldsymbol{r}_{k+1})}{(\boldsymbol{r}_k, \boldsymbol{r}_k)} \qquad (\because 式（29）)\tag{32}
\end{align}

となり、$\beta_k$ を変形することができました。

残差の直交性（21）の証明

では本当の最後に、式（21）の残差の直交性の証明に取り掛かります。少し大変です。

証明には数学的帰納法を用います。すなわち、まずは

(\boldsymbol{r}_i, \boldsymbol{r}_k) = 0 \qquad (i \le k-1) \tag{32}

を仮定します。そのうえで、

(\boldsymbol{r}_i, \boldsymbol{r}_{k+1}) = 0 \qquad (i \le k) \tag{33}

を示すのが目標です。

まず、式（9）と同様に、

\boldsymbol{r}_{k+1} = \boldsymbol{r}_k - \alpha_kA\boldsymbol{p}_k \tag{34}

です。この式と $\boldsymbol{r}_i$ の内積を取ると、

(\boldsymbol{r}_i, \boldsymbol{r}_{k+1}) = (\boldsymbol{r}_i, \boldsymbol{r}_k) - \alpha_k(\boldsymbol{r}_i, A\boldsymbol{p}_k) \tag{35}

となります。

i<=k-1 について

式（32）の仮定より、$i\le k-1$ においては右辺第一項はゼロです。そこで、$i\le k-1$ のもとで右辺第二項がゼロとなることを示しましょう。なお、$i=k$ については後程検討します。

式（32）の仮定により、$i\le k$ の範囲では式（17）を使うことができます。すなわち、

\boldsymbol{p}_{i} = \boldsymbol{r}_{i} - \beta_{i-1}\boldsymbol{p}_{i-1} \qquad (i \le k) \tag{36}

です。この式の一部を移項すると、

\boldsymbol{r}_{i} = \boldsymbol{p}_{i} + \beta_{i-1}\boldsymbol{p}_{i-1} \qquad (i \le k) \tag{37}

が得られます。この式と $A\boldsymbol{p}_k$ の内積を取ると、

(\boldsymbol{r}_i, A\boldsymbol{p}_k) = (\boldsymbol{p}_i, A\boldsymbol{p}_k) - \beta_{i-1}(\boldsymbol{p}_{i-1}, A\boldsymbol{p}_k) \qquad (i \le k) \tag{38}

ここで、

\begin{align}
(\boldsymbol{p}_i, A\boldsymbol{p}_k)
&= (A\boldsymbol{p}_i, \boldsymbol{p}_k) \qquad (\because Aは対称行列) \\
&= 0 \qquad (i \le k-1) \qquad (\because \boldsymbol{p} の共役直交性（15）) \tag{39}
\end{align}

ですので、式（38）の右辺はゼロとなり、

(\boldsymbol{r}_i, A\boldsymbol{p}_k) = 0 \qquad (i \le k - 1)\tag{40}

が導けました。これより、

(\boldsymbol{r}_i, \boldsymbol{r}_{k+1}) = 0 \qquad (i \le k-1) \tag{41}

が示せました。

i=k について

続いて、$i=k$ の場合に移ります。これを式（35）に代入すると、

\begin{align}
(\boldsymbol{r}_k, \boldsymbol{r}_{k+1})
&= (\boldsymbol{r}_k, \boldsymbol{r}_k) - \alpha_k(\boldsymbol{r}_k, A\boldsymbol{p}_k) \\
&= (\boldsymbol{r}_k, \boldsymbol{r}_k) - \frac{(\boldsymbol{r}_k, \boldsymbol{r}_k)}{(A\boldsymbol{p}_k, \boldsymbol{p}_k)}(\boldsymbol{r}_k, A\boldsymbol{p}_k) \\
\tag{42}
\end{align}

となります。式（38）で $i=k$ として、

(\boldsymbol{r}_{k}, A\boldsymbol{p}_k) = (\boldsymbol{p}_k, A\boldsymbol{p}_k) - \beta_{k-1}(\boldsymbol{p}_{k-1}, A\boldsymbol{p}_k) \tag{43}

となりますが、式（39）より、この式の右辺第二項はゼロとなるため、

(\boldsymbol{r}_{k}, A\boldsymbol{p}_k) = (\boldsymbol{p}_k, A\boldsymbol{p}_k) \tag{44}

となります。これを式（42）に代入すると、、

(\boldsymbol{r}_k, \boldsymbol{r}_{k+1}) = (\boldsymbol{r}_k, \boldsymbol{r}_k) - (\boldsymbol{r}_k, \boldsymbol{r}_k) = 0 \tag{45}

となり、$i=k$ の場合についても示すことができました。

帰納法のスタート地点

最後に、帰納法のスタート地点である

(\boldsymbol{r}_0, \boldsymbol{r}_1) = 0 \tag{46}

を示します。式（9）より、

\begin{align}
\boldsymbol{r}_1
&= \boldsymbol{r}_0 - \alpha_0A\boldsymbol{p}_0 \\
&= \boldsymbol{r}_0 - \frac{(\boldsymbol{r}_0, \boldsymbol{r}_0)}{(A\boldsymbol{p}_0, \boldsymbol{p}_0)}A\boldsymbol{p}_0 \\
&= \boldsymbol{r}_0 - \frac{(\boldsymbol{r}_0, \boldsymbol{r}_0)}{(A\boldsymbol{r}_0, \boldsymbol{r}_0)}A\boldsymbol{r}_0 \qquad (\because \boldsymbol{p}_0 = \boldsymbol{r}_0) \tag{47}
\end{align}

となります。従って、

\begin{align}
(\boldsymbol{r}_0, \boldsymbol{r}_1)
&= (\boldsymbol{r}_0, \boldsymbol{r}_0) - \frac{(\boldsymbol{r}_0, \boldsymbol{r}_0)}{(A\boldsymbol{r}_0, \boldsymbol{r}_0)}(\boldsymbol{r}_0, A\boldsymbol{r}_0) \\
&= 0 \tag{48}
\end{align}

として、帰納法のスタート地点における残差の直交性を示すことができました。

参考資料

戸川隼人（1977）『シリーズ新しい応用の数学　17　共役勾配法』教育出版株式会社

この記事の大部分はこの資料から勉強しました。丸々一冊がCG法に関する内容という非常に贅沢な本です。展開も付いていきやすいです。本腰を入れて勉強したい方にはぜひおすすめしたい良書です。

中島研吾『線形方程式の解法：反復法』

αとβの式変形で参考にしました。

はじめに

目次

前回のおさらい

共役方向法

共役勾配法（CG法）

計算手順

式（16）の証明

α と β に関する式（20）の証明

残差の直交性（21）の証明

i<=k-1 について

i=k について

帰納法のスタート地点

参考資料

戸川隼人（1977）『シリーズ新しい応用の数学 17 共役勾配法』教育出版株式会社

中島研吾『線形方程式の解法：反復法』

戸川隼人（1977）『シリーズ新しい応用の数学　17　共役勾配法』教育出版株式会社