$n\times n$の正定値対象行列$A$、$x\in {\mathbb{R}}^n$、$b\in {\mathbb{R}}^n$について関数

$$\begin{array}{}\text{(1)}& f(x)=\frac{1}{2}{x}^{\mathrm{T}}Ax-b^{\mathrm{T}}x\end{array}$$

を反復法によって最小化するとき、互いに$A$共役な方向について探索を行えば高々$n$回の反復で最小値に収束する。このときの$x$が線形方程式$Ax=b$の解であることは前のページで説明した。

$A$共役の定義を説明する前に簡単な式変形によって$A$共役の定義の理由を説明する。

まず行列$A$が正定値対象行列であることから行列$A$はある$Q$を用いて$A=Q^{\mathrm{T}}Q$と分解できる。行列の性質として当たり前だと感じるかもしれないが念のため少しわかりやすく説明しておく。対称行列は$P^{\mathrm{T}}P=I$であるような直行行列$P$を用いて$P^{\mathrm{T}}AP=D$と対角化できることは知っているだろう。このとき$D$は$A$の固有値${\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n$が並ぶ次のような対角行列である。

$$D=\left(\begin{array}{cccc}{\lambda }_1& & & \\ & {\lambda }_2& & \\ & & \ddots & \\ & & & {\lambda }_n\end{array}\right)$$

別な言い方をすると行列$A$を$A=PD{P}^{\mathrm{T}}$と固有値分解できるともいえる。ここまでは行列$A$が対称行列であることしか使っていないので正定値でなければ変形はここまで。いま行列$A$は正定値だから正定値性の定義のひとつより$A$の全ての固有値は正なので、固有値を並べた対角行列$D$は$D=\sqrt{D}{\sqrt{D}}^{\mathrm{T}}$のように分解できる。ここで$\sqrt{D}$とは次のような行列である。

$$\sqrt{D}=\left(\begin{array}{cccc}\sqrt{{\lambda }_1}& & & \\ & \sqrt{{\lambda }_2}& & \\ & & \ddots & \\ & & & \sqrt{{\lambda }_n}\end{array}\right)$$

全ての固有値が正なので$\sqrt{D}$の成分が虚数となることはない。これを使うと$A$は次のように書ける。

$$A=PD{P}^{\mathrm{T}}=P\sqrt{D}{\sqrt{D}}^{\mathrm{T}}{P}^{\mathrm{T}}=({\sqrt{D}}^{\mathrm{T}}{P}^{\mathrm{T}}{)}^{\mathrm{T}}{\sqrt{D}}^{\mathrm{T}}{P}^{\mathrm{T}}=Q^{\mathrm{T}}Q$$

最後に$Q={\sqrt{D}}^{\mathrm{T}}{P}^{\mathrm{T}}$とおいた。これで正定値対象行列$A$が$A=Q^{\mathrm{T}}Q$と分解できることが分かった。

次に、前のページのように関数$f(x)$を$Ay=b$を満たすような$y$(線形方程式の解)で平行移動して変形する。

$$f(x)=\frac{1}{2}{x}^{\mathrm{T}}Ax+C$$

ここで最小化に無関係な部分は定数として$C$とおいた。前述の通りこの関数$f(x)$が最小となるのは原点$x=0$である。ここに行列$A$の分解$A=Q^{\mathrm{T}}Q$を代入すると

$$f(x)=\frac{1}{2}{x}^{\mathrm{T}}{Q}^{\mathrm{T}}Qx+C=\frac{1}{2}(Qx{)}^{\mathrm{T}}Qx+C$$

となる。ここで$\hat{x}=Qx$と線形変換すると

$$f(x)=\frac{1}{2}{\hat{x}}^{\mathrm{T}}\hat{x}+C$$

これは成分$\hat{x}=({\hat{x}}_1,{\hat{x}}_2,\cdots ,{\hat{x}}_n{)}^{\mathrm{T}}$で書くことができて次のようになる。

$$f(x)=\frac{1}{2}\sum _{i=1}^n{\hat{x}}_i^2+C$$

いろいろと変形して$f(x)$の原型がなくなってしまったので一度整理すると、まず関数$f(x)$の最小値を与える$y$を原点にするように平行移動し、行列$A$を$A=Q^{\mathrm{T}}Q$と分解する$Q$によって$\hat{x}=Qx$という線形変換を施すと上のような形になるといえる。

ここで、変換後の最急降下法を使うと高々$n$回の反復で解に収束する。これを