共役勾配法
rkをkステップ目での残差
r k = b − A x k {\displaystyle \mathbf {r} _{k}=\mathbf {b} -\mathbf {Ax} _{k}}
とする。rkはx = xkでのfの負の勾配であることに注意されたい。最急降下法はrkの方向に進む解法である。pkは互いに共役でなければならないので、rkに最も近い方向を共役性を満たすように取る。これは
p k + 1 = r k + 1 − p k T A r k + 1 p k T A p k p k {\displaystyle \mathbf {p} _{k+1}=\mathbf {r} _{k+1}-{\frac {\mathbf {p} _{k}^{\mathrm {T} }\mathbf {A} \mathbf {r} _{k+1}}{\mathbf {p} _{k}^{\mathrm {T} }\mathbf {A} \mathbf {p} _{k}}}\mathbf {p} _{k}}
のように表すことができる(記事冒頭の図を参照)。
} α 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を計算すればよい。
非零ベクトルu、vが
u T A v = 0 {\displaystyle \mathbf {u} ^{\mathrm {T} }\mathbf {A} \mathbf {v} =\mathbf {0} }
を満たすとき、u、vはAに関して共役であるという。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つのベクトルが直交するなら、それらのベクトルは互いに共役である。