共役勾配法の紹介~LaTeXをMarkdownへ書き替えてみる~

今回の記事では $\LaTeX$ の数式文章をMarkdown記法への書き換えを試行してみました（の第三弾です）.使用した文章は,共役勾配法に関して過去に作成した $\LaTeX$ の文章をベースとしています.第一弾、第二弾の記事は以下のリンクをご覧ください.

https://qiita.com/ydclab_0009/items/cba4ff91301150f0d71b

https://qiita.com/ydclab_0009/items/276cdb51c66628e90740
# 本記事の目的
本記事は過去に私が執筆した博士論文[1]の中から計算式の導出を行った付録章(C)のみを抜き出して記載しています.前回非線形感受率を導出しましたが, 実際に使用している計算手法が共役勾配法となります.そのため, 前回の続きの位置づけとしてQiitaで公開することも有用であろうと考えました.以下, 論文調で読みにくい文体ですが, ご容赦ください.


# 付録C 共役勾配法

本研究で非線形感受率$\chi^{(3)}$を求める時に用いた共役勾配法について述べる. 
共役勾配法とは$\bf A$が正規行列, すなわち
```math
\begin{equation}
{\bf A}^{\dagger}{\bf A}={\bf A}{\bf A}^{\dagger}　\tag{C.1}
\end{equation}
```
である時, 方程式
```math
\begin{equation}
{\bf A}\vec{x}=\vec{y}　 \tag{C.2}
\end{equation}
```

を数値的に解く方法のことである.

まず, 次のような関数$f(\vec{x})$を用意する.
```math
\begin{equation}
f(\vec{x})=\vec{x}^{\dagger}{\bf A}\vec{x}-\vec{x}^{\dagger}\vec{y}-\vec{y}^{\dagger}\vec{x}　\tag{C.3}
\end{equation}
```
この$f(\vec{x})$が極値をとるような$\vec{x}$は,
```math
\begin{eqnarray}
&& \frac{\partial f(\vec{x})}{\partial \vec{x}}=\vec{x}^{\dagger}{\bf A}-\vec{y}^{\dagger}=0 \tag{C.4} \\
&& \frac{\partial f(\vec{x})}{\partial \vec{x}^{\dagger}}={\bf A}\vec{x}-\vec{y}=0 \tag{C.5}
\end{eqnarray}
```
となることより, 方程式(C.2)の解であることがわかる. 共役勾配法は逐次的に$f(\vec{x})$を最小（もしくは最大）にするような$\vec{x}$を見つけることによって,解を求める方法である.

次に, $\vec{x}$を逐次的に求めていく方法を述べる. 任意の初期ベクトル$\vec{x}_0$から順次に近似ベクトル$\vec{x}_1,\vec{x}_2,\cdots$を作っていき, $k$番目を$\vec{x}_k$ とすると, $k+1$番目の$\vec{x}\_{k+1}$ は次のようにして求められる.

$\vec{p}_k$は探索方向ベクトルと呼び, ある方向$\vec{p}_k$へ向かって探索を行い, その方向での$f(\vec{x})$の極値を次のステップの近似ベクトル$\vec{x}\_{k+1}$とする. 
```math
\begin{equation}
\vec{x}_{k+1}=\vec{x}_k+\alpha_k\vec{p}_k　\tag{C.6}
\end{equation}
```
ここで, $\alpha_k$は$\vec{x}_{k+1}$方向への修正の大きさである. 

探索の方向$\vec{p}_k$が決まると, その方向で$f(\vec{x})$が極値を持つ点, つまり$\alpha_k$の大きさは, 
```math
\begin{equation}
\frac{\partial f(\vec{x}_k+\alpha_k\vec{p}_k)}{\partial \alpha_k}
=\frac{\partial f(\vec{x}_k+\alpha_k\vec{p}_k)}{\partial \alpha_k^{\ast}}=0　\tag{C.7}
\end{equation}
```
の条件より, 
```math
\begin{equation}
\alpha_k=\frac{\vec{p}_k^{\dagger} \vec{r}_k}{\vec{p}_k^{\dagger}{\bf A}\vec{p}_k}　\tag{C.8}
\end{equation}
```
で与えられる. ただし, $\vec{r}_k$は近似ベクトル$\vec{x}_k$の残差ベクトルで
```math
\begin{equation}
\vec{r}_k=\vec{y}-{\bf A}\vec{x}_k　 \tag{C.9}
\end{equation}
```
となる. 

