共役勾配法

数値線形代数において、共役勾配二乗法（CGS）は、次の形式の線形方程式系を解くための反復アルゴリズムである。${\displaystyle A{\mathbf {x}}={\mathbf {b}}}$特に転置を計算する場合${\displaystyle A^{T}}$非現実的である。^{[ 1 ]} CGS法は、双共役勾配法の改良として開発された。^{[ 2 ] [ 3 ] [ 4 ]}

線形方程式系${\displaystyle A{\mathbf {x}}={\mathbf {b}}}$既知の行列で構成される${\displaystyle A}$既知のベクトル${\displaystyle {\mathbf {b}}}$システムを解くとは、未知ベクトルの値を求めることである。${\displaystyle {\mathbf {x}}}$^{[ 3 ] [ 5 ]}連立一次方程式を直接解く方法は、行列の逆行列を取ることである。${\displaystyle A}$計算${\displaystyle {\mathbf {x}}=A^{-1}{\mathbf {b}}}$しかし、逆行列の計算は計算コストが高い。そのため、反復法が一般的に用いられる。反復法は、まず初期値から始める。${\displaystyle {\mathbf {x}}^{(0)}}$、そして各反復で推測が改善されます。連続する推測の差が十分に小さくなると、この方法は解に収束します。^{[ 6 ] [ 7 ]}

共役勾配法、双共役勾配法、および線形方程式系を解くための同様の反復法と同様に、CGS法は、電力潮流解析、ハイパーパラメータ最適化、顔認識などの多変数最適化問題の解を見つけるために使用できます。^{[ 8 ]}

アルゴリズムは以下のとおりです。^{[ 9 ]}

1. 最初の推測値を選択してください${\displaystyle {\mathbf {x}}^{(0)}}$
2. 残差を計算する${\displaystyle {\mathbf {r}}^{(0)}={\mathbf {b}}-A{\mathbf {x}}^{(0)}}$
3. 選ぶ${\displaystyle {\チルダ {\mathbf {r}}}={\mathbf {r}}^{(0)}}$
4. のために${\displaystyle i=1,2,3,\dots }$する：
   1. ${\displaystyle \rho ^{(i-1)}={\tilde {\mathbf {r}}}^{T}{\mathbf {r}}^{(i-1)}}$
   2. もし${\displaystyle \rho ^{(i-1)}=0}$この方法は失敗します。
   3. もし${\displaystyle i=1}$:
      1. ${\displaystyle {\mathbf {p}}^{(1)}={\mathbf {u}}^{(1)}={\mathbf {r}}^{(0)}}$
   4. それ以外：
      1. ${\displaystyle \beta ^{(i-1)}=\rho ^{(i-1)}/\rho ^{(i-2)}}$
      2. ${\displaystyle {\mathbf {u}}^{(i)}={\mathbf {r}}^{(i-1)}+\beta _{i-1}{\mathbf {q}}^{(i-1)}}$
      3. ${\displaystyle {\mathbf {p}}^{(i)}={\mathbf {u}}^{(i)}+\beta ^{(i-1)}({\mathbf {q}}^{(i-1)}+\beta ^{(i-1)}{\mathbf {p}}^{(i-1)})}$
   5. 解決する${\displaystyle M{\hat {\mathbf {p}}}={\mathbf {p}}^{(i)}}$、 どこ${\displaystyle M}$これは前処理剤です。
   6. ${\displaystyle {\hat {\mathbf {v}}}=A{\hat {\mathbf {p}}}}$
   7. ${\displaystyle \alpha ^{(i)}=\rho ^{(i-1)}/{\tilde {\mathbf {r}}}^{T}{\hat {\mathbf {v}}}}$
   8. ${\displaystyle {\mathbf {q}}^{(i)}={\mathbf {u}}^{(i)}-\alpha ^{(i)}{\hat {\mathbf {v}}}}$
   9. 解決する${\displaystyle M{\hat {\mathbf {u}}}={\mathbf {u}}^{(i)}+{\mathbf {q}}^{(i)}}$
   10. ${\displaystyle {\mathbf {x}}^{(i)}={\mathbf {x}}^{(i-1)}+\alpha ^{(i)}{\hat {\mathbf {u}}}}$
   11. ${\displaystyle {\hat {\mathbf {q}}}=A{\hat {\mathbf {u}}}}$
   12. ${\displaystyle {\mathbf {r}}^{(i)}={\mathbf {r}}^{(i-1)}-\alpha ^{(i)}{\hat {\mathbf {q}}}}$
   13. 収束をチェックする：収束した場合は、ループを終了して結果を返す。

• 二重共役勾配法
• 二重共役勾配安定化法
• 一般化最小残差法