不完全ＬＵ分解前処理つき双共役勾配法についておしえてください。

質問

連立方程式を解くために不完全ＬＵ分解前処理つき双共役勾配法
について勉強しています。

前処理の際に、行列Ａを不完全ＬＵ分解しその逆行列(LU)^(-1)というのを使用します。LU分解まではできたのですが、この逆行列は普通にＬＵ分解＋直接法という形でもとめるのでしょうか。だとしたら、直接法をつかっていてあまり高速化が期待できない様な気がしました。

不完全コレスキー分解つき共役勾配法(ICCG)のときは、不完全コレスキー分解後、間接的にAの逆行列をもとめて使用する方法がありましたのでなにかいい方法があるのかと思い質問しました。

はじめてのプログラミングで見当違いなことをいっているかもしれませんがよろしくおねがいします。

回答No.5

DreaMMaster · ベストアンサー

あと、p.115の
6.2代入計算
の方が参考になるかもしれません。

お礼

DreaMMaster様

本当にご親切な解説ありがとうございました。
とてもよくわかりました。
結局のところＬＵ分解する「意味」が
わたしにわかっていなかったようです。

どうもありがとうございました。

回答No.4

DreaMMaster

小国力先生の『行列計算ソフトウェア―WS、スーパーコン、並列計算機』が手元にあれば、p.88-89の
4.3.3不完全これスキー分解と不完全LU分解
を見てください。

回答No.3

DreaMMaster

#2です。
　(L U)^(-1)を左からかける、と言うことは、L^(-1)を左からかけ、更にU^(-1)を左からかける。ということはお分かりでしょうか？
　Lは下三角行列ですから、逆行列をかけるためにいちいち逆行列の成分を求めなくても、良いことはおわかりでしょうか？（本質的にガウスの消去法の後半でもあり、LU分解の本質でもあるのですが…。未知ベクトルの第一成分はLの第11成分で定数項の第1成分を割れば良いです。未知ベクトルの第二成分は第一成分が分かれば計算できます。以下同様）

　Uの逆行列も同様です。

更に言うと、(L U)^(-1)Aをいかに簡略化するかがプログラミング上のポイントの一つですから、丁寧な本であれば、書かれているはずです。

小国力編著、『行列計算ソフトウェア―WS、スーパーコン、並列計算機』、丸善
渡部力,小国力, 名取亮 (監修)、 『Fortran77による数値計算ソフトウェア 』、丸善
などでは、きちんと書かれていて、しかもFortranとはいえソースコードも載っていますから参考になると思います。
　古い本しか紹介できず申し訳ありません。最近の動向は追っかけていないので…

補足

ご丁寧な解説ありがとうございます。

まさに、私の質問は、
「更に言うと、(L U)^(-1)Aをいかに簡略化するかがプログラミング上のポイントの一つ」の部分です。

小国力先生の『行列計算ソフトウェア―WS、スーパーコン、並列計算機』を借りてきました。たとえば　10,5,2 ILUBCGでも
10.5.4ILUCGSでも手順１、手順２で　不完全LU分解して(LU)^(-1)
をかけているような記述しかみあたりません。
私の持っているテキストと同じ書き方しかないように思えます。
（きっと私が見落としているだけだと思います）

すみませんが、どこに記述されているか教えてください。

よろしくお願いします。

回答No.2

DreaMMaster

ICCGと同様にすれば、反復法に持ち込めます。
と言うより、反復法に持ち込めるように、完全に分解しないので不完全分解と言うのですが…。

補足

すみません。私の舌足らずな（間違い）の文のせいでどうやら
質問の真意がお伝えできていないみたいです。

元の文で「LU分解まではできたのですが」というのは「不完全LU
分解はできたと」いう意味で、DreaMMaster様のおっしゃる
「反復法に持ち込めるように、完全に分解しないので不完全分解」
の意味は理解できております。

私がＩＣＣＧと同じようにできないと思っているのは

ICCGでは( L D L^(T) )^(-1) r というものを求める必要に対して
わざわざ( L D L^(T) )^(-1)を求めないで( L D L^(T) )^(-1) r
を一気にもとめているのに対し

不完全ＬＵ分解つきの双共役勾配法や自乗共役勾配法では
(L U)^(-1)(b-Ax)や　(L U)^(-1)A など　(L U)^(-1)を
つかう式が違った形で出てきていて、これには(L U)^(-1)
自体を求める必要があるのかという点です。

しかし、(L U)^(-1)をもとめてから(L U)^(-1)(b-Ax)や　(L U)^(-1)A
を求める演算は結構時間ががかりそうなので疑問に思い質問しました。

よろしくお願いします。

回答No.1

stomachman

「不完全LU分解」は知りませんけど、ともかくLU分解をした、つまり下三角行列Lと上三角行列Uとの積の形に分解したのだとします。面倒なので逆行列を*で表すことにすると、
(LU)* = U* L*
であり、L*は下三角行列、U*は上三角行列。
　LとL*がどっちも下三角行列であることを利用するとL*は簡単に計算できます。というのは、
L L* = E (単位行列)
だから、
E[j,j]=L[j,j] L*[j,j] = 1
他の項は全部0なんで、これだけになっちゃう。で、L*[j,j] が決まった。
　さて、
E[j,j-1] = L[j,j-1] L*[j-1,j-1] + L[j,j] L*[j,j-1]=0
であるから、L*[j,j-1]が決まった。
という調子です。
　U*も同様。

補足

ご丁寧な解説どうもありがとうございます。

逆行列の求め方はよくわかりました。

でも、前処理としてわざわざこれで逆行列を求めた後、
この逆行列を何度もかける演算をして真の逆行列を求めるのでは
かえって遅くなってしまうようなきがします。

実際やってみると速いんでしょうか