情報科学概論I
【第5週】単位区間上のカオスとフラクタル
~実数の不思議~
徳永隆治
(情報学類)
実数の成り立ち
【実数】実数は、有理数と無理数からなる
【有理数1】既約な分数(n/m)で表現できる実数
【無理数1】既約な分数で表現できない実数
【質問】小数表現を前提として、有理数と無理数を再定義せよ
【有理数2】循環する小数
【無理数2】循環しない小数
【質問】命題「デジタル計算機の中に無理数は存在する」は真か偽か?
【有理数3】有限語長(ビット長)で記述できる可能性がある実数
【無理数3】有限語長(ビット長)では記述できない実数
【質問】デジタル計算機は、無理数をいかにして扱うのか?
なぜ,有理数で無理数を扱えるのだろうか? 詳しく調べてみる!!
可算集合
【有限集合】元の総数が有限である集合
【無限集合】元の総数が有限ではない集合
【可算集合】元が数えられる無限集合
【数えるとは?】集合の元を一列に並べて左から正の整数を1:1で割り当てる操作
【命題1】単位閉区間[0,1]上の有理数は可算集合
【証明】
閉区間 [0,1] 上の有理数が,左から右へ順に並べられることを例証する.
分母1の有理数 分母2の有理数 分母3の有理数
0 1
1 1
1 2
0 1 2
×2 2 ×2
3
0 1
×3 3
4 5
分母nの有理数
2 3 ….
0 1 …. n
×
×
×n
3 3
n n
……..
m ……………
左から順に正の整数を割り当てることができる.
■
….
非可算集合
【非可算集合】可算集合ではない無限集合
【命題2】単位閉区間 [0,1] 上の実数は非可算集合
【証明】
〔仮定〕単位区間上の実数は,小数として上から下へ順に並べることができる
0. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 …..…
0. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 a b c d e f g …..…
0. 0 0 0 0 0 0 0 0 0 0 0 0 a’ b’ c’ d’ e’ f’ g’ h’ i’ j’ k’ l’ m’…..…
:
0. 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 a” b” c” d” e” f” g” …..…
:
1. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0…..…
0. 8 1 3
A B …..……..……..……..……..
A’…..……..……..…
この実数は,上の数表(区間[0,1] 上の実数)に存在しない. ■
内点,境界と閉包
【内部と外部】集合Xの元だけで囲まれる点を内点といい,補集合CXの元だけで
囲まれる点を外点という.内点の集合iXを内部といい,外点の集合を外部という.
【境界】内点でも外点でもない集合Xの元を境界点といい,境界点の集合∂Xを
境界という.
【質問】単位区間上の有理数の集合Aの内部と境界を答えよ.
【解答】 iA = f,∂A = [0,1]
【閉包】集合Xに境界∂Xを加えた集合を閉包cl{A} という.
【稠密】集合Aの部分集合Bの閉方cl{B}が,Aに一致するならば部分集合Bは,
A上で稠密であるという.
【命題3】単位閉区間 [0,1] 上で有理数は稠密である.
【証明】∂A = [0,1]より自明 ■
なぜデジタル計算機で無理数が扱えるのか
【完備;complete 】すべてのコーシー列が収束する距離空間は完備である.
コーシー列とは,極限値を目指す近似数列であり,数が多くなれば多いほど近似
精度が高まることを意味する.
空間の完備性は,“目標”となる値,そのものを扱うことはできないが,“目
標”が確かに存在し,幾らでも良い近似値を扱えることを意味する.
デジタル計算機とは,無理数を(有限語長で表現可能な)有理数で近似する
システムである.
有理数による近似精度は,有限のレジスタ長で限定されている.
再帰的プログラミングによって,時間方向に有理数列を発展させ,近似精度を
改善できる.
【区間演算;interval operation】真の実数値xを有理値区間[p,q]で表現する計算手法
を区間演算という.
大学受験問題
x n 1 
【非線形漸化式】
xn
【質問】初期条件x0∈[1, ∞)に関して,limn→∞xnを求めよ.
【解答】帰納的に,x0≧1 ならば,任意のn>0に対して,xn ≧ 1である .
したがって,
x n -1
x n -1
x n 1 -1  x n -1 

2
xn 1
|xn+1-1| ≦ 2-1 |xn-1| ≦ ….. ≦ 2-n |x0-1|
limn→∞ |xn+1-1| ≦ limn→∞ 2-n |x0-1| = 0
limn→∞ xn+1= 1
■
種明かし
x n -1
x n -1
x n 1 -1  x n -1 

