JULIAMANDELBROT分形图形逃逸时间算法的并行实现论文

1、julia/mandelbrot分形图形逃逸时间算法的并行实现 燕山大学本科生毕业设计(论文)摘 要利用并行计算来提高计算能力已经成为解决大数据量计算问题的切实可行的技术。通过对分形图形中最为经典的julia分形集和mandelbrot分形集的串并行算法转化，提高了分形集的生成速度。首先，对实验的开发环境及工具进行了简单地介绍；其次，介绍了julia / mandelbrot分形集的逃逸时间算法。再次，分析该算法的并行性，得出数据分解方案和该算法的并行实现方案，然后讨论了如何计算该并行程序的执行时间及如何将分形图像数据写进位图文件的方法，在并行设计的最后阶段，简要介绍了图形界面的开发。最后，在

2、集群环境下，编译、运行该并行程序。通过记录并行程序的执行时间和cpu个数，计算并行程序的加速比，看到了并行计算的优越性。实验验证了并行程序和串行程序在相同的输入情况下，执行结果是相同的，但并行程序每次的执行时间是不完全相同的，以及随着cpu个数的增加，并行计算加速比的增长幅度在不断减缓。该实验较好地达到了预定的目标。关键词并行计算；julia分形集和mandelbrot分形集；逃逸时间算法abstractusing parallel computing to solve problems with great data quantity which greatly improves the c

3、apability of computing has become a practical and feasible technology. transforming the most classical julia fractal set and mandelbrot fractal set from sequential to parallel improves the speed of its generating.the article first gives a general description to the experiment s development environme

4、nt as well as development tool ;then introducing the escape time algorithm of the julia and mandelbrot set .in the following, it analyzes the parallelism of this algorithm ,obtains the data decomposition and realizes the parallel algorithm .next ,it discusses how to calculate the execution time of t

5、his parallel program and how to write the fractal image data into a bmp format file .in the last stage of this design, it briefly introduces the development of the graphical interface. finally, under the environment of the cluster, it compiles, executes the program. by recording the programs executi

6、on time and the number of the cpu, it calculates the speed up and shows the superiority of parallel computing.the experiment proves that under the same input, the sequential and parallel program has the same result, but the execution time is not exactly the same every time, and with cpu number incre

7、asing, the speed up grows slowly.the experiment achieves the anticipative goal.keywordsparallel computing; julia fractal set and mandelbrot fractal set; escape time algorithm43目 录摘 要iabstracti第1章 绪论11.1 课题背景11.2 选题意义11.3 研究内容和内容安排1第2章 开发环境及工具简介12.1 集群环境简介12.2 linux简介12.3 mpi简介12.3.1 mpi的特点12.3.2 mpi

8、的优点12.3.3 mpi的框架结构12.3.4 mpi的子集12.3.5 mpi的初始化和结束12.3.6 mpi的消息传递函数12.4 gtk+简介12.5 本章小结1第3章 julia/mandelbrot分形算法13.1 分形简介13.1.1 分形几何学的创立13.1.2 分维的概念13.1.3 分形一词的由来13.1.4 分形的定义13.1.5 研究分形的意义13.2 分形类型13.2.1 julia集13.2.2 mandelbrot集13.2.3 mandelbrot集和julia集的关系13.3 逃逸时间算法13.3.1 基本思想13.3.2 算法描述13.4 julia集的逃

9、逸时间算法13.4.1 算法描述13.4.2 伪码表示13.5 mandelbrot集的逃逸时间算法13.5.1 算法描述13.5.2 伪码表示13.6 算法流程图13.7 本章小节1第4章 并行算法的设计与实现14.1 并行程序设计基础知识14.1.1 并行算法的定义与分类14.1.2 并行程序的性能评价14.2 并行算法设计14.2.1 并行性的来源14.2.2 数据分解方法14.3 并行算法实现14.3.1 开发并行算法14.3.2 并行算法流程图14.3.3 并行程序的执行时间14.4 将图像数据写入位图14.4.1 位图结构14.4.2 算法流程图14.5 图形界面的设计与实现14.

10、6 本章小节1第5章 实验结果及其分析15.1 编译15.2 运行15.3 实验分析15.4 实验结论15.5 程序开发过程中遇到的困难和存在的问题15.6 本章小节1结 论1参考文献1致 谢1附录1 开题报告i附录2 文献综述i附录3 文献翻译i燕山大学本科生毕业设计（论文）第1章 绪论1.1 课题背景第一台计算机问世已经半个世纪了，在这期间计算机技术经历了五次更新换代。更新换代的标志主要有两个：一个是计算机的器件，另一个是系统体系结构。从第一代到第五代计算机，器件发生了根本的变化：从电子管、晶体管发展到集成电路，而集成电路又经小规模、中规模、大规模、非常大规模等阶段发展到超大规模阶段。系统

