Projection法で&ref(ls_arnoldi3_fom.eq1.gif,nolink,70%);とする．
#ref(ls_arnoldi3_fom.eq2.gif,nolink,70%)

ここで，&ref(ls_arnoldi3_fom.eq3.gif,nolink,70%);である．
この条件を用いる方法としてFOMについて説明する．

近似解&ref(ls_arnoldi3_fom.eq4.gif,nolink,70%);を部分空間&ref(ls_arnoldi3_fom.eq5.gif,nolink,70%);から探索する．
探索するときの条件は&ref(ls_arnoldi3_fom.eq6.gif,nolink,70%);から，
#ref(ls_arnoldi3_fom.eq7.gif,nolink,70%)

いま，&ref(ls_arnoldi3_fom.eq8.gif,nolink,70%);とし，[[Arnoldi法]]で得られるKrylov部分空間の正規直交ベクトルを
並べた行列&ref(ls_arnoldi3_fom.eq9.gif,nolink,70%);により，
#ref(ls_arnoldi3_fom.eq10.gif,nolink,70%)

とすると，&ref(ls_arnoldi3_fom.eq4.gif,nolink,70%);は以下のように表される．
#ref(ls_arnoldi3_fom.eq11.gif,nolink,70%)

&ref(ls_arnoldi3_fom.eq4.gif,nolink,70%);のときの残差は，
#ref(ls_arnoldi3_fom.eq12.gif,nolink,70%)

&ref(ls_arnoldi3_fom.eq4.gif,nolink,70%);が解ならばこの式は0となるので，
#ref(ls_arnoldi3_fom.eq13.gif,nolink,70%)

両辺に&ref(ls_arnoldi3_fom.eq14.gif,nolink,70%);を掛ける．
#ref(ls_arnoldi3_fom.eq15.gif,nolink,70%)

Arnoldi法より実行列の場合，&ref(ls_arnoldi3_fom.eq16.gif,nolink,70%);なので，
#ref(ls_arnoldi3_fom.eq17.gif,nolink,70%)

&ref(ls_arnoldi3_fom.eq18.gif,nolink,70%);をこの式から計算し，&ref(ls_arnoldi3_fom.eq19.gif,nolink,70%);に代入することで，近似解が得られる．
&ref(ls_arnoldi3_fom.eq20.gif,nolink,70%);とし，上式をさらに変形する．
#ref(ls_arnoldi3_fom.eq21.gif,nolink,70%)

まとめると，
#ref(ls_arnoldi3_fom.eq22.gif,nolink,70%)

この式に基づき近似解を求める方法がFOM(Full Orthogonalization Method)である．


**FOMの手順 [#n4d69e45]
FOMで&ref(ls_arnoldi3_fom.eq23.gif,nolink,70%);の近似解を求めるアルゴリズムを以下に示す．

>
&ref(ls_arnoldi3_fom.eq24.gif,nolink,70%);を計算~
&ref(ls_arnoldi3_fom.eq25.gif,nolink,70%);の行列&ref(ls_arnoldi3_fom.eq26.gif,nolink,70%);の各要素を0で初期化~
for(j = 1,2,...,m){~
　　&ref(ls_arnoldi3_fom.eq27.gif,nolink,70%);~
　　for(i = 1,2,...,j)\{~
　　　　&ref(ls_arnoldi3_fom.eq28.gif,nolink,70%);~
　　　　&ref(ls_arnoldi3_fom.eq29.gif,nolink,70%);~
　　}~
　　&ref(ls_arnoldi3_fom.eq30.gif,nolink,70%);~
　　if(&ref(ls_arnoldi3_fom.eq31.gif,nolink,70%);) m=jとしてループを抜ける~
　　&ref(ls_arnoldi3_fom.eq32.gif,nolink,70%);~
}~
&ref(ls_arnoldi3_fom.eq33.gif,nolink,70%);~
&ref(ls_arnoldi3_fom.eq19.gif,nolink,70%);~


&ref(ls_arnoldi3_fom.eq34.gif,nolink,70%);のループの中は修正グラム・シュミット法を用いたArnoldi法([[Arnoldi法#pc5d0806]]参照)そのものである．
ここでは&ref(ls_arnoldi3_fom.eq35.gif,nolink,70%);が0かどうかで反復を抜ける判断をしているが，
実際には近似解に対する残差&ref(ls_arnoldi3_fom.eq36.gif,nolink,70%);の大きさで判断したい．
かつなるべく残差を計算するのにコストは掛けたくない．
そのため，以下の式を用いる．
#ref(ls_arnoldi3_fom.eq37.gif,nolink,70%)

この式の導出を以下に示す．

まず，残差ベクトルは，
#ref(ls_arnoldi3_fom.eq38.gif,nolink,70%)

と表される．いま，&ref(ls_arnoldi3_fom.eq39.gif,nolink,70%);であり，
また，Arnoldi法より，&ref(ls_arnoldi3_fom.eq40.gif,nolink,70%);なので，
#ref(ls_arnoldi3_fom.eq41.gif,nolink,70%)

&ref(ls_arnoldi3_fom.eq42.gif,nolink,70%);より，
#ref(ls_arnoldi3_fom.eq43.gif,nolink,70%)

よって，残差の大きさは以下となる．
#ref(ls_arnoldi3_fom.eq44.gif,nolink,70%)

この式を使って残差を求め，それを反復終了条件とすればよい．


**FOMの拡張 [#h25c542f]
FOMの計算コストは&ref(ls_arnoldi3_fom.eq45.gif,nolink,70%);である．計算コストを減らすためにいくつかの手法が提案されている．
ここでは，FOMの拡張であるFOM(m)，IOM，について簡単に紹介する(概要だけ)．

***FOM(m) [#hdc81b0d]
FOMの拡張の一つでRestarted FOMである．FOM(m)のアルゴリズムは，
++m=1と設定
++&ref(ls_arnoldi3_fom.eq46.gif,nolink,70%);からFOMで&ref(ls_arnoldi3_fom.eq4.gif,nolink,70%);を計算
++&ref(ls_arnoldi3_fom.eq47.gif,nolink,70%);として，2に戻る．

mが設定した上限値に達するか，残差が十分小さくなるまで，2,3を繰り返す．

***IOM [#n2daeaff]
グラム・シュミット法において，&ref(ls_arnoldi3_fom.eq48.gif,nolink,70%);の反復を
#ref(ls_arnoldi3_fom.eq49.gif,nolink,70%)
と変更する．これをincomplete orthogonalizationといい，これを用いたFOMを
IOM(Incomplete Orthogonalization Method)という．

*** [#v0836e6b]
***DIOM [#v0836e6b]
#include(DIOM,title)
トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS