迭代式与不动点

《迭代式与不动点》由会员分享，可在线阅读，更多相关《迭代式与不动点（8页珍藏版）》请在装配图网上搜索。

1、迭代式与不动点【实验目的】1. 了解迭代的基本概念。2. 了解不动点的基本概念。3. 学习掌握MATLAB软件有关的命令。【实验内容】计算数列、3,、：3, (t v：3 ,的极限【实验准备】1. 迭代的基本概念迭代数列：迭代就是把给定的函数f连续不断地反复作用在初值。上。通过迭代，我 们会得到一个迭代数列：a, f (a), f (f (a), f (f (f (。),把迭代数列记为x ,x,x，,X，。012 n迭代格式：迭代一种机械的重复动作，很适合于计算机的运算特点，因此迭代算法在各种数值方法中处于核心地位。迭代可以表示成如下的形式：X0 = a, X + = f (X ),n = 1

2、,2,3,称为由函数f导出的迭代格式。2. 不动点的基本概念对迭代格式的两端取极限n 8，当极限存在时，得到方程x = f (x).函数f的意义是 把自变量x映射成因变量y，而上式的意义时表示x在影射f得像不发生改变.因此称该方 程为不动点方程，方程的根称为函数f的不动点.3. 压缩映像原理定理1设y = f (x)把区间a,b映射成a,b,并且存在0 q 1,使得对于任意e a,b,有|f (气)-f (x2) qx1 -x2|,(1) *内存在唯一的不动点x*，满足x* = f (x*);(2)对任意初始值x0 e a,b,迭代序列x+1 = f (x)收敛于x* ；(3) x - x*

3、qx - x*qn定理2设y = f (x)在间。,b内可导，且y G a,b.若存在0 q 1,使得对任意 x g a, b均有f(x) q，则定理1的结论成立.由拉格朗日中值定理可知，定理2是定理1的特例.定理不仅给出了收敛条件，而且还给出 了收敛误差的估计.可以看出,q越小收敛越快.但是要确定对任意x g a,b均有I f(x) q 显然不太方便.在x*的附近，有如下局部收敛定理：定理3设y = f (x)在x*的一个领域内连续且|f(x*)| clear;x=3for i=1:10x=sqrt(x)end可算得迭代数列的前10项：7321, 1.3161, 1.1472, 1.0711

4、, 1.0349, 1.0173, 1.0086, 1.0043, 1.0021, 1.0011可见此数列的极限为1.本练习也可用while语句,while循环一般用于事先不能确定循环次数的情况.while循环 的一般形式为：while表达式语句体end只要表达式的值为1(真),就执行while与end之间的语句体，直到表达式的值为0(假)时终 止该循环.通常，表达式的值为标量，但对数组值也同样有效，此时，数组的所有元素都为真，才执 行while与end之间的语句体.本练习中,相应的MATLAB代码为：n=0; eps=1.0e-5; x=3;while abs(x-sqrt(x)epsx=s

5、qrt(x); n=n+1;endx, n结果为x =1.0000, n =16.这说明迭代到第16次后，数列的前后两项之间的误差小于10-5擞列 收敛到1.一般说来，在事先不知道迭代是否收敛时，可用for语句.如果知道迭代是收敛的,为了控制 迭代计算的误差，用while语句是比较合适的.迭代过程启发我们，设法将方程y = f=0变 形为不动点方程=g3)，就有可能利用迭代法求出方程的根.练习2利用迭代法求解方程x 3 - x -1 = 0.先请读者画出函数f (x) = x3 -x-1的图形，观测函数的图形可以看出，在区间1，2方 程有唯一正根.1 迭代格式1方程变形为X = (x +1)3

6、，先用for语句，初值设为1.5,相应的MATLAB代码为：clear;x=1.5;for i=1:10x=(x+1)八(1/3)end可算得迭代数列的前10项：1.3572, 1.3309, 1.3259, 1.3249, 1.3248, 1.3247, 1.3247, 1.3247, 1.3247, 1.3247可见此迭代格式是收敛的,方程的根约为1.3247.进一步，如果要控制计算误差，比如说要 使得计算误差小于10-5,可用while语句，相应的MATLAB代码为：n=0; eps=1.0e-5; x=1.5;while abs(x-(x+1)八(1/3)epsx=(x+1)八(1/3

7、); n=n+1;endx, n计算结果为x =1.3247,n =6,说明只需进行6次迭代，就可达到所要求的精度.1 + x 迭代格式2方程变形为x =，用for语句，初值设为1.5,相应的MATLAB代码为：x 2clear;x=1.5;for i=1:10x=(x+1)/x八2end可算得迭代数列的前10项：1.1111, 1.7100, 0.9268, 2.2433, 0.6445, 3.9590, 0.3164, 13.1504, 0.0818, 161.5755 可见此迭代格式是不收敛的.1迭代格式3方程变形为x,用for语句，初值设为1.5,相应的MATLAB代码为:X 2 1c

8、lear;x=1.5;for i=1:10x=1/(xA2-1)end可算得迭代数列的前10项：0.8000, -2.7778, 0.1489, -1.0227, 21.8055, 0.0021, -1.0000, 1.1256e+005, 7.8922e-011, -1 可见此迭代格式也是不收敛的.这个例子表明，迭代格式是否收敛的关键是迭代函数的选取.迭代函数选取恰当，迭代过 程会迅速地收敛到不动点，否则，若迭代函数选择不当,收敛速度可能很慢,甚至导致迭代发散.练习3利用压缩映像原理考察迭代格式X0 = 0, x J2,n = 1,2,3,的收敛性.此迭代格式相应的迭代函数为g(x) = 2

9、TX，首先画出函数y = x, y = g(x)的图形，相应的MATLAB代码为：clear;x=0:0.1:4;y1=x; y2=(2+x).八0.5;plot(x,y1,x,y2)相应的图形为图16.1迭代函数的图形从图形中可以看出，迭代函数g(x) =j2 + x在区间0,4,满足定理2的条件，故迭代数列必定收敛到唯一的不动点.且在区间0,4 内(甚至在更大范围内)与处置的选择无关.请加以验证.如果用while语句，取迭代精度为10-5,当初值为1时，相应的MATLAB代码为：n=0; eps=1.0e-5; x=1.0;while abs(x-(x+2)八(1/2)epsx=(x+2)

10、八(1/2); n=n+1;endx, n计算结果为x=2.0000, n=9,说明只需进行9次迭代，就可达到所要求的精度.1 2:练习4 (一种计算平方根的迭代算法)验证不动点方程X = (X + )的不动点是、2。2 X,、1 ,2、首先作迭代函数g(x) = c (X + )的图形，相应的MATLAB代码为： 2 X clear;x=1.2:0.01:2;y1=x; y2=0.5*(x+2./x);plot(x,y1,x,y2)相应的图形为2/1.8/1.61.4/1.2 1.21.41.61.82图16.2迭代函数的图形再分析迭代的收敛性，由于当x 1时，|广(X)=2 - x. n=

11、0; eps=1.0e-10; x=2.0;while abs(x-0.5*(x+2/x)epsx=0.5*(x+2/x); n=n+1;endvpa(x,30), n计算结果为ans =1.4142135 62 3746898 698271934 3359 , n=4,比较 *2 的30位精确值.u2 =1.4142135 62 37 309504880168 8 72 421可见迭代的收敛速度非常快，仅迭代了4次,就精确到了 12位小数，经一步计算可知.迭代5次, 就精确到25位小数！为能了解迭代数列X收敛或发散的原因，通过几何图形观测使用迭代格式 nXo = a, X +1 = f (X

12、), n = 1,2,3,进行迭代的过程。在图16.3中，不动点由直线y = X与曲线y = f (x)的交点确定。根据初始值Xo可得曲线y = f 3)上的点匕，其纵坐标为气，依箭头方向经过直线y = x折射后得到曲线上的点P，其纵坐标为x，再依箭头方向进行下去，得到点列P , P , P ,。点列出间向交点逼 12234近，因此迭代数列是收敛的。图16.4中的情况则完全不同，按同样的方法产生的点列P,P ,P ,P，逐渐远离交点 1234而去，可知迭代数列是不收敛的。在另外一些情况下，迭代过程将会周期地进行，请读者自行验证。图16.3和16.4称为蛛 网图。图16.3收敛的数列图16.4发

13、散的数列下面介绍一下迭代收敛的速度即不动点迭代的收敛阶的有关知识.对迭代函数y = g (x)，在不动点x *处作泰勒展开2!g(x ) = g(x*) + g(x*)(x -x*) + g(x*)(x -x*)2 k1/ 、/、n!+1g (n) (x*)(x - x*)n +n!k注意到 xk+1 = g(xk )，x* = g(x*), k = xk x*，上式改写为，/、1 , , 、1,、 k 1 = g (x *) k + 五 g (x *) 2 + . + - g (n)(x *) n + .若g(x*)。0,则limA = g(x*)，迭代数列x 为1阶收敛； nk s ck若

14、 g(x*) = 0,g(x*)丰 0,则limk+1 = g(x*),迭代数列x 为2阶收敛;k * 2nk若 g(x*) = g(x*)=g(p-1)(x*) = 0,g(p)(x*)。0，则 lim+t = g(p)(x*),迭代 k * pk数列xn为p阶收敛.11_2在练习2 中,g (x) = (x + 1)3, g(x) = 3(x + 1) 3 丰 0,迭代 1 阶收敛；,、12、 ，/ 、 11 ，,、 c在练习4中,g(x)= (x + ),g (x) = -一,g (x*) = 0,迭代2阶收敛.2x2 x 2【练习与思考】1. 用f (x) = ax + b构造线性迭代

15、数列x, n = 1,2,3,(1) 在什么条件下，迭代对任意初值x：都收敛？(2) 影响收敛性的主要因素是什么?它与f (x)的一阶导数有什么关系？(3) 收敛速度的快慢由什么量决定？2. 利用不动点方法求解一阶线性方程ax + b = 0.(1) a, b在什么范围时，能保证迭代收敛？(2) a,b在什么范围时，迭代会出现循环？3. 为求解方程x3 - x2 -1 = 0在x = 1.5附近的一个根，使用以下不动点方程构造迭代 格式进行计算，并分析收敛性：11(1) x =1+x 21,、1(2)x = (1 + x2)3(3)x =.t x 14,数列 x 满足 x +1 = 2(x + a)(a 0, x0 0).n(1) 验证数列x收敛；n(2) 利用此迭代式近似计算a的平方根；(3) 使用迭代格式x= x； + 曾 (a 0,x 0)计算*,并比较迭代结果.n+13 x 2 + a0n5 .设 f (x) = x5 + x 1. 证明方程f (x) = 0在区间0,1内有且仅有一个根；(2) 用迭代格式x = 1 - x5构造迭代式，迭代过程收敛吗？(3) 对迭代格式x = (1-人)x -人(1 - x 5),选择人值进行迭代,观测收敛速度，记录实验结 果.