实验四函数的迭代、混沌与分形[实验目的]1. 认识函数的迭代；2. 了解混沌和分形.迭代在数值计算中占有很重要的地位,了解和掌握它是很有必要的.本实验将讨论用Newton迭代求方程根的问题,以及迭代本身一些有趣的现象.§1 基本理论1.1 迭代的概念给定某个初值,反复作用以同一个函数的过程称为迭代.函数f(x)的迭代过程如下:x0,x1=f(x0),x2=f(x1),……..,x n=f(x n-1)…..,它生成了一个序列{x n}迭代序列.许多由递推关系给出的数列,都是递推序列.例如数列.X0=1,x n=1+1/(1+x n-1) (n=1,2,…………..)是由函数f(x)=1+1/(1+x)=(2+x)/(1+x)取初值为1所得的迭代序列.1.2 迭代序列的收敛性定理设函数f(x)满足:(1)对任意x∈(a,b),f(x)∈(a,b);(2)f(x)在(a,b)内可导,且存在常数L使得|f(x)'|=L<1,则当初值x0∈(a,b)时,由f(x)生成的迭代序列收敛.在迭代函数f(x)连续的条件下,如果迭代数列收敛,则它一定收敛于方程x=f(x)的根.该方程的根也称函数f(x)的不动点.设x*为f(x)的不动点,f(x)'在x*的附近连续,若|f(x*)'|<1,则称不动点x*是稳定的;若f(x*)'=0,则称不动点x*是超稳定的.在超稳定点x*附近,迭代过程x n+1=f(x n)收敛到x*的速度是非常快的.1.3 Newton迭代法设函数g(x)具有一阶导数,且g(x)'≠0,则函数f(x)=x-g(x)/g(x)'的迭代称为Newton迭代,若函数f(x)存在不动点,则它一定是方程g(x)=0的根,故Newton迭代法可用来求方程g(x)=0的根.§2 实验内容与练习2.1 迭代的收敛对于函数迭代,最重要的问题是迭代序列的收敛性.一般说,迭代序列是否收敛取决于迭代函数与初值.作为一个例子，我们用来讨论用Newton迭代法求函数g（x）=（x-17）5/3（x-5）-2/3的根，其Mathematica程序为：Clear[g，x]；g[x_]：=（x-17）^(5/3)*(x-5)^(-2/3);f[x_]=Factor[x-g(x)]/D[g[x],x]];x0=5.5;n=20;For[i=1,i<=n,i++,x0=N[f[x0]];Print[i,”“,x0,”“,D[f[x],x]/.x->x0]]执行结果见表4.1.表4.1的结果说明迭代序列收敛于g(x)的零点17.我们注意到程序中取的迭代处值为5.5,如果其它的数作为初值,所得的迭代序列是否收敛于17呢?我们可以取其它初值做实验,结果得到表4.2(表中第三列是迭代序列的前6位有效数字首次为17.0000的步数).从表4.2中可看出,只要初值不取5,迭代序列都收敛于17,且收敛速度与初值的选取关系不大.前面程序中使用的f(x)为g(x)的化简过的Newton迭代函数,用Mathematica命令可检查出它为(25x-85)/(x+3)(注意,这个式子扩充了原迭代函数在x=5,x=17处的定义),解方程f(x)=x.得到x=17,与x=5.即17和5是f(x)的两个不动点,有前面的讨论知这两个不动点是有区别的:对于17,不管初值取为多少(只要不为5),迭代序列总是收敛于它;而对于5,只要初值取为5时,迭代序列才以它为极限,这样一种现象在函数的迭代中普遍存在,为方便区分起见,我们给这样两种点各一个名称:像17这样的所有附近的点在迭代过程中都趋向于它的不动点,称为吸引点;而像5这样的所有附近的点在迭代过程中都远离它的不动点,称为排斥点.上面的f(x)=(25x-85)/(x+3)是一个分式线性函数,对于一般的分式线性函数,迭代序列是否总是收敛呢?练习1 编程判断函数f(x)=(x-1)/(x+1)的迭代序列是否收敛.在上节我们已经指出,如果迭代序列收敛,一定收敛到函数的某个不动点,这就是说,迭代函数存在不动点是迭代序列收敛的必要条件.那么如果迭代函数存在不动点,迭代序列是否一定收敛呢?练习2 先分别求出分式线性函数f1(x)=(x-1)/(x+3),f2(x)=(-x+15)/(x+1)的不动点,再编程判断它们的迭代序列是否收敛.运用上节的收敛定理可以证明:如果迭代函数在某不动点处具有连续的导数且导数值介于-1与1之间,那么取该不动点附近的点为初值所得到的迭代序列一定收敛到该不动点.练习3 你能否说明为什么17是f(x)=(25x-85)/(x+3)的吸引点,而5是f(x)的排斥点?尽量多找些理由支持这个结论.练习4 能否找到一个分式线性函数(ax+b)/(cx+d),使它产生的迭代序列收敛到给定的数?用这种办法计算2.2.2迭代的”蜘蛛图”对函数的迭代过程,我们可以用几何图象来直观地显示它.在xoy平面上,先作出函数y=f(x)与y=x的图象,对初值x0,在曲线y=f(x)上可确定一点p0,它以x0为横坐标,过p0引平行x轴的直线,设该直线与y=x交与点Ｑ1作平行于y轴的直线它与曲线y=f(x)的交点记为p1,重复上面的过程,就在曲线y=f(x)上得到点列p1,p2,……，如图４.１，不难知道，这些点的横坐标构成的序列x0,x1,x2,……，xn……就是迭代序列.若迭代序列收敛,则点列p1,p2,……趋向于y=f（x）与y=x的交点p*，因此迭代序列是否收敛，可以在图上观查出来，这种图因其形状像蜘蛛网而被称为“蜘蛛网”图。
图4.2显示了分式线性函数f（x）=（25x-85）/（x+3）取初值为5.5的迭代过程，从图中可以看出该迭代是收敛的，且收敛到不动点17。
图4.2的“蜘蛛网”图可通过下面的程序获得Clear[f]；图4.2 函数f（x）=（25x-85）/（x+3）的f[x_]:=(25*x-85)/(x+3);g1=Plot[f[x],{x,-10,20}, PlotStyle->RGBColor[1,0,0],DisplayFunction->Identity];g2=Plot[x,{x,-10,20}, PlotStyle->RGBColor[0,1,0],DisplayFunction->Identity];x0=5.5;r={};r0=Graphics[{RGBColor[0,0,1],Line[{{x0,x0},{x0,f[x0]},{f{x0},f[x0]}}]}]];x0=f[x0]];Show[g1,g2,r,r0,PlotRange->{-1,20},DisplayFunction->$DisplayFunction]练习五通过观察图4.2或通过改变初值重画f（x）=（25x-85）/（x+3）的蜘蛛网图，你是否能说明为什么该函数迭代的收敛速度与初值的选取关系不大？对于其他收敛的分式线形函数的迭代，是否有类似的结论？f[x_]:=(25*x-85)/(x+3);g1=Plot[f[x],{x,-10,20}, PlotStyle->RGBColor[1,0,0],DisplayFunction->Identity];g2=Plot[x,{x,-10,20}, PlotStyle->RGBColor[0,1,0],DisplayFunction->Identity];x0=5.5;r={};r0=Graphics[{RGBColor[0,0,1],Line[{{x0,x0},{x0,f[x0]},{f{x0},f[x0]}}]}]];x0=f[x0]];Show[g1,g2,r,r0,PlotRange->{-1,20},DisplayFunction->$DisplayFunction]练习五通过观察图4.2或通过改变初值重画f（x）=（25x-85）/（x+3）的蜘蛛网图，你是否能说明为什么该函数迭代的收敛速度与初值的选取关系不大？对于其他收敛的分式线形函数的迭代，是否有类似的结论？2.3认识混沌迭代序列若不收敛，它可能出现两种情况：1.迭代次数充分大时，迭代序列出现周期性重复。
即存在自然数N，k>0, 使x N+k=x N，这样迭代序列便成为：x0，x1，。
x N，x N+1，。
，x N+k-1，x N，x N+1，。
，x N+k-1。
.此时，x N，x N+1，。
，x N+k-1称为周期为k的循环；而初始点x0称为预周期点。
例如，对函数f(x)=-2+sin1.5x取初值x=0的迭代，可画出其蜘蛛网图如4.3所示，由该图可判断该迭代得到了一个周期为2的循环，0是该循环的一个预周期点。
2.序列没有规律`杂乱无章，称之为混沌。
例如，图4.4是函数f(x)= -2+sin1.5x取初值为-0.7的迭代图，可看出该迭代产生了混沌。
图4.3 迭代出现循环图4.4迭代出现混沌混沌具有两个特性：非随机性和对初始值的敏感性。
若初始值产生微小的误差，则该误差随迭代序列次数呈指数性增长，因此尽管迭代序列由初值和迭代函数完全决定，但随迭代次数的增加，它与随机序列并无多大差别，故混沌又称做确定性的随机运动。
练习6 通过观察图形进一步了解函数f(x)=a+sinbx的迭代（多取几组参数及初值）。
练习7 下列函数的迭代是否会产生混沌？（1）2x , 0<=x<=1/2,f(x)=2(1-x), 1/2<x<=1;(2)f(x)=1/2(x+a/x).练习8 函数f(x)=ax(1-x)(0<=x<=1)称为Logistic映射，试从“蜘蛛网”图观察它取初值为x0=0.5产生的迭代序列的收敛性，将观察记录填入表4.3，若出现循环，请指出它的周期。
2.4 人口增长的Logistic模型Logistic映射来源于对人口变化规律的研究，下面我们简单加以介绍。
世界人口的增长，受到自然资源的约束，设地球允许承载的总人数为，以x（t）表示时刻为t时的人口总人数。
我们容易想到，在t时刻到时刻t+△t的人口平均增长速度，与t时刻的人口数成正比，也与容许增长的人口数成正比，故[x（t+△t）-x（t）]/ △t=kx（t）（x m-x(t)）, (4.1)其中k为比例系数，表示人口增长系数相关的系数。
设以一年为一时间单位，当△t=1时，上面的式子变为x（t+1）-x（t）= kx（t）（x m-x(t)），即x（t+1）=（1+kx m）x（t）（1-kx（t）/1+kx mk*x（t+1）/（1+kx m）=（1+kx m）k/1+kx m x（t）（1-kx（t）/1+kx m以n代替t，并令x n= k/1+kx m x（n），则有x n+1=（1+kx m）x n（1-x n）令α=1+kx m，可得x n+1=αx n（1-x n）此式正是由Logistic映射构成的迭代式。