CGNR

共役勾配法では正定値対称行列のみを対象としているが, 非対称行列には対応できないのだろうか. 前処理のところで元の方程式と等価になるように係数行列を変形させて条件数を改善したが, 同様にして非対称行列を対称行列にする前処理をすれば簡単に対応は可能である. つまり,

ls_cgnr.eq1.gif

と変形すると,Aが非対称行列でもls_cgnr.eq2.gifは(半)正定値対称行列になる. また,Aは正方行列でなくてもよく,ls_cgnr.eq3.gifの任意の行列で構成される正規方程式(Normal equations)に共役勾配法を適用できる. この式を方程式ls_cgnr.eq4.gifに当てはめると,

ls_cgnr.eq5.gif

となり,ls_cgnr.eq6.gifを最小化する問題に帰着する. これは最小自乗法となる.この方法は一般的に未知数の数よりも方程式の数が多い問題に用いられる. つまり,ls_cgnr.eq7.gifにおいて,ls_cgnr.eq8.gifとなるような場合である. このような問題はNR(Normal equations to minimize the Residual)と呼ばれる. そのため,ls_cgnr.eq2.gifにより対称行列を作り共役勾配法(CG法)を使って解く方法はCGNR法と呼ばれる.

CGNE

CGNRとは別の方法として,ls_cgnr.eq9.gifと置き,

ls_cgnr.eq10.gif

ls_cgnr.eq11.gifについて共役勾配法で解き, ls_cgnr.eq11.gifからls_cgnr.eq12.gifを求める方法もある. CGNR法と同様にして方程式に当てはめると,

ls_cgnr.eq13.gif

今,ls_cgnr.eq14.gif,つまり,方程式の数よりも未知数の数が多い問題を考える. 解の一つをls_cgnr.eq15.gifとすると,ls_cgnr.eq16.gifより,

ls_cgnr.eq17.gif

となり,ls_cgnr.eq11.gifについてls_cgnr.eq18.gifを最小化する問題となる. この方法はls_cgnr.eq14.gifであるunderdeterminedな線形システムに用いられる. このような問題はNE(Normal equations to minimize the Error)と呼ばれ, これを共役勾配法を使って解く方法はCGNE法と呼ばれる.

CGNRとCGNEの収束性

CGNRやCGNEを使うことで共役勾配法を正規方程式に適用できるが, これらの方法は特に条件数が大きいときの収束性に問題を抱えている. ls_cgnr.eq19.gifの条件数がls_cgnr.eq20.gifのときの,ls_cgnr.eq2.gifの条件数(2乗ノルムの条件数)を求めてみる.

ls_cgnr.eq21.gif

スペクトル半径ls_cgnr.eq22.gifと行列の2乗ノルムの間の関係式

ls_cgnr.eq23.gif

を用いると,

ls_cgnr.eq24.gif

このようにls_cgnr.eq2.gifの条件数はls_cgnr.eq19.gifの条件数の2乗となるので, ls_cgnr.eq25.gifが大きいと収束性はさらに悪化してしまう. 一方で2乗ノルムの条件数が1に近い場合は,とてもよい解法である.

参考文献

  • Yousef Saad, Iterative methods for sparse linear systems 2nd ed., SIAM, 2003.

添付ファイル: filels_cgnr.eq6.gif 643件 [詳細] filels_cgnr.eq4.gif 754件 [詳細] filels_cgnr.eq8.gif 608件 [詳細] filels_cgnr.eq7.gif 645件 [詳細] filels_cgnr.eq9.gif 563件 [詳細] filels_cgnr.eq25.gif 614件 [詳細] filels_cgnr.eq5.gif 766件 [詳細] filels_cgnr.eq3.gif 713件 [詳細] filels_cgnr.eq1.gif 625件 [詳細] filels_cgnr.eq20.gif 574件 [詳細] filels_cgnr.eq13.gif 617件 [詳細] filels_cgnr.eq23.gif 637件 [詳細] filels_cgnr.eq14.gif 1572件 [詳細] filels_cgnr.eq24.gif 566件 [詳細] filels_cgnr.eq2.gif 654件 [詳細] filels_cgnr.eq10.gif 647件 [詳細] filels_cgnr.eq17.gif 610件 [詳細] filels_cgnr.eq21.gif 617件 [詳細] filels_cgnr.eq12.gif 594件 [詳細] filels_cgnr.eq11.gif 637件 [詳細] filels_cgnr.eq19.gif 616件 [詳細] filels_cgnr.eq18.gif 624件 [詳細] filels_cgnr.eq16.gif 577件 [詳細] filels_cgnr.eq15.gif 625件 [詳細] filels_cgnr.eq22.gif 615件 [詳細]

トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2022-11-30 (水) 13:48:13