11、体系结构的不断改进，许多重要的概念的不断提出并且得到实现，推动计算机技术向更高的层次发展。从早期的变址寄存器、通用寄存器、程序中断和i/o通道等概念，到虚拟存储器、cache存储器、微程序设计、系列机、基于总线的多cpu系统、向量处理机等概念，发展到64位risc处理器、基于mpp、numa、集群等体系结构的可伸缩并行处理系统，计算机系统技术也取得了突飞猛进的发展1。将多台同构或异构的计算机连接起来协同完成特定的任务就构成了集群系统。集群系统主要分为高可用性集群和高性能集群。高可用性集群的主要功能就是提供不间断的服务。有许多应用程序都必须一天二十四小时地不停运转，如所有的web服务器、工业控制

12、器、atm、远程通讯转接器、医学与军事监测仪以及股票处理机等。对这些应用程序而言，暂时的停机都会导致数据的丢失和灾难性的后果。 高性能集群通过将多台机器连接起来同时处理复杂的计算问题。模拟星球附近的磁场、预测龙卷风的出现、定位石油资源的储藏地等情况都需要对大量的数据进行处理。传统的处理方法是使用超级计算机来完成计算工作，但是超级计算机的价格比较昂贵，而且可用性和可扩展性不够强，因此集群成为了高性能计算领域瞩目的焦点。图1-1给出了了从20世纪60年至今高性能计算系统的发展趋势。从图1-1可以看出高性能计算系统的发展趋势是向集群发展，这是由于集群式超级计算机有以下基本特点：(1) 价格相对低廉，

13、易于推广。系统可以由高性能的微机和服务器实现，而不是昂贵的专用硬件，能充分利用已有的硬件资源。(2) 具备高容错能力和可靠性。对某个服务节点出现故障时，系统会在软件的支持下，将这个节点从系统中隔离出去，通过各节点之间的负载转嫁机制，完成新的负载分担，在系统执行过程中支持断点续作。(3) 较高的系统计算能力和较大的存储空间。系统具备负载共享能力，充分利用每个节点的性能，并根据一定的策略分配到各个服务节点上并行处理从而迅速提高性能，达到超级计算机的能力。(4) 较好的动态扩展性。由于采用分布结构，群集系统可扩展性很强，可以通过增加节点数量来适应更高的性能要求，并可以保证在不中断服务的情况下进行动态

14、扩展。(5) 较好的软件平台。在软件平台上，可选择客户优化开放源代码的操作系统，允许透明的集成定制的应用程序，并支持大部分的编程语言2。图1-1 高性能计算系统的发展趋势图九十年代末期，linux操作系统不断走向成熟，它的健壮性不断增强，并且提供了gnu软件和标准化的pvm、mpi消息传递机制，最重要的是linux在普通pc机上提供了对高性能网络的支持，这样就大大推动了基于linux的集群系统的发展。mpi是目前最重要的并行编程工具，它具有移植性好、功能强大、效率高等多种优点，而且有多种不同的免费、高效、实用的实现版本，几乎所有的并行计算机厂商都提供对它的支持，这是其它的并行编程环境所无法比拟

15、的。1.2 选题意义大型科学与工程问题要利用高性能的并行机来进行计算，并行程序设计的好坏直接影响并行机性能的发挥。通常并行程序只能发挥并行峰值性能的10左右。很多并行程序是根据串行程序直接修改而成的，程序并行性还没有充分开发出来。这就对并行算法的设计提出了新的要求。本课题作为河北省高等教育改革项目的一部分，旨在加深对并行计算的理解。为了充分开发程序的并行性，使并行计算效果更加显著，需要把现存的经典串行算法转化为并行算法。在所有经典的串行算法中，julia / mandelbrot分形算法有着广泛的应用。本文对分形图形中最为经典的julia分形集和mandelbrot分形集的串并行算法转化进行了

16、研究，并在集群环境下实现了该并行算法。1.3 研究内容和内容安排主要研究内容：(1) 通过对逃逸时间算法的研究，给出julia分形集和mandelbrot分形集逃逸时间算法的实现方案。(2) 通过分析逃逸时间算法的并行性，得出数据分解方案。基于该分解方案，提出并行算法的设计流程图，用mpi实现该并行算法。(3) 通过分析位图文件的格式，将分形图像数据写入位图。为方便参数传递，降低复杂度，用gtk+设计了图形用户界面。(4) 记录实验数据，计算并行加速比，进行性能分析。内容安排：第1章 主要介绍了课题的研究背景和选题意义。第2章 介绍了本课题所使用的开发环境及工具。其主要内容包括：集群环境简介；

