《数值分析方程求根课件.ppt》由会员分享，可在线阅读，更多相关《数值分析方程求根课件.ppt（37页珍藏版）》请在三一办公上搜索。
1、数值分析,第二章 方程求根（2）,2014年11月2日,clcclear allx=-3:0.05:3;f=inline(x.2-1);y=f(x);plot(x,x,LineWidth,3);hold onplot(x,y,k,LineWidth,3);grid onx0=-2.732;%1.618,1.619,0.618,0.619%=-2.732,0.732x1=x0;y0=-3;y1=y0;for i=1:80 y1=f(x1);plot(x0 x1,y0 y1,r);x0=x1;y0=y1;x1=y1;plot(x0 x1,y0 y1,r);x0=x1;y0=y1;end,迭代法的收
2、敛性,求方程,在,内的根,例：,。,解：,原方程可以等价变形为下列三个迭代格式,由迭代格式（1）,取初值,得,由迭代格式（2）,取初值,得,结果精确到四位有效数字，迭代到,得到收敛结果。,由迭代格式（3）,取初值,得,结果精确到四位有效数字，迭代到,得到收敛结果。,迭代格式（1）的迭代函数为,求导得,当,时,故迭代格式（1）是发散的。,分析:,迭代格式（2）的迭代函数为,当,时,由,知当,时，,所以迭代格式（2）是收敛的。,迭代格式（3）的迭代函数为,当,时,由,时，,知当,所以迭代格式（3）也是收敛的。,结论:,通过以上算例可以看出对迭代函数,所得到的,若小于1，则收敛；且上界越小收敛速度越
3、快。,求导，,的上界若是大于1，则迭代格式发散；,构造不同迭代方法求 X2-3=0的根x*=sqrt(3),4.加速收敛技术,L越小迭代法的收敛速度越快，因此，可以从寻找较小的L来改进迭代格式以加快收敛速度。,思路,(1).松弛法,引入待定参数,，将,作等价变形为,将方程右端记为,，则得到新的迭代格式,由定理2知,为了使新的迭代格式比原来迭,代格式收敛得更快，只要满足,且,越小，所获取的L就越小，,迭代法收敛的就越快，因此我们希望,。,可取,，若记,则上式可改写为,称为松弛因子，这种方法称为松弛法。为使迭代速度加快，需要边计算边调整松弛因子。由于计算松弛因子需要用到微商，在实际应用中不便使用，
4、具有一定局限性。若迭代法是线性收敛的，当计算 不方便时，可以采用埃特金加速公式。,(2).埃特金加速公式,设迭代法是线性收敛，由定义知,成立，故当,时有,由此可得,的近似值,（2.3.1）,由此获得比,和,更好的近似值,，利用（2.3.1）,序列,的方法称为,(3).Steffensen 加速法：,将Aitken加速公式与不动点迭代相结合，可得,（2.3.4）,式构造,埃特金（Aitken）加速方法。,利用（2.3.4）式构造序列,的方法称为Steffensen加速方法。,即每进行两次不动点迭代，就执行一次Aitken加速。,k xk yk zk 0 1.5000 2.3750 12.3965
5、 1.0000 1.4163 1.8409 5.2389 2.0000 1.3557 1.4914 2.3173 3.0000 1.3289 1.3471 1.4444 4.0000 1.3248 1.3252 1.3271 5.0000 1.3247 1.3247 1.3247,clcclear alldtol=1e-5;%容差x1=1.5;nMax=10;f=inline(x.3-1);disp(k xk yk zk);for i=1:nMax x0=x1;y1=f(x1);z1=f(y1);disp(i-1 x1 y1 z1);x1=x0-(y1-x0)2/(z1-2*y1+x0);%d
6、isp(x1);if(abs(x0-x1)=dtol)break;endend,例2 试用简单迭代法和Steffensen加速法求方程,在,附近的根，精确至四位有效数。,解：记,，简单迭代法公式为：,计算得,Aitken加速公式,计算得,clcclear alldtol=1e-8;%容差x0=0.5;nMax=20;f=inline(exp(-x);x(1)=x0;x2=x0;m=0;for i=1:nMax x0=x(i);x1=x2;x(i+1)=f(x0);if(i=2)m=m+1;x2=x(m)-(x(m+1)-x(m)2/(x(m+2)-2*x(m+1)+x(m);if(abs(x1
7、-x2)=dtol)break;end endend,5迭代过程的收敛速度,设由某方法确定的序列xk收敛于方程的根x*，如果存在正实数p，使得,（C为非零常数）,定义：,则称序列xk收敛于x*的收敛速度是p阶的，或称该方法具有p 阶收敛速度。当p=1时，称该方法为线性（一次）收敛；当p=2时，称方法为平方（二次）收敛；当1 p 2或C=0,p=1时，称方法为超线性收敛。,3 牛顿法,一、牛顿法的迭代公式 考虑非线性方程,原理：将非线性方程线性化 Taylor 展开,取 x0 x*，将 f(x)在 x0 做一阶Taylor展开:,，在 x0 和 x 之间。,将(x*x0)2 看成高阶小量，则有：
8、,只要 f C1，且每步迭代都有，而且,则 x*就是 f(x)的根。公式（9.4.1）称为牛顿迭代公式。,构造迭代公式,x*,x0,x1,x2,二、牛顿法的几何意义,三、牛顿法的收敛性,定理4：设f(x)在a,b上存在二阶连续导数且满足下列条件：（1）f(a)f(b)0则由（2.4.1）确定的牛顿迭代序列xk二阶收敛于f(x)在a,b上的唯一单根x*。,注：Newton法的收敛性依赖于x0 的选取。,x*,并得出了,例3 Leonardo于1225年研究了方程,用牛顿迭代格式,clcclear allf=inline(x.3+2*x.2+10*x-20);g=inline(3*x.2+4*x+
9、10);x1=1.5;x0=2;dtol=1e-8;while(abs(x0-x1)dtol)x0=x1;x1=x0-f(x0)/g(x0);disp(x0 x1);end,由于Newton迭代法的收敛性依赖于初值,的选取，如果,离方程的根,较远，则Newton迭代法可能发散。为了防止迭,代发散，可以将Newton迭代法与下山法结合起来使用，放宽,初值,的选取范围，即将（2.4.1）式修改为：,其中，,称为下山因子，选择下山因子时，希望,满足下,山法具有的单调性，即,这种算法称为Newton下山法。,在实际应用中，可选择,。,六、牛顿法的变形,1、牛顿下山法,牛顿下山法的计算步骤：,（1）选取
10、初始近似值x0；,（2）取下山因子=1；,（3）计算,（4）计算f(xk+1)，并比较 与 的大小，分以下二种情况,1）若，则当 时，取x*xk+1，计算过程结束；当 时，则把 xk+1 作为新的 近似值，并返回到（3）。,2）若，则当且|f(xk+1)|，取x*xk，计算过程结束；,否则若，而 时，则把xk+1加上一个适当选定的小正数，,即取xk+1+作为新的xk值，并转向（3）重复计算；当；且 时，则将下山因子缩小一半，取/2代入，并转向（3）重复计算。,计算量比较大；且迭代过程中计算,时，仅利用了,点的信息，,或难以求出时，,迭代格式构造,(2)构造方法：将Newton迭代格式中的导数用差商代替。,2、割线法：,(1)构造思想：用割线的斜率代替牛顿迭代法中切线的斜率；,设法避开导数值的计算，因此可以采用离散牛顿法（割线法）。,一个自然的想法就是在充分利用“旧信息”的同时，,切线斜率割线斜率,初值 x0 和 x1。,割线法的几何意义,