次に, 探索方向ベクトル$\vec{p}\_k$の求め方を述べる.
$\vec{p}_{k}$は$f(\vec{x}\_{k+1})$が$f(\vec{x}_k)$よりも小さくなるように決めれば良い. そこで, 式(C.4),(C.5)より, 
```math
\begin{eqnarray}
&&-\frac{\partial f(\vec{x}_k+\alpha_k\vec{p}_k)}{\partial \vec{x}}=\vec{r}_k, \tag{C.10}\\
&&-\frac{\partial f(\vec{x}_k+\alpha_k\vec{p}_k)}{\partial \vec{x}^{\dagger}}=\vec{r}_k \tag{C.11}
\end{eqnarray}
```
という関係式が成り立つ. すなわち, 残差ベクトル$\vec{r}_k$は関数$f(\vec{x})$の傾斜が最大の方向を示すベクトルになっていることがわかる. 
このことから, 探索方向ベクトル$\vec{p}_k$として, まず$\vec{r}_k$を選ぶことが出来る（最大勾配法）. ここで, $n$次元空間内の探索で, 一次独立な方向を順次選んでいき, $n$回の探索で極値に到達したい. しかし, それぞれのステップ毎に傾斜が最大の方向になるといっても, 必ずしも効率よく極値へたどりつく保証はない. そこで, 第$k$回目のステップにおける検索方向ベクトルを前のステップの検索方向ベクトルに修正を加えて
```math
\begin{equation}
\vec{p}_k=\vec{r}_k+\beta_{k-1}\vec{p}_{k-1},\tag{C.12}
\end{equation}
```
とする. ここで, $\vec{p}\_k$は$\vec{p}_{k-1}$と一次独立になる条件としての $\bf{ A} $に関して共役の関係
```math
\begin{equation}
\vec{p}_k{\bf A}\vec{p}_{k-1}=0 \tag{C.13}
\end{equation}
```
を満たすように$\beta_k$を決める. 
```math
\begin{equation}
\beta_k=-\frac{\vec{r}_{k+1}^{\dagger}{\bf A}\vec{p}_k}{\vec{p}_{k}^{\dagger}{\bf A}\vec{p}_k},\tag{C.14}
\end{equation}
```
このように, 式(C.12), (C.14)に従って$\vec{p}\_k$を決めることで, $\vec{p}\_k$は$\vec{p}\_{k-1}$だけではなく, すべての探索方向ベクトル($\vec{p}\_{k-2}$, $\vec{p}\_{k-3}$, $\cdots,\vec{p}_0$)とも共役になる. よって, 
```math
\begin{equation}
\vec{p}_i {\bf A} \vec{p}_j=0, \ \ \  i \neq j \tag{C.15}
\end{equation}
```
が成立する. そのため各ステップにおける残差ベクトルも
```math
\begin{equation}
\vec{r}_i^{\dagger}  \vec{r}_j=0, \ \ \  i \neq j \tag{C.16}
\end{equation}
```
という直交関係を満たしていることがわかる. 
$n$次元空間内で互いに直交する$n$個のベクトル$\vec{r}\_{0}$, $\vec{r}\_{1}$, $\cdots,\vec{r}\_{n-1}$がある時, これらのすべてに直交するベクトル$\vec{r}_n$は$0$ベクトルだけである. 従って, $n$回の探索を終えた時に得られている$\vec{x}_n$の残差ベクトル$\vec{r}_n$は$0$であり, $\vec{x}_n$が求めたい$\vec{x}$である. 以上の手順で探索方向を順次決めながら$f(\vec{x})$の極値を求める方法を共役勾配法という. 

# 参考文献
[1]:  高橋亮, 博士論文(東北大学)(2003).


# おわりに
 今回の記事では過去に$\LaTeX$で作成した文章のMarkdown形式化を試してみましたの第三弾です. 20年ぶりに見直してみるとちょっと書き直したいところも出てきますがそのままとしました.
以下はMarkdownに変更するにあたり削除対応等した主なコマンドです.
・\cite
・\label
・\ref

今回は文章中の数式で下付き文字列があった際の変更にはまりました.

例：もともと用意していた文章

次に, $\vec{x}$を逐次的に求めていく方法を述べる. 任意の初期ベクトル$\vec{x}_0$から順次に近似ベクトル$\vec{x}_1,\vec{x}_2,\cdots$を作っていき, $k$番目を$\vec{x}_k$ とすると, $k+1$番目の$\vec{x}_{k+1}$ は次のようにして求められる.

```
次に, $\vec{x}$を逐次的に求めていく方法を述べる. 
任意の初期ベクトル$\vec{x}_0$から順次に近似ベクトル$\vec{x}_1,\vec{x}_2,\cdots$を作っていき,
 $k$番目を$\vec{x}_k$ とすると, $k+1$番目の$\vec{x}_{k+1}$ は次のようにして求められる.
```
例：修正後の文章


次に, $\vec{x}$を逐次的に求めていく方法を述べる. 任意の初期ベクトル$\vec{x}_0$から順次に近似ベクトル$\vec{x}_1,\vec{x}_2,\cdots$を作っていき, $k$番目を$\vec{x}_k$ とすると, $k+1$番目の$\vec{x}\_{k+1}$ は次のようにして求められる.
```
次に, $\vec{x}$を逐次的に求めていく方法を述べる. 
任意の初期ベクトル$\vec{x}_0$から順次に近似ベクトル$\vec{x}_1,\vec{x}_2,\cdots$を作っていき, 
$k$番目を$\vec{x}_k$ とすると, $k+1$番目の$\vec{x}\_{k+1}$ は次のようにして求められる.
```
修正箇所は最後の$\vec{x}\_{k+1}$ のみで.↑のソースをご確認ください.文章中に数式を入れる際,以下の要因でバックスラッシュが必要です.バックスラッシュをk+1の数式に対して施すことで一つ前の表記崩れも直ります.
「インライン数式の中でコントロールシンボル（`\{`のような, バックスラッシュの後に記号が続くもの）を使うと, 後述のバックスラッシュによるMarkdownのエスケープと衝突してしまいます.」

今回こちらの修正に気が付くのに以下記述を参考としています。ありがとうございます。

https://qiita.com/Qiita/items/c686397e4a0f4f11683d

https://qiita.com/BlueRayi/items/7965798ba1127d269ebb