1. No category

3 次元双曲多様体の精度保証付き数値計算
Neil Hoffman
市原一裕
柏木雅英
正井秀俊
大石進一
高安亮紀
(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 Cliffs, 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. Hoffman, K. Ichihara, M. Kashiwagi, H. Masai, S. Oishi, and A. Takayasu, Verified
computations for hyperbolic 3-manifolds, submitted (arXiv:1310.3410), 2013.