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

共役勾配法は正定値対称行列にのみ適用できる.
なぜ対称行列出なければならないのかというのは方程式&ref(ls_cond.eq1.gif,nolink,70%);の最小化に関しての記述のところで説明した.一方でなぜ正定値(positive definite)でなければならないのかを考える.
方程式
#ref(ls_cond.eq2.gif,nolink,70%)
は2次式であり,個々の式は&ref(ls_cond.eq3.gif,nolink,70%);の形で表すことができる.
この2次式が最小値を持つ条件を考える.
まず,2次式&ref(ls_cond.eq3.gif,nolink,70%);を,
#ref(ls_cond.eq4.gif,nolink,70%)

と変形する(要は解の公式を導出する過程の式).
このとき&ref(ls_cond.eq5.gif,nolink,70%);にかかる係数&ref(ls_cond.eq6.gif,nolink,70%);が&ref(ls_cond.eq7.gif,nolink,70%);ならば2次式のグラフが上に開いた形になり,最小値を持つ.
逆に&ref(ls_cond.eq8.gif,nolink,70%);だと2次式は最大値を持ち,&ref(ls_cond.eq9.gif,nolink,70%);で最小値も最大値も持たない.
大事なのは係数&ref(ls_cond.eq6.gif,nolink,70%);の符号である.

一方,&ref(ls_cond.eq10.gif,nolink,70%);の場合はどうだろうか.
まず,Aが正定値であるということは,&ref(ls_cond.eq11.gif,nolink,70%);の任意の実ベクトル&ref(ls_cond.eq12.gif,nolink,70%);について,
#ref(ls_cond.eq13.gif,nolink,70%)
であるということである.ここで,&ref(ls_cond.eq14.gif,nolink,70%);を行列Aの2次形式と呼ぶ.
 行列が正定値であること = その行列の固有値がすべて正
であるので,行列の固有値がすべて正ならば最小値を持つことを証明する.

n元連立1次方程式&ref(ls_cond.eq15.gif,nolink,70%);の係数行列Aの
モード行列をR,固有値を対角成分にした対角行列をDとする.
モード行列とは行列の固有ベクトルを並べた行列で,&ref(ls_cond.eq16.gif,nolink,70%);の直交行列である.
係数行列は&ref(ls_cond.eq17.gif,nolink,70%);で表されるので,連立1次方程式の式は,
#ref(ls_cond.eq18.gif,nolink,70%)

となる.ここで,&ref(ls_cond.eq19.gif,nolink,70%);とおくと,
#ref(ls_cond.eq20.gif,nolink,70%)

よって,
#ref(ls_cond.eq21.gif,nolink,70%)

である.方程式&ref(ls_cond.eq22.gif,nolink,70%);を&ref(ls_cond.eq23.gif,nolink,70%);を使って表すと,
#ref(ls_cond.eq24.gif,nolink,70%)

ここで,
#ref(ls_cond.eq25.gif,nolink,70%)

と変形できるので,
#ref(ls_cond.eq26.gif,nolink,70%)

となる.さらに,&ref(ls_cond.eq27.gif,nolink,70%);とおくと,
#ref(ls_cond.eq28.gif,nolink,70%)

Dは対角行列なので&ref(ls_cond.eq29.gif,nolink,70%);である.よって,
#ref(ls_cond.eq30.gif,nolink,70%)

右辺第1項は2次形式である.そして,Dは対角行列で,その対角成分,つまり,固有値が&ref(ls_cond.eq31.gif,nolink,70%);の係数aになる.
上で示したように,2次式が最小値を持つ条件は&ref(ls_cond.eq7.gif,nolink,70%);であるので,
すべての固有値が正ならば&ref(ls_cond.eq1.gif,nolink,70%);は最小値を持つ.
つまり,言い換えるとAが正定値ならば&ref(ls_cond.eq1.gif,nolink,70%);は最小値を持つ.

これでAが正定値でなければならないことは証明できた.
次に,&ref(ls_cond.eq32.gif,nolink,70%);に関する式が実際にどのようになっているかを考える.
2次元(&ref(ls_cond.eq33.gif,nolink,70%);)のとき,
#ref(ls_cond.eq34.gif,nolink,70%)

の形になる.この式は&ref(ls_cond.eq35.gif,nolink,70%);を軸とする楕円(&ref(ls_cond.eq36.gif,nolink,70%);)であり,
固有値(&ref(ls_cond.eq37.gif,nolink,70%);)の比は,軸の長さ&ref(ls_cond.eq38.gif,nolink,70%);の平方根の比と等しい.
つまり,固有値の最大値と最小値の差が大きいと平べったい楕円になってしまう.
ここで,行列Aの条件数(condition number)というものを考える.
条件数は,
#ref(ls_cond.eq39.gif,nolink,70%)

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

トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS