update: 9/08/2008

暗号理論の応用を試みた行列変換のあれこれ。そのレポートの続きです。


Top Page へ

Contents
 

◎　逆行列変換フローチャート 

◎　３x３行列の場合
◎　２x２行列の場合

◎　４x４〜１０x１０行列の場合

◎　結論

◎　サンプルプログラム

◎　改良結果

 


◎ 　逆行列変換フローチャート
 
 
掃出し法のアルゴリズムはエラー要因を良く考慮したものがありますが、
改めて作成してみるとプログラム言語の影響と思われる部分もありました。
 
 
[アスキーデータの行列化]
　　　|
[ det = 0 ] --- yes --- [ (a) 他の変換 ]
      |
[ 掃出し法  A → A-1 ]
      |
[ 小数点 n 桁での打切り　B = A-1 - ε(n+1) ]
      |
[ ファイルに保存 ]
      |
[ ファイルから読出し ]
      |
[ 掃出し法  B → B-1 ]
      |
[ 復元精度の比較  B-1 = A ? ] --- no --- [ (b) 他の変換 ]
      |
[ 小数点桁 n の利用 ] 
 
 
top 
 


◎  ３x３行列の場合
 
 
３ｘ３ 行列での実験プログラムでは、ｎと復元失敗の関係は次のようになりました。
英数文字６２９＝？　の組合せからランダム抽出で１０００回を１０セット試験します。
 

保存桁ｎ / セット
1
2
3
4
5
6
7
8
9　
10
割合
 
4
711
684
689
666
694
715
687
708
710
696
70%
 
5
1
2
1
1
1
3
0
3
2
4
 - 0.4%
 
6
0
2
0
1
2
2
0
3
1
2
 - 0.3%
 
7
1
2
0
1
0
1
3
5
2
1
 - 0.5%

 
計算のように４桁ではありませんが、５桁からはほぼ完全に復元できました。
保存桁を増やしても精度が改善されないのは、復元行列を整数へ
近似する時にエラーが起きてたのが原因でした。
例えば復元の結果　65.000123 という値になったのに、整数変換して整数 65 と
比較一致すると False 判定がでます。
整数値の比較方法としては、次のものが考えられます。
 
�@ 四捨五入の方法
 
　 a) Int 型でのキャスト。(int)1.99 = 1.0 のように切下げになるのを利用する。
 
　 b) Java には、最も近い整数に変換する Math.rint(double) が
　    用意されているので、これを使う。
 
�A 極限値の考え方
 
　２数の差の絶対値により評価します。Math.abs(a-b)<= 0.00001 のような判定です。
 
�@の方法が当初のプログラムでしたが、�Aの方法に変更しました。
 
整数値への四捨五入ですので、差が 0.5 以上の場合、復元失敗と見なします。
 
 

保存桁ｎ / セット
1
2
3
4
5
6
7
8
9　
10
割合
 
4
717
704
702
701
707
696
701
698
663
698
70%
 
5
0
0
0
0
1
0
0
0
0
0
 - 0.01%
 
6
0
0
0
1
0
0
0
0
0
0
 - 0.01%
 

 
なぜ�@の方法では駄目なのでしょう？ Math.rint() メソッドにエラーが無いならば、
A==B の数値判定では、初期化後に代入した数値と、演算後に代入した数値では
ビット的な差がでる場合があるのかもしれません。
 
�Aの方法でも残るエラーは、教科書通りにピボットがゼロとなる例でした。
２桁以上の例はあまり見かけないので記録しておきました。
 
98  101  75          80  112  117
98  101  79          85  119   67
76  101 112          52  115   82
 
２行目と３行目を交換すると、無事に計算できますが、交換行の記録が必要になり、
0.01% ほどなので、この場合は逆行列変換は中止しました。
 
top 

 

◎  ２x２行列の場合
 
３ｘ３行列で思わぬエラーが出たので、２Ｘ２行列も丁寧に調査しました。
 

保存桁ｎ / セット
1
2
3
4
5
6
7
8
9　
10
割合
 
3
974
974
970
975
978
964
969
969
983
978
97%
 
4
399
391
366
403
421
384
382
383
401
435
 40%
 
5
0
0
1
0
0
0
0
0
0
0
 0.002% （５回に１回ぐらい）
 
6
1
0
0
0
0
0
0
0
0
0
 0.002% （５回に１回ぐらい）

 
計算と異なり、５桁までの保存が必要でした。
0.002% のエラーの原因は特殊な場合に起きるゼロ計算エラーでした。
次の行列式はいずれもゼロですが、double 型の関数呼出で計算した値は
大きな負の値になっていました。
 
