数值分析方程求根课件.ppt

《数值分析方程求根课件.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）的迭代函数为）的迭代函数为 求导得求导得 当当时时故迭代格式（故迭代格式（1 1）是发散的。）是发散的。分析分析:迭代格式（迭代格式

3、（2 2）的迭代函数为）的迭代函数为 当当时时由由知知当当时，时，所以迭代格式（所以迭代格式（2 2）是收敛的。）是收敛的。迭代格式（迭代格式（3 3）的迭代函数为）的迭代函数为当当时时 由由时，时，知知当当所以迭代格式（所以迭代格式（3 3）也是收敛的。）也是收敛的。结论结论:通过以上算例可以看出对迭代函数通过以上算例可以看出对迭代函数所得到的所得到的若小于若小于1 1，则收敛；且上界越小收敛速度越快。，则收敛；且上界越小收敛速度越快。求导，求导，的上界若是大于的上界若是大于1 1，则迭代格式发散；，则迭代格式发散；构造不同迭代方法求 X2-3=0的根x*=sqrt(3)4.加速收敛技术加速

4、收敛技术 L越小迭代法的收敛速度越快，因此，可以从越小迭代法的收敛速度越快，因此，可以从寻找较小的寻找较小的L来改进迭代格式以加快收敛速度。来改进迭代格式以加快收敛速度。思思路路(1).松弛法松弛法引入待定参数引入待定参数，将将 作等价变形为作等价变形为 将方程右端记为将方程右端记为，则得到新的迭代格式，则得到新的迭代格式 由定理由定理2知知 为了使新的迭代格式比原来迭为了使新的迭代格式比原来迭代格式收敛得更快，只要满足代格式收敛得更快，只要满足且且 越小，所获取的越小，所获取的L就越小，就越小，迭代法收敛的就越快，因此我们希望迭代法收敛的就越快，因此我们希望。可取可取，若记，若记 则则上上式

5、可改写为式可改写为 称为称为松弛因子松弛因子，这种方法称为，这种方法称为松弛法松弛法。为使迭代速度加快，。为使迭代速度加快，需要边计算边调整松弛因子。由于计算松弛因子需要用到微商，需要边计算边调整松弛因子。由于计算松弛因子需要用到微商，在实际应用中不便使用，具有一定局限性。若迭代法是线性收在实际应用中不便使用，具有一定局限性。若迭代法是线性收敛的，当计算敛的，当计算 不方便时，可以采用不方便时，可以采用埃特金加速公式。埃特金加速公式。(2).埃特金加速公式埃特金加速公式设迭代法是线性收敛，由定义知设迭代法是线性收敛，由定义知成立，故当成立，故当 时有时有 由此可得由此可得 的近似值的近似值（2

6、.3.1）由此获得比由此获得比 和和 更好的近似值更好的近似值，利用利用（2.3.1）序列序列 的方法称为的方法称为(3).Steffensen 加速法：加速法：将将Aitken加速公式与不动点迭代相结合，可得加速公式与不动点迭代相结合，可得（2.3.4）式构造式构造埃特金（埃特金（AitkenAitken）加速方法）加速方法。利用（利用（2.3.4）式构造序列）式构造序列 的方法称为的方法称为Steffensen加速方法。加速方法。即每进行两次不动点迭代，就执行一次即每进行两次不动点迭代，就执行一次Aitken加速。加速。k xk yk zk 0 1.5000 2.3750 12.3965

7、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.3247clcclear 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);%dis

8、p(x1);if(abs(x0-x1)=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-x2)=dtol)break;end endend5迭代过程的收敛速度迭代过程的收敛速度 设由某方法确定的序列设由某方法确定的序列xk收敛于方程的根收敛于方程的根x*，如果存在正实数如果存在正实数p，使得，使得（C C为非零常数）为非零常数）定义：定义：则称序列则称序列xk收敛于收敛于x*的收敛速度是的收敛速度是p阶的阶的，或称该方法，或称该方法具有具有p 阶阶收收敛速度敛速度。当。当p=1时，称该方法为时，称该方法为线性（一次）收

9、敛线性（一次）收敛；当当p=2时，称方法为时，称方法为平方（二次）收敛平方（二次）收敛；当；当1 p 2或或C=0,p=1时，称方法为时，称方法为超线性收敛超线性收敛。3 3 牛顿法牛顿法一、牛顿法的迭代公式一、牛顿法的迭代公式 考虑非线性方程考虑非线性方程 原理：原理：将非线性方程线性化将非线性方程线性化 Taylor 展开展开取取 x0 x*，将将 f(x)在在 x0 做一阶做一阶Taylor展开展开:，在在 x0 和和 x 之间。之间。将将(x*x0)2 看成高阶小量，则有：看成高阶小量，则有：只要只要 f C1，且每步迭代都有，且每步迭代都有 ，而且而且则则 x*就是就是 f(x)的根

