收敛与混沌.doc

收敛与混沌
第三章 收敛与混沌----迭代迭代
产生的数列
可能是：(1)收敛；(2)周期性变化；(3)分岔；(4)混沌。
如：用
迭代产生的数列
是否收敛？ 答：
0.4000 0.7200 0.6048 0.7171 0.6087 0.7146 0.6119 0.7125 0.6146 0.7106 0.6169 0.7090 0.6190 0.7075 0.6208 0.7062 0.6224 0.7050 0.6239 0.7040 0.6252 不收敛。
§3—1 不动点与迭代
1．什么是迭代定义：任意给定一个输入
，由一个函数表达式
得到一个输出
；再将
作为新的输入
，由同一个
得到下一个输出；重复。这中对某个函数规则
反复将输出作为新输入的重复执行过程就称为迭代。一个迭代过程的数学表示为

其中，
称为迭代函数，产生的数列
称为迭代数列，
称为迭代初值。
迭代函数
是关键，迭代数列的变化趋势主要由它决定。
例1：
，则迭代式为
，
分别取
=0,0.1,0.8,1,2,99计算，得下面数列：
0,0,0,0,0,0,0,0,0,0,……
0.1,0.31,0.56,0.74,0.86,0.93,0.96,0.98 0.99 0.99 …...
0.8 0.89 0.94 0.97 0.98 0.99 0.99 ……
1 1 1 1 1 1 1 …….
2,1.41,1.18,1.09,1.04,1.02,1.01,1.00,1.00,…..
99,9.94,3.15 1.77 1.33 1.15 1.07 1.03 1.01 1.00 1.00 …
结论：迭代函数
对于初值
保持不动（称为不动点）；对于其余初值（非1的任何正数）都收敛于1,
问：
时，迭代规律？
2．不动点定义：若存在点
，满足
，则称点
为迭代函数
的一个不动点。
对于同一个
，其不动点不一定存在、不一定唯一。
在某个不动点附近取初值，迭代可能收敛于这个不动点，称它为吸引的（如例1中的不动点1）；也可能远离此不动点，称它为排斥的（如例1中的不动点0）。
§3—2 用图示法体现迭代数列的规律线性迭代：

二次函数迭代：

一种特殊的二次函数迭代：著名的Logistic函数

，其中，参数
在0到4之间取值对应的Logistic迭代为

