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

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

ls_cond.eq2.gif

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

ls_cond.eq4.gif

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

一方,ls_cond.eq10.gifの場合はどうだろうか. まず,Aが正定値であるということは,ls_cond.eq11.gifの任意の実ベクトルls_cond.eq12.gifについて,

ls_cond.eq13.gif

であるということである.ここで,ls_cond.eq14.gifを行列Aの2次形式と呼ぶ.

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

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

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

ls_cond.eq18.gif

となる.ここで,ls_cond.eq19.gifとおくと,

ls_cond.eq20.gif

よって,

ls_cond.eq21.gif

である.方程式ls_cond.eq22.gifls_cond.eq23.gifを使って表すと,

ls_cond.eq24.gif

ここで,

ls_cond.eq25.gif

と変形できるので,

ls_cond.eq26.gif

となる.さらに,ls_cond.eq27.gifとおくと,

ls_cond.eq28.gif

Dは対角行列なのでls_cond.eq29.gifである.よって,

ls_cond.eq30.gif

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

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

ls_cond.eq34.gif

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

ls_cond.eq39.gif

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


添付ファイル: filels_cond.eq39.gif 487件 [詳細] filels_cond.eq31.gif 509件 [詳細] filels_cond.eq33.gif 516件 [詳細] filels_cond.eq36.gif 545件 [詳細] filels_cond.eq26.gif 524件 [詳細] filels_cond.eq32.gif 432件 [詳細] filels_cond.eq10.gif 476件 [詳細] filels_cond.eq17.gif 484件 [詳細] filels_cond.eq35.gif 451件 [詳細] filels_cond.eq4.gif 452件 [詳細] filels_cond.eq3.gif 442件 [詳細] filels_cond.eq1.gif 471件 [詳細] filels_cond.eq22.gif 458件 [詳細] filels_cond.eq27.gif 486件 [詳細] filels_cond.eq30.gif 457件 [詳細] filels_cond.eq5.gif 489件 [詳細] filels_cond.eq11.gif 488件 [詳細] filels_cond.eq2.gif 480件 [詳細] filels_cond.eq7.gif 449件 [詳細] filels_cond.eq18.gif 452件 [詳細] filels_cond.eq8.gif 436件 [詳細] filels_cond.eq23.gif 415件 [詳細] filels_cond.eq34.gif 440件 [詳細] filels_cond.eq21.gif 409件 [詳細] filels_cond.eq16.gif 440件 [詳細] filels_cond.eq29.gif 541件 [詳細] filels_cond.eq14.gif 422件 [詳細] filels_cond.eq12.gif 440件 [詳細] filels_cond.eq24.gif 445件 [詳細] filels_cond.eq19.gif 416件 [詳細] filels_cond.eq37.gif 425件 [詳細] filels_cond.eq28.gif 505件 [詳細] filels_cond.eq38.gif 407件 [詳細] filels_cond.eq6.gif 407件 [詳細] filels_cond.eq20.gif 416件 [詳細] filels_cond.eq15.gif 432件 [詳細] filels_cond.eq25.gif 451件 [詳細] filels_cond.eq9.gif 420件 [詳細] filels_cond.eq13.gif 498件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2012-07-03 (火) 12:51:59 (3317d)