17、linux简介；mpi简介；gtk+简介。第3章 详细讲解了julia分形集和mandelbrot分形集的分形算法。首先介绍了分形基本知识，其次介绍了逃逸时间算法，最后实现了julia分形集和mandelbrot分形集的逃逸时间算法。第4章 主要讲解了并行算法的设计与实现。首先介绍了并行程序设计的基础知识，其次对julia/mandelbrot分形集逃逸时间算法的串并行算法转化做了详细的讲解，然后介绍了将图像数据写入位图文件的方法，最后简单介绍了该程序的图形用户界面。第5章 实验结果及其分析。计算并行加速比，得出实验结论；分析实验过程中遇到的困难和存在的问题。第6章 结论。第2章 开发环境及工

18、具简介2.1 集群环境简介燕山大学信息学院计算机系并行与分布式处理研究室的集群系统是与清华大学合作构建的。整个集群系统由9个节点构成：其中8个计算节点是一个由2路piv xeon 2.4ghz处理器构成的smp结构的工作站，每个节点内存1gb，scsi硬盘36gb；1个存储结点是由piv xeon 3.6ghz处理器构成，专门负责连接一个由8块200g的硬盘构成的磁盘阵列(1.6t)；每个结点的网卡是由两块100/1000m自适应的网卡组成；此外还有两个千兆以太网交换机，其浮点计算速度840亿次/秒。采用smp架构的集群系统，既能够充分利用每个计算节点的资源，同时利用集群系统的可扩展性，大大加

19、快了并行任务的计算速度。系统的软件配置如下：各个计算节点的操作系统采用了redhat linux 9.0，并行运算环境为mpich，采用cm集群管理系统。我们通过对系统软件进行机优化，将整个集群的运算效率提高到了系统峰值计算能力的32%，目前在省内处于领先水平。在我院并行分布式系统研究室利用到的集群环境是由16个cpu组成的，它们内部是以千兆位以太网互联起来的，外部同我们平常的网络连接是一样的。2.2 linux简介linux诞生于1991年底，是一个芬兰大学生开发出来的。它是一种适用于pc机的计算机操作系统，是目前唯一免费的非商品化操作系统。由于具有结构清晰，功能强大等特点，它很快成为许多院

20、校学生和科研机构的研究人员学习的对象。由于它是基于pc机上运行的操作系统，并且内核源代码是公开的，使得linux成为时下最流行的操作系统。linux具有如下主要优异性能：(1) 真正的多用户、多任务、多平台操作系统。(2) 提供具有内置安全措施的分层的文件系统，支持多达32种文件系统。(3) 提供shell命令解释程序和编程语言。(4) 提供强大的管理功能。(5) 具有内核的编程接口。(6) 具有图形用户接口。(7) 具有大量有用的使用程序和通信、联网工具。(8) 具有面向屏幕的编辑软件。(9) 许多组成部分的源代码是开放的，任何人都能修改和重新发布它。(10) 不仅可以运行许多自由发布的应用

21、软件，还可以以运行许多商业化的应用软件3。2.3 mpi简介mpi是一个消息传递函数库的标准说明，它统一了以前那些互不兼容的用户界面，保证了系统的可移植性和操作的简易性。所谓消息传递接口是指在分布式存储结构环境下建立的基于底层通信原语所定义的高层函数和抽象描述。正是由于这些系统的开放性和再开发性，加之pc集群的廉价、方便和高可用性等特点，使得以前许多受到经济上的限制而无法开展的课题，现在也都能开展起来。2.3.1 mpi的特点(1) mpi是一个库，而不是一门语言。(2) mpi是一种标准或规范的代表，而并不特指某一个对它的具体实现；迄今为止，所有的并行计算机制造商都提供对mpi的支持，可以在

22、网上免费得到mpi在不同并行计算机上的实现，一个正确的mpi程序，可以不加修改地在所有的并行机上运行。(3) mpi是一种消息传递编程模型，并成为这种编程模型的代表和事实上的标准。mpi虽然很庞大，但是它的最终目的是服务于进程间的通信。2.3.2 mpi的优点mpi吸取了众多消息传递系统的优点，是目前国际上最流行的并行编程环境之一。它具有如下优点：(1) 有可移植性和易用性。(2) 有完备的异步通信功能。(3) 有多种不同的免费、高效、实用的实现版本。(4) 有正式和详细的精确定义，因而为软件产业的增长提供了必要的条件4。2.3.3 mpi的框架结构掌握mpi的框架结构对进一步理解消息传递接口

