情報科学概論I 【第５週】単位区間上のカオスとフラクタル ～実数の不思議～ 徳永隆治　（情報学類）.

Presentation on theme: "情報科学概論I 【第５週】単位区間上のカオスとフラクタル ～実数の不思議～ 徳永隆治　（情報学類）."— Presentation transcript:

1 情報科学概論I 【第５週】単位区間上のカオスとフラクタル ～実数の不思議～ 徳永隆治　（情報学類）

2 実数の成り立ち 【実数】実数は、有理数と無理数からなる 【有理数１】既約な分数（n/m）で表現できる実数
【無理数１】既約な分数で表現できない実数 【質問】小数表現を前提として、有理数と無理数を再定義せよ 【有理数２】循環する小数 【無理数２】循環しない小数 【質問】命題「デジタル計算機の中に無理数は存在する」は真か偽か？ 【有理数３】有限語長（ビット長）で記述できる可能性がある実数 【無理数３】有限語長（ビット長）では記述できない実数 【質問】デジタル計算機は、無理数をいかにして扱うのか？ なぜ，有理数で無理数を扱えるのだろうか？　詳しく調べてみる！！

3 可算集合 【有限集合】元の総数が有限である集合 【無限集合】元の総数が有限ではない集合 【可算集合】元が数えられる無限集合
【数えるとは？】集合の元を一列に並べて左から正の整数を１：１で割り当てる操作 【命題１】単位閉区間[0,1]上の有理数は可算集合 【証明】 　閉区間 [0,1] 上の有理数が，左から右へ順に並べられることを例証する． 1 分母1の有理数 2 1 分母2の有理数 分母3の有理数 3 1 2 33 分母nの有理数 n 1 …. × × × …… m …………… 　左から順に正の整数を割り当てることができる．　■

4 非可算集合 【非可算集合】可算集合ではない無限集合 【命題２】単位閉区間 [0,1] 上の実数は非可算集合 【証明】 〔仮定〕単位区間上の実数は，小数として上から下へ順に並べることができる …..… a b c d e f g …..… a’ b’ c’ d’ e’ f’ g’ h’ i’ j’ k’ l’ m’…..… : a” b” c” d” e” f” g” …..… …..… 0. 8 1 3 A’…..……..……..… この実数は，上の数表（区間[0,1] 上の実数）に存在しない．　■ A B …..……..……..……..……..

5 内点，境界と閉包 【内部と外部】集合Xの元だけで囲まれる点を内点といい，補集合CXの元だけで
　囲まれる点を外点という．内点の集合iXを内部といい，外点の集合を外部という． 【境界】内点でも外点でもない集合Xの元を境界点といい，境界点の集合∂Xを 　境界という． 【質問】単位区間上の有理数の集合Aの内部と境界を答えよ． 【解答】 iA = f，∂A = [0,1] 【閉包】集合Xに境界∂Xを加えた集合を閉包cl{A} という． 【稠密】集合Aの部分集合Bの閉方cl{B}が，Aに一致するならば部分集合Bは， 　A上で稠密であるという． 【命題３】単位閉区間 [0,1] 上で有理数は稠密である． 【証明】∂A = [0,1]より自明　■

6 なぜデジタル計算機で無理数が扱えるのか 【完備；complete 】すべてのコーシー列が収束する距離空間は完備である．
コーシー列とは，極限値を目指す近似数列であり，数が多くなれば多いほど近似精度が高まることを意味する． 空間の完備性は，“目標”となる値，そのものを扱うことはできないが，“目標”が確かに存在し，幾らでも良い近似値を扱えることを意味する． デジタル計算機とは，無理数を（有限語長で表現可能な）有理数で近似する　　システムである． 有理数による近似精度は，有限のレジスタ長で限定されている． 再帰的プログラミングによって，時間方向に有理数列を発展させ，近似精度を　改善できる． 【区間演算；interval operation】真の実数値xを有理値区間[p,q]で表現する計算手法　を区間演算という．

7 大学受験問題 【非線形漸化式】 【質問】初期条件x０∈[1, ∞)に関して，limn→∞xnを求めよ．
【解答】帰納的に，x0≧1 ならば，任意のn>0に対して，xn ≧ 1である ． したがって， |xn+1-1| ≦ 2-1 |xn-1| ≦ ….. ≦ 2-n |x０-1| limn→∞ |xn+1-1| ≦ limn→∞ 2-n |x０-1| = 0 limn→∞ xn+1= 1　　　　　　　　　　　　　　　　■