10、。的根。公式（公式（9.4.19.4.1）称为）称为牛顿迭代公式。牛顿迭代公式。构造迭代公式构造迭代公式x*x0 x1x2xyf(x)二、牛顿法的几何意义二、牛顿法的几何意义三、牛顿法的收敛性三、牛顿法的收敛性定理定理4：设设f(x)在在a,b上存在二阶连续导数且满足下列条件上存在二阶连续导数且满足下列条件：（1）f(a)f(b)0则由则由（2.4.1）确定的牛顿迭代序列确定的牛顿迭代序列xk二阶收敛于二阶收敛于f(x)在在a,b上的唯一单根上的唯一单根x*。注：注：注：注：Newton法的收敛性依赖于法的收敛性依赖于x0 的选取。的选取。x*x0 x0 x0并得出了并得出了 例例3 Leon

11、ardo于于1225年研究了方程年研究了方程 用牛顿迭代格式用牛顿迭代格式所以，所以，。clcclear allf=inline(x.3+2*x.2+10*x-20);g=inline(3*x.2+4*x+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迭代法可能发散。为了防止迭迭代法可能发散。为了防止迭代发散，可以将代发散，可

12、以将Newton迭代法与下山法结合起来使用，放宽迭代法与下山法结合起来使用，放宽初值初值的选取范围，即将（的选取范围，即将（2.4.1）式修改为：）式修改为：其中，其中，称为下山因子，选择下山因子时，希望称为下山因子，选择下山因子时，希望 满足下满足下山法具有的单调性，即山法具有的单调性，即这种算法称为这种算法称为Newton下山法。下山法。在实际应用中，可选择在实际应用中，可选择。六、六、牛顿法的变形牛顿法的变形1 1、牛顿下山法、牛顿下山法牛顿下山法的计算步骤：牛顿下山法的计算步骤：（1 1）选取初始近似值）选取初始近似值x x0 0；（2）取下山因子取下山因子 =1=1；（3）计算计算（

13、4）计算）计算f(xk+1)，并比较，并比较 与与 的大小，分以下二种情况的大小，分以下二种情况1）若）若 ，则当，则当 时，取时，取x*xk+1，计算过程结束；，计算过程结束；当当 时，则把时，则把 xk+1 作为新的作为新的 近似值，并返回到（近似值，并返回到（3）。）。2）若）若 ，则当，则当 且且|f(xk+1)|，取，取x*xk，计算过程结束；，计算过程结束；否则若否则若 ，而，而 时，则把时，则把xk+1加上一个适当选定的小正数，加上一个适当选定的小正数，即取即取xk+1+作为新的作为新的xk值，并转向（值，并转向（3）重复计算；当）重复计算；当 ；且；且 时时，则将下山因子缩小一

14、半，取，则将下山因子缩小一半，取/2代入，并转向（代入，并转向（3）重复计算。）重复计算。y=f(x)x0 x1x2x*牛顿迭代法每迭代一次都需计算函数值牛顿迭代法每迭代一次都需计算函数值 和导数值和导数值 计算量比较大；且迭代过程中计算计算量比较大；且迭代过程中计算 时，仅利用了时，仅利用了 点的信息，点的信息，而没有充分利用已经求出的而没有充分利用已经求出的；在导数计算比较麻烦；在导数计算比较麻烦或难以求出时，或难以求出时，迭代格式构造迭代格式构造(2)构造方法：将构造方法：将Newton迭代格式中的导数用差商代替。迭代格式中的导数用差商代替。2、割线法、割线法：(1)(1)构造思想：用割线的斜率代替牛顿迭代法中切线的斜率；构造思想：用割线的斜率代替牛顿迭代法中切线的斜率；设法避开导数值的计算，因此可以采用设法避开导数值的计算，因此可以采用离散牛顿法（割线法）离散牛顿法（割线法）。一个自然的想法就是在充分利用一个自然的想法就是在充分利用“旧信息旧信息”的同时，的同时，切线斜率切线斜率 割线斜率割线斜率初值初值 x0 和和 x1。x0 x1x2割线法的几何意义割线法的几何意义