关于几个3x+1推广函数和广义M集的若干分形性质的研究
|
摘要
本论文主要内容为作者在吉林大学计算机科学与技术学院攻读博士学位期间对3x+1推广函数与广义Mandelbrot集的分形性质研究的内容与结论,同时构造了新的算法以降低分形生成的时间。
分形理论是Mandelbrot在1982年提出的,随即成为了一个新兴的研究热点。近三十年来,许多学者对分形进行了广泛的研究,并以分形为基础进行了一系列的研究推广。
研究目的:本文主要对3x+1推广函数和广义的Mandelbrot集(此后简称M集)进行了分形研究,主要包括对它们的组成、不动点、周期点、边界性等进行研究。这些研究基本说明了广义M集和3x+1推广函数的分形结构。同时构造了新的分形生成算法以加速生成时间。
实验方法:本文对3x+1推广函数的研究使用了复解析动力分析的方法,首先构造了一个3x+1近似推广函数并对其进行分形研究,然后在它的基础上对3x+1推广函数进行了分析。通过生成它们的分形图形可以得知,它们有很大的相似性。在对广义M集的研究过程中,本文首先在实轴上考察其基本性质,然后将其推广至复平面。
结果与结论:本文求解并证明了一类3x+1推广函数的不动点分布,并证明了其不动点有无穷多的结论,同时本文提出了一个普适性的分形生成算法用于生成分形图形。本文证明了一类广义M集的最小逃逸阈值,提出并证明了判断逃逸点的等价条件和边界点的求解公式。
For generalized 3x+1 function T(x), the feature of fixed points and their existence-domain analysis is an important problem in fractal. T(x) is a complex transcendental function and its fixed point in C-plane is hardly to solve. Meanwhile, the feature of fixed point is difficult to analyze; all these become an obstacle for the further study of T(x) dynamic system.
In order to study the fractal character of representative complex exponential function just as generalized 3x+1 function T(x). We create a generalized approximate 3x+1 function B(x). We analyze B(x) in real axis and C-plane and find the fixed point of B(x) at real axis and C-plane. Then we prove zero is the only attract fixed point. Moreover, we show the symmetry of B(x) and use escape time algorithm to draw the fractal figures. We show B(x)’s iteration have endless points make (?) B~i(x)=∞in [n,n+1] when n∈and |n|>3. At last, we put forward a conjecture that all the divergence areas of B(x) is similar to each other. The research conclusion of B(x) is play a direct hole in promoting research of T(x).
In fact, by research conclusion of B(x), we study more of the characters of T(x)’s fixed point. Firstly, Because of the topological invariance of T(x), the constructive proof of its fixed point in C-plane is presented, and then the analysis for the existence domain of fixed points is given as well as their feature. Based on the existence domain of T(x) fixed points, their distributions in C-plane are estimated. So a numerical algorithm for solving the fixed points of T(x) is put forward on the basis of distributions analyses. Furthermore, some convergence domains of T(x) in C-plane are obtained, as well as fractal image of these domains. The result of numerical experiment shows that the algorithm in this paper is correct and easy to implement.
Moreover, In order to study more about the fractal character of T(x), we research the characters of T(x)’s periodic points with the research of T(x)’s fixed point. In this paper, we proved that T(x) has periodic points of every period in bound (n, n+1) when n>1 in real axis. Then, we found the distribution of 2-periods points of T(x) in real axis. We put forward the bottom bound of 2-periodic point’s number and proved it. Moreover, we found the number of T(x)’s 2-periodic points in different bounds to validate our conclusion. Then, we extended the conclusion to i-periods points and find similar conclusion. Finally, we proved there exist endless convergence and divergence points of T(x) in real axis.
At the same time, we also study fractal construction of another generalized 3x+1 function C(x). At first, we find the character of fixed points of C(x) at real axis by complex analytical analysis. Then we improve the solving algorithm of its fixed points. We proved that the integer fixed points of C(x) are 0 and -1 and the attract fixed points of C(x) are 0 and -1.2777. Popularized the result to complex plane, we prove that there is no fixed point of C(z) except real axis. We draw the fractal figures of C(x) by escape time algorithm to prove the result and give a conjecture from the fractal figures. The conjecture guess that the attract domain of C(x) is a connected domain which is connected with single point.
Then we study the fractal structure of generalized M set in this paper. It is well known that Mandelbrot set is an important part of fractal and chaos for its simple expression and complex structure, In this essay, we construct a class of polynomial curves and gain boundary points and periodic points of M-set. At first, we have proved that the threshold is number 2. In other words, for point z in complex plane, it is not in M-set when |fn(z)|>2 (fn(z)=f○fn-1(z)). Secondly, with this threshold condition, we construct a class of polynomial approximation curves for M-set. We have proved that the curves are contained level by level, and the limit curve is M-Set when the iteration tends to infinity. Then, we construct the equations to gain periodic and boundary points by using the polynomial approximation curves. Finally, we extend the conclusion to the generalized M-Set with positive integer order, and prove that there exists similar conclusion for the generalized M-Set with positive integer order.
Otherwise, we research generalized M set with negative integer index. We define a series {yi} as the ith iterations of generalized M set. By to study characters of each item of series {yi-y1}, we solve all escape points of its fractal image and point out that all these points are denumerable infinite and discrete. Then we put forward a better algorithm to create figures more accurate. To compare with the different points in fractal figures drawn by classic and our algorithm, we find the new algorithm draws better figures to fit the definition of M set.
Further more, in order to create the fractal image faster, we improve the fractal image creating algorithm. It is known that the escape time algorithm is the most universal algorithm when to create fractal image. With the study of a class of algorithms based on escape time algorithm, we find there is wasting-calculation in these algorithms. In this paper, when combined with the feature of eventually periodic point of functions, we define a kind of points as no-escape point. To analyze the shortcomings of the classic algorithm, we improve the escape time algorithm base on the no-escape points. We analyze the algorithm and put forward the best application scope for it. By create lots of fractal figures, we find the figures created by the two algorithms are consistent with each other except a few escape points. We compare the complexity between the two algorithms and find the iteration times by the improved algorithm are less than escape time algorithm when creating the fractal figures. We do several experiments and find the improved algorithm is universal and it reduces the time-consuming.
分形理论是Mandelbrot在1982年提出的,随即成为了一个新兴的研究热点。近三十年来,许多学者对分形进行了广泛的研究,并以分形为基础进行了一系列的研究推广。
研究目的:本文主要对3x+1推广函数和广义的Mandelbrot集(此后简称M集)进行了分形研究,主要包括对它们的组成、不动点、周期点、边界性等进行研究。这些研究基本说明了广义M集和3x+1推广函数的分形结构。同时构造了新的分形生成算法以加速生成时间。
实验方法:本文对3x+1推广函数的研究使用了复解析动力分析的方法,首先构造了一个3x+1近似推广函数并对其进行分形研究,然后在它的基础上对3x+1推广函数进行了分析。通过生成它们的分形图形可以得知,它们有很大的相似性。在对广义M集的研究过程中,本文首先在实轴上考察其基本性质,然后将其推广至复平面。
结果与结论:本文求解并证明了一类3x+1推广函数的不动点分布,并证明了其不动点有无穷多的结论,同时本文提出了一个普适性的分形生成算法用于生成分形图形。本文证明了一类广义M集的最小逃逸阈值,提出并证明了判断逃逸点的等价条件和边界点的求解公式。
For generalized 3x+1 function T(x), the feature of fixed points and their existence-domain analysis is an important problem in fractal. T(x) is a complex transcendental function and its fixed point in C-plane is hardly to solve. Meanwhile, the feature of fixed point is difficult to analyze; all these become an obstacle for the further study of T(x) dynamic system.
In order to study the fractal character of representative complex exponential function just as generalized 3x+1 function T(x). We create a generalized approximate 3x+1 function B(x). We analyze B(x) in real axis and C-plane and find the fixed point of B(x) at real axis and C-plane. Then we prove zero is the only attract fixed point. Moreover, we show the symmetry of B(x) and use escape time algorithm to draw the fractal figures. We show B(x)’s iteration have endless points make (?) B~i(x)=∞in [n,n+1] when n∈and |n|>3. At last, we put forward a conjecture that all the divergence areas of B(x) is similar to each other. The research conclusion of B(x) is play a direct hole in promoting research of T(x).
In fact, by research conclusion of B(x), we study more of the characters of T(x)’s fixed point. Firstly, Because of the topological invariance of T(x), the constructive proof of its fixed point in C-plane is presented, and then the analysis for the existence domain of fixed points is given as well as their feature. Based on the existence domain of T(x) fixed points, their distributions in C-plane are estimated. So a numerical algorithm for solving the fixed points of T(x) is put forward on the basis of distributions analyses. Furthermore, some convergence domains of T(x) in C-plane are obtained, as well as fractal image of these domains. The result of numerical experiment shows that the algorithm in this paper is correct and easy to implement.
Moreover, In order to study more about the fractal character of T(x), we research the characters of T(x)’s periodic points with the research of T(x)’s fixed point. In this paper, we proved that T(x) has periodic points of every period in bound (n, n+1) when n>1 in real axis. Then, we found the distribution of 2-periods points of T(x) in real axis. We put forward the bottom bound of 2-periodic point’s number and proved it. Moreover, we found the number of T(x)’s 2-periodic points in different bounds to validate our conclusion. Then, we extended the conclusion to i-periods points and find similar conclusion. Finally, we proved there exist endless convergence and divergence points of T(x) in real axis.
At the same time, we also study fractal construction of another generalized 3x+1 function C(x). At first, we find the character of fixed points of C(x) at real axis by complex analytical analysis. Then we improve the solving algorithm of its fixed points. We proved that the integer fixed points of C(x) are 0 and -1 and the attract fixed points of C(x) are 0 and -1.2777. Popularized the result to complex plane, we prove that there is no fixed point of C(z) except real axis. We draw the fractal figures of C(x) by escape time algorithm to prove the result and give a conjecture from the fractal figures. The conjecture guess that the attract domain of C(x) is a connected domain which is connected with single point.
Then we study the fractal structure of generalized M set in this paper. It is well known that Mandelbrot set is an important part of fractal and chaos for its simple expression and complex structure, In this essay, we construct a class of polynomial curves and gain boundary points and periodic points of M-set. At first, we have proved that the threshold is number 2. In other words, for point z in complex plane, it is not in M-set when |fn(z)|>2 (fn(z)=f○fn-1(z)). Secondly, with this threshold condition, we construct a class of polynomial approximation curves for M-set. We have proved that the curves are contained level by level, and the limit curve is M-Set when the iteration tends to infinity. Then, we construct the equations to gain periodic and boundary points by using the polynomial approximation curves. Finally, we extend the conclusion to the generalized M-Set with positive integer order, and prove that there exists similar conclusion for the generalized M-Set with positive integer order.
Otherwise, we research generalized M set with negative integer index. We define a series {yi} as the ith iterations of generalized M set. By to study characters of each item of series {yi-y1}, we solve all escape points of its fractal image and point out that all these points are denumerable infinite and discrete. Then we put forward a better algorithm to create figures more accurate. To compare with the different points in fractal figures drawn by classic and our algorithm, we find the new algorithm draws better figures to fit the definition of M set.
Further more, in order to create the fractal image faster, we improve the fractal image creating algorithm. It is known that the escape time algorithm is the most universal algorithm when to create fractal image. With the study of a class of algorithms based on escape time algorithm, we find there is wasting-calculation in these algorithms. In this paper, when combined with the feature of eventually periodic point of functions, we define a kind of points as no-escape point. To analyze the shortcomings of the classic algorithm, we improve the escape time algorithm base on the no-escape points. We analyze the algorithm and put forward the best application scope for it. By create lots of fractal figures, we find the figures created by the two algorithms are consistent with each other except a few escape points. We compare the complexity between the two algorithms and find the iteration times by the improved algorithm are less than escape time algorithm when creating the fractal figures. We do several experiments and find the improved algorithm is universal and it reduces the time-consuming.
引文
[1] AlvesJF,Graca MM,Dias MES,et al. A linear algebra approach to the conjecture of Collatz. Linear Algebra and Its Applications,2005,394(1):277-289
[2] Lagarias JC. The 3x+l Problem and Its Generalizations. American Mathematical Monthly,1985,92(1):3-23
[3] Wirsehing GJ. The dynamical system generated by the 3n+1funetion. Lecture Notes in Mathematics,1998,1681:153-159
[4] Wu Jiabang,Hao Shengwang. On equality of the adequate stopping time and the coefficient stopping time of n in the 3N+1 conjecture. J. Huazhong Univ. of Sci. & Tech.(Nature Science Edition),2003,31(5):114-116(in Chinese with English Abstract).
[5] Belaga,Mignotte. Embedding the 3x + 1 Conjecture in a 3x + d Context. Experimental Mathematics,1998,7(2) 145-151
[6] John Simons,Benne de Weger. Theoretical and computational bounds for m-cycles of the 3n + 1 problem. Acta Arith,2005,117 (1), 51-70
[7] Mandelbrot BB. The fractal geometry of nature[M]. San Fransisco: Freeman W H,1982,1-122
[8] PeJL.The 3x+1 fractal[J]. Computers and graphics,2004,25(3) 431-435
[9] Dumont JP,Reiter CA. Visualizing generalized 3x+1 function dynamics[J]. Computers and Graphics,2001,25(5):553-595
[10]王兴元,于雪晶.基于分形可视化方法研究广义3x+1函数的动力学特性.自然科学进展2007,17(4):529-535
[11]李向华,王钲旋. 3x+1推广函数构造广义M集及其艺术分形图像.计算机辅助设计与图形学学报,2007,19(4):419-424
[12]王钲旋,王巧龙,冯月萍,等.一个3x+1推广函数在实轴上的不动点与生成的分形图象.第十一届全国图象图形学学术会议,上海,2003:346-349
[13]王则柯.复平面上计算超越函数零点的一种有效算法[J].中山大学学报, 1981年,第3期: 15-21
[14] Yunliang Long, Edward K.N.Yung. Kuhn Algorithm: Ultraconvenient Solver to Complex Polynomial and Transcendental Equations without Initial Value Selection[J].International Journal of RF and Microwave Computer-Aided Engineering, 2002, 12(6): 540-547
[15]黄永念.Mandelbrot集及其广义情况的整体解析特性.中国科学(A辑),1991,(8):823~830.
[16] Gujar U G,Bhavsar V C. Fractal images from z←zα+c in the complex C-plane[J].Computers&Graphics,1991,15(3):441-449.
[17] Dhurandhar S V,Bhavsar V C,Gujar U G. Analysis of Z-plane fractal images from z←zα+c forα< 0 [J]. Computers & Graphics,1993,17(1):89-94.
[18] Shirriff K W. An investigation of fractals generated by z→z-n+c [J]. Computers &Graphics,1993,17(5):603-607.
[19] Wang XY, Liu XD, Zhu WY, Gu SS. Analysis of c-plane fractal images from for z←zα+c (α<0). Fractals, 2000,8(3): 307~314.
[20]朱志良,焉德军,朱伟勇.复迭代的广义Mandelbrot集.东北大学学报(自然科学版),2000,21(5):469~472.
[21]谭建荣,程锦.复映射z = zα+c(α≥2)的广义M集及其对称周期检测法[J].软件学报,2003,14(3):666-674.
[22]朱伟勇,朱志良,刘向东等.周期芽苞Fibonacci序列构造M-J混沌分形图谱的一族猜想[ J].计算机学报,2003,26(2): 221~226.
[23]朱志良,曹林,朱伟勇等.广义M-集周期芽苞Fibonacci序列的拓扑不变性[J].东北大学学报(自然科学版), 2002,23(4): 307~310.
[24]朱伟勇,宋春林,邓学工等. Fibonacci序列构造z-2+c广义M-J混沌分形图谱及其标度不变性的研究[J].计算机学报,2004,27(1): 52~57
[25]王兴元,负实数阶广义M集内部结构的探讨[J]计算机辅助设计与图形学学报2001,13(10): 868-873
[26]刘向东,焉德军,朱伟勇等.广义M-J集的界与J-集Hausdorff维数的估计[J].应用数学和力学,2001,22(11):1187-1192
[27]刘鸿雁,隋涛,徐喆等. Fibonacci序列构造广义M-J混沌分形图谱周期性的研究[J].中国图象图形学报,2008,13(3):536-540
[28]章立亮,广义M-J集的边界构造及分维数计算[J].小型微型计算机系统,2008,29(7):1338-1342
[29]王兴元,骆超.一个非解析复映射的广义Mandelbrot集[J].大连理工大学学报,2009,49(1):52-57
[30]胡纪阳,胡瑞安,具有周期性的分形图象及其生成算法,工程图学学报,1991年第2期15-18
[31]陈宁,朱伟勇构造高阶广义M─分形图及对称逃逸时间算法,东北大学学报(自然科学版),1996年6月第17卷第3期225-229
[32]陈宁,朱伟勇构造高阶广义Julia分形图及旋转逃逸时间算法,东北大学学报(自然科学版),1997年2月第18卷第1期94-97
[33]陈宁,复迭代z←(?)+c构造上半平面分形图及“Escher”极限图,计算机研究与发展,2000年2月第37卷第2期214-217
[34]陈宁,朱伟勇.复迭代z←e iπ2zw+c (w=α,+iβ)构造M集,计算机研究与发展,1997年12月,第34卷第12期899~907
[35] Chen Ning,Zhu Weiyong. Bud-sequence conjecture on M fractal image and M-J conjecture between c and z planes from z←e iπ2zw+c (w=α+iβ),Computers &Graphics, 1998, 22(4) 537~546
[36]秦宣云,管继虹,任波等.广义Julia集关于迭代参数的对称性分析,计算机辅助设计与图形学学报,2007年7月第19卷第7期927-930
[37]秦宣云,任波.逃逸时间法生成Julia集的算法分析和具体实现,计算机工程与应用,2007年2月第43卷第5期30-32
[38]吴尚智,任小康.用加速逃逸时间算法构造Julia集图形,计算机应用与软件,2006年5月第23卷第5期119-120
[39]章立亮,构造广义M-J集的邻域逃逸时间算法,工程图学学报,2008年3月第3期109-115
[40]姜卓睿,陈幼均.基于埃特金加速算法实现的Julia集分形图形,计算机应用与软件,2008年4月第25卷第4期212-214
[41] K Falconer. Fractal Geometry: Mathematical Foundations and Applications, Second Edition[M]. John Wiley @ Sons, Inc, 2003, 1-296
[2] Lagarias JC. The 3x+l Problem and Its Generalizations. American Mathematical Monthly,1985,92(1):3-23
[3] Wirsehing GJ. The dynamical system generated by the 3n+1funetion. Lecture Notes in Mathematics,1998,1681:153-159
[4] Wu Jiabang,Hao Shengwang. On equality of the adequate stopping time and the coefficient stopping time of n in the 3N+1 conjecture. J. Huazhong Univ. of Sci. & Tech.(Nature Science Edition),2003,31(5):114-116(in Chinese with English Abstract).
[5] Belaga,Mignotte. Embedding the 3x + 1 Conjecture in a 3x + d Context. Experimental Mathematics,1998,7(2) 145-151
[6] John Simons,Benne de Weger. Theoretical and computational bounds for m-cycles of the 3n + 1 problem. Acta Arith,2005,117 (1), 51-70
[7] Mandelbrot BB. The fractal geometry of nature[M]. San Fransisco: Freeman W H,1982,1-122
[8] PeJL.The 3x+1 fractal[J]. Computers and graphics,2004,25(3) 431-435
[9] Dumont JP,Reiter CA. Visualizing generalized 3x+1 function dynamics[J]. Computers and Graphics,2001,25(5):553-595
[10]王兴元,于雪晶.基于分形可视化方法研究广义3x+1函数的动力学特性.自然科学进展2007,17(4):529-535
[11]李向华,王钲旋. 3x+1推广函数构造广义M集及其艺术分形图像.计算机辅助设计与图形学学报,2007,19(4):419-424
[12]王钲旋,王巧龙,冯月萍,等.一个3x+1推广函数在实轴上的不动点与生成的分形图象.第十一届全国图象图形学学术会议,上海,2003:346-349
[13]王则柯.复平面上计算超越函数零点的一种有效算法[J].中山大学学报, 1981年,第3期: 15-21
[14] Yunliang Long, Edward K.N.Yung. Kuhn Algorithm: Ultraconvenient Solver to Complex Polynomial and Transcendental Equations without Initial Value Selection[J].International Journal of RF and Microwave Computer-Aided Engineering, 2002, 12(6): 540-547
[15]黄永念.Mandelbrot集及其广义情况的整体解析特性.中国科学(A辑),1991,(8):823~830.
[16] Gujar U G,Bhavsar V C. Fractal images from z←zα+c in the complex C-plane[J].Computers&Graphics,1991,15(3):441-449.
[17] Dhurandhar S V,Bhavsar V C,Gujar U G. Analysis of Z-plane fractal images from z←zα+c forα< 0 [J]. Computers & Graphics,1993,17(1):89-94.
[18] Shirriff K W. An investigation of fractals generated by z→z-n+c [J]. Computers &Graphics,1993,17(5):603-607.
[19] Wang XY, Liu XD, Zhu WY, Gu SS. Analysis of c-plane fractal images from for z←zα+c (α<0). Fractals, 2000,8(3): 307~314.
[20]朱志良,焉德军,朱伟勇.复迭代的广义Mandelbrot集.东北大学学报(自然科学版),2000,21(5):469~472.
[21]谭建荣,程锦.复映射z = zα+c(α≥2)的广义M集及其对称周期检测法[J].软件学报,2003,14(3):666-674.
[22]朱伟勇,朱志良,刘向东等.周期芽苞Fibonacci序列构造M-J混沌分形图谱的一族猜想[ J].计算机学报,2003,26(2): 221~226.
[23]朱志良,曹林,朱伟勇等.广义M-集周期芽苞Fibonacci序列的拓扑不变性[J].东北大学学报(自然科学版), 2002,23(4): 307~310.
[24]朱伟勇,宋春林,邓学工等. Fibonacci序列构造z-2+c广义M-J混沌分形图谱及其标度不变性的研究[J].计算机学报,2004,27(1): 52~57
[25]王兴元,负实数阶广义M集内部结构的探讨[J]计算机辅助设计与图形学学报2001,13(10): 868-873
[26]刘向东,焉德军,朱伟勇等.广义M-J集的界与J-集Hausdorff维数的估计[J].应用数学和力学,2001,22(11):1187-1192
[27]刘鸿雁,隋涛,徐喆等. Fibonacci序列构造广义M-J混沌分形图谱周期性的研究[J].中国图象图形学报,2008,13(3):536-540
[28]章立亮,广义M-J集的边界构造及分维数计算[J].小型微型计算机系统,2008,29(7):1338-1342
[29]王兴元,骆超.一个非解析复映射的广义Mandelbrot集[J].大连理工大学学报,2009,49(1):52-57
[30]胡纪阳,胡瑞安,具有周期性的分形图象及其生成算法,工程图学学报,1991年第2期15-18
[31]陈宁,朱伟勇构造高阶广义M─分形图及对称逃逸时间算法,东北大学学报(自然科学版),1996年6月第17卷第3期225-229
[32]陈宁,朱伟勇构造高阶广义Julia分形图及旋转逃逸时间算法,东北大学学报(自然科学版),1997年2月第18卷第1期94-97
[33]陈宁,复迭代z←(?)+c构造上半平面分形图及“Escher”极限图,计算机研究与发展,2000年2月第37卷第2期214-217
[34]陈宁,朱伟勇.复迭代z←e iπ2zw+c (w=α,+iβ)构造M集,计算机研究与发展,1997年12月,第34卷第12期899~907
[35] Chen Ning,Zhu Weiyong. Bud-sequence conjecture on M fractal image and M-J conjecture between c and z planes from z←e iπ2zw+c (w=α+iβ),Computers &Graphics, 1998, 22(4) 537~546
[36]秦宣云,管继虹,任波等.广义Julia集关于迭代参数的对称性分析,计算机辅助设计与图形学学报,2007年7月第19卷第7期927-930
[37]秦宣云,任波.逃逸时间法生成Julia集的算法分析和具体实现,计算机工程与应用,2007年2月第43卷第5期30-32
[38]吴尚智,任小康.用加速逃逸时间算法构造Julia集图形,计算机应用与软件,2006年5月第23卷第5期119-120
[39]章立亮,构造广义M-J集的邻域逃逸时间算法,工程图学学报,2008年3月第3期109-115
[40]姜卓睿,陈幼均.基于埃特金加速算法实现的Julia集分形图形,计算机应用与软件,2008年4月第25卷第4期212-214
[41] K Falconer. Fractal Geometry: Mathematical Foundations and Applications, Second Edition[M]. John Wiley @ Sons, Inc, 2003, 1-296