(应用数学专业论文)元胞自动机devaney混沌条件的分析.pdf_第1页
(应用数学专业论文)元胞自动机devaney混沌条件的分析.pdf_第2页
(应用数学专业论文)元胞自动机devaney混沌条件的分析.pdf_第3页
(应用数学专业论文)元胞自动机devaney混沌条件的分析.pdf_第4页
(应用数学专业论文)元胞自动机devaney混沌条件的分析.pdf_第5页
已阅读5页,还剩23页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

摘要 元胞自动机是一种行为复杂的时空离散的动力系统。对线性元胞自动机在 d e v a n e y 意义下混沌的研究已经有了很好的结果,而对于非线性规则的研究却 鲜有进展。本文提出了在此意义下混沌的一个必要条件,并且对于初等元胞自 动机给出了判断这个条件是否满足的算法。接着用此条件证明了一种非线性元 胞自动机一投票自动机非混沌。 整篇文章按下面的结构进行组织: 第一章,给出关于元胞自动机以及混沌的预备知识,定义与基本定 理。并给出问题描述,及已有结果。 第二章,给出本文主要定理,及其证明。 第三章,定理对初等元胞自动机的应用,以及对一类非线性元胞自动 机的应用。 关键字:元胞自动机;混沌;不变块;临界规则:投票规则 a b s t r a c t c e l l u l a ra u t o m a t a ( c a ) i so fd i s c r e t ed y n a m i c a ls y s t e m sw i t h i nv a r i o u sd y n a m i c a l b e h a v i o r si n c l u d i n gc o m p l e xd y n a m i c s a sam a t t e ro ff a c t ,t h es u b j e c t so nc h a o t i c d y n a m i c so fl i n e a rc ai nt h es e n s eo fd e v a n e yh a v eb e e nf u l l yi n v e s t i g a t e di nt h e l i t e r a t u r e sr e c e n t l y h o w e v e lt h ec o r r e s p o n d i n gr e s u l t sf o rn o n l i n e a rc aa r el i m i t e d i n t h i sp a p e r ,an e c e s s a r yc o n d i t i o ng u a r a n t e e i n gt h ee x i s t e n c eo fc h a o si nn o n l i n e a r c ai nt h es e n s eo fd e v a n e yi sp r e s e n t e d a na l g o r i t h mi sf u r t h e re s t a b l i s h e df o r e l e m e n t a r yc at ov e r i f yt h ee x i s t e n c eo fc h a o s i na d d i t i o n ,as p e c i f i c k i n do f n o n l i n e a rc a v o t ec ai s p r o v e dt ob ec h a o t i c ,w h i c h i l l u s t r a t e st h ep o s s i b l e a p p l i c a t i o no fo u rt h e o r e t i c a lr e s u k s t h er e s tp a r to ft h i sp a p e ri so r g a n i z e da sf o l l o w s i n c h a p t e r1 ,s o m ep r e l i m i n a r i e s o nc e l l u l a ra u t o m a t aa n dc h a o sa r eg i v e n , i n c l u d i n gd e f i n i t i o n sa n db a s i ct h e o r e m p r o b l e md e s c r i p t i o na n de x i s t i n gr e s u l t sa r e g i v e ni nt h i sc h a p t e r t o o i nc h a p t e r2 ,t h em a i nt h e o r e mo ft h i sp a p e ra n di t sp r o v ea r eg i v e n i nc h a p t e r3 ,a p p l i c a t i o n st oe l e m e n t a r yc e l l u l a ra u t o m a t aa n dak i n do fn o n l i n e a r r u l ea r eg i v e n k e y w o r d s :c e l l u l a ra u t o m a t a ;c h a o s ;i n v a r i a n tb l o c k ;t h r e s h o l dr u l e ;v o t em l e 1 l l 一 月l j 舌 元胞自动机是一种时空离散的动力系统。它作为种理论计算机首先被冯 诺依曼提出。基于以下简单但本质的思想:许多系统中局部的变化只取决于它 的邻域的状态,元胞自动机的提出者们认为其将是模拟生命和物理系统( 如细 胞复制,菌落繁殖,晶体生长,化学过程,扩散,湍流等等) 的有力工具 1 】。 事实上,由于基本单元( 即元胞) 具有空间离散、时间离散、状态离散、相互 作用局部化和并行性等显著特点,元胞自动机特别适合于计算机模拟 2 。在应 用领域,元胞自动机被用于预测森林火灾的发展 3 ,模拟城市交通和分析全球 气候的变化 4 】。最近,有人将其用于声音数据的压缩 5 】。 数学家对元胞自动机的兴趣始于s w o l f r a m 对初等元胞自动机的研究。初 等元胞自动机布局在一维空间上,有两种状态,且邻域为标准三邻域。 s w o l f r a m 给出了它的一种分类 4 。随后的二十年时间里,很多工作都是围绕 如何给出这种分类数学上的严格定义展开的,同时分类的基础:动力学和拓扑 性质也被加以充分的讨论。 混沌是非线性研究的中心议题之一,所以依照w o l f r a m 的分类,数学家开 始考虑如何用混沌元胞自动机进行分类,也就是指出哪些是混沌的,而哪些不 是。d e v a n e y 的定义是一种被普遍接受的关于混沌的定义,其关注离散动力系 统的拓扑性质 6 】。根据符号动力系统的结论,移位规则在d e v a n e y 意义下是混 沌的 7 。 8 中证明了一维线性元胞自动机也是混沌的。 9 1 q u 给出初等元胞自动 机混沌的充要条件,这是第一个关于它的完整的数学分类,但是这个条件对于 非初等元胞自动机不正确。线性规则可以进一步推广到高维情况,证明见于 1 0 。以上是关于线性元胞自动机的一些很好的工作,但是非线性规则鲜有提 及。本文将给出一些关于非线性规则的结论。 第一章预备知识 第一节元胞自动机 1 9 7 0 年,j h c o n w a y 编制了一个名叫“生命”的游戏程序,在正方形的平 面网格中,有一种生命,其细胞会繁殖和死亡,并遵循以下规律:当一个格子周 围8 个格子中活细胞的个数为3 时,该格子中会繁殖出一个细胞;当一个活细胞 周围活细胞数为2 或3 时,该细胞存活;其他情况下,若格点中没有细胞,则没 有细胞繁殖,若格点中有活细胞,则死亡。这些简单的法则能产生意想不到的复 杂行为,生命的生长,变形,复制,定形都能从中得到,从此吸引了计算机科学 家和数学家去研究它 1 1 】。实质上,生命游戏是元胞自动机的一个例子。 元胞自动机是一种布局于格点空间的动力系统。n 维格点空间可以认为是 z ”,其中z 为整数集。每个格点从状态集a 中取值,状态集用有限集 1 2 ,p ) 表示。构型c ( 即元胞自动机的状态) 是从z “到a 的映射, c :z “_ a 。 构型空间x 是所有构型的集合, x = a z n , a 掣= c lc :z 4 _ a ) 。 全局映射f :a 掣_ a 掣为构型空间的自映射,定义如下: f ( c ) 以 = f ( c a + a i ,c a + a 2 ,c a + 口,】) , 其中c n 】表示构型c 在a 格点处的状态。f 口。,a 2 ,a ;) ,a 。z ”,i = 1 ,2 ,s 是元胞 自动机的邻域,邻域是元胞自动机的一个重要概念,它表示格点a 的变化只依赖 于当时 d + 口。,a + c h ,a + a ,) 的状态。局部规则f :a “a ,决定了邻域是如何 决定格点的变化的。 9 容易得出,( x ,f ) 是一个动力系统。 引理1 1 1 1 1 】定义a ”上的移位算子玩为: d ;( c ) = c 以+ 哥】, 其中,c a ,d ,哥z “,那么对任何f ,民与全局映射f 可交换,即 f 。瓯= 吒。f , 也就是说对每个c a 2 ”成立: f ( ( c ) ) = 呒( f ( c ) ) a 元胞自动机具有以下特征 1 1 : l , 空间离散,齐性。将空间分成离散的元胞,每个元胞的变化都服从 相同的方式,分布方式也相同。 2 , 时间离散。将连续的变化转化成离散的迭代。 3 , 状态离散,有限。状态可以用一个有限的符号序列表示。 4 , 同步计算。可以在同一个时刻完成对所有元胞的更新。将元胞自动 机的构型变化看成对数据或信息的计算( 处理) ,那么这时的重要特 征是计算的并行性。 5 , 局部性。每一个元胞的变化,只依赖于一个有限邻域中的元胞的当 前状态,也可以说,每个元胞的当前状态,只对一个有限邻域中的 元胞在下一时刻的状态可能发生影响。从信息传输的角度来看,在 元胞自动机中,信息传输的速度是有限的。 6 , 维数高。动力系统中一般将变量的个数称为维数。从这个角度来讲, 每个元胞都是一个变量,元胞自动机是一类无穷维动力系统。 为了研究元胞自动机的拓扑性质,必须在构型空间x 上赋予拓扑结构。弓 入以下距离: 定义1 1 1 ( t y c h o n o f f 距离) 9 对于n 维元胞自动机,称映射: d :a 2 “a 2 “_ a 为t y c h o n o f f 距离,当且仅当对所有,6 a ”, m 渤= 互丁l a 1 7 - b , 7 l记z ”r 其中( i ) 。取向量矿分量绝对值的最大值。容易验证d 是构型空间a ”上的度量。 在由此诱导出的拓扑下,a 掣是一个有界、紧致、完全不连通的空间,即康托集。 并且,全局映射f 是a 。上的连续映射。 以下引理给出此拓扑空间的开集。 引理1 1 2 1 0 】( 构型空间上的开集) c v 1 _ c 1c v 2 = c 2 ,c v a = q ) 在t y c h o n o f f 拓扑下是构型空间a 掣上的开集,其中 c ea ,1 j i , 2 ,v s z n , c l ,c 2 ,c j a 。 第二节离散动力系统的拓扑性质 与d e v a n e y 意义下的混沌 兀胞自动机是一种特殊的离散动力系统,因此关于离散动力系统的所有拓扑 性质都适用。而本文只关注那些与d e v a n e y 意义混沌有关的性质。 定义1 2 1 ( 拓扑传递性)动力系统( x ,) 拓扑传递当且仅当对所有非空集 u ,y x ,都存在正整数n ,使得f “f u ) n v 囝。 定义1 2 2 ( 周期点稠密) 动力系统( x ,f ) 周期点稠密当且仅当p ( f ) 是x 的 稠密子集。其中p ( f ) 是f 的周期点的集合, p ( ,) = 工x1 3 n en :f 4x ) - - - - x ) 。 定义1 2 3( 初值敏感性)动力系统( x ,f ) 初值敏感当且仅当存在占 0 ,使 得 v x ex ,占 o ,3 y x ,n en :d ( x ,y ) 0 , f “( ,o ,1 ,0 ,) = ( ,o ,1 ,0 ,) 。 同样,在其它类型的元胞自动机中也可以观察到这种现象。这种不随元胞自 动机的演化而变化的块暗示了元胞自动机的某些稳定的性质,由此我们提出“不 变块”的概念。 定义2 1 1 ( 不变块) 称有限取值组合 ( t ,包) j e z “,包a ,i = 1 ,2 ,m ) 为n 维元胞自动机的不变块,当且仅当对所有c ea ”, 如果 c 谚】= b i ,v i = 1 ,2 ,m , 那么 ,( c ) e = 岛,v i = 1 ,2 ,m , 其中m 为一有限数,z “是格点空间,a 是状态集,是全局映射。 显然,存在含有不变块的元胞自动机,但并不是所有规则都有不变块,如移 位算子对应的元胞自动机就不含不变块。 第二节不变块与混沌 这一节给出本文的主要定理,揭示了不变块与d e v a n e y 意义混沌的关系。 定理2 2 1 若元胞自动机( x ,f ) 含有不变块,则它不是拓扑传递的。 证明:设x = a ”,并且该元胞自动机含有以下不变块: ( t ,b i ) i e z “,b l a ,i = l ,2 ,m ) 。 设u c x ,其元素m 满足: “ 砭 _ 唾,v i = 1 ,2 ,m a 根据引理1 1 1 ,u 是x 中的开集。 另一个开集y 的元素v 满足: v 谚 _ d i ,i = 1 ,2 ,m , 并且 ( b l ,b 2 ,吒) ( d l , d :,如) 。( + ) 根据不变块的定义,容易得出对所有正整数n ,f “( u ) 的每个元素有以下性质: “。 e 】= d i ,i = 1 ,2 ,m 。 那么根据( t ) ,不存在n ,使得u 。v ,即 v n ,f “( u ) n v = o 。 定理得证。口 因为传递性是d e v a n e y 混沌的必要条件,自然可得以下推论。 推论2 2 1 对任意元胞自动机( x ,f ) ,如果含有不变块,那么其在d e v a n e y 意 义下非混沌。 尽管初值敏感性不是元胞自动机d e v a n e y 混沌的本质条件,但是它在其它学 科如物理学里却是一个非常重要的概念,本文也对其进行了讨论。 引理2 2 1 ( 不变块的平移不变性) 若 ( 霹,岛) i t z “,岛a ,i = 1 ,2 ,m ) 是元 胞自动机( x ,f ) 的不变块,那么对任意i z “ r ( e + i ,岛) i t z “,b l a ,i = 1 ,2 ,m ) 仍是( x ,f ) 的不变块。 证明:对任意i z ”,假设对v c ea ”, c 【v + vj 2 岛,z2 1 ,2 ,”, 根据移位算子的定义,即 吒( c ) e 】包, 因为 ( e ,b i ) f e z 4 ,岛a ,i = 1 ,2 ,m ) 是,下的不变块,由不变块的定义可得 v c ,f 。吒( 4 p , - 包, 由引理1 1 1 ,交换全局映射f 和移位算子 v c ,吒。f ( c ) e = 包, 即 v c ,( c ) 谚+ i = 岛, 再根据不变块的定义, ( t + 可,b i ) l i e z ”,包a ,i = 1 ,2 ,m 】仍是( x ,f ) 的不变 块。定理得证。口 定理2 2 2 若对于n 维格点空间z “中的任意超立方体c ,元胞自动机( x ,f ) 都 有可将其覆盖的不变块,那么( x ,f ) 不是初值敏感的。不变块 ( t ,b i ) l e z ”,岛a ,i = 1 ,2 ,m ) “覆盖”c 是指对于v i c ,都 i ,使得哥= 讧。 证明:因为构型空间a 掣在t y c h o n o f f 距离下是一个有界的度量空间,那么对于 任意万 0 ,都存在, 0 ,r e n 使得以r 为半径的超立方体c ,有开集: o c = c ic t 】= 岛,v e c ,岛a ) , 其半径d ( d ) 8 ,则由抽屉原理,一定存在两个不同的正整数 1 z h 1 9 其中五x ,h 豫,丑r 。 定义3 3 2 ( 投票规则) 4 称满足x = o ,1 ) ,五= 1 ,i = 1 ,2 ,s ,h = 妄的临界规则 z 为投票规则。 这种规则在很多领域,如经济、博弈论中都有应用 4 ,一个格点状态的变 化由某种投票决定,即由邻域的主要状态决定。投票规则在d e v a n e y 意义下是否 混沌,以下的定理回答了这个问题。 定理3 3 1 一个遵循投票规则的元胞自动机在d e v a n e y 意义下非混沌,当其邻域 是标准诺依曼邻域或摩尔邻域。 证明:容易验证, ( e ,龟) i 砭c ,包a ,i = 1 ,2 ,m ) 是诺依曼邻域下的不变块,c 是n 维空间中的超立方体,且边长 s 。 曼曼曼曼 m _ - m 曼量曼曼一 舅舅曼量i i i i 一一一 | 釜i3 3 12 维投票规则的不变块( 诺依曼邻域) 图3 3 i2 维投票规则的不变块( 摩尔邻域) 而对于摩尔邻域, ( 谚,包) i e c 7 ,包a ,i = 1 ,2 ,m ) 是不变块,其中c 是去掉顶点的超立方体。口 定理3 3 2 一个遵循投票规则的元胞自动机非初值敏感,当其邻域是标准诺依曼 邻域或摩尔邻域。 证明:因为上述的c ,c 7 都可任意放大,所以可覆盖任何超立方体,由定理2 2 2 得证。口 第四节结论 本文给出了元胞自动机在d e v a n e y 意义下混沌的一个必要条件一不变块,并 给出了寻找初等元胞自动机不变块的算法。然后由此证明了各向同性投票元胞自 动机非混沌,这是对非线性规则的应用。 2 1 参考文献 1 英 肖帕德,德罗斯著;祝玉学,赵学龙译,物理系统的元胞自动机模拟,清 华大学出版社,北京,2 0 0 3 2 赵松年,元胞自动机和复杂性研究,物理,1 9 9 4 ,2 3 ( 9 ) :5 6 6 5 7 0 3 】周成虎,孙战利,谢一春,地理元胞自动机研究,科学出版社,1 9 9 9 4 s w o l f r a m ,an e wk i n do fs c i e n c e ,w o l f r a mm e d i a ,2 0 0 2 5 s h i g e t o s h in a r a ,n a o y aa b e ,m a s a t ow a d a ,j o u s u k ek u r o i w a ,an o v e lm e t h o do f s o u n dd a t ad e s c r i p t i o nb ym e a n so fc e l l u l a ra u t o m a t aa n di t s a p p l i c a t i o nt od a t a c o m p r e s s i o n ,i n t e r n a t i o n a lj o u r n a lo fb i f u r c a t i o na n dc h a o s ,1 9 9 9 ,v 0 1 9 ,n o 6 : 1 2 1 1 1 2 1 7 6 l d e v a n e yr ,a ni n t r o d u c t i o nt oc h a o t i cd y n a m i c a ls y s t e m s ,2 n de d i t i o n , r e a d i n g ,m a ,u s a ,a d d i s o n w e s l e y ,1 9 8 9 7 张伟年,动力系统基础,高等教育出版社,施普林格出版社,2 0 0 1 8 f a v a t ip l o t t igm a r g a r al ,a d d i t i v eo n e d i m e n s i o n a lc e l l u l a ra u t o m a t aa r e c h a o t i ca c c o r d i n gt od e v a n e y sd e f i n i t i o no fc h a o s ,t h e o r e t i c a lc o m p u t e rs c i e n c e , 1 9 9 7 ,1 7 4 ( 1 - 2 ) :1 5 7 1 7 0 9 】c a t t a n e ogd e n n u n z i oa ,m a r g a r al ,s o l u t i o no fs o m ec o n j e c t u r e sa b o u t t o p o l o g i c a lp o r p e r t i e so fl i n e a rc e l l u l a ra u t o m a t a ,t h e o r e t i c a lc o m p u t e rs c i e n c e , 2 0 0 4 ,3 2 5 :2 4 9 2 7 1 2 2 1 0 c a t t a n e og ,f i n e l l im ,m a r g a r al ,i n v e s t i g a t i n gt o p o l o g

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论