实验6 迭代与分形-2007.10.24.doc

实验7 迭代（二）分形在我们生活着的大千世界里，除了有像房屋建筑、公路桥梁、汽车、飞机、轮船以及各种劳动生活工具等这些人造的形态规则的几何形体之外，更广泛地充满了诸如花草树木、山川河流、烟雾云彩等形态极不规则的几何形体。大自然在向人们展示其美丽多变形态的同时也提出了难以回答的询问：如何描述复杂的自然表象？如何分析其内在的机理？科学家与艺术家一直在苦苦追寻着这些问题的答案，并力图从传统的欧几里得几何体系中解放出来。最近几十年，一些科学家开始朦胧地“感觉”到了另一个几何世界的存在，这个几何世界的描述对象是自然界的几何形态。七十年代，美国科学家BMandelbrot用Fractal（原意是碎片、分数等）这个词来定义这门新的几何学科分形几何学。分形几何把自然形态看作是具有无限嵌套层次的精细结构，并且在不同尺度下保持某种相似的属性，于是在简单的迭代过程中就可以得到描述复杂的自然形态的有效方法。尽管分形的提出只有三十多年的时间，但它已经在自然科学的诸多领域如数学、物理、化学、材料科学、生命科学、地质、地理、天文、计算机乃至经济、社会、艺术等极其广泛的领域有着重大的应用。可以毫不夸张地说，“分形是大自然的几何学”，“分形处处可见”。本实验的目的是以迭代的观点介绍分形的基本特性以及生成分形图形的基本方法，使读者在欣赏美丽的分形图案的同时对分形几何这门学科有一个直观的了解，并从哲理的高度理解这门学科诞生的必然，激发读者探寻科学真理的兴趣。7.1 生成元早在上世纪末及本世纪初，一些数学家就构造出一些边界形状不光滑的图形。由于这类图形长期以来被视为“不可名状的”或“病态的”，因而，只有当人们需要反例时才想到它们。这类图形的构造方式都有一个共同的特点，即最终图形F都是按照一定的规则R通过对初始图形F0不断修改得到的。其中最具有代表性的图形是Koch曲线，Koch曲线的构造方式是：给定一条直线F0，将该直线三等分，并将中间的一段用以该线段为边的等边三角形的另外两边替代，得到图形F1（如图71所示）。然后，再对图形F1中的每一小段都按上述方式修改，以至无穷，则最后得到的极限曲线 即是所有的Koch曲线。图71Koch曲线的修改规则R是将每一条直线段F0用一条折线F1替代，我们称F1为该分形的生成元。分形的基本特性完全由生成元决定。因此，给定一个生成元，我们就可以生成各种的分形。以下是几个经典的分形及其生成元：图72 Minkowski “香肠”图73 Sierpinski 三角形图74 龙曲线图75 Hilbert 曲线图76 树木花草其中，前两种分形图形的生成元比较简单。但后三种分形图形的生成元相对比较复杂。在龙曲线中，生成元将一直线段修改为由两互相垂直的线段构成的折线。但在决定向哪个方向折时存在两种选择（假设线段都有确定的定向，即我们要决定折线是在线段的左边还是在右边）。本生成元规定，折线方向对每条线段依次交替他改变（见图74）。对Hilbert曲线，虽然它的生成元十分复杂，但其原理与龙曲线类似。在图75中，每个小城段的左侧或右侧都画了一根短线，它并不是分形图形的组成部分，它表示在下一步迭代时，生成元应位于短线指示的小正方形之内。树木花草的生成元有些特别，它具有所谓的分支结构。其中有一些参数可以改变，如每段树枝的长度以及树枝之间的夹角。练习1用计算机绘出 Koch曲线，Sierpinski三角形及一树木花草的图形。你能否自己构造一些生成元，并由此给出相应的分形图形？任取分形图形的一个局部并将它放大，它同原来的分形图形有什么关系？练习2从一个正三角形出发，用 Koch曲线的生成元做迭代得到的极限图形称为Koch雪花曲线。（1）试计算雪花曲线的边长及面积，它们是否有限？你如何解释所得出的结论？（2）雪花曲线是否光滑（即每一点是否有切线存在）？（3）其它的一些分形是否具有类似的性质？练习3假设生成元由n条线段构成，每段长度为原线段长度的，定义该分形的维数为 （l）想一想，这样定义分形的维数有什么道理？分形维数的大小反映了分形的什么特性？（2）利用上述公式，计算雪花曲线 Minkowski香肠的维数。（3）从直观上看，Hilbert曲线将填满整个正方形，你是否相信这个事实？你猜测Hilbert曲线的维数是多少？（4）Sierpinski三角形的维数该如何定义？按你的定义，计算Sierpinski三角形的维数，并解释所得结果。练习4 定义Weierstrass函数如下： , , 12 对不通的值，画出函数的图象。观察图象的不规则性与此同时的关系，由此猜测 Weierstrass函数图象的维数与的关系。7.2 复变函数迭代早在上个世纪就有一些数学家对复变函数的迭代进行研究。然而，直到本世纪80年代。B.Mandelbrot才将复变函数的迭代与分形联系起来，并绘制出了第一张以他的名字命名的引人入胜的分形图形。复变函数的迭代由此再一次成为数学家的热点研究问题。给定初始复数，考虑如下的迭代=+， k = 0,1,2, （1）其中，k = 0, 1, 2, ，为复数，为（复）常数。对于给定的初始点，迭代序列有可能有界，也可能发散到无穷。令是使得迭代序列有界的所有初值构成的集合，即=|迭代序列有界 (2)我们称在复平面上构成的集合为Julia集。对不同的参数，Julia集的形状也会不同。特别地，=0对应的Julia集为单位圆盘。如果固定初值，则对不同的参数，迭代序列的有界性也不相同。令是使得迭代序列有界的所有参数构成的集合，即 =|迭代序列Z有界 （3）则称在复平面上构成的集合为Mandelbrot集。为了便于在计算机上绘制出Julia集和Mandelbrot集，我们令,则（1）可改写为 k = 0, 1, 2, (4)记,则Julia集为使得序列有界的初始点（,）构成的集合，Mandelbrot集为使得序列有界的参数（）构成的集合。Julia集和Mandelbrot集会是什么样子？如果没有计算机的帮助，你是很难想象的。下面，我们给出这两种集合的计算机做图方法。Julia集绘制方法：（1） 设定初值，一个最大的迭代次数N，图形的分辨率的大小和使用的颜色数K（如K = 16）（或者给定灰度级L）。（2） 设定一个上界值 。（3） 将矩形区域分成的网格，分别以每个网格点,，作为初值（,）利用（riter）做迭代（实际上，只需对满足的初始点迭代）。如果对所有,则将图形的（）象素点用黑色显示。否则，如果从迭代的某一步n开始有,则用第mod K种颜色显示相应象素（或者用相应的灰度级显示）。Mandelbrot集的绘制方法：（1） 设定一个最大的迭代次数，图形的分辨率的大小和使用的颜色数（如16）（或者给定灰度级）。（2） 设定一个上界值。（3） 将矩阵区域分成的网格，分别以每个网格点,，作为参数值() 利用（riter）做迭代（实际上，只需对满足的初始点迭代）,每次迭代的初值均取为（,）= (0, 0) 。如果对所有,则将图形的（）点用黑色显示。否则，如果从迭代的某一步n开始有,则用第mod K种颜色显示相应象素（或者用相应的灰度级显示）。练习 编写绘制Julia集的程序。对不同的参数() ：(0, 1)，(, 0)，(0.11, 0.66)，观察Julia集的变化。取Julia集的不同局部放大，你能看到某种自相似现象吗？练习6 绘制Mandelbrot集。然后,任意选取它的一个局部将其放大,然后再将放大图形的不同局部放大。由此观察Mandelbrot集与Julia集有何关系。进一步,取参数位于Mandelbrot集的不同部位（如内部、外部、边界、某个苞芽的内部等），观察相应的Julia集的形状的变化。练习7 Julia集与Mandelbrot集可以推广到高阶情形。一般地，考虑迭代使得迭代（5）有界的初值Z构成n阶Julia集。对固定的参数Z使得迭代（5）有界的参数c构成n阶Mandelbrot集。试画出三阶、四阶及五阶Julia集与Mandelbrot集，并通过放大不同的局部观察它们的自相似性。7.3 IFS迭代让我们以下面的一个简单的绘图游戏来说明IFS迭代。在平面上任取不共线的三点,和，并确定三个相应的概率, ,。任取一个点,按下述步骤在平面上画出新的点列, ,2, ; 以概率选定为与的中点，以概率选定为与的中点，以概率选定为与的中点。即如果我们按上述步骤迭代下去，最终得到的图形会是什么样子呢？如果迭代仅仅只有一千次或一万次，你将会看到乱七八糟的一片，因此，有人把这个游戏称为“混沌游戏”。但当迭代次数在一百万次以上时，图形将渐渐开始清晰。图12-7给出了迭代一亿次的结果。读者可以看出，它正是我们前面提到的Sierpinski三角形的逼近图形！ 图77上述绘图游戏中的迭代即是IFS迭代。IFS迭代的一般提法是：给定一组（仿射）变化：以及相应的一组概率.对于任意选取的初始值,以概率选取变换做迭代则点列收敛的极限图形称为一个IFS吸引子。利用IFS迭代不仅可以生成许多有趣的分形图形，而且可以应用于分形图象的压缩。下面，我们给出IFS迭代绘制分形的方法。设计算机屏幕的可视窗口为按分辨率大小的要求将分成的网络，网格点为,这里用表示矩形区域。假设我们采取具有（如=256）级灰度的黑白图象绘制，总共的迭代次数为N，其中落于区域中的点的个数为。再记 则象素的灰度与落于中的点数成正比： 于是即给出了IFS迭代产生的分形的级灰度图象。练习8 回到前面的“混沌游戏”。如果把三个概率分别取为， 则迭代一百万次的图形如何？再取一组其它