ここでは前処理付き共役勾配法について説明する前に, 共役勾配法の収束性と係数行列の条件数について述べる. 共役勾配法は正定値対称行列にのみ適用できる.
なぜ対称行列出なければならないのかというのは方程式 ![]() は2次式であり,個々の式は ![]() と変形する(要は解の公式を導出する過程の式).
このとき 一方, ![]() であるということである.ここで, 行列が正定値であること = その行列の固有値がすべて正 であるので,行列の固有値がすべて正ならば最小値を持つことを証明する. n元連立1次方程式 ![]() となる.ここで, ![]() よって, ![]() である.方程式 ![]() ここで, ![]() と変形できるので, ![]() となる.さらに, ![]() Dは対角行列なので ![]() 右辺第1項は2次形式である.そして,Dは対角行列で,その対角成分,つまり,固有値が これでAが正定値でなければならないことは証明できた.
次に, ![]() の形になる.この式は ![]() と書け,2つのノルムの積となる. 正定値実対称行列の場合,最大固有値を最小固有値で割った比が条件数になる(すべての固有値は正であることに注意). 条件数の最小値は1であり,条件数が1に近いほど誤差が小さく,アルゴリズムの収束性がよくなるため, 連立1次方程式の精度や収束性を評価する上でとても重要な指標となる. |