条件数

ここでは前処理付き共役勾配法について説明する前に， 共役勾配法の収束性と係数行列の条件数について述べる．

共役勾配法は正定値対称行列にのみ適用できる． なぜ対称行列出なければならないのかというのは方程式の最小化に関しての記述のところで説明した．一方でなぜ正定値(positive definite)でなければならないのかを考える． 方程式

は2次式であり，個々の式はの形で表すことができる． この2次式が最小値を持つ条件を考える． まず，2次式を，

と変形する(要は解の公式を導出する過程の式)． このときにかかる係数がならば2次式のグラフが上に開いた形になり，最小値を持つ． 逆にだと2次式は最大値を持ち，で最小値も最大値も持たない． 大事なのは係数の符号である．

一方，の場合はどうだろうか． まず，Aが正定値であるということは，の任意の実ベクトルについて，

であるということである．ここで，を行列Aの2次形式と呼ぶ．

行列が正定値であること = その行列の固有値がすべて正

であるので，行列の固有値がすべて正ならば最小値を持つことを証明する．

n元連立1次方程式の係数行列Aの モード行列をR，固有値を対角成分にした対角行列をDとする． モード行列とは行列の固有ベクトルを並べた行列で，の直交行列である． 係数行列はで表されるので，連立1次方程式の式は，

となる．ここで，とおくと，

よって，

である．方程式をを使って表すと，

ここで，

と変形できるので，

となる．さらに，とおくと，

Dは対角行列なのでである．よって，

右辺第1項は2次形式である．そして，Dは対角行列で，その対角成分，つまり，固有値がの係数aになる． 上で示したように，2次式が最小値を持つ条件はであるので， すべての固有値が正ならばは最小値を持つ． つまり，言い換えるとAが正定値ならばは最小値を持つ．

これでAが正定値でなければならないことは証明できた． 次に，に関する式が実際にどのようになっているかを考える． 2次元()のとき，

の形になる．この式はを軸とする楕円()であり， 固有値()の比は，軸の長さの平方根の比と等しい． つまり，固有値の最大値と最小値の差が大きいと平べったい楕円になってしまう． ここで，行列Aの条件数(condition number)というものを考える． 条件数は，

と書け，2つのノルムの積となる． 正定値実対称行列の場合，最大固有値を最小固有値で割った比が条件数になる(すべての固有値は正であることに注意)． 条件数の最小値は1であり，条件数が1に近いほど誤差が小さく，アルゴリズムの収束性がよくなるため， 連立1次方程式の精度や収束性を評価する上でとても重要な指標となる．