本节就以Logistic迭代为例，讨论揭示迭代数列规律的图形方法。你将会看到某写全新的现象和问题，如分岔、混沌等古怪现象。
先求不动点：令
，解得两个不动点
与
再分析迭代规律：
若
，则因为“
总有
”，从而
，所以，对于任意初值
，都收敛于不动点0；
（2）若
，则对于任意初值
，都收敛于不动点
；
（3）若
，则迭代规律很乱，对于不同的
分别呈现诸如收敛、周期性震荡、分岔、混沌之类的从有规律到无规律、又从无规律到有规律等等的非常复杂的、有趣的、怪异的现象。
定义：若迭代数列中，当下标n充分大时，每隔k个数就出现周期性重复，则称此迭代为k—周期。
下面介绍刻画迭代数列规律的三种图形方法
1．线性联结图横坐标：
纵坐标：
把向邻的点用折线联结。 看书 P26 图
画 图3.1 的程序为：
a=3.8;x(1)=0.2;
for i=1:20
x(i+1)=a*x(i)*(1-x(i));
end
plot(0:20,x)
画 图3.2 的程序为：
a=[3.2,3.5,3.5644,3.8284];y =0.2*[1,1,1,1];
for i=1:10000
y=a.*y.*(1-y);
end
x(1,:)=y;
for i=1:20
x(i+1,:)=a.*x(i,:).*(1-x(i,:));
end
subplot(2,2,1),plot(0:20,(x(:,1))')
subplot(2,2,2),plot(0:20,(x(:,2))')
subplot(2,2,3),plot(0:20,(x(:,3))')
subplot(2,2,4),plot(0:20,(x(:,4))')
从线性联结图上，看不出当a=3.5644,a=3.8284时，Logistic迭代到底是几---周期的？ 用下面蛛网图就可以看清楚。
2．蛛网图先计算出
，再做下列工作：
（1）画曲线
和直线
；
出发点
，
过A做竖直线交曲线于点
，过B做水平线交直线于新的点
；再过新A做竖直线交曲线于新的点
，过新B做水平线交直线于新的点
；重复多次。
画 图3.4中第3个图 的程序为：
hold on
x=0:0.05:1;y=3.5644*x.*(1-x);
plot(x,y),plot([0,1],[0,1])
a=3.5644;x=0.2;
for i=1:10000
x=a*x*(1-x);
end
for i=1:20
y=3.5644*x.*(1-x);
plot([x,x],[x,y]),plot([x,y],[y,y])
x=y;
end
hold off
从蛛网图3.4容易看出，周期分别是2、4、8、3.
3．费根鲍姆图为了研究Logistic函数
中参数
对迭代的影响，现以参数
为横坐标、以
为纵坐标作图。（为体现规律，从迭代了10000次以后的点开始）。
画 图3.6 的程序为：
a=[2.9,3.2,3.5,3.5644,3.7,3.8284];x =0.2*[1,1,1,1,1,1];
for i=1:10000
x=a.*x.*(1-x);
end
hold on
for i=1:1000
x=a.*x.*(1-x);
for j=1:6
plot(a(j),x(j))
end
end
hold off
§3—3 分岔与混沌
上一节内容表明迭代结果很敏感地受到参数
的影响，利用费根鲍姆图可以很直观地刻画这种影响。现令
从2到4以步长h=0.02逐步取值，对
的每个值都画出迭代了10000项后的1000项的费根鲍姆图。
见书P30图3.7，借此可分析得到一些结果。
画 图3.7 的程序为：
a=2:0.02:4;x =0.2*ones(1,101);
for i=1:10000
x=a.*x.*(1-x);
end
hold on
for i=1:1000
x=a.*x.*(1-x);
for j=1:101
plot(a(j),x(j))
end
end
hold off
1．倍周期当
3时,为1—周期（即收敛）
当
3.44时,为2—周期当
3.54时，为4—周期当
3.56时，为8—周期称这种现象为倍2—周期现象。
2．分岔随着a的增大，每过一段，图形就会分岔，分岔的本质就是周期扩大2倍。
从1—周期分裂成2—周期的分岔点为a=3；
从2—周期裂成4—周期分岔点记为
；
从4—周期裂成8—周期分岔点记为
；
从8—周期裂成16—周期分岔点记为
；
2—周期的区段长为
；
4—周期的区段长为
；
8—周期的区段长为
；
通常，记
—周期的区段长为
费根鲍姆发现了下面结果：

（此数称为费根鲍姆数）
3．混沌当
时，迭代无规律，进入混沌。
在很狭窄的区段
上，迭代呈现出3—周期、倍3—周期（即6—周期、12—周期 等）。
在另一个很狭窄的区段
上，迭代呈现出5—周期、倍5—周期（即10—周期、20—周期 等）。
§3—4 二元函数迭代
由两个二元函数
构造的迭代为

此迭代将产生两个数列
，可用前面的图形法研究此迭代。
若
，则称
为二元迭代函数
的不动点。
1．高斯算术几何平均数列由两个二元函数
构造迭代
产生的数列
就是著名的高斯算术几何平均数列。
有无穷多个不动点：

结论1：对于任给的初值
，高斯算术几何平均数列总收敛，且
，极限值依赖于两个初值

结论2：
，

2．旋转数列

，

有一个不动点：（0，0）
结论：（1）
时，对任意初值，此迭代都收敛于不动点（0，0）；（2）
时，对任意初值，此迭代都不收敛。
3．海伦数列看书 图
作业,P37 操练一
图论
第十一章 图论
P167之题：写出Matlab环境下，由加权图的边权矩阵表示，转化为带权邻接矩阵表示，的函数M—文件。
解：根据边权阵
，以下由程序实现：
（1）点的个数n=？ 边的条数m=？
（2）因为，带权邻接阵中，主对角线为0，无边时为
，所以，先产生n阶方阵a，主对角线为0，其余元素为

（3）再修改a，将有边时的权替代
，输出带权邻接阵

function a=syp167hswj(e)
n1=max(e(1,:));n2=max(e(2,:));n=max(n1,n2);m=length(e(1,:));
a=ones(n,n)*inf;
for i=1:n
a(i,i)=0;
end
for j=1:m
a(e(1,j),e(2,j))=e(3,j);
a(e(2,j),e(1,j))=e(3,j);
end
最短路径
第十三章 连通图中从一个点出发到其余点的最短路径顶点
出发，到其余顶点
的最短路(最短距离记为
)
Dijkstra(狄克斯特拉)算法：
与
相邻的点中，谁最近？不妨设是
，则记录下
，令
；
与S相邻的点中，谁距离
最近？该点加入S，并记录下距离；
重复（2），直至全部顶点进入S.
完毕.
手工做 P195之例1 P197之例2
文件名：syp195
clear
a=inf*ones(6,6);
a(1,2)=6;a(1,4)=5;a(1,5)=8;a(2,3)=4;a(2,4)=2;a(3,4)=2;a(3,6)=3;a(4,6)=7;a(5,6)=10;
a(2,1)=6;a(4,1)=5;a(5,1)=8;a(3,2)=4;a(4,2)=2;a(4,3)=2;a(6,3)=3;a(6,4)=7;a(6,5)=10;
n=6;i=1;t(1)=i;jl(1)=0;ddd=ones(1,n);
zx=min(a(i,:));
for j=1:n
if a(i,j)==zx
t(2)=j;jl(j)=zx;break
end
end
[i,t(2),zx]
k=2;ddd(t(1))=0;ddd(t(2))=0;
while k<n
k=k+1;zx=inf;zx1=0;
for j=1:k-1
for l=2:n
aaa=a(t(j),l);
if ddd(l)~=0&aaa<inf
zx1=jl(t(j))+aaa;
if zx1<zx
t(k)=l;zx=zx1;zw=t(j);
end
end
end
end
ddd(t(k))=0;jl(t(k))=zx;[zw,t(k),zx]
end
函数文件：syp195hswj
function syp195hswj(a,i)
n=length(a(1,:));t(1)=i;jl(i)=0;ddd=ones(1,n);
for j=1:n
a(j,j)=inf;
end
zx=min(a(i,:));
for j=1:n
if a(i,j)==zx
t(2)=j;jl(j)=zx;break
end
end
[i,t(2),zx]
k=2;ddd(t(1))=0;ddd(t(2))=0;
while k<n
k=k+1;zx=inf;zx1=0;
for j=1:k-1
for l=1:n
aaa=a(t(j),l);
if ddd(l)~=0&aaa<inf
zx1=jl(t(j))+aaa;
if zx1<zx
t(k)=l;zx=zx1;zw=t(j);
end
end
end
end
ddd(t(k))=0;jl(t(k))=zx;[zw,t(k),zx]
end
文件名：syp197
clear
a=inf*ones(11,11);
a(1,2)=8;a(1,7)=7;a(2,3)=3;a(2,7)=6;a(3,4)=5;a(3,5)=6;
a(4,5)=1;a(4,11)=12;a(5,6)=2;a(5,10)=9;a(6,7)=9;a(6,9)=3;
a(7,3)=5;a(7,8)=10;a(8,1)=8;a(9,5)=7;a(9,8)=9;a(10,9)=2;
a(10,11)=2;a(11,5)=10;
syp195hswj(a,1)