3 次元双曲多様体の精度保証付き数値計算

3

N. Hoffman (The University of Melbourne) 市原 一裕 (日本大学文理学部)

柏木 雅英 (早稲田大学) 正井 秀俊 (東京工業大学)

大石 進一 (早稲田大学／CREST, JST) 高安 亮紀 (早稲田大学)

日本数学会2014年度年会@学習院大学 3月15日

Gluing equations

[W. Thurston]

∀ M : triangulated 3-manifold, possibly with torus boundary.

∃ equation s.t. whose solution (IF ANY) gives rise to a hyperbolic structure on M . (Gluing equation)

∏

j=1

(z

)

· (1 − z

)

=

∏

j=1

( − 1)

for m = 1, · · · , n + 2k + h and

∑n

j=1

arg((z_j)^{(aj,m−cj,m)}) + arg((1−z_j)^{(−bj,m+cj,m)}) =ϵ_m−

∑n

j=1

c_j,m·πi.

SnapPea

[J. Weeks] SnapPea: a computer program to make/solve glueing equations.

[M. Culler - N. Dunfiled] SnapPy: ”SnapPea on python”

SnapPea uses Newton’s method.

▶

floating point error?

▶

finitely many calculations can ensure convergece?

Previous work

H. Moser, Proving a manifold to be hyperbolic once it has been approximated to be so, Algebraic & Geometric Topology, 9 (2009), 103–133.

The literature says that Kantorovich’s convergence theorem guarantees the convergence of Newton’s method. There is an exact solution in the neighborhood of an approximate solution.

Can you believe the computer-aided procedure?

Previous work

H. Moser, Proving a manifold to be hyperbolic once it has been approximated to be so, Algebraic & Geometric Topology, 9 (2009), 103–133.

The literature says that Kantorovich’s convergence theorem guarantees the convergence of Newton’s method. There is an exact solution in the neighborhood of an approximate solution.

Can you believe the computer-aided procedure?

Gluing equations

Finally, the gluing equation is described by Find z ∈ C

s.t. g(z) = 0, where g is a mapping from C

onto itself.

Setting z

= x

+ ix

(j = 1, · · · , n), it is equivalent to Find x ∈ R

s.t. f (x) = 0,

where f : R

→ R

is a differentiable nonlinear real

mapping.

Gluing equations

Finally, the gluing equation is described by Find z ∈ C

s.t. g(z) = 0, where g is a mapping from C

onto itself.

Setting z

= x

+ ix

(j = 1, · · · , n), it is equivalent to Find x ∈ R

s.t. f (x) = 0,

where f : R

→ R

is a differentiable nonlinear real

mapping.

Newton’s iteration converges but...

Exact solution?

▶

In numerical computations, there are truncation errors when stopping an infinite series, e.g.

sin x ≈ x − x

3! + x

5! − x

7! + x

9! − x

11!

Influence of rounding error?

▶

It is well-known that a rounding error occurs in every floating-point operation.

1

10 ≈

Newton’s iteration converges but...

Exact solution?

▶

In numerical computations, there are truncation errors when stopping an infinite series, e.g.

sin x ≈ x − x

3! + x

5! − x

7! + x

9! − x

11!

Influence of rounding error?

▶

It is well-known that a rounding error occurs in every floating-point operation.

1

10 ≈

To prove the hyperbolicity Truncation error

Krawczyk’s test

Rounding error

Interval analysis

⇒ We develop a python module: HIKMOT.

It obtains mathematically rigorous conclusions from results of numerical computations based on the floating-point arithmetic.

Our package performs a rigorous numerical existence test for solutions of gluing equations.

http://www.oishi.info.waseda.ac.jp/~takayasu/hikmot/

To prove the hyperbolicity Truncation error

Krawczyk’s test

Rounding error

Interval analysis

⇒ We develop a python module: HIKMOT.

It obtains mathematically rigorous conclusions from results of numerical computations based on the floating-point arithmetic.

Our package performs a rigorous numerical existence test for solutions of gluing equations.

http://www.oishi.info.waseda.ac.jp/~takayasu/hikmot/

To prove the hyperbolicity Truncation error

Krawczyk’s test

Rounding error

Interval analysis

⇒ We develop a python module: HIKMOT.

It obtains mathematically rigorous conclusions from results of numerical computations based on the floating-point arithmetic.

Our package performs a rigorous numerical existence test for solutions of gluing equations.

http://www.oishi.info.waseda.ac.jp/~takayasu/hikmot/

To prove the hyperbolicity Truncation error