23、mpi提供的通信方法有很大的帮助。而mpi又是一个复杂的系统，通常情况下，可以只使用其中的6个最基本的函数就能编写一个完整的mpi程序去求解很多问题。而这6个最基本的函数就是通常所说的mpi子集，也是掌握mpi提供的通信方法的基础，为此，需要首先介绍消息传递接口mpi的框架结构，如图2-1所示。图2-1 mpi程序的框架结构图2.3.4 mpi的子集mpi系统包含了129个函数(根据1994年发布的mpi标准)。事实上，1997年修订的标准，称之为mpi-2，已超过200，目前最常用的也有约30个。通常所说的mpi子集所包含的6个基本函数是：启动和结束计算，识别进程以及发送与接受消息。mpi_

24、init：启动mpi计算；mpi_finalize：结束mpi计算；mpi_comm_size： 确定进程数；mpi_comm_rank：确定自己的进程标识符；mpi_send：发送一条消息；mpi_recv：接收一条消息。下面给出c语言的格式调用描述：(1) mpi初始化函数 mpi_init(int *argc, char *argv)：第一个mpi函数调用，初始化mpi编程环境，只能被调用一次。(2) mpi结束函数 mpi_finalize()：最后一个mpi函数调用，使程序退出mpi编程环境。(3) 获取当前进程标识 mpi_comm_rank(mpi_comm comm., int

25、 *rank)：这一调用返回调用进程在给定的通信域中的进程标识号，有了这一标识号，不同的进程就可以将自己和其它的进程区别开来，实现各个进程之间的并行和协作。(4) 通信域中所包含的进程数 mpi_comm_size(mpi_comm comm., int *size)：这一调用返回给定的通信域中所包括的进程的个数，不同的进程通过这一调用得知在给定的通信域中一共有多少个进程在并行执行。(5) 消息发送 mpi_send(void *buf, int count, mpi_datatype datatype, int dest, int tag, mpi_comm comm)：该调用将发送缓冲区中

26、的count个datatype数据类型的数据发送到目的进程，目的进程在通信域中的标识号是dest，本次发送的消息标志是tag，使用这一标志，就可以把本次发送的消息和本进程向同一目的进程发送的其他消息区别开来。(6) 消息接收 mpi_recv(void *buf, int count, mpi_datatype datatype, int source, int tag, mpi_comm comm., mpi_status *status)：该调用从指定的进程source接收消息，并且该消息的数据类型和消息标识号和本接收进程指定的datatype和tag相一致，接收到的消息所包含的数据源的个

27、数最多不能超过count。注意：返回状态变量status的用途很广，它是mpi定义的一个数据类型，使用之前需要用户为他分配空间。在c语言的实现中，状态变量至少是由三个域组成的结构类型，这三个域分别是：mpi_source、mpi_tag和mpi_error。它还可以包括其它的附加域。这样通过对status.mpi_source、status.mpi_tag和status.mpi_error的引用，就可以得到返回状态中所包含的发送数据进程的标识、发送数据使用的tag标识和本接收操作返回的错误代码5。2.3.5 mpi的初始化和结束mpi程序的初始化工作是通过调用mpi_init()函数来完成的，

28、该函数是mpi程序的第一个函数调用，同时也是mpi程序的第一条可执行语句。而mpi_finalize()函数是mpi程序的最后一个调用，它结束mpi程序的运行，是mpi程序的最后一条执行语句。如果没有该函数调用，程序的运行结果是不可预知的。命令行的参数将传递给mpi_init()，以允许mpi进行设置要发生的动作，即：main(int argc, char *argv)mpi_init(&argc, &argv);mpi_finalize();初始化后，mpi自动创建一个通信域称为mpi_comm_world，由它定义通信操作的作用域。并且为域内每个进程分配一个独立的序号(进程标识)，如果有n

29、个进程，则其标识为0n-1。用户可以使用mpi初始化创建的通信域，也可以按照mpi提供的函数调用方式，在已经存在的通信域上生成新的通信域。2.3.6 mpi的消息传递函数mpi提供了点对点通信和组通信的消息传递函数，两类函数调用其通信方式上都使用了通信域，用这种方法，可以使库的通信域与用户程序分开。(1) 点对点通信 通信在两个进程之间进行，即：将消息由源进程传递到目的进程。通常用mpi的发送和接受函数调用来完成，它们是：mpi_send()：发送消息；mpi_recv()：接收消息；(2) 组通信 组通信就是指通信的范围涉及组内所有进程。在组通信中，mpi提供了一个广播函数和一组汇集和散播函

