ジョルダン標準形の

ジョルダン標準形の
アルゴリズム安定化の実装について
伊藤広晃
東邦大学理学部情報科学科
2014/02/10
1
なぜ安定化か？その１
係数を近似してそのままアルゴリズムを実行しても、結果
が必ずしも正確に近づけない場合がある

そこで
2
・安定化手法を使い
正確な出力に近づける
なぜ安定化か？その２
1
1－ ×３＝０は真か？
3

厳密計算

1
1－ ×3＝1－1
3
YES
＝0
NO
近似計算
1
1－ ×3＝1－0.333×3
3
YES
正
＝0.001
NO
誤
アルゴリズムの条件分岐で道を誤る
それが原因で不安定になることがある
3
安定化手法の３原則

区間化



…ある数xを[a,b](a≤ 𝑥 ≤b)と表す
精度桁を定める
1
 ＝0.3333…
3

区間演算


…[A,B]★[C,D]
＝[min(A★C,A ★D,B ★C,B ★D),
max(A★C,A ★D,B ★C,B ★D)]

ゼロ書き換え

…区間内に0を含む場合→[0,0]
4
例
＝[0.333,0.334]

[0.33,0.34]+[0.14,0.15]
=[0.47,0.49]

[-0.2,0.3]=[0,0]
安定化手法の具体例


安定化手法
1
1－ ×3
3
（入力）
＝[1,1]－[0.333,0.334]×[3,3]
＝[－0.002,0.001]
＝[0,0]
＞YES
（出力）
5
安定化手法の
3原則
←区間化
←区間演算
←ゼロ書き換え
安定化手法の定理（白柳-Sweedler)




A＝与えられたアルゴリズム
𝑓＝ 𝑎𝑖 𝑥 𝑖 （入力多項式）
S𝑡𝑎𝑏 𝐴 ＝Aを安定化したアルゴリズム
𝐹𝑁 ＝ 𝑖[𝑎𝑖𝑁 , 𝑎𝑖𝑥 ]𝑥 𝑖 （入力区間多項式）
このとき
 𝐹𝑁 → 𝑆𝑡𝑎𝑏 𝐴 𝐹𝑁 → 𝐴 𝑓
 l.e. 入力が収束すれば、出力も収束する
6
ジョルダン標準形とは？

固有値が

2重解のとき

7
3重解のとき
𝑃−1 𝐴𝑃
𝜆1
= 0
0

1
𝜆1
0
固有値が
0
0
𝜆2
𝑃−1 𝐴𝑃
𝜆1
= 0
0
1
𝜆1
0
0
1
𝜆1
厳密計算と近似計算の違い
厳密計算
入力：


1
6
1
9
近似計算
1
−
4
1
2
固有方程式：
2
1
1
2
𝑥 − 𝑥+ = 𝑥−
3
9
3
→2重解

8

0.166 −0.250
0.111 0.500
固有方程式：
𝑥 2 − 0.667𝑥 + 0.11125
= 𝑥 − 0.3212101739
𝑥 − 0.3447898261
 →単解

2
入力：
実験その１

区間係数行列に対して、固有値の重複度を
調査する

固有多項式をニュートン法で解くことによって、
固有値を計算
実験方法
 数式処理ソフトMapleを使用

9
実験その２

入力行列
0
A＝
1
3
−

1
3
0
−
𝑥2
0
1
3
1
3
固有多項式
y=

2
3
2
3
𝑥3
4
+
27
ニュートン法の式
𝑥𝑛+1 = 𝑥𝑛 −
10
𝑓(𝑥𝑛 )
𝑓′ (𝑥)|𝑥=𝑥𝑛
実験結果その２
初精
期度
値桁
1
3
11
出力結果
初精
期度
値桁
出力結果
9
[-781.5436641,1313.101047]
9
10
[-699.0524481, 1205.453871]
10 [-0.3334906552, -0.3331759867]
−
[-0.3344361515, -0.3322292982]
1
11 [-0.3333333333, -0.3333333333]
3
11
[0.6666604416, 0.6666604416]
12
[0.6666604416, 0.6666604416]
12 [-0.3333333333, -0.3333333333]
13
[0.6666604416, 0.6666604416]
13 [-0.3333333333, -0.3333333333]
まとめと今後の課題

区間係数行列の固有値を求めることができた

ジョルダン標準形の安定化の完成
参考文献
 「線型代数入門」 1977年財団法人東京大学出版会
著者斎藤正彦
 「コンピュータのカオスをおさえる新しい「安定」計算術」 2003年
NTTコミュ二デーション科学基礎研究所監修著者白柳潔
12

Download Report