2
xn 1
大学入試の問題では,漸化式
の解は必ず収束しなくてはな
らない.
xn+1
微係数が,1より小さいなら,
公比が1より小さい等比級数
で押さえられる.
1
逆に,微係数の大きさが1よ
り大きいとき,とんでもない
事が起こる.
0
0
1
xn
カオス
【非線形漸化式】xn+1 = f(xn) = 2xn – q(xn-0.5), q(x) = if x <0 then 0 else 1
1
xn+1
0
0
x0
x1 xn
x2
1
【軌道】初期条件x0から漸化式で求められる点列 {xn}を軌道という.
【質問1】初期条件x0が有理数の場合,軌道{xn}はどうなる?
【質問2】初期条件x0が無理数の場合,軌道{xn}はどうなる?
【ヒント】実数xを2進数で表現するとき,漸化式は何を意味するのか?
解答1
【2進数表現】x = 0.s0 s1 s1 s2 …. sN …………
【漸化式】 ビットシフト:xn = 0.s0 s1 s1 s2 …. sN … → xn+1 = 0.s1 s1 s2 …. sN …
【質問1】初期条件x0が有理数の場合,軌道{xn}はどうなる?
【解答】 x0が有理数
⇔ ビット列は循環する.
x0 = 0.s0 s1 ….sM | s0 s1 ….sM |…… | s0 s1 ….sM |……
したがって,
x1 = 0. s1 ….sM | s0 s1 ….sM |…… | s0 s1 ….sM |…… ≠ x0
x2 = 0. s2 ….sM | s0 s1 ….sM |…… | s0 s1 ….sM |…… ≠ x0
:
xM+1 = 0. s0 s1 ….sM |…… | s0 s1 ….sM |…… = x0
軌道は,周期Mで閉じる
■
解答2
【質問2】初期条件x0が無理数の場合,軌道{xn}はどうなる?
【解答】 x0が無理数
⇔ ビット列は循環しない.
x0 = 0.s0 s1 ….sN………………………………
したがって,
x1 = 0. s1 ….sN………………………………… ≠ x0
x2 = 0. s2 ….sN …………………………………≠ x0 , x1
:
xN+1 = 0. sN ………………………………… … ≠ x0 , x1 ,.., xN
軌道は,閉じることはない.
■
閉じない軌道{xn}は,乱数を意味する.
決定論的機構から生成される乱数列を決定論的カオスという.
奇妙な集合
【非線形漸化式】 f:x  [0,1]  (3/2) (1-|2x-1|)  R1
【質問】発散しない初期値の集合
Λ = {x [0,1] : limn→∞ xn [0,1] }
はどんな形になるか?
【ヒント】区間の像の関係
0
f : [1,∞]  [0, - ∞]
f : [0, - ∞]  [0, - ∞]
から,一度でも1よりも大きくなると軌道は発散してしまう.
1
解答
【質問】発散しない初期値の集合
Λ = {x [0,1] : limn→∞ xn [0,1] }
はどんな形になるか?
【解答】xn [0,1] か否かは,合成関数fnで判別できる.
閉区間を3等分にして,中央の開区間を取り除く操作
を全ての閉区間で無限回再帰的に反復してできる集合
(Cantor集合)となる.
【Cantor集合】
I0
①コンパクト集合(有界かつ閉集合)
どの段階でも閉集合であり,極限も閉集合
②完全非連結(内点を持たない)
I00
I1
I01 I11
000 001 011 010
110 111 101 100
どの段階でも区間の左と右は離れている
③完全(非可算集合)
区間を表す記号は,[0,1] 上の2進数と1:1対応する
I10
L
自己相似集合
【自己相似集合;self affine set】自身の縮小像の和集合で自身を構成できる集合
【例】単位線分は最も単純な自己相似集合である.
=
【例】単位正方形は最も単純な自己相似集合である.
=
【例】Cantor集合は自己相似集合である.
=
複雑な自己相似集合
【自己相似集合】自身の4つの縮小像の和集合で“羊歯” の絵が作られている.
位相次元と非整数次元
【例】単位線分の位相次元は1である.
=
1
○
=
1/2 + 1/2
【例】単位正方形の位相次元は2である.
=
1
=
×
1/2 + 1/2
1
=
○
(½)2 + (½)2 + (½)2 + (½)2
+ 1/2 + 1/2
【例】 Cantor集合の位相次元は?
=
1
=
(1/3)D + (1/3) D
1
=
2(1/3) D
0
=
log2 - D log3
D
=
log2/log3
レポート問題3
【問題3】以下の過程の極限における自己相似集合の非整数次元を求めよ.
レポート提出方法
○問題1~問題2をレポート用紙(A4)に回答せよ.
○レポートを,
理科系修士棟B523
(締め切り:24日 金曜日午後5時)
へ提出せよ.(期限外は認めず,直ちに零点となる)
○レポートは,締め切り後の1週間の間,カオス研で返却する.
(返却されなかったレポートは,廃棄するので注意せよ)
ダウンロード

講義用スライド(pptファイル)