安定化手法のユークリッド互除法とスツルムのアルゴリズムへの適用東邦大学理学部情報科学科卒業研究発表５５０８０３４菊池裕也白柳研究室１．研究の背景と目的白柳らは代数的アルゴリズムを近似計算したときに起こる不安定性に対し安定化手法を提案。安定化手法に関する研究は数多く行われているが数式処理システムMaple14で行われた例はない。 Maple14で安定化手法を使えるようにする。ユークリッド互除法とスツルムのアルゴリズムに適用させ結果を考察する。 2 ２．安定化手法、ユークリッド互除法安定化手法（１）入力多項式に対し、係数の区間化（２）アルゴリズムの構造は変えず、命令に従い区間演算（３）YES,NO判定の際、区間に０が含まれる場合０とみなす（ゼロ書き換え）任意の２つの式に対し、最大公約式を求める 3 ３．ユークリッド互除法の適用結果実験 64 147 16 98 [ 𝑥 − 1, 𝑥 − 1] 343 49 出力結果厳密計算 4 49 −1 + 𝑥 7 近似計算 −0.004515235604 1.15550013610−7 −1.000000000 + 0.5714285714𝑥 49 −1.000000000 + 0.5714285716𝑥 49 安定化計算 CPU 精度桁 0 0 0 0 0 0.016 2 7 8 10 2 0.5294117647,0.6250000000 𝑥 49 + [−1, −1] 0.5670731707,0.5766871166 𝑥 49 0.016 3 + [−1, −1] 0.5713848227,0.5714810731 𝑥 49 0.016 5 + [−1, −1] 0.5714285711,0.571428520 𝑥 49 0.078 10 + [−1, −1] 4 ４．スツルムの定理重根を持たない実数係数の代数方程式の、任意に与えられた閉区間における根の個数を計算できる定理。 [例] 閉区間 −1,2 𝑓 𝑥 = 𝑥 3 − 4𝑥 2 + 3𝑥 answer=２ 5 𝑓0 𝑥 = 𝑓 𝑥 , 𝑓1 𝑥 = 𝑓 , (𝑥) 𝑓𝑘−1 𝑥 を𝑓𝑘 (𝑥)で割った余りを−𝑓𝑘+1 (𝑥)とする 𝑓𝑟−1 (𝑥)は𝑓𝑟 (𝑥)で割り切れる（𝑓𝑟 (𝑥) ≠ 0) 𝑓0 𝑥 , 𝑓1 𝑥 , 𝑓2 𝑥 , … … … , 𝑓𝑟 (𝑥)をスツルム列という。スツルム列に対し、閉区間[a.b]のaとbを代入 𝑓0 𝑎 , 𝑓1 𝑎 , … , 𝑓𝑟 𝑎 に対し、符号の変わった数をV(a)とする 𝑓0 𝑏 , 𝑓1 𝑏 , … , 𝑓𝑟 𝑏 に対し、符号の変わった数をV(b)とする 𝑉 𝑎 − 𝑉 𝑏 = 𝑎𝑛𝑠𝑤𝑒𝑟 6 [例]𝑓 𝑥 = 𝑥 3 − 4𝑥 2 + 3𝑥 区間[−1,2] 𝑓0 𝑥 = 𝑥 3 − 4𝑥 2 + 3𝑥 𝑓0 −1 = −8 𝑓1 −1 = 14 26 𝑓2 −1 = − 9 81 𝑓3 −1 = 49 𝑓1 𝑥 = 𝑓0 ′ 𝑥 = 3𝑥 2 − 8𝑥 + 3 14 4 𝑓2 𝑥 = − 𝑓0 𝑥 ÷ 𝑓1 𝑥 = 𝑥− 9 3 81 𝑓3 𝑥 = − 𝑓1 𝑥 ÷ 𝑓2 𝑥 = 49 𝑥 = −1 𝒇𝟎 − 𝒇𝟏 + 𝒇𝟐 − 𝒇𝟑 + 𝑽(𝒙) 3 𝑥=2 − − − + 1 𝑓0 2 = −2 𝑓1 2 = −1 16 𝑓2 2 = − 9 81 𝑓3 2 = 49 𝑎𝑛𝑠𝑤𝑒𝑟 = 𝑉 −1 − 𝑉 2 = 2 7 ５．スツルムの定理の安定化手法適用結果 19 3 388 2 𝑞= − 𝑥 + 𝑥 + 20𝑥 − 100 7 3 𝑠𝑢𝑡𝑢𝑟𝑢𝑚𝑢 q, −5,5 4 −10𝑥 4 q2 = −10𝑥 4 − 2.7143𝑥 3 + 129.3333𝑥 2 + 20𝑥 − 100 −5,5) 𝑠𝑢𝑡𝑢𝑟𝑢𝑚𝑢(𝑞2, 4 q3 = −10, −10 𝑥 4 + −2.7144, −2.7142 𝑥 3 + 129.333299,129.333301 𝑥 2 + 20,20 𝑥 + −100, −100 𝑘𝑢𝑘𝑎𝑛𝑠𝑢𝑡𝑢𝑟𝑢𝑚𝑢(𝑞3, −5,5) 4 8 ６.まとめと考察・Maple14で区間演算のプログラムを構築した。・安定化手法をユークリッド互除法、スツルムの定理へ適用させた。・ユークリッド互除法では、低い精度桁で安定化手法の適用で利点が見られた。また、精度桁を上げることにより真の値に近づく計算結果を得られた。・スツルムの定理では、近似計算でも可能になってしまい、安定化手法の優位性は見られなかった。近似計算では不可能になるデータをより多く集め、安定化手法の優位性を高めることが今後の研究課題となる。