精华区文章阅读

发信人: qpcwth (独翅鸟), 信区: Science
标  题: 《分形艺术》48
发信站: 哈工大紫丁香 (2001年11月03日18:19:33 星期六), 站内信件

第六章复平面上的迭代
6.6 牛顿法求根
    求代数方程f(x)=0的精确解是很难的事情，特别地当f(x)是高于5次的多项式时，
不能通过多项式系数的有限次运算得到根的表达式。在这种情况下求方程的近似解却是
可以的，牛顿法就是一种比较好的逐次逼近法。牛顿法在求根过程中逼近很快，用计算
机计算是十分方便的。
    牛顿法的本质仍然是“以直代曲”，首先猜测一个值x_1，用它近似方程的根 c,用
过(x_1,f(x_1))点的切线
y=f(x_1)+f′(x_1)(x-x_1)
近似代替曲线f(x),然后用切线方程
y=f(x_1)+f′(x_1)(x-x_1)=0
的根
x=x_2=x_1-f(x_1)/f′(x_1)
近似代替曲线方程的根c,这样就得到c的第二个近似值。依此类推可得到迭代公式
x_(n+1)=x_n-f(x_n)/f′(x_n).
在复平面上选定一个区域，对于任意初始点(除去(0，0)点)，讨论它在牛顿法迭代过程
中的行为。一般选f(x)=x^p-1,其中p是大于2的正整数。这样，迭代公式还可以改写为

x_(n+1)=[(p-1)x^p_n+1]/px^(p-1)_ n.
对于x^3-1=0，有三个根：
x_1=1,
x_2=[-1+SQRT(3)i]/2，
x_3=[-1-SQRT(3)i]/2，
三个根均匀地分布在单位圆上。这三个根周围构成三个“吸引盆”(attractor basin)，
初始点迅速被吸引到盆内，最后停止在三点之一。用计算机迭代，以当前点到三个终点
的距离远近为标准，标上不同的颜色，就能得到美丽的分形图，特别是在120°线、240
°线附近有复杂的“项链”结构。
    迭代过程照例要先将复数分解为实部和虚部：
x→2x/3+(x^2-y^2)/[3(x^2+y^2)^2]，
y→2y/3-2xy/[3(x^2+y^2)^2]
    以f(x)=x^3-1为例，用牛顿法生成分形图形的一个简单的PASCAL源程序如下：
{NEWTON.PAS, Newton Method 1994-02-02}
Uses Graph,Crt;
Label 30;
Var
i,np,nq,gd,gm,k: integer;
x1,y1,x,y,nx,ny,cm:real;
Function  dist(x,y:real):real;｛定义一个距离函数｝
BEGIN
dist:=x*x+y*y;
END;
BEGIN
gd:=VGA;  gm:=VGAHI;
InitGraph(gd,gm,'d:\pascal');
FOR nx:=-160 TO 160  do
FOR ny:=-160 TO 160 do
BEGIN
     x:=nx/80;   y:=ny/80;
     for k:=1 to 30 do
     BEGIN
       if (nx=0) and (ny=0) then goto 30;｛排除(0，0)点｝
       cm:=3*dist(x,y)*dist(x,y);
       newx:=2*x/3+(x*x-y*y)/cm;
       newy:=2*y/3-2*x*y/cm;
       x:=newx; y:=newy;
     END;
     if dist(x-1,y) < 0.03 then putpixel(nx+200,200-ny,2);
     if dist(x+1/2,y-sqrt(3)/2) < 0.03 then putpixel(nx+200,200-ny,3);
     if dist(x+1/2,y+sqrt(3)/2) <0.03 then putpixel(nx+200,200-ny,4);
30:
     if KeyPressed then exit;
END;
CloseGraph;
readln;
END.
    以上程序采用浮点运算，速度是比较慢的。如果每迭代一次就计算一次距离，则速
度会更慢。为了使不同吸引区域有不同的颜色，并且能够表现收敛速度，必须做更多的
距离计算，但得到的图形也更美丽。特别是将分界处的“项链”放大来看，会得到精致
的结构。
实际上可以把牛顿法扩展到形式为x^y-r=0的复迭代，其中x和y均为复数，r为实数，也
可以为复数。特别应当考虑y为纯虚数时的迭代，这时有极漂亮的“编织结构”。

--
心事浩茫连广宇,于无声处听惊雷

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.229.154]

Science 版 (精华区)