30、数调用，它们是：mpi_bcast()：从根进程向所有进程广播消息；mpi_gather()：根进程汇集所有进程发送的消息；mpi_scatter()：根进程散播消息给所有进程；mpi_alltoall()：所有进程向所有进程发送消息；mpi_reduce()：将所有进程发送缓冲区中的数据按给定操作组合，结果存入根进程的接收缓冲区；mpi_reduce_scatter()：在前个功能基础上再散播给所有进程；mpi_scan()：每个进程归约其前面进程发送缓冲区中的数据6。2.4 gtk+简介gtk+(gimp toolkit)是一套用于创建图形用户界面的工具包。它遵循lgpl许可证，所以你可以

31、用它来开发开源软件、自由软件，甚至是封闭源代码的山野软件，而不用花费任何钱来购买许可证和使用权。gtk+ 被称为 gimp 工具包是因为最初写它是用来开发 gimp (gnu 图像处理程序) 的，但是它现在已经被用于很多软件项目了，包括 gnome (gnu 网络对象模型环境)。gtk+ 是在 gdk (gimp drawing kit) 和 gdk-pixbuf 的基础上建立起来的，gdk 基本上是对访问窗口的底层函数 (在 x 窗口系统中是 xlib) 的一层封装，gdk-pixbuf 是一个用于客户端图像处理的库。gtk+ 实质上是一个面向对象的应用程序接口 (api)。尽管完全用 c

32、写成的，但它是基于类和回调函数 (指向函数的指针) 的思想实现的。还有一个名为 glib 的第三个组件，包含一些标准函数的替代函数，以及一些处理链表等数据结构的函数等。这些替代函数被用来增强gtk 的可移植性，因为它们所实现的一些函数在其它 unix 系统上未实现或不符合标准，比如 g_strerror()。一些是对 libc 的对应函数的增强，比如 g_malloc() 具有增强的调试功能。在 2.0 版中，glib 又加入这样一些新内容：构成 gtk+ 类层次基础的类型系统 (type system)，在 gtk+ 中广泛使用的信号系统，对各种不同平台的线程 api 进行抽象而得的一个线程

33、 api，以及一个加载模块的工具。2.5 本章小结本章介绍了本次毕业设计所使用的开发环境及工具。其主要内容包括：集群环境简介；linux简介；mpi简介；gtk+简介。通过本章的学习，对linux、mpi和集群有了大致的了解。特别地，对毕业设计的实验设备有了一定的认识，为以后的实验环节做准备。第3章 julia/mandelbrot分形算法3.1 分形简介3.1.1 分形几何学的创立1973年，曼德勃罗(b.b.mandelbrot)在法兰西学院讲课时，首先提出了分维和分形几何的设想。分形(fractal)一词，是由曼德勃罗创造出来的，其原意是具有不规则、支离破碎等意思，分形几何学是一门以非规

34、则几何形态为研究对象的几何学。由于不规则现象在自然界是普遍存在的，因此分形几何又称为描述大自然的几何学。分形几何建立以后，很快就引起了许多学科的关注，这是由于它不仅在理论上，而且在实用上都具有重要价值。分形几何与传统几何相比有什么特点：(1) 从整体上看，分形几何图形是处处不规则的。例如，海岸线和山川形状，从远距离观察，其形状是极不规则的。(2) 从不同尺度上，图形的规则性又是相同的。上述的海岸线和山川形状，从近距离观察，其局部形状又和整体形态相似，它们从整体到局部，都是自相似的。当然，也有一些分形几何图形，它们并不完全是自相似。其中一些是用来描述一般随机想象的，还有一些是用来描述混沌和非线性

35、系统的。3.1.2 分维的概念在欧氏空间中，人们习惯把空间看成三维的，平面或球面看成二维，而把直线或曲线看成一维。也可以稍加推广，认为点是零维的，还可以引入高维空间，但通常人们习惯于整数的维数。分形理论把维数视为分数，这类维数是物理学家在研究混沌吸引子等理论时需要引入的重要概念。为了定量地描述客观事物的“非规则”程度，1919年，数学家从测度的角度引入了维数概念，将维数从整数扩大到分数，从而突破了一般拓扑集维数为整数的界限。分维的概念我们可以从两方面建立起来：一方面，我们首先画一个线段、正方形和立方体，它们的边长都是1。将它们的边长二等分，此时，原图的线度缩小为原来的1/2，而将原图等分为若干

