《离散动力系统生成Sierpinski三角形》由会员分享，可在线阅读，更多相关《离散动力系统生成Sierpinski三角形（5页珍藏版）》请在金锄头文库上搜索。
1、2 0 0 1 年 增刊 工 程 图 学 学 报 J OU RN AL OF E NG I NE ERI NG GR AP HI CS 离散动力 系统生成S i e r p i n s k i 三角形 抚 顺 石 油 学 院 计 算 机 科 学 与 技 术 系纪玉波薛 全 摘 要 在 分 形几 何中 ， S ie r p in s k i 三角 形 是一个 典型的并 且非 常 有 代 表性的 分形图 形， 它的生 成方法 有若干种， 本文在 研究离 散动力系 统的 基础 上， 提出了 一 种生 成 S ie r p in s k i 三角 形的 全 新方 法. 此方法 生 成图 形 速 度.决
2、 ， 清 晰美 观， 同 时 通过 所 生成的S ic 印 in s k i 三 角形特点有助于 深入了 解离 散动力系 统的 特性. 关 键词 S ie r p i n s k i 三 角 形， S i e r p i n s k i 地 毯， 动 力系 统 混 沌 0引言 波 兰 数学家W a c o a l S i e r p in s k i 于1 9 1 6 年 提出了 以 他 名字 命名的S ie r p i n s k i 三角 形， 被 公认为是一 种非常典型而且重 要的分形图形。在分形几何中， S i e r p i n s k i三角形构造清 晰 简洁明了，具有分形图形的显
3、著 性质，即 严格的自 相似性，无 特征尺度却有标度律， 是各种分形生成系统中的典型例子。 有多种构造S i e r p i n s k i 三角形的方法， 例如 递归 生成算法; 利用 L 系 统的文 法生成 方法;迭代函 数系统( I F S ) 的吸引子生成方法等。本文提出的算法思路与前几种方法完全 不同，利用了一种离散混沌动力系统构造出 S i e r p i n s k i三角形，并进一步构造出 S i e r p i n s k i 地毯。这种方法充分利用了 离散 动力系 统具有倍周期分岔产生混沌的 特性， 以 一种新的方式得到了同样的 S i e r p i n s k i三角形
4、，并且 生成图形的效率有较大提高， 避免 了 递归算法占 用大量内 存， I F S 系统需要人为的介入等弊端。同时，生成S i e r p i n s k i 三 角 形的变化过程也说明该动力系统确实具有复杂的混沌性质， 其参数的变化对系统动力行为 产生明显的影响。 1 S i e r p i n s k i 三角 形的 传 统生 成算 法 S i e r p i n s k i 三角 形一 般的 构造 过程 如图1 所示， 首 先 取定一 个三 角形 如图1 ( a ) ， 连 接各边中点从而将原三角形分割成四个小三角形，除去中 间的小三角形如图 1 ( b ) ， 下一 步将剩下的三个小
5、三角形按上面同样的方法继续分割，并继续舍弃中间的三角形，如此 不断重复分 割与舍弃， 就形成如图 i ( c ) 所示的一个中 间留有大量空隙的三角形，这 就是 S i e r p i n s k i 三角形。 从S i e r p i n s k i 三角形的构造过程我们可以 看出， S i e r p i n s k : 三角 形的生成是一个逐 步细化的过程， 每一步均重复相同的动作， 因此可采用递归的方法完成。递归 算法的关键 是定义一个递归函数，此函 数的功能是 将一个三角形分 成四 个小三角形， 并将中间的三角 纪玉波 等: 离 散 动力 系 统生 成S i e r p in s l
6、a 三角 形 (a) ， 形同 其它三个三角形中区分出 来 角形( 4 1 S i e r p i n s k i 三 角形 生成 过 程 当 递归调用达到一定的深度， 就可生成 S i e r p i n s k ， 三 利用 S i e r p i n s k i 三角形的严格自 相似性和构造的规则性， 也可以 使用 L系统生成该 分形图。L 系统定义为一个三元式:L = ， 其中G为字符集，为起始符号元且为G 中的成员， 用于确定字符串的起始状态， P为生 成规则集合。 选用适当的文法就可以生成 S i e r p i n s k i 三角形 s 。 生成S i e r p i n s
7、k : 三角形还可以 选用迭代函 数系统工 F S 混沌 游戏就是 利用 工 F S生成 该图 形的著名例子。 预先取定三个压缩映射和三个压缩映射分别对应的 概率， 可以形 成一 个迭代函数序列， 根据此序列在三角形内 部描点， 当达到一定的次教后得到这个混沌游戏 算 法生 成的 分形图 形， 即S i e r p i n s k i 三 角形. l 2离散的混沌动力 系统生成S i e r p i n s k i 三兔形 对离散的混沌动力系统而言t当 其参数变化时 ， 它的动力学 特性也发生相应变化，由 稳定的动力系统产生倍周期分岔行为直至产生混 沌现象。 利用动力系统的这种特性 通过 控
8、制参数的变化司生成不同的分形图形， 其中包括 S i e r p i n s k i 三角形和 S i e r p i n s k i地 毯。 考虑如下的离散动力系统决定的函数: Ax ) = x ， 一 b x + a ( 1 ) 则由该函数可以确定迭代公式: x, = x 矛 - 6 x十 a ( i = 1 , 2 , . , N ) ( 2 ) 并产生 迭代函数序列: 执卜 x x = , . . ., x n ( = L 2 , . . ., N ) ( 3 ) 作为一种离散化的有理函 数确定的动力系统，尽管形式上很简单但它却具有丰富的非 线形性质和混沌特性， 下面对它进行比 较详细
9、的 分析， 研究其混沌 特性。 首先可以 看出 这是一 个几司 数， 关于原点对称， 即具有对称性。 对给定的系数 a , b , 在选定一个 x的初值后， 利用( 3 ) 式产生的有理数迭代序列在屏幕上描点，当 迭代次 数 n 逐渐增大时，可以观察发现系统由 稳定态开始进入了倍周期分叉状态直到产生出混沌状 态。图2 所示是计算了1 1 5 0 个点生成的图形，为了 使生成的分岔图更清晰， 舍去了 前 1 5 0 工 程 图 学 学 报 个点，将后面的 1 0 0 0 个点描出得到图形。 图 2 在此混沌动力系统中系数 b起着决定性的作用。 这是因为它对轨道的临界点起着主 导 作 用。 所 谓
10、 临 界 点 就 是厂( x ) _ 。 的 点 ， 由( 1 ) 式 确 定 的 有 理 函 数 有 两 个晦 界 点 ， 分 别 ， 二 厘 _ ， _ = _ _厘 N 3 一 “V 3 ( 4 ) 事实上，由( 1 )式确定的混沌动力系 统是复 数域内的 对称映射动力系 统在实数域内 的 表示形式， 给定控制参数 a ,匕的值，该 动力不 统可以 产生倍周期分岔，直到出现混沌 现 象 ， 迭 代 序列 x 卜 x , , x ， ， 一 ( i = 1 , 2 , . ., n , . ) 最 终 趋向 于 它 确 定 的 混 沌 吸 引 子 。 如图 2中的图形有两个稳定的分岔，表明
11、该系统在两个临 界点处都会产生倍周期分叉行 为，田( 3 ) 式确定的迭代序列逐渐通近并最终归向 于该动力系统的混沌吸引子。 我们在研 究了动力系统由稳定态转变为混沌态的发展过程以后，充分考虑和利用了 产生混沌吸引 子 的生成序列，设计出由离散的混沌动力系统( 1 ) 式生 成 S i e r p i n s k i 三角 形的具体算法， 具体构造过程如下: 1 . 定 义两 个 数组: 阔 值数组f p l i l U l ( i 二 1 ,2 , .- -,M; j = 1 ,2 , . 一， N ) 描 点 数组g p l i l l i l ( i 二 1 ,2 , . - , M;
12、j = 1 , 2 , 一 N) 阐 值 数 组f p l 门 口 的 作 用是 根 据上 述 生 成 混 沌 吸引 子 的 生 成 序列 的 过 程 值 来 判 定 是否在平面上描点，只有大于阐值的点才被描绘出来。 描 点 数 组g p ( i l 口 l 的 作用 是 对 平 面 上 满 足闭 值 的 点 进 行 具 体的 绘 制 2 . 初 始 化数 组夙月 口 和g p ( 月 ( j 元 素 为 零; 3 . 利 用( 3 ) 式的 迭代 序 列 对闽 值 数组f p ( i l 口 的第 一 行赋 值: x ; , i = x 了 一 b x + a ( j = 1 ,2 ,.,
13、N ) f p l a l f i l = x ; ( i = 1, 2 , . 1 .1 , N ) 4 . 数 组斑i 口 l 的 其 它 行 用 下 述 方 法 斌 值 f p ( i + 1 j = IO li l li 一 f p l i l (J + I 5 . 利 用 阂 值 数 组f p ( l C i l 对 描 点 数 组 g p ( i l ( i l 赋 值 : 八i l j 0 .5 几 f j l s o s = 1 , 2 , . . . , M; J = 1 , 2 , . . . , N -一 肿 纪 玉波 等: 离 散 动力 系 统生 成s i e r p
14、u is la 三角形 其中问值选为0 . 5 ，点的颜色为黑或白 6 . 利用描点数组9 m月 1 月在平面上描点，就可以产生一个大小为MXN的 S i e r p i n s k ， 三角形 . 3实验结果 我们对该算法进行了 编程实现， 其中 选定 M = 2 0 0 , N = 2 0 0 , 阀 值为 。 . 5 , 迭代次 数为 3 0 0 次。 当 选取b = 1 . 9 ， a = 1 . 5 得到图3 ， 此图是一幅标准的S i e r p i n s k i 三角形:当 选取b = 2 . 1 a = 1 . 5 得到图4 ， 是一些散 列在平面上的 三角形组成的 S i
15、e r p i n s k i 地毯. 通过多次的实验 我们发现系数 b的变化要比系 数 a的变化对图形 的影响大得多， 这与前面对临界点的 讨 论结 果 是 一 致的 ，同 时 我 们 发 现 生 成S i e r p i n s k i 三角 形的 系 数a 值 可以 任意 选 取， 但 是 b 值 应 在。 . 6 8 8 7 - 2 之 间 ， 当b 的 值 小 于。 . 6 8 8 7 时 平 面 上 没 有 任 何 图 形 ， 当b 的 值 大 于 2 时S i e r p i n s k i 三角形就转化为S i e r p i n s k i 地 毯，并且b 的 取值不同S i
16、 e r p i n s k ， 地毯 的分布密度也不相同， b 值越大S i e r p i n s k i 地毯 在平面上的填充 就越充分，当b ? 9 . 8 , 生成的S i e r p i n s k i地毯于文献 1 - 3 生成的图形 类似。同时，阐值越大要求迭代的次数 也越多，计算时阿越长。 图3 图 4 4结束语 利用简单的 二次、 三次以至 。次 有理函 数构成的 动力系统本身所具有的混沌行为， 可以生成包括 S i e r p i n s k i 三角形在内的多 种分 形图 形， 这种方法不同于分 形几何中 常用 的 I F S迭代系统或 L系统。同 时利用动力系统生 成的不同图形，也可以 对动力系统的 性 质进行分析。 如我们在实验过程中 发现， 系数 b的变化比 系数 a的 变化对该系统的 动力 性质影响要大， b 的不同选取导致了S i e r p i n s k i 三角形图3 和S i e r
