Conjugate Gradient
共役勾配法とは、対称正定値な Ax=b を解く手法であり、A 共役方向を用いて（厳密計算の下で）n ステップで収束する。
目的
大規模でスパースな対称正定値の連立一次方程式を、反復的に効率よく解けるようにする。
メカニズム
直交ではなく A 共役な方向に沿って探索し、各ステップは Krylov 部分空間内で最適である。A を陽に持たず、行列ベクトル積のみを必要とする。前処理付き CG は収束を加速する。計算量は O(√κ log(1/ε)) である。
ユースケース
- 大規模な線形計算のソルバー
- 最適化アルゴリズム
- 科学計算シミュレーション