36、个相似的图形。其线段、正方形、立方体分别被等分为21、22和23个相似的子图形，其中的指数1、2、3，正好等于与图形相应的经验维数。一般说来，如果某图形是由把原图缩小为1/a的相似的b个图形所组成，有：ad=b，d=logb/loga的关系成立，则指数d称为相似性维数，d可以是整数，也可以是分数。另一方面，当我们画一根直线，如果我们用0维的点来量它，其结果为无穷大，因为直线中包含无穷多个点；如果我们用一块平面来量它，其结果是0，因为直线中不包含平面。这样，只有用与其同维数的小线段来测量才可以得到有限值，而这里直线的维数为1(大于0、小于2)。与此类似，如果我们画一个koch曲线，其整体是一条无

37、限长的线折叠而成，显然，用小直线段量，其结果是无穷大，而用平面量，其结果是0(此曲线中不包含平面)，那么只有找一个与koch曲线维数相同的尺子量它才会得到有限值，而这个维数显然大于1、小于2，那么只能是小数(即分数)了，所以存在分维。其实，koch曲线的维数是1.261883.1.3 分形一词的由来据曼德勃罗教授自己说，fractal一词是1975年夏天的一个寂静夜晚，他在冥思苦想之余偶翻他儿子的拉丁文字典时，突然想到的。此词源于拉丁文形容词fractus，对应的拉丁文动词是frangere(“破碎”、“产生无规碎片”)。此外与英文的fraction(“碎片”、“分数”)及 fragment(

38、“碎片”)具有相同的词根。在70年代中期以前，曼德勃罗一直使用英文fractional一词来表示他的分形思想。因此，取拉丁词之头，撷英文之尾的fractal，本意是不规则的、破碎的、分数的。曼德勃罗是想用此词来描述自然界中传统欧几里德几何学所不能描述的一大类复杂无规的几何对象。例如，弯弯曲曲的海岸线、起伏不平的山脉，粗糙不堪的断面，变幻无常的浮云，九曲回肠的河流，纵横交错的血管，令人眼花僚乱的满天繁星等。它们的特点是，极不规则或极不光滑。直观而粗略地说，这些对象都是分形。3.1.4 分形的定义曼德勃罗曾经为分形下过两个定义：定义3.1：满足条件dim(a)dim(a)的集合a，称为分形集。其中

39、，dim(a)为集合a的hausdoff维数(或分维数)，dim(a)为其拓扑维数。一般说来，dim(a)不是整数，而是分数。 定义3.2：部分与整体以某种形式相似的形，称为分形。然而，经过理论和应用的检验，人们发现这两个定义很难包括分形如此丰富的内容。实际上，对于什么是分形，到目前为止还不能给出一个确切的定义，正如生物学中对“生命”也没有严格明确的定义一样，人们通常是列出生命体的一系列特性来加以说明。对分形的定义也可同样的处理。 (1) 分形集都具有任意小尺度下的比例细节，或者说它具有精细的结构。 (2) 分形集不能用传统的几何语言来描述，它既不是满足某些条件的点的轨迹，也不是某些简单方程的

40、解集。(3) 分形集具有某种自相似形式，可能是近似的自相似或者统计的自相似。(4) 一般，分形集的“分形维数”，严格大于它相应的拓扑维数。(5) 在大多数令人感兴趣的情形下，分形集由非常简单的方法定义，可能以变换的迭代产生9。3.1.5 研究分形的意义首先，分形形态是自然界普遍存在的，研究分形，是探讨自然界的复杂事物的客观规律及其内在联系的需要，分形提供了新的概念和方法。其次，分形具有广阔的应用前景，在分形的发展过程中，许多传统的科学难题，由于分形的引入而取得显著进展。分形作为一种新的概念和方法，正在许多领域开展应用探索。80年代初国外开始的“分形热”经久不息。美国著名物理学家惠勒说过：今后谁

41、不熟悉分形，谁就不能被称为科学上的文化人。3.2 分形类型经典的分形主要包括cantor集、koch曲线、sierpinski集、julia集、mandelbrot集。其中前三个几何都属于规则分形，是数学家构造的分形几何，而后两个集合是在复平面上的分形集合，即我们所称的复动力分形集，也是现在研究最多的分形集。我们主要研究的是在复平面上的分形集。3.2.1 julia集julia集是由法国数学家gaston julia和pierre faton在发展了复变函数迭代的基础理论后获得的。julia集是由一个复变函数f迭代生成。在复平面c，像f(z)=z2+c这样一个带有常数c的简单函数，由很简单的迭