8 種明かし xn+1 1 0 1 xn 大学入試の問題では，漸化式の解は必ず収束しなくてはならない．
　　 　 　　　 xn 微係数が，１より小さいなら，公比が１より小さい等比級数で押さえられる． 逆に，微係数の大きさが１より大きいとき，とんでもない事が起こる．

9 カオス 【非線形漸化式】xn+1 = f(xn) = 2xn – q(xn-0.5), q(x) = if x <0 then 0 else 1 1 xn+1 xn x1 x2 x0 【軌道】初期条件x０から漸化式で求められる点列 {xn}を軌道という． 【質問１】初期条件x０が有理数の場合，軌道{xn}はどうなる？ 【質問２】初期条件x０が無理数の場合，軌道{xn}はどうなる？ 【ヒント】実数xを２進数で表現するとき，漸化式は何を意味するのか？

10 解答１ 【２進数表現】x = 0.s0 s1 s1 s2 …. sN …………
【漸化式】 ビットシフト：xn = 0.s0 s1 s1 s2 …. sN … → xn+1 = 0.s1 s1 s2 …. sN … 【質問１】初期条件x０が有理数の場合，軌道{xn}はどうなる？ 【解答】 x０が有理数　⇔　ビット列は循環する． 　　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で閉じる 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　■

11 解答２ 【質問２】初期条件x０が無理数の場合，軌道{xn}はどうなる？ 【解答】 x０が無理数 ⇔ ビット列は循環しない．
　　x0 = 0.s0 s1 ….sN……………………………… 　したがって， 　　x1 = 0. s1 ….sN………………………………… ≠ x0 　　x2 = 0. s2 ….sN …………………………………≠ x0 , x1 : 　　xN+1 = 0. sN ………………………………… … ≠ x0 , x1 ,.., xN 軌道は，閉じることはない． 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　■ 閉じない軌道{xn}は，乱数を意味する． 決定論的機構から生成される乱数列を決定論的カオスという．

12 奇妙な集合 【非線形漸化式】 f：x  [0,1]  (3/2) (1-|2x-1|)  R1 【質問】発散しない初期値の集合
　　　　　Λ = {x [0,1] : limn→∞ xn [0,1] } 　はどんな形になるか？ 0　　　　　　 1 【ヒント】区間の像の関係 　f : [1,∞]  [0, - ∞] 　f : [0, - ∞]  [0, - ∞] 　から，一度でも１よりも大きくなると軌道は発散してしまう．

13 解答 I00 I01 I11 I10 I0 I1 L 【質問】発散しない初期値の集合
　Λ = {x [0,1] : limn→∞ xn [0,1] } 　はどんな形になるか？ I00 I01 I11 I10 I0 I1 【解答】xn [0,1] か否かは，合成関数fnで判別できる． 閉区間を３等分にして，中央の開区間を取り除く操作 を全ての閉区間で無限回再帰的に反復してできる集合 （Cantor集合）となる． 【Cantor集合】 ①コンパクト集合（有界かつ閉集合） 　どの段階でも閉集合であり，極限も閉集合 ②完全非連結（内点を持たない） 　どの段階でも区間の左と右は離れている 000 001 011 010 110 111 101 100 L ③完全（非可算集合） 　区間を表す記号は，[0,1] 上の２進数と1:1対応する

14 自己相似集合 【自己相似集合；self affine set】自身の縮小像の和集合で自身を構成できる集合
【例】単位線分は最も単純な自己相似集合である． = 【例】単位正方形は最も単純な自己相似集合である． = 【例】Cantor集合は自己相似集合である． =

15 複雑な自己相似集合 【自己相似集合】自身の４つの縮小像の和集合で“羊歯” の絵が作られている．

16 位相次元と非整数次元 【例】単位線分の位相次元は１である． = 1 = 1/2 + 1/2 ○ 【例】単位正方形の位相次元は２である． =
= / /2 ○ 【例】単位正方形の位相次元は２である． = = / / / /2 × = (½) (½)2 + (½)2 + (½)2 ○ 【例】 Cantor集合の位相次元は？ = = (1/3)D + (1/3) D = (1/3) D = log2 - D log3 D = log2/log3

17 【問題３】以下の過程の極限における自己相似集合の非整数次元を求めよ．
レポート問題３ 【問題３】以下の過程の極限における自己相似集合の非整数次元を求めよ．

18 レポート提出方法 ○問題１～問題２をレポート用紙(A4)に回答せよ． ○レポートを，
　　　理科系修士棟B523 　(締め切り：２４日　金曜日午後５時) 　 　へ提出せよ．(期限外は認めず，直ちに零点となる) ○レポートは，締め切り後の１週間の間，カオス研で返却する． 　(返却されなかったレポートは，廃棄するので注意せよ)