\(A\)を\(n\times n\)の正方行列で正定値対称行列とする。\(x\in\mathbb{R}^n\)を変数ベクトル、\(b\in\mathbb{R}^n\)を定数ベクトルとする線形方程式
\[ Ax=b\tag{1}\]
は共役勾配法(Conjugate Gradient Method: CG法)によって解くことができる。共役勾配法ではまず、この問題を次の関数\(f(x)\)の最小化問題に取り換える。
\[ f(x)=\frac12x^\mathrm{T}Ax-b^\mathrm{T}x\tag{2}\]
このページではこの部分について詳細に説明する。
ある点\(x=(x_1,x_2,\cdots,x_n)\)で式(2)の関数が極値をとったとする。このとき\(x\)は線形方程式の解であることを示す。
\(x\)が関数\(f(x)\)の極値であるとき次が成り立つ。
\[ \frac{\partial f(x)}{\partial x_i}=0\qquad(i=1,2,\cdots,n)\tag{3}\]
\(A=(a_{ij})\)として左辺を計算すると,
\[ \begin{eqnarray} \frac{\partial f(x)}{\partial x_k}&=& \frac{\partial}{\partial x_k}\left(\frac12\sum_{i=1}^n\sum_{j=1}^na_{ij}x_ix_j-\sum_{i=1}^nb_ix_i\right)\\&=& \frac12\sum_{i=1}^n\sum_{j=1}^n\left(a_{ij}x_i\frac{\partial x_j}{\partial x_k}+a_{ij}\frac{\partial x_i}{\partial x_k}x_j\right)-\sum_{i=1}^nb_i\frac{\partial x_i}{\partial x_k}\\&=& \frac12\sum_{i=1}^n\sum_{j=1}^n(a_{ij}x_i\delta_{jk}+a_{ij}\delta_{ik}x_j)-\sum_{i=1}^nb_i\delta_{ik}\\&=& \frac12\sum_{i=1}^n\sum_{j=1}^na_{ij}x_i\delta_{jk}+\frac12\sum_{i=1}^n\sum_{j=1}^na_{ij}\delta_{ik}x_j-\sum_{i=1}^nb_i\delta_{ik}\\&=& \frac12\sum_{i=1}^na_{ik}x_i+\frac12\sum_{j=1}^na_{kj}x_j-b_k\\&=& \frac12\sum_{i=1}^na_{ik}x_i+\frac12\sum_{i=1}^na_{ki}x_i-b_k\\&=& \frac12\sum_{i=1}^na_{ki}x_i+\frac12\sum_{i=1}^na_{ki}x_i-b_k\\&=& \sum_{i=1}^na_{ki}x_i-b_k\qquad(k=1,2,\cdots,n)\tag{4} \end{eqnarray}\]
ただし、変形の際に積の微分公式、偏微分の結果
\[ \frac{\partial x_i}{\partial x_j}=\delta_{ij}\]
（クロネッカーのデルタ）、さらに問題設定より\(A\)が対称行列\(A^\mathrm{T}=A,\ a_{ij}=a_{ji}\)であることを用いた。 この結果より\(x\)が関数\(f(x)\)の極値をとるとき、\(x\)は線形方程式\(Ax=b\)の解である。
次に、関数\(f(x)\)について極値を求めることと\(f(x)\)の最小化問題が全く同じであることを示す。これには\(A\)の正定値性を用いる。行列\(A\)が正定値であるとは任意の\(x\neq 0\)について\(x^\mathrm{T}Ax\gt 0\)が成り立つことである。
\(x\)の平行移動\(x\to x-y\)を考える。関数\(f(x)\)のこれまで\(x\)だった部分を\(x-y\)に置き換えて計算を進めると
\[ \begin{eqnarray} f(x)&=&\frac12(x-y)^\mathrm{T}A(x-y)-b^\mathrm{T}(x-y)\\ &=&\frac12x^\mathrm{T}Ax-\frac12x^\mathrm{T}Ay-\frac12y^\mathrm{T}Ax-\frac12y^\mathrm{T}Ay-b^\mathrm{T}x+b^\mathrm{T}y\\ &=&\frac12x^\mathrm{T}Ax-(Ay)^\mathrm{T}x-b^\mathrm{T}x-\frac12y^\mathrm{T}Ay+b^\mathrm{T}y\\ &=&\frac12x^\mathrm{T}Ax-(Ay-b)^\mathrm{T}x-\frac12y^\mathrm{T}Ay+b^\mathrm{T}y\tag{5} \end{eqnarray}\]
となる。ただし、2番目の式では内積の性質や行列\(A\)が対称行列であることを用いて次のような変形を行っている。
\[ x^\mathrm{T}Ay=(x,Ay)=(Ay,x)=(Ay)^\mathrm{T}x\\ y^\mathrm{T}Ax=(A^\mathrm{T}y)^\mathrm{T}x=(Ay)^\mathrm{T}x\]
平行移動は言葉の通り関数\(f(x)\)の本質的な性質は変えないので\(y\)は自由に選ぶことができる。問題の性質から\(Ay=b\)を満たす(つまり線形方程式の解である)ような\(y\)を選択すれば関数\(f(x)\)は第2項が消えて
\[ f(x)=\frac12x^\mathrm{T}Ax-(\frac12y^\mathrm{T}Ay-b^\mathrm{T}y)\tag{6}\]
という簡単な形になる。この式の後半2つの項は\(y\)にしか依存しないため\(x\)についての最小化問題には何ら影響は与えない定数とみなすことができる。行列\(A\)の正定値性より最小化問題に影響する第1項は\(x=0\)のときのみ0となりそれ以外の時には\(\frac12x^\mathrm{T}Ax\gt0\)である。したがって平行移動を施した後の関数\(f(x)\)は\(x=0\)で極小かつ最小となる。これは平行移動前の関数\(f(x)\)が\(x=y\)(つまり線形方程式の解)で最小となることを示している。
以上が共役勾配法の説明で真っ先に出てくる前ふりの部分。次のページでは共役勾配法の原理について説明する。