逆行列は、行列式を通じて定義することで一意だと説明できるが、ほぼこれだけが行列式の存在意義である。逆行列は色々と有用だが、 行列式が本当に利用されることは滅多にない。だいいち、行列式を普通に利用しようとすると、正方行列の一辺 L に対し、O(L!) 程度のステップが必要になり、 たいてい許せるレベルではない。逆行列を、いわゆる余因子行列の行列式から求める計算も O((L+1)!) の程度で、お話にならない。
だが今回、逆行列を利用する上で、正則性の事前判定が欲しいことがあって、気がついた。逆行列を求める直接法の計算の途中で、 変換を通じて行列式の値が不変な手段を使うが、この性質に着目して対角行列(または上三角行列)にまで変換すれば、 得られた行列の行列式は対角積として求められ、逆行列と同じ O(L^3) 程度のステップで解が得られることになる。 この考えによって作った行列式計算のソースコードを以下に公開します(頁末のボタンを押すと表示されます)。
もとに戻るが、行列式など、世間一般でもほとんど利用されていないはずで、だから、こうした手段の改良は話題にされないのかも知れない。
正方行列の サイズL |
従来法の経過時間 (ミリ秒) |
今回法の経過時間 (ミリ秒) |
---|---|---|
10 | 13 | 0 |
11 | 17 | 0 |
12 | 32 | 0 |
13 | 78 | 0 |
14 | 234 | 0 |
15 | 362 | 0 |
16 | 663 | 0 |
17 | 1,452 | 0 |
18 | 3,874 | 0 |
19 | 9,271 | 0 |
20 | 19,652 | 0 |
100 | - | 0 |
150 | - | 13 |
500 | - | 449 |
1000 | - | 2,740 |
1500 | - | 9,062 |
2000 | - | 21,283 |