共役勾配法（きょうやくこうばいほう、英: conjugate gradient method、CG法とも呼ばれる）は対称正定値行列を係数とする連立一次方程式を解くためのアルゴリズムである[1][2][3][4]。反復法として利用され[1][2][3][4]、コレスキー分解のような直接法では大きすぎて取り扱えない、大規模な疎行列を解くために利用される。そのような問題は偏微分方程式などを数値的に解く際に常に現れる[1][5][6][7]。

共役勾配法は、エネルギー最小化などの最適化問題を解くために用いることもできる[8][9][10]。

双共役勾配法（英語版）は、共役勾配法の非対称問題への拡張である[11]。また、非線形問題を解くために、さまざまな非線形共役勾配法が提案されている[12][13][14]。
詳説

対称正定値行列Aを係数とするn元連立一次方程式

Ax = b

の解をx*とする。
直接法としての共役勾配法

非零ベクトルu、vが

u T A v = 0 {\displaystyle \mathbf {u} ^{\mathrm {T} }\mathbf {A} \mathbf {v} =\mathbf {0} }

を満たすとき、u、vはAに関して共役であるという[2][3][4]。Aは対称正定値なので、左辺から内積

⟨ u , v ⟩ A := ⟨ A T u , v ⟩ = ⟨ A u , v ⟩ = ⟨ u , A v ⟩ = u T A v {\displaystyle \langle \mathbf {u} ,\mathbf {v} \rangle _{\mathbf {A} }:=\langle \mathbf {A} ^{\mathrm {T} }\mathbf {u} ,\mathbf {v} \rangle =\langle \mathbf {A} \mathbf {u} ,\mathbf {v} \rangle =\langle \mathbf {u} ,\mathbf {A} \mathbf {v} \rangle =\mathbf {u} ^{\mathrm {T} }\mathbf {A} \mathbf {v} }

を定義することができる。この内積に関して2つのベクトルが直交するなら、それらのベクトルは互いに共役である。この関係は対称で、uがvに対して共役なら、vもuに対して共役である（この場合の「共役」は複素共役と無関係であることに注意）。

{pk}をn個の互いに共役なベクトル列とする。pkは基底Rnを構成するので、Ax = bの解x*をこの基底で展開すると、

x ∗ = ∑ i = 1 n α i p i {\displaystyle \mathbf {x} _{*}=\sum _{i=1}^{n}\alpha _{i}\mathbf {p} _{i}}

と書ける。ただし係数は

A x ∗ = ∑ i = 1 n α i A p i = b . {\displaystyle \mathbf {A} \mathbf {x} _{*}=\sum _{i=1}^{n}\alpha _{i}\mathbf {A} \mathbf {p} _{i}=\mathbf {b} .}
p k T A x ∗ = ∑ i = 1 n α i p k T A p i = p k T b . {\displaystyle \mathbf {p} _{k}^{\mathrm {T} }\mathbf {A} \mathbf {x} _{*}=\sum _{i=1}^{n}\alpha _{i}\mathbf {p} _{k}^{\mathrm {T} }\mathbf {A} \mathbf {p} _{i}=\mathbf {p} _{k}^{\mathrm {T} }\mathbf {b} .}
α k = p k T b p k T A p k = ⟨ p k , b ⟩ ⟨ p k , p k ⟩ A = ⟨ p k , b ⟩ ‖ p k ‖ A 2 . {\displaystyle \alpha _{k}={\frac {\mathbf {p} _{k}^{\mathrm {T} }\mathbf {b} }{\mathbf {p} _{k}^{\mathrm {T} }\mathbf {A} \mathbf {p} _{k}}}={\frac {\langle \mathbf {p} _{k},\mathbf {b} \rangle }{\,\,\,\langle \mathbf {p} _{k},\mathbf {p} _{k}\rangle _{\mathbf {A} }}}={\frac {\langle \mathbf {p} _{k},\mathbf {b} \rangle }{\,\,\,\|\mathbf {p} _{k}\|_{\mathbf {A} }^{2}}}.}

で与えられる。

この結果は、上で定義した内積を考えるのが最も分かりやすいと思われる。

以上から、Ax = bを解くための方法が得られる。すなわち、まずn個の共役な方向を見つけ、それから係数αkを計算すればよい。
反復法としての共役勾配法

共役なベクトル列pkを注意深く選ぶことにより、一部のベクトルからx*の良い近似を得られる可能性がある。そこで、共役勾配法を反復法として利用することを考える[2][3][4]。こうすることで、nが非常に大きく、直接法では解くのに時間がかかりすぎるような問題にも適用することができる。

x*の初期値をx0 = 0 とする。x*が二次形式

f ( x ) = 1 2 x T A x − b T x , x ∈ R n . {\displaystyle f(\mathbf {x} )={\frac {1}{2}}\mathbf {x} ^{\mathrm {T} }\mathbf {A} \mathbf {x} -\mathbf {b} ^{\mathrm {T} }\mathbf {x} ,\quad \mathbf {x} \in \mathbf {R} ^{n}.}

を最小化する一意な解であることに注意し、最初の基底ベクトルp1をx = x0でのfの勾配Ax0−b=−bとなるように取る。このとき、基底の他のベクトルは勾配に共役である。そこで、この方法を共役勾配法と呼ぶ[2][3][4]。