（计算机应用技术专业论文）分形中若干问题的算法设计与理论研究.pdf

摘要 本文讨论了分形学中具有较重要意义的四个问题：n i f s 州o n l i n e a r i t e r a t e d f u n c t i o l l s y s t e m ，非线性迭代函数系统) 的建模与表示、非线性m a r k o v 迭代函数系统( n o n l i n e a r m a r k o vi t e r a t e df u n c t i o ns y s t e m ) 的理论与研究方法、单参数高次复多项式的s c h r 6 d e r 迭 代法的根的求解问题以及一类广义m j 集的结构特征。 n i f s 引伸于i f s ( i t e r a t e d f u n c t i o ns y s t e m ，迭代函数系统) 理论，但其性质和研究方 法已经发生了根本性的变化。n i f s 要讨论的问题很多，本文讨论了其理论和在自然景 观模拟中的应用问题，并且对真实场景韵构造给出了一些例子，这一成果已经发表在计 算机科学上。 接下来将随机过程中具有重要理论意义和应用价值的m a r k o v 过程和n i f s 理论结 合起来，推广了d e k k i n g 关于线性m a r k o vi f s 的讨论，讨论了非线性m a r k o vi f s 中的 矩的递归计算、平衡向量测度、吸引子的分析等重要问题，丰富了n m i f s 理论，对于 在这一领域的深入研究起着良好的推动作用。本文的这一成果即将在自然科学进展 上发表。 在求解方程根的方法中，s c h r 6 d e r 函数迭代方法是其中很有效的一种。但用这种方 法在求解方程根的同时，会引入额外不动点。分析额外不动点中自由临界点的吸引域的 收敛性和结构特征，是用来分析m a n d e l b r o t 集和j u l i a 集的重要方法。本文第四章将前 人的工作推广为普遍形式，对于一类单参数高次多项式的s c h r 6 d e r 函数迭代法研究j u l i a 集的问题给出了比较完善的讨论，对于其中的j u l i a 集的结构特征进行了深入研究和探 讨。 广义m - j 集的结构和生成机理也是一个很有意义的研究方向。通过结合逃逸时间 算法和周期点查找算法，本文研究了两种不同多项式形式j u l i a 集的结构，讨论了一类 具有普遍意义广义m - j 集的结构特征。 关键词：分形；迭代函数系统：m a n d e l b r o t 集；j u l i a 集；s e h r i d e r 迭代函数：平衡向 量测度：逃逸时间算法 a b s t r a c t i nt h i st h e s i sf o u ri m p o r t a n tp r o b l e m sa r ed i s c u s s e d ：m o d e l i n ga n dr e n d e r i n go fn i f s ( n o n l i n e a ri t e r a t e df u n c t i o ns y s t e m ) t 1 1 et h e o r ya n dr e s e a r c hm e a n so fn m i f s ( n o n l i n e a r m a r k o v i f s ) ，t h ec o n v e r g e n c ea n ds t r u c t u r eo f t h ea t t r a c t i v eb a s i na n dt h er e p u l s i v eb a s i no f t h ef r e ec r i t i c a l p o i n t si nj u l i as e to ft h es c h r 6 d e ri t e r a t e df u n c t i o n so fao n e p a r a m e t e r f a m i l yw i t hh i g ! ad e g r e ep o l y n o m i a l s ，a n dt h es t r u c t u r ec h a r a c t e r i s t i co f ac l a s sg e n e r a l i z e d m js e t t h et h e o r yo fn i f si se x t e n d e df r o mi f s b u ti t se s s e n c eh a sb e e na n o t h e rt h i n g i nt h i s t h e s i st h eb a s i ct h e o r ya n di t sa p p l i c a t i o ni nt h es i m u l a t i o no fn a t u r a js c e n ea r em a i n l y d i s c u s s e d t h er e s u l th a sb e e np u b l i s h e do nt h ek e m e li o u m a lc o m p u t e rs c i e n c e i nt h ef o l l o w i n gb yc o m b i n i n gt h em a r k o vp r o c e s sw i t hn i f s ，t h ea u t h o rg e n e r a l i z e s d e k k i n g sw o r ko nl i n e a rm a r k o vi f sa n dp u t sf o c u so ns o m ei m p o r t a n ta s p e c t ss u c ha s b a l a n c e dv e c t o rm e a s u r e s ，t h er e c u r s i v e c o m p u t a t i o n o fm o m e n t s ，a n dt h e c o m p u t e r s i m u l a t i o no ft h ea t t r a c t o r so fs o m en m i f s s t h er e s u l th a sb e e na c c e p t e db yt h ej o u r n a l p r o g r e s sf nn a t u r es c i e n c ea n dw i l lb ep u b l i s h e ds o o n a m o n g t h em a n ym e a n st og e tt h er o o t so fa n ye q u a t i o n ，s c h r 6 d e ri t e r a t i o ni sav e r y u s e f u lo n e h o w e v e r , e x t r af i x e dp o i n t sw i l lb ei n t r o d u c e di nt h i sp r o c e d u r e ，t oa n a l y z et h e c o n v e r g e n c ea n ds t r u c t u r eo f t h ea t t r a c t i v eb a s i na n dt h er e p u l s i v eb a s i no ft h ef r e ec r i t i c a l p o i n t si nt h ee x t r af i x e dp o i n t si sv e r yi m p o r t a n tw a y t os t u d ym a n d e l b r o ta n dj u l i as e t i n t h i sp a p e r , t h ea u t h o rg e n e r a l i z e so t h e r sw o r ka n dg i v e sab e a u t i f u lw a y t os o l v et h ep r o b l e m o ft h ej u l i as e to ft h es c h r 6 d e rf u n c t i o n so fo n e p a r a m e t e rf a m i l yp o l y n o m i a l sw i t hi x i g h d e g r e e t h es t r u c t u r ea n dt h ec o n s t r u c t i o no f g e n e r a l i z e dm js e ta r ea l s oam e a n i n g f u ls u b j e c t w i t he s c a p i n g t i m ea l g o r i t h ma n dt h ec y c l e f i n d i n ga l g o r i t h mt w od i f f e r e n tj u l i as e t sa r e s t u d i e da n dt h es t r u c t u 而c h a r a c t e ro f ac l a s so f g e n e r a l i z e dm - j s e ti sd i s c u s s e d k e y w o r d s ：f r a c t a l s ；i t e r a t e df u n c t i o ns y s t e m ；m a n d e l b r o ts e t ；j u l i as e t ；s e h r s d e r i t e r a t i o nf u n c t i o n ；b a l a n c e dv e c t o rm e a s u r e s ；e s c a p i n g - t i m ea l g o r i t h m 分形中若干问题的算法设计与理论研究 0 前言 相对于经典数学、物理学等学科来讲，分形学算是一门从正式提出到现在只有二十 多年历史的年轻学科。分形理论是描述具有无规结构的复杂系统结构形态的一门新兴边 缘科学。在过去2 0 多年中，分形理论已成功地应用于许多不同学科的研究领域，并对 一些久悬未解的难题的研究取得突破性进展。今天，分形已被认为是研究非线性复杂问 题最好的一种语言和工具，成为世人瞩目的学术热点。 分形来源于数学，分形中很多急待解决的问题，追根溯源，本质上仍回归到数学问 题的解决。因此，分形几何学面临着巨大的难题和严峻的挑战。自上八十年代以来，随 着分形的发展，分形自身的一些基本问题，诸如：维数理论与简单有效的计算算法、 m a n d e l b r o t 集的局部连通性问题、多重分形的数学理论、分形几何的形的刻画等己十分 尖锐地摆在人们的面前，这些问题已直接影响到分形的实质性的、深入的研究。所以， 这些基本问题将是分形理论研究的焦点。为此，本文重点研究了n i f s 和非线性m a r k o v i f s 的相关理论及吸引子的模拟、广义m _ j 集的分形结构、s c h d s d e r 迭代法中自由临界 点的吸引域和斥性域的结构特征。 全文共分六章。第章介绍了分形理论的发展史、分形学研究的主要内容和本书研 究的主题。第二章介绍了非线性迭代函数系统的基本理论及其在自然景观模拟中的初步 探讨。非线性迭代函数系统的出现极大地丰富了迭代函数系统理论，其使用的它使用的 非线性映射使得它几乎能够对任何形状来建模，本章通过一个简单的例子说明了其灵活 性。第三章介绍了非线性m a r k o v 迭代函数系统基本理论、矩的递归计算、平衡向量测 度、n m i f s 吸引子的计算机模拟。m a r k o v 过程在随机过程中具有重要的地位，通过与 非线性迭代函数系统结合，使得n m i f s 的表示范围和应用领域更大。第四章分析了动 力平面和参数平面上的单参数高次复多项式的s c h r 6 d e r 函数的根的求解过程中所得的 自由临界点的吸引域和斥性域的收敛情况和结构特征，主要是对参数平面上j u l i a 集和 动力平面上m a n d e l b r o t 集的结构进行了较深入的分析。第五章结合逃逸时间算法和周期 点查找算法探讨了两种不同多项式形式j u l i a 集的结构，并且讨论了不同临界点的 m a n d e l b r o t 集在复平面上的动力学特征。 分形中若干问题的算法设计与理论研究 1 分形概论 1 1 分形理论的产生与发展 就像生命不会凭空诞生，计算机科学的新分支不会突然造就产生一样，分形几何的 思想也不是凭空而出的。对于分形的起源我们可以一直追溯到十九世纪束，那时数学家 们创造了些由点的集合所构成的一些图形，这些图形在自然界中并没有相对应的事 物。具有讽刺意义的是，其后产生的原本用来描述纯理论的“抽象”数学却被发现较之 于学科，它更适合于描述这类形状和过程【l ，2 ，。 也许我们不应对此表示惊讶。古希腊的几何学家早就发现了圆锥形状的曲线之美， 而直到两千多年后，c o p e r n i c u s 、b r a h e 、k e p l e r 勒和n e w t o n 等科学家才能完整和准确 的证明所有重物体的运动曲线都是圆周形的，并且在行星、彗星和抛射物体的轨道上发 现了椭圆、抛物线和双曲线形状。 十七世纪n e w t o n 和l e i b n i z 创造了微积分学，用来求函数的微分或导数一一用几何 术语来讲，就是求曲线上任意一点上的切线。诚然，有一些函数是不连续的，它们在某 些点或区域并不可微。还有一些函数有“奇异”点，在这些点上切线变得毫无意义。但 在当时看来，这些函数是特殊的，与已经发现和正在研究的那些在对自然建模的“行为 良好的”函数相比，数量如此之少，表现如此之怪异，以至于当时并没有纳入专门的考 虑之列，而只作为“病态”的函数处理。然而，在十九世纪七十年代后，一些新的发现 使得当时数学产生了危机1 2 j 。 1 8 7 5 年，德国数学家k w e i e r e s t r a s s 构造了处处连续但处处不可微的函数，集合论 创始人g c a n t o r 构造了三分康托集，他只使用个简单的过程就把平面上的一条直线无 限细分为堆杂乱的点的集合。1 8 9 0 年，意大利数学家g p e a i l o 构造了一种平面环绕曲 线，这条曲线能充满整个平面。1 9 0 4 年，瑞典数学家h v o nk o c h 设计出类似雪花和岛 屿边缘的一类曲线。1 9 1 5 年，波兰数学家w s i e r p i n s k i 设计了像地毯和海绵一样的几何 图形。这些奇异的形状看起来介于一维直线和二维平面之间。虽然大多数人仍然把它们 看作“病态”的例子而没有在意，但是已经有一部分人开始研究这些形状的性剧2 ，。 同时，在其它领域也发现了类似的奇怪形状。十九世纪八十年代p o i n c a r e 在分析太 阳系的稳定性时发现在传统的研究方法存在动力学问题；之后，他提出了“状态空间” 的概念，在该空间中，每一个点都属于某个行星轨道，并定性研究了这些轨道的“连通 性”j 。这种方法的重要性在于它揭示了这样一个事实：虽然当时有许多创新性的成果 不断加进经典理论( 即前面所描述的不包括“病态”曲线的研究) 早面，但仍然存在大 量具有“混沌”性质的轨道，它们的动力学行为没有周期性，是不可预测的。另外，在 自然和社会学等其它领域也发现了类似的现象，海岸线的长度、分子的布朗运动、经济 领域的各种价格的上下波动、人口数目的变化等都不能用传统的数学方法来近似描述。 多年以来，这些发现表面上好像并没有什么关联，但它们内部却总有一丝相同的东 西。这正类似于抽象数学中的曲线和混沌轨道运动在不规则的时间序列中常常有自相似 2 分形中若干问题的算法设计与理沦研究 的特性：任意抽出- - 4 , 部分，放大后仍然与整体是相似的，这正是分形所具有的最重要 的特征。 尽管在二十世纪七十年代以前分形的研究取得了许多重要的结果，并使这一学科在 理论上初见雏形，但是绝大部分从事这领域工作的人主要局限于纯数学理论的研究， 而未与其它学科发生联系。另方面，物理、地质、天文学和工程学等等学科已产生了 大量与分形几何有关的问题，迫切需要新的思想与有力的工具来处理。虽然很多理论和 应用数学家推动了这些进程，但最后作为大统一者却是b e n o i tm a n d e l b r o t 。 m a n d e l b r o t 于1 9 2 4 年1 1 月2 0 日生于波兰华沙，后来迁往巴黎。虽然巴黎是经典数 学分析的摇篮，但他却更倾向于几何学，无论什么问题，他总是设法将代数与分析问题 化成几何问题，巧妙地将它们解决。在1 9 5 8 成为约克郡离地沃森研究中心( t j w a g o n r e s e a r c hc e n t e r ，i b m 的个研究基地) 物理部研究人员后，他和一群志同道合的研究人 员系统、深入、创造性地研究了海岸线的结构、具有强噪声干扰的电子通讯、月球的表 面、银河系中星体的分布、地貌的生成的几何性质等等典型的自然界中的分形现象，并 取得了一系列令人瞩目的成功。通过研究，使m a n d e l b r o t 深刻地意识到，传统数学中被 认为是“病态的”、“反常的”的“魔鬼集”，其实是大自然中具有“粗糙和自相似”形 态的事物的非常合适的数学模型。因此，m a n d e l b r o t 把具有“粗糙和自相似”特点的各 种不规则图形或函数或点集称为分形，并且找到了描述它们的数学模型【1 ”。这标志着分 形思想已经产生，说明有必要建立- - f - 以分形为研究对象的新的几何学1 4 】。 ，m a n d e l b r o t 涉猎众多学科，加上他善于把各学科联系起来，从具体的、个别问题中 发现抽象的、一般的共性，最终产生分形思想。1 9 7 5 年。m a n d e l b r o t 将前人的结果进行 总结，集其大成，以“分形：形状、机遇和维数”为名发表了他的划时代的专著。在此 专著中，第一次系统地阐述了分形几何的思想、内容、意义和方法。此专著的发表标志 分形几何作为一个独立的学科正式诞生，从而把分形理论推进到一个更为迅猛发展的阶 段m 2 , 4 1 。 自1 9 7 5 年以来，分形理论无论是在数学基础还是在应用方面都有快速发展口，“l 。由 于分形几何极强的应用性，它在物理的相变理论，材料的结构与控制，力学中的断裂与 破坏，高分子链的聚合，模式识别，自然图形的模拟，酶的生长等领域取得令人瞩目的 成功。由于应用学科和计算机制图的刺激与推动，分形的数学理论也得以迅速发展，并 且目的更明确，思想更深入。近年来，在维数的估计与算法，分形集的生成结构，分形 的随机理论，动力系统的吸引子理论与分形的局部结构已获得较深入的结果，其势方兴 未艾。在此期间，国际上分形研究方兴未艾，有关专著纷纷问世，物理、化学、数学及 生物学中的分形论文逐年增加。1 9 9 1 年英国培格曼出版社推出了混沌、孤子和分形 的国际刊物，1 9 9 3 年初新加坡世界科学出版社推出了分形关于大自然复杂几何的 交叉科学杂志：同时，国际专题会议此起彼伏，特别是在8 0 年代中期，令人感到了雷 霆万钧之势，“自然科学中的分形大自然中复杂几何学的国际学术讨论会”于1 9 9 3 年8 月3 0 日至9 月2 日在匈牙利布达佩斯召开。为此，有人曾经指出：“1 9 世纪后半期 似乎是科学与数学变得更加专门化的时期。令人瞩目的是，在近l o 年中，非线性动力 学与分形使上述趋势得以逆转：两者均已被应用到对一系列深层次的交叉学科的研究 中”。在国内，分形研究起步较晚，但进展较快。1 9 8 9 年7 月在成都市四川大学召开了 “第一届全国分形理论及应用学术讨论会”，1 9 9 1 年1 1 月在武汉华中理工大学召开了第 分形中若二f 问题的算法设计与理沦研究 二届会议，第三届会议于1 9 9 3 年1 0 月在合肥中国科学技术大学召开。拟定每两年召开 一次。 今天，分形理论已经与计算机科学理论等领域相结合，这种结合使人们对久悬未解 的基本难题的研究取得突破性进展，在探索、描述及研究客观世界的复杂性方面发挥了 巨大作用【1 7 2 0 , “j 。其作用涉及到几乎整个自然科学和社会科学。混沌分形已被认为是 研究非线性复杂问题最好的一种语言和工具。并受到各国政府及学者的重视和公认，成 为举世瞩目的学术热点。1 9 9 8 年研究几何与混沌的麦克马伦获菲尔兹奖，再一次说明 了研究混沌分形理论在科学研究中的地位。我国“国家攀登计划”中有关非线性科学、 纳米材料科学、生命科学等项目中，就列举了有关混沌分形理论的五个专题。“国家自 然科学基金”中也列出混沌分形理论及其应用的内容，并指出这是一项具有跨学科前沿 交叉性特点的基础性和应用基础性的研究，具有广阔的应用前景。我国“国家攀登计划” 中有关非线性科学、纳米材料科学、生命科学等项目中，就列举了有关混沌分形理论的 五个专题。“国家自然科学基金”中也列出混沌分形理论及其应用的内容( a 0 1 0 1 0 7 0 5 ， a 0 1 0 2 0 4 0 5 ) ，并指出这是一项具有跨学科前沿交叉性特点的基础性和应用基础性的研 究，具有广阔的应用前景。 分形是人们在自然界和社会实践活动中所遇到的不规则事物的一种数学抽象。人们 对于分形的兴趣是由于可以用它来描述和解决一些实际问题。正如历史上人们对于欧氏 几何与微积分的应用样，这种描述和应用允许在一定尺度下的近似性。同样，在利用 分形来描述海岸线、云层的边界、地表的形状、岩石的裂缝、流体的湍流以及一些经济 现象时，也具有一定意义下近似性。实际上，现实世界中没有真正的分形，正如 m a n d e l b r o t l 4 1 所强调的那样自然界的分形与我们数学中讨论的分形是有区别的。 分形理论的发展是迅猛的，分形的思想和方法e 同益影响着现代社会的生活和活 动，随着分形的广泛应用，一些新的数学方法和数学工具被不断提出，所有这些都显示 了分形理论的强大生命力和迅猛发展势头。 1 2 分形的定义 分形理论是非线性科学研究中十分活跃的一个分支，它的研究对象是自然界和非线 性系统中出现的不光滑和不规则的几何形体。遗憾的是，目前对分形还没有严格的数学 定义，只能给出描述性的定义。英国数学家f a l c o n e r 认为，分形的定义应该以生物学家 给出“生命”定义的类似方法给出，即不寻求分形的确切简明的定义，而是寻求分形的 特性【20 1 。一般地，称集f 是分形，即认为它具有下述典型的性质： ( 1 ) f 具有精细的结构，即有任意小比例的细节。 ( 2 ) f 是不规则的，以至于不能用传统的几何语言来描述。 ( 3 ) f 通常有菜种自相似的形式，可能是近似的或统计的。 ( 4 1f 在某种方式下定义的“分形维数”通常大于它的拓扑维数。 ( 5 ) 在大多数令人感兴趣的情况下，f 可以以非常简单的方式来定义，可能由迭代 产牛。 分形中若干问题的算法设计与理论研究 1 3 分形学的主要应用领域 分形几何的应用研究比理论研究更为引人注目，很难再有另外一门学科能在这么短 的时间内渗透到如此多的学科中并产生重要的影响。 一般来说，分形学的主要研究和应用领域包含以下几个方面： 1 。在图像、数据压缩方面的研究 分形理论在图像、数据压缩技术中发挥了重要作用。c o l l a g e ( 1 9 8 8 ) ，b a m s l e y ( 1 9 9 3 ) 等应用迭代函数系统编码在分形信息压缩方面做了有益的尝试。8 0 年代末，美国数学家 b a m s l e y 提出了一种利用图像本身的复杂性中包含的自相似性进行压缩编码的新方法。 b a r n s l e y 和s l o a n 在一篇文章中令人惊讶地宣称，利用他们的方法对静止图像压缩可获 得高达1 0 ，0 0 0 ：1 的压缩比。这当然在从事图像压缩的人群中引起了极大的震动。 分形图像压缩编码方法适用于二值图和灰度( 彩色) 图像，其理论基础是迭代函数系 理论。从目前的实际情况来看，分形图像压缩的效果远非像b a r n s l e y 等人所宣称的那样 令人满意。事实上，在分形图像压缩的理论研究方面还存在着不少问题，但作为一种新 的图像编码框架，其前景仍是十分光明的。 2 。分形在复杂性刻画方面的应用 二分形几何作为非线性科学的一个重要分支，从一开始就与刻画非线性复杂性紧密相 连；近年来，多标度分形、随机分形的研究方兴未艾。国内外学者在利用分形模型进行 复杂性刻画方面的成功例子比t e 皆是，在此不再赘述。 。3 。分形在计算机图形学中的应用 作为“t h e f r a c t a l g e o m e t r y o f n a t u r e ，分形几何在描述自然界的真实特征和细节纹 理方面具有特殊的作用。因此，分形技术是计算机真实感几何造型方面十分活跃并且有 效的方法和手段。而计算机的应用也大大地推动了分形理论的发展，并形成了一种新的 研究领域：计算机实验数学。h e i n z o t t o p e i t g e n ( 1 9 8 8 ) ，j o e p r i t c h a r d ( 1 9 9 2 ) ，p h i l l a p l a n t e ( 1 9 9 3 ) 等在计算机模拟分形方面做了大量工作，形成一系列有效算法：d e a n g e l i s ( 1 9 9 3 ) 将其应用到生命科学中：我国许多学者也做出了不少有益的工作。目前，国外已经推出 多种不同的以分形技术为特征的计算机绘图软件，而且，在许多产品设计中也用到了分 形的思想和方法。混沌分形理论在信息压缩、传送及自然景观的模拟中发挥了重要作用。 4 。分形生长模型 分形方法提供了一种描述自然界各种生长现象的新的模型。著名的d l a 模型和l 一 系统模型在模拟无机生长现象和植物生长形态描述方面取得了令人鼓舞的成功，各种新 的模型和方法也正在不断发展之中。 5 。分形在社会科学中的应用 近年来，分形在社会科学中的研究也已经取得了很大的发展。分形作为一种工具和 其它非线性方法一道被用来刻画社会、经济领域中的各种复杂性现象，取得了一系列新 的进展。“分形认识论”和“分形方法论”的正在逐步形成自己的哲学体系。 分形中若二f 问题的算法设计与理论研究 1 4 分形学的哲学意义 近半个世纪以来，理论自然科学发展的一个重要特点是研究各种非线性问题。这正 如中国科学院院士、物理学家郝柏林教授在混沌现象的研究一文中所指出的那样： “从数理科学基础研究的角度看，近二三十年来的一个重要发展特征，可以概括为非 字当头：非线性、非平衡、非晶态如此等等，不一而足。”科学家对非线性问题的 共性的研究已经形成一门新兴的交叉学科一一非线性科学，它主要包括混沌、分形和孤 子三大普适类。非线性科学已经阐明，世界本质上是非线性的；就分形学而言，其哲学 内涵也是很丰富的。 1 4 1 分形中的辩证法 分形中充满着辩证法思想，它不仅为辩证法提供了新的事例，而且可以丰富人们对 辩证法的认识。 。 l 。简单与复杂 辩证唯物主义告诉我们，客观事物既是复杂的又是简单的，是复杂与简单的统一体。 科学研究的目的就是要透过事物的复杂关系中，抽取出反映事物的简单关系，然后才研 究这些简单关系的性质、变化规律。分形几何中的迭代函数系统方法为我们提供认识简 单与复杂的辩证关系的生动例子。在i f s 方法中，如何把复杂的分形图变成简单的i f s 代码的过程就是一个复杂到简单的过程，这个过程是通过一组相似子图来覆盖原图，然 后用一组仿射压缩变换来描述这些相似子图。并求出每一个仿射变换的伴随概率，这样， 就把复杂的分形图编成一组简单的i f s 码。另一方面，如何由简单i f s 码再现复杂的分 形图则是上述过程的逆过程，即是一个简单到复杂的过程。可见，分形几何中确实存在 这复杂与简单的辩证法。 2 。整体与局部 分形学的出现，打破了整体与部分之间的隔膜，找到了部分过渡到整体的媒介和桥 梁即整体与部分之间的相似，使人们对整体与部分的关系的思维方法由线性进展到非线 性的阶段，从一个新的层面深化和丰富了整体与部分之间的辨证关系。在整体与局部的 关系上，分形几何已经揭示出一个重要特点：自相似，即取分形上任意- - d 部分加以放 大，就可以发现部分与整体是相似的。因为这种相似是与整体滋生相似的，所以称为自 相似。这种“放大”可以用缩小观察尺度，也可以用数学方法对需要放大的“部分”重 新计算，以显示自相似性。这种自相似可以是严格的或有规的，也可以是近似的或统计 的。因此，自相似性为我们理解部分与整体的辩证关系提供了新的科学依据。迭代函数 系统的基本思想也是利用分形具有局部与整体的内在自相似特点而产生的一种简单有 效的方法。 另外，分形几何中还存在着确定性与随机性、必然性与偶然性、有序与无序等辩证 关系，进一步丰富和深化了唯物辩证法关于普遍联系和世界统一性原理，这主要表现在 两个方向：一是分形论从一个特定层面直接揭示了宇宙的统一图景，同时，分形论所揭 示的整体与部分的内在联系方式，是对宇宙普遍联系与内在统一的具体机制的一种揭 分形中若干问题的算法设计与理论研究 示。恩格斯曾经把存在于自然、社会和思维中的普遍联系称之为“一幅由种种联系和相 互作用无穷无尽地交织起来的画面。”这种联系的普遍机制应包括分形论。二是关于世 界物质统一性，分形论可以从共时态与历史性两个维度上展开说明：一方面在自然界中 蕴涵着历史的演化与嬗变的信息另方面部分与分形整体之间普遍的相似性编织了一 张世界统一的网络。 1 4 2 分形几何的方法论意义 作为非线性科学三大理论前沿之一的分形理论，为人们从部分中认知整体，从有限 中认知无限提供了可能的根据。它在研究复杂系统的空间结构性质的过程中，创造出一 种研究复杂系统的简单方法一一迭代法。它是从复杂系统( 它的几何形态表现为复杂图 形) 中提取少量的数据信息，建立数学模型，然后通过计算机进行迭代简单的重复操作 过程( 迭代过程) ，再现复杂图形。这样人们就可以通过研究简单的数学模型及其迭 代过程，达到研究复杂事物( 图形) 的目的。美国佐治亚工学院的数学教授m e b a r n s l e y 于1 9 8 5 年提出了迭代函数系统( i t e r a t e df u n c t i o ns y s t e m i f s ) ，这一方法将迭代法的 普遍意义和应用前景推向了顶峰。i f s 的理论将在第二章详细介绍。对于任何分形图， 只要知道了其i f s 码，我们就可以使用i f s 的绘制算法绘制出其分形图；相反，给定一 个分形图，我们可以利用目标图像和仿射压缩变换都具有自相似特点，采用拼贴法确定 i f s 代码中的压缩变换，从而得到其i f s 码。基于还原法的简化事物的传统方法无法描 述不规则但具有自相似的点集，而出现的一种新的简化复杂事物形态的有效方法。在i f s 方法实际应用于描述和生成分形图像的过程中，无论是i f s 代码的确定，还是由i f s 代 码生成分形图像，都离不开计算机。因此，我们可以说，没有计算机就不可能产生i f s 方法。从这个意义上说，计算机在分形几何中的应用变革了科学研究方法，产生新的简 化事物的新方法。所以，分形理论的出现具有重要的方法论意义。 分形学的产生和发展不仅大大丰富了唯物主义和辩证法的内容，而且对整个自然科 学和哲学体系也带来了巨大的冲击，它可能成为产生变革的持久动力，无疑将在人类探 索自然的实践中起着开阔眼界、解放思想的作用【4 7 1 。 1 5 本文研究的主要内容 分形来源于数学，分形中很多急待解决的问题，追根朔源，本质上仍回归到数学问 题的解决。因此，分形几何学面临着巨大的难题和严峻的挑战。自八十年代以来，随着 分形的发展，分形自身的一些基本问题，诸如：维数理论与简单有效的计算算法、 m a n d e l b r o t 集的局部连通性问题、多重分形的数学理论、分形几何的形的刻画等已十分 尖锐地摆在人们的面前，这些问题己直接影响到分形的实质性的、深入的研究。所以， 这些基本问题将是分形理论研究的焦点。 为此，本文选取了n i f s 吸引子的研究、广义m j 集的分形结构、s c h r 6 d e r 函数的 求根等若干问题为突破口，进行了以下较为深入研究： ( 1 ) 数学上最早用压缩映射族即i f s ( i t e r a t e d f u n c t i o ns y s t e m ，简称i f s ) 来构造和研 分形中若干问题的算法设计与理论研究 究分形集的是h u t c h i n s o n l l l ，其完整理论是b a r n s l e y 2 ，3 i 等人建立的。到目前为止，用一 个数学系统去解析地构造、研究具有“自记忆”、“全息”( 比例自相似性) 结构的分形， 最为成功的就是i f s 的分形吸引子，它既包含了确定性的过程又包含随机的过程。遗憾 的是，非线性迭代函数系统一直欠缺深入的研究。众周所知，从线性过渡到非线性，不 仅仅是复杂度的增加，更重要的是待研究事物的本质也发生了质的变化：由线性i f s 过 渡到非线性i f s ，不仅要重建理论，而且研究工具和指导思想也要随之变化。本文中， 作者在前人的基础上p 0 1 给出一些探索性的研究，对n i f s 做出了一些有意义的工作。 ( 2 1 自从d e k k i n g t 列提出了m a r k o vi f s 后，b a m s l e y 、e l t o n 、g f i g o r e s c u 、v r s c a y 、 l a s o t a 和s t e n f l o 等人在这方面做了大量的工作 8 1 3 j ：其中讨论得最多的是平衡向量测度、 矩、h a u s d o r f f - b e s i c o v i t c h 维数、遍历理论、动力系统等，但他们的讨论也仅局限于线 性i f s 。为此，本文将d e k k i n g 、b a m s l e y 等人的工作进行了推广，讨论了一类n m i f s 吸引子的平衡向量测度和矩的递归计算，分析了n m i f s 吸引子的结构特征。 ( 3 ) 迭代法在数学上是求方程的根的一种传统的方法，e r n s ts c h r 6 d e r 在1 8 7 0 年和 1 8 7 1 年最早使用迭代法对复动力系统进行了研究。尽管即使是牛顿法的最简单的形式也 可以用来研究复动力系统，但s c h r 6 d e r 是最先研究单参数的正则多项式方程的复根p i 3 6 1 。对于多项式方程来说，它要求对有理函数在复r i e m a n n 球上进行迭代( j u l i a 和f a t o u 的经典理论对复r i e m a n n 球进行了详尽的描述【3 2 ，3 4 1 ) 。s c h r o d e r 迭代函数方法可以用来 求方程的根，传统的n e w t o n 求根法是它的一种特殊形式。然而，对于s c h r o d e r 迭代函 数方法所得自由临界点的吸引域的和斥性域的结构特征仍然知之甚少。在本文中，我们 推广了前人的工作，对于一类单参数高次多项式的s c h r 6 d e r 函数迭代法研究j u l i a 集的 问题给出了比较完善的讨论。 f 4 ) 自从m a n d e l b r o t 利用计算机构造并研究了复映射f ：z _ z 2 + c 的动力z 平面上 的j 集和参数c 平面上的m 集【4 】以来，人们对m ，j 集的结构和生成机理进行了较深入 的研究。根据j u l i a 和f a t o u 的理论：映射l ( z ) = z 2 + c 的临界点的轨道决定了，的动力 学行为【训，而，只有唯一临界点z 。= 0 。这样基于z 。的轨道，采用逃逸时间算法，即可 构造出m 集；而在m 集上选取不同的c 值，还可做出结构各异的j 集i j j 。那么对于多 临界点的映射，如何构造其对应的m - j 集昵? 本文在前人的基础上，结合逃逸时间算法 和周期点查找算法探讨了两种不同多项式形式j u l i a 集的结构，并且讨论了不同i 临界点 的m a n d e l b r o t 集在复平面上的动力学特征。 分形中若干问题的算法设计与理论研究 2 非线性迭代函数系统的建模与表示 m a n d e l b r o t 于上世纪7 0 年代所创立的分形几何，为科学地研究具有随机形态特征 及无穷细节的自然现象，提供了一种全新的数学工具 1 - 4 1 。分形几何的基本特征是自相 似性，即局部结构与整体结构相似的特征。这种相似性，形成分形体的层次结构，各个 层次之间以一定的标度因子相联系，即其有标度不变性。因而，分形集应与所谓相似变 换相关。另一方面，层次结构实际上反映了一种递归性质。所以，可以通过相似变换的 递归迭代过程产生分形结构。这类分形称为i f s 的分形吸引子。目前，国内外对( 线性) i f s 讨论得比较多【i ”，h s u e h t i n gc h u 2 5 1 等研究过三维i f s 吸引子的界；t o m e k m a r t y n 等【2 6 - 3 0 1 对i f s 的层次结构和测度等问题进行了深入讨论。而非线性迭代函数系统的讨论 相对少一些1 2 。正因为如此，本论文主要基于非线性i f s 迭代函数系统的基本理论，在 前期工作1 1 训的基础上对如何使用n i f s 来生成逼真的自然景物图形进行了较深入的探讨 和研究。 2 1n i f s 基本理论及绘制n i f s 吸引子的两种算法 h u t c h i n s o n 【i j ，b a r n s l e y 【2 3 1 ，m a n d e l b r o t 4 1 等在他们的著作中深刻阐述了了i f s 完整理 论。通常，在i f s 中，我们所讨论的映射是以仿射变换为基础的，在应用映射w 时，任 何集合都收敛于此吸引子。使用仿射变换是由一些原因的：仿射函数很容易处理，也很 容易理解，并且可以通过矩阵和向量变换来精炼的表达。仿射变换描述了线性变换，如 直线间的相互映射，并且通过对诸如矩阵或三角形之类的简单图形利用函数 w ，：r2 寸r2 可以直观地感知其变换效果。 ( a ) c = 一0 8 + 0 2 i( b ) c = 一0 6 + o 2 j 图21 非线性迭代函数系统i f s 尺2 ：w l ，w 2 ，w l = + ；= i ，w 2 = 一；= i f i g 2 1n 1 f s r2 ：w 1w 2 ) ，w i = + 五二，w 2 = 一厄i 在i f s 的描述中使用非线性函数极大地增加了可建模图型的数量：实际上，有一组 众所周知的图形，它们的集合是非线性i f s c ；w l ，w ：) 的吸引子，这里w ，和w 2 是复平面c 上的两个函数，这个非线性i f s 吸引子就是所谓的j u l i a 集( 见图2 1 ) ，它使用复映射 分形中若干问题的算法设计与理论研究 f ( z ) = z 2 + c ，通过迭代在动力z 平面上生成f 4 , 2 3 1 。因该映射有两个反函数w 1 ( ”) = 、，再i 和w ：( “) = 一万i ，故我们也可把 c ：w 1w ：) 看成一个n f f s ，然后采用随机迭代算法， 即可绘制j u l i a 集( 如图2 1 所示) 。 2 1 1n i f s 基本理论 如果( x ，肋是度量空间，则( f ( x ) ，h 。) 表示相应的带有h a u s d o r f r 距离的非空紧子集 空间。 定义2 1 7 1 一个双曲n i f s 由一族( x ，p ) 上的有限个压缩映射 w i ，n = 1 , 2 ，n 组 成，并对每个w ，：x 斗，都有 i ( j ) 一、( y ) l ，i x - - y l ，v x ，y x 这里o c 。 0 ，其中只= 1 。取x j t l 并且依照递归方式独立地取 一 w ，( t 一。) ，w 2 ( x 。) ，一，w , v ( x 。) ) ，i = 1 ，2 ，。 分形中若干问题的算法设计与理论研究 其中事件x ，= w i ( x i 一。) 的概率是a 。选取充分大的整数n 。、，则序列“，f 。 收敛于 n i f s 的吸引子4 。但利用计算机绘制吸引子a 的图像，当迭代次数n 达到一定值时， 由于计算机屏幕的图像分辨率限制，再增加迭代次数并不能明显改变图像效果。那么此 时所得的分形集e 与n i f s 吸引子a 的差别是多少? 下面的拼贴定理对这个问题给出了 h a u s d o r f f 测度意义下的估计。 定理2 - 2 【7 】设( x ，p ) 是完备度量空间，( x ，( w 0 ) ，k ) 是压缩比为c 的n i f s ， 它的不动点( 不变集) 是a ，则 厂 n 、 ，( e ，a ) ( 1 c ) h ，le ，u w 。( e ) jf ( ) ，j = i l ”0 拼贴定理保证了在计算机屏幕上，来自于迭代n 次后的分形集e 就是这个n i f s 的 吸引子爿的一种逼近。这两个集合之间的h a u s d o r f f 距离，可以用集合e 与集合e 的像 之间的h a u s d o r f f 距离来估计。因此，拼贴定理提供了构造n i f s 吸引子的计算机逼近理 论依据。 2 。1 3 确定性算法 绘制n i f s 吸引子的第二种方法是基于下面的事实所得到的一个立即值，即：在函数 的迭代下，每一对象4 将接近于i f s 的吸引子，因此，确定性算法使用如下近似吸引子： a 。w ”“( 爿) 这里，i q m