C言語関係掲示板

過去ログ

No.90.複素行列の行列式を求めるプログラム(2)


何回もこの事で書き込んでいます
本当に申し訳ないです

ある程度自分で組んでみたのですが
なかなかうまくいきません(>o<)(泣)
いろいろ教えていただいたのに
できない自分が悔しいです

そして、あれから行列式に関するページを見つけたのですが
プログラム中に????の部分がありよくわかりません
だれか説明していただけませんでしょうか?
http://www.d4.dion.ne.jp/~sekiya_z/na/e01mpis.html


ども。


>http://www.d4.dion.ne.jp/~sekiya_z/na/e01mpis.html

これは以前述べた、上三角行列にして対角成分を求める、という方法を実装した
もののようです。以下に、「半分だけ」関係のある、ガウスの消去法について
簡単に説明しておきます。

ガウスの消去法は、線形方程式Ax=bの解法ですが、その過程で、係数行列Aを
上三角行列にするような変換(前進代入過程)を行います。数式で書くと
U=(上三角行列)としてMAx=Ux=Mbですね。この後にxの各成分をもとめます
(後退代入過程)。Ux=b'(=Mb)においてUが上三角行列なので、xが(下から順に)
簡単に求まります。

で。
行列式を求めるだけならば、後退代入過程は不要で、また、bも(ないので)不要
です。

前進消去(はきだし)による上三角化はMの算出と行列積(MA)を行わなければ
なりませんが、これは実装の際には 1.Mの算出 2.MA というように行うの
ではなく、M=(Mn)..(M2)(M1)というように考えて、Miの計算と積を1回の
反復で同時に行います。Uを作るには、a(i,j)(ただしi<j)を0にしなければ
なりませんが、これは、i行目を定数倍して他の行から引くことによって実現
します。これがMiの計算と積に相当します。

ポイントは、行列式を求める際に、i行目を定数倍して他の行から引くという
作業を行った行列も、行列式は同じ値になるという点です。したがって、
そのような作業の積み重ねで作られた上三角行列の行列式は元の行列式と
等しいままとなります。上三角行列の行列式が、その対角成分の積で得られる
ことは明らかですので、任意n×nの行列であっても上三角行列に持ち込めさえ
すればよいということになります。


いったんきります。


では。


ども。


ここからは主に実装について。前の説明が(悪くて)わからなかったら、(行列式
よりも)ガウスの消去法について調べて(検索して)みてください。きっと、いい
説明がたくさんみつかります。。


>前進消去(はきだし)による上三角化はMの算出と行列積(MA)を行わなければ
>なりませんが、これは実装の際には 1.Mの算出 2.MA というように行うの
>ではなく、M=(Mn)..(M2)(M1)というように考えて、Miの計算と積を1回の
>反復で同時に行います。Uを作るには、a(i,j)(ただしi<j)を0にしなければ
>なりませんが、これは、i行目を定数倍して他の行から引くことによって実現
>します。これがMiの計算と積に相当します。

で、実際の消去ですが、左上->左下、1つずれて左上->左下..というような
順で行います。注目行で1、それを残りの行に定数倍して引くので1、その際
各成分の引き算に1、の合計3重のループになります。

気をつけなければならないことは、2点あって、ひとつは、0除算が起こる可能性
があるという点で、もうひとつは、注目行の選択順によって精度が変わるという
点です。これらのコードが含まれていることもあって、コードからしくみを
理解しようとした場合は苦労します。なお、紹介されたコードは対角成分の
積の算出を一番外側のループで同時に行っています(1周すると対角成分が
1つ求まるので)。


で、その解決方法ですが、どちらも注目要素の選択(ピボット選択)によって
解決します。選択とは具体的に何をするのかというと、行(ないし列)の
入れ替えです。行(ないし列)の入れ替えによって処理順序を変えます。
行と列の入れ替えは両方やってもよいのですが、0除算についてだけならば
どちらかのみで対応できます(正則ならば)。精度を追求する場合は両方やる
こともあるかもしれません。
# 行/列を入れ替えても行列式は変わりません。念のため。

しかし、入れ替えのコストは当然あります。ここで、行列のメモリへの
マッピングが重要になります。Cの場合、行の入れ替えはポインタの入れ替えで
済むことは以前どこかで書きましたが、列の入れ替えは実際にデータを入れ替え
なければなりません。そのため、通常、Cでは、行の入れ替えのみが実装され
ます(精度的にもこれで十分な場合が多い)。

ちなみに。
行/列の入れ替えは、行列の掛け算に相当しますが、線形方程式のを解く場合
列の入れ替えは定数ベクトルにも掛け算をしなければならないため、行の入れ
替えよりもかなりコストがかかります。ので、その理由からも、行の入れ替え
のみが実装されることがほとんどのようです(行列式ではこっちの理由は関係
ありませんが)。


とりあえず、以上。

何倍にして引けばいいのかとか、どれをピボットにするかとか、抜けてる点が
ありますが、ガウスの消去法も含めて、適当なコード(紹介されたのでもOK)
を読めばわかると思います。


では。

戻る


「初心者のためのポイント学習C言語」 Last modified:2002.01.11
Copyright(c) 2000-2002 TOMOJI All Rights Reserved