No | 215912 | |
著者(漢字) | 関川,浩 | |
著者(英字) | ||
著者(カナ) | セキガワ,ヒロシ | |
標題(和) | 近似計算を用いた代数的数のゼロ判定法と数式処理アルゴリズムへの応用 | |
標題(洋) | Zero Determination of Algebraic Numbers using Approximate Computation and its Application to Algorithms in Computer Algebra | |
報告番号 | 215912 | |
報告番号 | 乙15912 | |
学位授与日 | 2004.02.20 | |
学位種別 | 論文博士 | |
学位種類 | 博士(数理科学) | |
学位記番号 | 第15912号 | |
研究科 | 数理科学研究科 | |
専攻 | ||
論文審査委員 | ||
内容要旨 | 本論文では,近似計算の一種である区間計算および,Mahler measure と呼ばれる代数的数の measure の評価を用いて代数的数の計算を行う方法を提案し,この方法によって,与えられた代数的数α1, α2, …, αnに加減乗算を施して得られた結果が0か否かを厳密に判定できることを示す.なお,本論文は,[1], [2], [3] に基づくものである. 代数的数の計算を正確演算により厳密に行うことは可能であるがコストがかかる.そこで,効率のよい近似計算を利用しようと考えるのは自然である.本論文では,近似計算として,数値計算の一種で単純な浮動小数計算よりも誤差解析が容易である区間計算を用いる.代数的数の数値計算を行うため,QをCに埋め込み,代数的数αの値は,この埋め込みによりαを複素数と見たときの数値のこととする.さらに,入力される代数的数αiは,αiを根とするfi(x)∈Z[x] および,fi(x) の根のうちαiのみを含む区間の対として与えられているものとする. 一般に,正確演算に基づいたアルゴリズムをそのまま近似計算で実行すると,近似の精度をいくら高めても真の出力に収束するとは限らない.この性質を不安定性という.簡単のため,以下,加減乗算と等号判定(実の場合は符号判定も含む)による条件分岐のみからなるアルゴリズムを考える.加減乗算は連続であるが,等号判定は等号が成り立つ点で不連続であり,判定結果により以降の計算の道筋がまったく変わってしまう.すなわち,不安定性は,もっとも単純化すれば,計算結果が0か否か,という形で起こる.この問題をゼロ判定問題という. 白柳は,可換環のイデアルの Grobner 基底を求める Buchberger のアルゴリズムを安定化する手法を提案した.その手法は,アルゴリズムの構造はそのままとし,区間計算を用い,「ゼロ書き換え」という規則を適用する.ゼロ書き換えとは,計算の途中で0を含む区間が現れたら,それをただ一点0に書き換えるという規則である.この手法は,入力とアルゴリズム中の近似計算の精度をいくらでも上げられるならば,出力は真の出力に収束し,さらに,ある有限精度から先では常に出力が妥当となることが証明されている.妥当とは,与えられた入力に対してアルゴリズムを実行したときのすべてのゼロ書き換えが正しい,すなわち,0を含む区間は,正確演算で実行すれば0となる値である,ということである.この手法の根底にあるアイディアは白柳と Sweedler により一般化され,代数的アルゴリズムの安定化理論となった. ただし,この手法には課題もある.すなわち,妥当な出力を得るにはどの程度の精度が必要か,あるいは,ある精度での出力が妥当か否かをいかに判定するか,という問題である.今,ゼロ書き換えなしで計算があるところまで進んだとせよ.この時点での計算の途中結果の区間Iが0を含まなければ,対応する計算を正確に行なったときの真の値αは0ではない.しかし,もし,Iが0を含めば,α=0か否かは,この区間計算の結果のみからは判定できない.なぜならば,α≠0であっても,精度が不十分であれば0∈Iとなり得るからである.これは,先に述べたゼロ判定問題である. そこで,このゼロ判定問題を解決する手法を提案するのが本論文の目的である.代数的数αが,与えられた代数的数α1, α2, …, αn の間の加減乗算の結果であるとしたとき,「|α|<εならばα=0」を成立させるε>0を見出すことができる,というのが提案する手法の要点である.このようなεをαの分離限界と呼ぶ. 定理1(ゼロ判定の原理)代数的数αの分離限界εと,αを含む区間Iがわかっているとせよ.(1)0∈Iならばα≠0と判定でき,(2)0∈I,かつ,Iが0を中心とする半径εの円の内部に含まれるならばα=0と判定でき,それ以外の場合は,(3)αのゼロ判定にはさらに精度を上げることが必要であることが分かる.そして,精度を上げて計算を繰り返せば,必ず(1)か(2)の状態に到達する. 分離限界を見つけることは可能である.なぜならば,原理的には,αを根とするf(x)∈Z[x]は,与えられた代数的数αiの情報から構成できるからである.しかし,fを計算するにはコストがかかる.そこで,fを計算することなくεを見出す一般的な枠組を提案し,代数的数αの Mahler measure M(α) を利用することによりそれが実現できることを示す. 代数的数αに対し,その整数係数の原始的な最小多項式をとしたとき,Mahler measure は,で定義される.さらに,二つの measure M0, M1を,と定義し,MをM0とM1の積に分解しておく. 以上の準備のもとに主結果を述べる. 定理2 KをRまたはCとし,K0=K∩Qとする. XをK0上定義された述語の集合とする.Xに対し,我々は以下のことを知っているものとする.(a) 代数的数αが,αを根とするf(x)∈Z[x] および,f(x) の根のうちαのみを含む区間の対で与えられているとき,αが満たす述語ξ∈Xを見出す方法,(b) 代数的数α, βがそれぞれ述語ξ, η∈Xを満たすとき,α*β (*∈{+, -, ×}) が満たす述語ζ∈Xをξ, ηから見出す方法,(c) 代数的数αが述語ξ∈Xを満たすとき,αに対する分離限界を見出す方法.このとき,α∈K0がα1, α2,…, αn∈K0から加減乗算により得られ,各αiに対し,αiを根とするfi(x)∈Z[x] および,fi(x) の根のうちαiのみを含む区間の対で与えられているとき,αに対する分離限界を計算できる. 「degα≦dかつM(α)≦A」,ただし,d∈N, A≧1, という述語全体からなる族をYとする(degα=[Q(α) : Q].このとき,Yは1の三つの条件を満たす. 「degα≦dかつM0(α)≦A0かつM1(α)≦A1」,ただし,d∈N, A0, A1≧1, という述語全体からなる族をYとする.このとき,Yは1の三つの条件を満たす. 「degα≦dかつM0(α)≦A0かつM1(α)≦A1かつα∈I」,ただし,d∈N, A0, A1≧1, Iは区間,という述語全体からなる族をYとする.このとき,Yは1の三つの条件を満たす. Mahler measure の性質より定理2の第1項が証明される.第2項は,代数的数α, βに対し,M(α*β) (*∈{+, -, ×})をM(α), M(β)を用いて評価する,すでに知られている不等式を用いて証明される.さらに,M0, M1それぞれについての同様な不等式を二通り示すことにより第3項,第4項が証明されるが,新しく証明された不等式は,元の Mahler measure に関する不等式を改良したものになっている.なお,そのうちの一つは,α, βの近似値を用いる. 以上の枠組を実際のプログラムに適用するために,(1)区間計算と Mahler measure の計算を同時に行う方法と,(2)計算履歴を保存しながら区間計算を行い,ゼロ判定の必要があるときのみ Mahler measure の計算を行う二つの方法を提案し,実際に計算幾何学のアルゴリズム(二次元の凸包構成)に適用した実験結果も示す. | |
審査要旨 | 近年,コンピュータの性能が上がり,単純な数値計算だけでなく数式を扱うような代数的な問題にも有効に活用されるようになってきている.このような場合は,数式は有理数を係数とする多変数の多項式や有理関数などの枠組みで扱って,厳密な計算を行う数式処理が用いられる.特に数学における基本的な概念である環のイデアル計算を数式処理で扱うには,イデアルを一意的に表現するため Grobner 基底が用いられ,その基底を元に計算が行われる.この Grobner 基底を求める基本的手法は,Buchberger のアルゴリズムとして知られている. 一方,複雑な問題に対して数式処理で厳密な計算を行うには,大変コストがかかり,アルゴリズムとしては正しくても,数理的な問題に適用するには実用的でないことが多く起こる.そのため,数を厳密な表現でなく,近似値で置き換え,必要に応じて精度を上げることが考えられる.しかしながら,式の値が正負や零になるのに応じた条件分岐があるアルゴリズムでは,判定結果によって以降の計算が全く変わってしまうので,厳密な計算に基づいたアルゴリズムにおいて近似計算を行うと,近似の精度を高めていっても真の値に近づくとは限らない,という不安定性が起こり得る.この安定性は,計算結果が0か否か,というゼロ判定問題に帰着される. 白柳は,近似計算を用いた Buchberger のアルゴリズムを安定化するため「ゼロ書き換え」という手法を提案した.これは,アルゴリズムは変えずに誤差を考慮した区間計算の途中で0を含む区間が現れたらそれを0に置き換える,というものであり,近似計算の精度をいくらでも上げられるなら,正確な計算を行った結果に収束することが証明されている.このアイデアは,白柳と Sweedler により一般化され,代数的アルゴリズムにおける安定化理論となった. この安定化理論を現実の問題に適用するにおいて,区間をどのように取ればよいか,すなわち近似の精度がどの程度であれば,ゼロ判定が正しいか,ということを与えることは別の問題として考えなくてはならない. この論文では,複数の代数的数に四則演算を施したとき,すなわち整数係数の1変数多項式の根として具体的に指定した複数の数に対して四則演算を行ったとき,その結果のゼロ判定問題に対し,「ゼロを含むある区間Iに近似値が入っていれば,実際には0である」という区間Iを具体的に与える手法,すなわち,分離限界を求めてゼロ判定を近似計算で行う手法を与えた.その概略は以下の通りである. 代数的数αに対し,その整数係数の原始的な最小多項式をとすると,とおいたとき,を Mahler measure と呼ぶ.代数的数αjの演算の結果は,代数的数となり,演算を行った結果の数γの Marler measure M(γ)を,元の Mahler measure からM(γ)<Lのように具体的な数Lで評価することによって,「|γ|<1/Lならばγ=0が結論できる」という原理を用いる. 本論文では,代数的数に対し,誤差の範囲を込めた区間と Marler measure の組を考え,それらの和,差,積の結果の数に対する区間と Marler measure の評価式を与えることにより,実際の計算に適用できる手法を提供した.また,計算のコストを下げるため,知られている評価式の改良もなされている. Galois の意味で解けないただ1つの実根を持つ3つの5次方程式を与え,それらの実根の間に成り立つ2次の関係式を証明する問題,2次の無理数で座標が与えられた平面上の多数の点の凸包を求める問題などに,この手法を応用し,この手法の有効性を明らかにすると共に,計算コストの評価に役立つ結果が得られている.前者に対してはこの論文による手法を用いない場合は,複雑な数式処理を行う問題となる. 論文提出者は,本論文で「代数的数の演算のゼロ判定問題に近似計算を用いる」という斬新なアイデアを初めて打ち出し,その手法を開発した.これは計算機科学における新たな方向性を示した先駆的なアルゴリズムであり,応用上も重要である.よって,論文提出者関川浩は,博士(数理科学)の学位を受けるにふさわしい充分な資格があると判断した. | |
UTokyo Repositoryリンク | http://hdl.handle.net/2261/49007 |