Krawczyk’s test

Rounding error

Interval analysis

⇒ We develop a python module: HIKMOT.

It obtains mathematically rigorous conclusions from results of numerical computations based on the floating-point arithmetic.

Our package performs a rigorous numerical existence test for solutions of gluing equations.

http://www.oishi.info.waseda.ac.jp/~takayasu/hikmot/

Interval analysis

Basic idea of interval analysis

A computer cannot deal with √

2 as an exact number, it can compute

1.41421356 ≈ √

2 ∈ [1.41421356, 1.41421357]

We write an interval

X := { x ∈ R : x ≤ x ≤ x, x, x ∈ R} = [x, x].

▶

IR : the set of such intervals.

Interval arithmetic

For a unary operation u : R → R and a binary operation

◦ : R × R → R , we can extend these operations to

˜

u : IR → IR and ˜ ◦ : IR × IR → IR , defined by

˜

u(X) := { u(x) : x ∈ X } and

X ˜ ◦ Y := { x ◦ y : x ∈ X, y ∈ Y }

for X, Y ∈ IR .

Gluing equations

The gluing equation can be rewritten as Find x ∈ R

s.t. f (x) = 0,

where f : R

→ R

is a differentiable nonlinear real mapping. Set m = 2n.

Krawczyk’s mapping K : IR

→ IR

is defined by K (X) := c − Rf (c) + (I − Rf

(X))(X − c),

where I ∈ R

is a unit matrix, R ∈ R

a certain matrix to be an approximate inverse of f

(c) and c ∈ X is an

approximate solution of f(x) = 0.

Gluing equations

The gluing equation can be rewritten as Find x ∈ R

s.t. f (x) = 0,

where f : R

→ R

is a differentiable nonlinear real mapping. Set m = 2n.

Krawczyk’s mapping K : IR

→ IR

is defined by K (X) := c − Rf (c) + (I − Rf

(X))(X − c),

where I ∈ R

is a unit matrix, R ∈ R

a certain matrix to be an approximate inverse of f

(c) and c ∈ X is an

approximate solution of f(x) = 0.

Theorem (Krawczyk’s test)

For a given interval X ∈ IR

, let int(X) be the interior of X.

If the condition

K(X) ⊂ int(X)

holds, then there uniquely exists an exact solution x

in X.

Furthermore, it is also shown that R and all matrices C ∈ f

(X) including f

(x

) are nonsingular.

R. Krawczyk, Newton-Algorithm zur Bestimmung von

Nullstellen mit Fehlerschranken, Computing 4(1969), 187–201.

Krawczyk’s test

If the condition

K(X) ⊂ int(X)

holds, then there exists x in X with invertibility of R.

⇓ Rigorous existence test

There exists a real vector x ∈ X such that f (x) = 0.

Krawczyk’s test

If the condition

K(X) ⊂ int(X)

holds, then there exists x in X with invertibility of R.

⇓ Rigorous existence test

There exists a real vector x ∈ X such that f (x) = 0.

Advantages of interval arithmetic

▶

Fast (especially compared to exact arithmetic)

▶

Uses less memory

▶

Overwrites the basic four operations (+, − , × , ÷ )

▶

Extends to functions naturally

▶

Accumulates numerical error by itself

Further techniques to implement

▶

Automatic differentiation

▶

Complex arithmetic

▶

Verified computations for arg(z) (atan2 function)

Advantages of interval arithmetic

▶

Fast (especially compared to exact arithmetic)

▶

Uses less memory

▶

Overwrites the basic four operations (+, − , × , ÷ )

▶

Extends to functions naturally

▶

Accumulates numerical error by itself

Further techniques to implement

▶

Automatic differentiation

▶

Complex arithmetic

▶

Verified computations for arg(z) (atan2 function)

HIKMOT

N. Hoffman, K. Ichihara, M. Kashiwagi, H. Masai, S. Oishi, and A. Takayasu, Verified computations for hyperbolic 3-manifolds, submitted (arXiv:1310.3410), 2013.

The python module is available on

http://www.oishi.info.waseda.ac.jp/~takayasu/hikmot/

Thank you for kind attention!

HIKMOT

N. Hoffman, K. Ichihara, M. Kashiwagi, H. Masai, S. Oishi, and A. Takayasu, Verified computations for hyperbolic 3-manifolds, submitted (arXiv:1310.3410), 2013.

The python module is available on

http://www.oishi.info.waseda.ac.jp/~takayasu/hikmot/

Thank you for kind attention!