Ｎｅｗｔｏｎ分形的原理及Ｍａｔｌａｂ实现
作者：张健徐聪全付勇智
来源：《电脑知识与技术》2009年第24期
摘要:详细推导了复平面上Newton迭代法的原理和计算公式,用MATLAB编制程序实现了Newton迭代算法,得到了一些奇异、绚丽的分形图形。
对《数学实验》课程有一定的参考价值。
关键词:Newton迭代法;分形;Matlab;数学实验
中图分类号:TP312文献标识码:A文章编号:1009-3044(2009)24-6997-03
The Principles of Newton Fractal and it's Realization Using MATLAB
ZHANG Jian, XU Cong-quan, FU Yong-zhi
(Department of Basic Courses, Southwest Forestry College, Kunming 650224, China)
Abstract: The Principles and formulas of Newton fractal was explained,fractal graphics of Newton iteration was created using Matlab.
Key words: newton iteration; fractal; Matlab; mathematical experimental
分形是非线性科学的一个重要分支,应用于自然科学和社会科学的众多领域。
其中,分形图形以其奇异、绚丽多彩的特点,广泛应用于纺织印染、广告设计、装潢设计、计算机美术教学等领域[1]。
很多分形图形都是用迭代的方式实现的,Newton迭代法就是其中的一种。
由Newton迭代法产生的分形图形称为Newton分形[2]。
很多文献都对Newton分形进行了介绍,但都没有详细的计算公式和算法说明,读者很难编制相应程序。
本文详细介绍了复平面上Newton迭代法的原理和计算公式,设计了相应的实现算法,并用Matlab编制程序实现了Newton分形的绘制,生成了一些奇异、瑰丽的分形图形。
由于国内高校《数学实验》课程大多采用Matlab软件,同时很少涉及分形图形的实验,因此,Newton分形的Matlab实现可以丰富《数学实验》课程的内容,对数学类、计算机类、艺术类学生和教师有一定的参考价值。
1 Newton迭代法
17世纪,牛顿创立了一种依靠简单迭代计算求方程f(x)=0的根的方法[3]:
任取一点x0,利用公式(1)进行迭代,若存在,则序列xt收敛于方程f(x)=0在x0附近的一个根。
我们把复数z应用到公式(1)上,就得到了复平面上的Newton迭代公式:
现在,取一个较简单的函数f(z)=zn-1,则f(z)的一阶导数f’(z)=nzn-1,代入公式(2)得:
根据复数的三角表示式,可记zt为:
zt=xt+iyt=|zt|(cosθ+isinθ) (4)
其中,称为复数zt的模,θ为复数zt的辐角的主值,-π≤θ≤π。
辐角主值θ的计算方法如下[1]:
由复变函数知识可知:
将(5)、(6)两式代入(3)得:
即有:
(8)
式(8)就是编写程序时需要的迭代计算公式。
2 Newton分形的生成算法
在复平面上取定一个窗口,将此窗口均匀离散化为有限个点,将这些点记为初始点z0,按公式(8)进行迭代。
其中,大多数的点都会很快收敛到方程f(z)=zn-1的某一个零点,但也有一些点经过
很多次迭代也不收敛。
为此,可以设定一个正整数M和一个很小的数δ,若果当迭代次数小于M 时,就有两次迭代的两个点的距离小于δ,即
则认为z0是收敛的,即点z0被吸引到方程f(z)=zn-1=0的某一个根上;反之,当迭代次数达到了M,而|zt+1-zt|>δ时,则认为点z0是发散(逃逸)的。
这就是逃逸时间算法的基本思想。
当点z0比较靠近方程f(z)=zn-1的根时,迭代过程就很少;离得越远,则迭代次数越多甚至不收敛[2]。
由此设计出函数f(z)=zn-1的Newton分形生成算法步骤如下:
1)设定复平面窗口范围,实部范围为[a1,a2],虚部范围为[b1,b2],并设定最大迭代步数M和判断距离δ;
2)将复平面窗口均匀离散化为有限个点,取定第一个点,将其记为z0,然后按公式(8)进行M 次迭代。
每进行一次迭代,按公式(9)判断迭代前后的距离是否小于δ,如果小于δ,根据当前迭代的次数M选择一种颜色在复平面上绘出点z0;如果达到了最大迭代次数M而迭代前后的距离仍然大于δ,则认为z0是发散的,选择白色(也可换为其他颜色)在复平面上绘出点z0。
3)在复平面窗口上取定第二个点,将其记为z0,按第(2)步的方法进行迭代和绘制。
直到复平面上所有点迭代完毕。
3 Matlab程序设计
Matlab是由MathWorks公司与1984年推出的数学软件,原意为“矩阵实验室”。
Matlab以其强大的功能和良好的开放性、面向问题性、易学易用等特点,越来越被广大科研人员和工程计算人员以及高校学生和老师所重视[4]。
国内外《数学实验》课程大多采用Matlab软件作为计算工具,为此,我们使用Matlab编制了绘制Newton分形的程序。
程序由3个函数组成:
1)主函数newton.m:
function f = newton(n)
m=13;%迭代次数
a1=-2;%复平面窗口实部范围
a2=2;
b1=-1.5; %复平面窗口虚部范围
b2=1.5;
delta=0.01 %收敛判定距离
hold on
for i = a1:0.02:a2
for j =b1:0.02:b2
%对每一个点,调用迭代函数,返回收敛时间(即判断为收敛时的迭代次数M) f=f_iterat(i,j,n,m,delta);
if f > 0%用7种颜色(不含白色)绘制收敛点
switch rem(f,7) %求f除以7的余数
case 0
plot(i,j,'b.')%蓝色
case 1
plot(i,j,'c.')%青色
case 6
plot(i,j,'y.')%黄色
end
end
end
hold off
2)Newton迭代函数f_iterat.m:
%参数说明:(x,y)为点的实部与虚部,n为方程的幂次,m为最大迭代次数,delta为收敛判断距离
function f=f_iterat(x,y,n,m,delta)
delta = 0.01;%收敛判断距离
f=0; %赋初值为0,表示发散
for i = 1:m
p = sqrt(x*x+y*y);%计算复数的模
seta = f_arg(x,y); %计算复数的辐角
x2=((n-1)*p*cos(seta)+p^(1-n)*cos((1-n)*seta))/n;%实部
y2=((n-1)*p*sin(seta)+p^(1-n)*sin((1-n)*seta))/n;%虚部
dis = sqrt((x2-x)^2+(y2-y)^2); %计算迭代前后两点的距离
if dis < delta %收敛
f=i; %返回收敛时间
break%结束循环
end
x=x2;
y=y2;
end
其中,函数f_arg(x,y)为计算复数z=x+iy的辐角主值θ的函数,根据公式(5)不难写出。
4 实验结果
在MATLAB命令窗口中,输入“>> newton(3)”或“>> newton(4)”,即可绘制出函数f(z)=z3-1
或f(z)=z4-1对应的Newton分形的图形:
在图1中,白色区域表示发散点所组成的区域,彩色区域为收敛点组成的区域。
收敛区域内的点,由于收敛时间的不同,所呈现的颜色不同,构成了一幅五彩斑斓、奇异复杂的图形。
输入其他的n,则可绘制出函数f(z)=zn-1对于的Newton分形,举例如下:
5 结论
用VB、VC等程序设计语言编写的Newton分形生成程序需要两个窗口:绘图窗口和参数窗口,然后要建立绘图窗口到参数窗口之间的映射[5-6]。
而用MATLAB编制的程序直接在参数窗口(复平面窗口)中绘图,所编制的程序简单易懂,所绘制的图形奇异瑰丽、绚丽多彩,体现了数学、计算机、艺术三者的结合,学生有很大的吸引力,对有关专业的教师、学生以及分形爱好者有一定的参考作用。
而且,只要稍微改动迭代参数,如迭代次数M、判断距离?啄、复窗口范围等,所得到的图形会出现很多意想不到的变化,很适合做为理工科《数学实验》课程的内容。
参考文献:
[1] 秦宣云,任波.逃逸时间法生成Julia集的算法分析和具体实现[J].计算机工程与应
用,2007,43(5):30-32.
[2] 李水根.分形[M].北京:高等教育出版社,2004:20-30.
[3] 孙博文.分形算法与程序设计[M].北京:科学出版社,2004:61-91.
[4] 曾建军,李世航,王永国等.MATLAB语言与数学建模[M].合肥:安徽大学出版社,2005:1-30.
[5] 姜卓睿,宋中山,苏斌.基于重根牛顿迭代法和比较算法实现的分形图形的研究 [J].电脑开发与应用,2008;21(7):12-13.
[6] 吴运兵,李勇.牛顿迭代法在分形图形生成上的应用研究[J].西安科技大学学
报,2005,25(3):365-367.。