double det=det2(a,b,c,d);
 
...
 
public static double det2(double a, double b, double c, double d){
 
double detr=a*d-b*c;
 
return detr;
 
}
 
 
70   76     　　                      87  120    
105 114   →  det = -6.36804E7        87  120  →  det = -9.43035E7
 
念のため、50 〜 120 の値で行列式を計算すると、
 
  50x50 - 50x50 = -6.25E6
120x120 - 120x120 = -2.0736E8
 
のように変化していきます。１を足すと、-6249999　のようになるので、
プログラムとしては、負の数として認識しています。
関数呼出でも引き算ではこのような現象は起きず、関数呼出せずに、
ベタで書いても( double det=a*d-b*c ; ) このような計算エラーは起きませんでした。
論理演算での符号ビット、補数表現などが関係していそうですが、
エラーメッセージがあってもよさそうです。
 
 
 
top 
 

 

◎ 　４ｘ４〜１０ｘ１０行列の場合
 
４ｘ４

保存桁ｎ / セット
1
2
3
4
5
6
7
8
9　
10
割合
 
4
883
885
896
868
901
894
886
870
868
877
 88%
 
5
0
1
0
0
0
0
0
0
0
0
 0.005% （２回に１回ぐらい）
 

 
 
５ｘ５

保存桁ｎ / セット
1
2
3
4
5
6
7
8
9　
10
割合
 
4
982
976
969
967
967
965
964
967
958
965
97%
 
5
0
3
1
1
1
1
0
1
0
1
 0.1 - 0.3%
 
6
0
0
0
0
1
0
0
0
0
0
 0.002% （５回に１回ぐらい）
 

 
 
７ｘ７

保存桁ｎ / セット
1
2
3
4
5
6
7
8
9　
10
割合
 
4
1000
998
996
998
998
995
997
992
995
998
99%
 
5
19
20
23
26
21
26
30
17
17
26
 - 0.6% （１０回に３回ぐらい）
 
6
0
0
1
0
0
0
0
0
0
0
 0.01% 
 

 
 
１０ｘ１０

保存桁ｎ / セット
1
2
3
4
5
6
7
8
9　
10
割合
 
4
996
997
997
995
999
998
995
998
999
998
99%
 
5
146
166
144
158
144
148
158
166
176
150
 15%
 
6
0
0
0
1
0
0
0
0
0
0
 0.005% （２回に１回ぐらい）
 

 
 
最後まで残ったエラーは、やはり掃出し法のピボットがゼロとなるケースでした。
 
105 115  66 108
57  106 102  77
53  106 106 112
54   57  56  86
 
 89 55  90  53  121
 89 55  88  86   72
 74 48  76 107  121
113 66  49  78  120
 84 57 121  50   70
 
107 116 119  74 106  86  78
107 116 102 109 115  88  81
 88  52  99  50 116 119  70
118  78  76  88  68  54 100
 55  67  84 118  89  84 108
104  99  50  57  83  69  99
 87 102 102 106  73 122  78
 
 50  55  74 109  71  86  53  54  99  68
100 110  55 100 120  81  98 116  84 122
108 103 100  89  66 109 104 114  66  51
 98  78  65 112  51  84 102  71  80  80
 82 103 113 121  71  87 105  69  57  67
 53 118  80  50  70  74 113 112  87 104
107  87  98  66  55  67  51  55 107 121
103  78  78 121  70 122  54 121  69  53
 71 110  68  52  80  78 109 107  87 122
 68 113  57  75  74  77 117  76 106  54
 
 
 
top 
 


◎ 　結論
 
 

行列次元
安全な保存小数点桁数
復元失敗の確率 %
保存容量の増加(byte)
２ｘ２
5
0.002 
 16  →    64
３ｘ３
5
0.01  
 36  →   126
４ｘ４
5
0.005 
 64  →   224
５ｘ５
5
0.002 
100  →   350
７ｘ７
6
0.01  
196  →   686
１０ｘ１０
6
0.005 
400  →  5600

 
文字数はｎ２で、１文字を２桁の数字と考えると Unicode では４byteです。
よって当初の　４ｎ２ から、５桁の場合は１４ｎ２で ３．５倍、
６桁の場合は１６ｎ２で４倍ぐらいの保存容量の増加があります。
 
top 
 


◎ 　サンプルプログラム
 
ダウンロード ( Java )
 


 
top 
 


◎ 　改良結果
 
実装中...
 
 
top 
 


 
  調査レポート作成 :tmlbworks