42、代过程就能生成很复杂的集，或者说具有奇异形状的分形。一般地，julia集是动力系统中的斥子(repeller)。为了说明斥子的概念，我们先说吸引子的定义。简单的说，一个吸引子就是一个集合并且使得附近的所有轨道都收敛到这个集合上。精确的定义如下：设d是rn的一个子集，并且设f：dd的一个连续映射，则fk表示f的k次迭代。称d的子集f为f的吸引子，如果f是一个闭集，并且在f的作用下是不变的(f(f)=f)，使得对包含f的一个开集v中的所有点x，fk(x)到f的距离随k趋于无穷大而趋于零。集v称为f的吸引域。类似地，对于一个闭不变子集f，如果f附近的所有点经过迭代后远离f，则f就为一个斥子。在这里，

43、一个迭代系统函数图fk就称为一个离散的动力系统。吸引子和斥子可能正好是一个周期为p的轨道。通常，如果f有分形吸引子或分形斥子f，那么f在f上的性质表现为“混沌”。为了叙述方便，令f：cc为复系数的n=2阶的多项式f(z)=a0+a1z*z+an*zn。照例，记fk为函数f的k重复合。如果f()= ,就称为f的不动点。如果存在某个大于等于1的整数p，使得fp()= ,则称为f的周期点，使fp()= 的最小整数p称为的周期。称，f()，fp()为周期p的轨道。设为周期为p的周期点，且复变微商(fp)()= 。点称为超吸引的，如果0吸引的，如果0|1f的julia集j(f)定义为f的斥性周期点集的闭

44、包。对多项式的julia集的几何性质和分形性质的研究表明，j(f)在f下是完全不变的，即j=f(j)=f-1(j)，且j为非空紧集，f在j上表现为“混沌”性质，且j通常是分形。3.2.2 mandelbrot集令fc(z)=z2+c定义3.3：mandelbrot集m为使fc的julia集连通的参数c的集合，m=cc:j(fc)是连通的。m集看起来和j集有很大的关系，实际上m包含了关于julia集构造的无穷信息。3.2.3 mandelbrot集和julia集的关系fc的吸引周期点是j(fc)结构的关键。可以证明若是多项式f的吸引周期点，则存在临界点z使得fk(z)被吸引到包含的周期轨道上。因

45、为fc的唯一临界点是0，所以fc至多有一个吸引周期轨道。而且若c不属于集合m，则由前面可知f c (0) ，所以fc不能有吸引周期轨道。自然的根据吸引轨道的周期p对fc进行分类，如果这种轨道存在的话。相应于不同p的c值对应于mandelbrot集m的不同区域。关系如下图3-1和图3-2所示。图3-1 mandelbrot集和julia集的关系图1图3-2 mandelbrot集和julia集的关系图2定理3.1：设|c|(5+26)/4，则j(fc)是全不连通的。定理3.2：若|c|0，则j(fc)是分形曲线。若c点在主心形线内，fc有吸引不动点且julia集为拟圆。对于c在m集的芽胞中，fc

46、有周期为p的吸引轨道，与julia集内的p区域相交于每个尖点上。在m集外函数fc没有吸引轨道且j(fc)不连通。当c在m的边界上的“例外”值时他所对应的julia集在数学上是最难分析处理的。若c点在m的芽胞或心形图的边界上，则fc有不同的周期点。若c在芽苞与母体接触的颈部则j(fc)包括了一系列把它的边界于不同的周期点连接起来的卷须。对于c位于心形图另外的点上，j(fc)可能包含siegel吸盘。j(fc)由无数多个包围着开区域的曲线组成，且fc将每个这样的区域映射成更大的一个，直到得到包含不动点的区域为止。另外一种可能性，如果c在m的一个发状分支上，则j(fc)可能是无圈曲线，即具有树状结构

47、。在复平面迭代过程可以产生许多分形形状，但mandelbrot集却只有一个，它的主要特点为：m集是二维，复平面上大量点的堆积，它的形状不是由一次求解一个方程来定义的，而是在复平面上通过反馈环进行迭代来定义的。此时的迭代方程就变成了过程而不是描述，是动态的而不是静态的。m集的产生就是无穷次的迭代和精细化的结果，迭代产生的大量的点并不满足一定的方程，而是产生一种行为，它可以有三种结果：一种是定态，一种是收敛到某一状态的周期重复，还有一种趋向于无穷大。应该指出，这里的迭代规则极其简单，而规则的迭代又与尺度的无关地反复重演某种整体的信息，这就表明这个迭代的规则确切的全面的给形状的整体信息。对m集而言，

