3 次元双曲多様体の精度保証付き数値計算 Neil Hoﬀman 市原一裕柏木雅英正井秀俊大石進一高安亮紀 (The University of Melbourne)∗1 (日本大学) (早稲田大学) (東京工業大学) (早稲田大学) (早稲田大学) 1. はじめに本講演では，理想三角形分割されたトーラス境界を持つ 3 次元多様体 M に対して，M および M の Dehn filling が完備有限体積双曲構造をもつかどうかを精度保証付き数値計算を用いて厳密に証明する手法について考える．ここで精度保証付き数値計算とは数値計算のすべての誤差を把握して，数学的に正しい結果を数値計算によって得ることをいう．3 次元多様体の双曲構造に対する数値的分類手法は Moser [1] によるものが有名であり，多くの論文で分類手法として使用されている．[1] では Kantorovich の収束定理を用いることで Newton 法の誤差評価を厳密に得られる一方，数値計算に生じる誤差の把握が全く行われておらず，これを無視して数学証明とすることは難しい．数値計算に生じる誤差の把握は区間演算 [2, 3] を用いることが一般的であり，本手法の要は区間演算と Krawczyk による非線形方程式の解の検証手法の実装である．これらの手法は非線形方程式の解に対する精度保証付き数値計算法のスタンダードであり，高速に誤差の把握ができるだけでなく，ユーザーが気軽に使用できる汎用性がある．以下では M に対する接着方程式: Find z = (z1 , . . . , zn ) ∈ Cn s.t. g(z) = 0 に対してその解を完璧に正しく包含する精度保証付き数値計算の手法を紹介する．ここで g は Cn からそれ自身への写像とする．実装のために zj = x2j−1 + ix2j (j = 1, · · · , n) とすると，上記の方程式は Find x = (x1 , . . . , x2n ) ∈ R2n s.t. f (x) = 0, と同値である．ここで f : R2n → R2n は微分可能な非線形写像とする．上記の方程式の解を数値計算する場合，Newton 法の反復を途中で停止する打切り誤差と数値計算を行う丸め誤差の 2 種類の誤差が混入する．本手法では丸め誤差は区間演算を用いて厳密に把握し，Newton 法の打切り誤差を Krawczyk の検証定理によって厳密に把握することで，計算に生じるすべての誤差を考慮した精度保証付き数値計算が可能になる． 2. 区間演算通常の数値計算は浮動小数点数を用いて計算を行う．浮動小数点演算には計算毎に丸め誤差が生じることがよく知られている．ここでは丸め誤差を考慮しながら数値計算を行える区間演算について述べる．X := {x ∈ R : x ≤ x ≤ x, x, x ∈ R} = [x, x] を R ∗1 e-mail: [email protected] web: http://www.oishi.info.waseda.ac.jp/~takayasu/hikmot/ 上の区間とする．R 上の区間全体を IR で表すとする．各区間に対して区間演算を定義することができ，例えば区間 X = [x, x] ,Y = [y, y] に対する四則演算は [ ] X + Y = x + y, x + y [ ] X − Y = x − y, x − y [ ] X · Y = min{x · y, x · y, x · y, x · y}, max{x · y, x · y, x · y, x · y} ] [ 1 1 , (0 ̸∈ Y ) X/Y = X · , y y と定義できる．一般に区間同士の演算は無限回の演算を必要とするようにみえるが，実際には有限回の端点の計算のみで計算が可能となる．区間演算を用いるメリットは高速な浮動小数点数演算を行いながら，演算を多重定義することで数値計算に含まれるすべての誤差を正確に把握できることである． 3. Krawczyk による検証手法 X ∈ IRm を各成分が区間のベクトルとする．いま c ∈ X を方程式 f (x) = 0 の近似解（例えば SnapPy [4] によって得られる近似解）とし，R ∈ Rm×m をヤコビアン f ′ (c) の逆行列に近いある行列とする．Krawczyk 写像 K : IRm → IRm は I ∈ Rm×m を単位行列とすると K(X) = c − Rf (c) + (I − Rf ′ (X))(X − c) と定義できる．このとき Krawczyk による検証定理 [5] が存在する． Theorem 3.1 (Krawczyk’s test) 各区間 X ∈ IRm に対して，int(X) = {x ∈ X : xi < xi < xi (i = 1, · · · , m)} を X の内包とする．もし条件 K(X) ⊂ int(X) が成り立つならば，X 内に方程式 f (x) = 0 をみたす厳密解 x が局所一意に存在する．さらに R と C ∈ f ′ (X) をみたす行列 C が正則である．講演では投稿中の論文 [6] をもとに我々の手法を実装したパッケージ HIKMOT について紹介し，区間演算を浮動小数点数を用いて実現する実装の手法と HIKMOT の応用について説明する．参考文献 [1] H. Moser, Proving a manifold to be hyperbolic once it has been approximated to be so, Algebraic & Geometric Topology, 9 (2009), 103–133, Code associated to the paper is available here: http://www.math.columbia.edu/ moser/. [2] T. Sunaga, Theory of an interval algebra and its application to numerical analysis, RAAG Memoirs 2 (1958), 29–46. [3] R.E. Moore, Interval Analysis, Prentice-Hall, Englewood Cliﬀs, 1966. [4] M. Culler, N. M. Dunfield, and J. R. Weeks. SnapPy, a computer program for studying the geometry and topology of 3-manifolds, http://snappy.computop.org [5] R. Krawczyk, Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing 4 (1969), 187–201. [6] N. Hoﬀman, K. Ichihara, M. Kashiwagi, H. Masai, S. Oishi, and A. Takayasu, Verified computations for hyperbolic 3-manifolds, submitted (arXiv:1310.3410), 2013.