プログラムな日常>理数学習このままでイイン会?>
行列式は要らない。けど、
(determinant may be just instructive)

逆行列は、行列式を通じて定義することで一意だと説明できるが、ほぼこれだけが行列式の存在意義である。逆行列は色々と有用だが、 行列式が本当に利用されることは滅多にない。だいいち、行列式を普通に利用しようとすると、正方行列の一辺 L に対し、O(L!) 程度のステップが必要になり、 たいてい許せるレベルではない。逆行列を、いわゆる余因子行列の行列式から求める計算も O((L+1)!) の程度で、お話にならない。

だが今回、逆行列を利用する上で、正則性の事前判定が欲しいことがあって、気がついた。逆行列を求める直接法の計算の途中で、 変換を通じて行列式の値が不変な手段を使うが、この性質に着目して対角行列(または上三角行列)にまで変換すれば、 得られた行列の行列式は対角積として求められ、逆行列と同じ O(L^3) 程度のステップで解が得られることになる。 この考えによって作った行列式計算のソースコードを以下に公開します(頁末のボタンを押すと表示されます)。

もとに戻るが、行列式など、世間一般でもほとんど利用されていないはずで、だから、こうした手段の改良は話題にされないのかも知れない。


表:行列式を求める C# の実行につき、従来法(数学の教科書に定義されている方法)と今回の方法とのエラップスタイム比較:

正方行列の
サイズL
従来法の経過時間
(ミリ秒)
今回法の経過時間
(ミリ秒)
10130
11170
12320
13780
142340
153620
166630
171,4520
183,8740
199,2710
2019,6520
100-0
150-13
500-449
1000-2,740
1500-9,062
2000-21,283


追伸(2月15日)

遠い昔の出版だが、「マトリクスの数値計算」(戸川隼人 著、初版 1971 年)に、今回の記事と同じと思われる方法が推奨されていました。 これによれば、「 n=20 でもすでに、48658040163532800000 回 という途方もない数になってしまうので実用的でない」とされており、 プログラム例の文献も挙げられています。

ただ、この時代には逆に、低速ルーチンの方が、理屈はわかっても気軽に試すのは難しかったんじゃないかな? それに、いくら何でもこの数字は大きすぎる。 私のは低速ルーチンであっても、ハッシュ表とか使って、これよりはかなり高速化していると思います。

プログラムを表示する(2022/3/14 一部改訂):