48、进行迭代时，将z的起始值永远的定为0，对c却选择一个不为零的数，使c在复平面的某个区域上有规律的变化，用不同的c值进行反复的迭代。那些进行了无数次迭代运算之后，z*z+c的值也是有限个复数c的集合，就构成了形状极其复杂的m集。而产生j集的规则正好相反，即把c值固定，而z作为原始点进行变化。按照这种规则可以产生不计其数的j集，只要任选一个c值，就能产生一个与众不同的j集。跨越尺度极其深渊，具有无穷复杂的边界。虽然m集在并不像经典的分形集那样在数学上严格相似的，但是它具有一个相关特征：如果将m集边界放大，便会显示出该集的无穷多个微型缩影，而这些微型的m集没有一个与母集相同，它们自己各有不同。从某种

49、意义上讲，m集概括了所有可能j集，它是无穷数量的j集的直观的图解目录表。根据c在m集中位置，就能预测与之相关的j集的外形及大小，如果c点在m集内部，则相应的j集就是连通的，如果c点在m集之外，其j集就是不连通的。复数迭代理论的一个简单结果表明，要使z在迭代过程中趋于无穷大，其充要条件是在迭代的某一步，z的大小等于或大于2。因此在研究m集和j集时候，如果迭代值z的大小达到2，那么z的值肯定趋向于无穷大，再也不能返回。m集和j集的区域如下：madelbrot集：x的范围 2.251.75y的范围 1.81.5julia集： x和y的范围均为1.81.5所以，这就是为什么我们在计算机绘制这两个分形集

50、合时，我们使用|z|2或(zz)4条件来限制迭代次数10。3.3 逃逸时间算法生成分形图形的算法有多种，例如递归算法，文法构图算法，迭代函数系统算法，分形演化算法还有逃逸时间算法。而对于像julia和mandelbrot这类复动力分形集(复平面上的分形集合)，首推逃逸时间算法。下面，简单介绍一下逃逸时间算法。3.3.1 基本思想首先选定一个复变函数f( z )= z 2 + c，经过该函数的迭代，可以生成分形图形。当c = 0时，由于z是复数，即z = x + yi,则有z2 = z*z = (x + yi)*(x + yi) = x2 + y2*i2 + 2xyi = (x2 y2)+(2x

51、y)i，则复数z = x + yi 的绝对值：|z| = sqrt(x2 + y2)，|f(z0)| = | x02 -y02 + 2x0y0i| = | z02 |，若0 | z0 | 1,| f(z0) | 1,经过迭代z会趋向无穷，z向无穷逃逸；若| z0 | = 1，z是平面上的单位圆。当c0时，其吸引子不再是0，而是一个区域，称混沌区。如图3-3所示，假设有一个充分大的整数n，当未逃逸区域m中的初始点a经过小于n次迭代就到达未逃逸区域m的边界，甚至超出了边界，我们就认为点a逃逸出去了；而如果经过n次迭代后a的轨迹仍未到达m的边界，我们就认为a是a上的点。用这样的方法描绘出a的边界图形

52、，这便是逃逸时间算法的基本思想11。图3-3 逃逸时间算法示意图3.3.2 算法描述(1) 设置收敛区域a的左上角与右下角坐标分别为(a，b)和(c，d)。(2) 设置分辨率m为正整数，并设置正整数p和q，其中p，q=0，1，2，m-1。初始点坐标x0 = a + (c-a)*p/m,y0 = b + (d-b)*q/m。(3) 设置大数n(逃逸时间)和r(逃逸边界半径)。(4) 计算初始点的迭代是否在n步之内大于r。如果大于，则计算下一个初始点；如果不大于则在第n步所在位置画点。(5) 重复执行步骤(4)，使得未逃逸区域内的所有点都计算完毕为止。3.4 julia集的逃逸时间算法julia集是复迭代过程z z2 + c当c为某一固定值的一个吸引域，其中：z = x + yi，c = p + qi;且x,p为复数的实部，y，q为复数的虚部，i为虚常数，即i = 。分别计算julia集的实部和虚部，则有xt+1 = xt 2- yt2 + p;yt+1 = 2xtyt + q;从逃逸时间算法的角度看，julia集的内部收敛于某一点或某几个点，而julia集的外部随着逃逸时间t的增加，将发散至，其逃逸边界便是julia集。我们可以根据点(x，y)逃向的速度决定逃逸区中各点的颜色。3.4.1 算法描述假设绘图窗口的图形分辨率是mxmy，可显示颜色k+1种，以数字0 k表示，且0表