数值分析方程求根

1、数值分析第二章 方程求根（2） 2014年11月2日 xyy = xx*y= (x)x0p0 x1p1 xyy = xx*y= (x)x0p0 x1p1 xyy = xx*y= (x)x0p0 x1p1xyy = xx*y= (x)x0p0 x1p1yxy *xababx)(xy bxa| )(|kx)(1kkxxclcclear 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、=-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|*)( |*)()(|*|xxxxxxkkk 11 Lx | )( | 由|*|xxLk |*|xxLk 12|*|.xxLk 01*|*|*|xxxxLxxkkk 0|*|*|xxLxxkk 1迭代法的收敛性迭代法的收敛性kx1kx)(kx)(1kx 324100f xxx11.5，*x求方程求方程在在内的根内的根例：例：。解：解：

3、原方程可以等价变形为下列三个迭代格式原方程可以等价变形为下列三个迭代格式2313111040,1,2,.1100,1,2,.22100,1,2,.34kkkkkkkkxxxxkxxkxkx （1） （ ） （ ）由迭代格式由迭代格式 （1） 231104kkkkxxxx01.25x 取初值取初值得得 123.04687526.04005xx 311102kkkxxx01.25x 1021324354657687981091.418351.336661.379481.357861.368981.363311.366211.364731.365491.36510 xxxxxxxxxxxxxxxxx

4、xxx，10 x由迭代格式由迭代格式 （2） 取初值取初值得得 结果精确到四位有效数字，迭代到结果精确到四位有效数字，迭代到得到收敛结果。得到收敛结果。 1104kkxxx01.25x 102132431.380131.363341.365471.36512xxxxxxxx4x 由迭代格式（由迭代格式（3） 取初值取初值得得 结果精确到四位有效数字，迭代到结果精确到四位有效数字，迭代到得到收敛结果。得到收敛结果。 23104xxxx 21 83xxx 1,1.5x 2381101xxx 迭代格式（迭代格式（1 1）的迭代函数为）的迭代函数为 求导得求导得 当当时时故迭代格式（故迭代格式（1 1

5、）是发散的。）是发散的。分析分析: : 31102xx1,1.5x 33111.5 ,110 1.5 ,10 1221.287,1.51,1.5x 2330,410 xxx 33323401008xxxx 迭代格式（迭代格式（2 2）的迭代函数为）的迭代函数为 当当时时由由1,1.5x 2231.51.50.65561410 1.5x知知当当时，时， 所以迭代格式（所以迭代格式（2 2）是收敛的。）是收敛的。 104xx1,1.5x 10101.5 ,1,1.54141.348,1.4141,1.5x 迭代格式（迭代格式（3 3）的迭代函数为）的迭代函数为当当时时 2532131040,104

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

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

8、可取可取 =()1kkx ，若记，若记 11kk则则上上式可改写为式可改写为1kkkkkxxx =(1-)+()n 称为称为松弛因子松弛因子，这种方法称为，这种方法称为松弛法松弛法。为使迭代速度加快，。为使迭代速度加快，需要边计算边调整松弛因子。由于计算松弛因子需要用到微商，需要边计算边调整松弛因子。由于计算松弛因子需要用到微商，在实际应用中不便使用，具有一定局限性。若迭代法是线性收在实际应用中不便使用，具有一定局限性。若迭代法是线性收敛的，当计算敛的，当计算 不方便时，可以采用不方便时，可以采用埃特金加速公式。埃特金加速公式。 ( )x(2). 埃特金加速公式埃特金加速公式设迭代法是线性收敛

9、，由定义知设迭代法是线性收敛，由定义知*1* lim0kkkxxcxx成立，故当成立，故当 k 时有时有 *12*1kkkkxxxxxxxx由此可得由此可得 的近似值的近似值 x2121()2kkkkkkkxxxxxxxx（2.3.1） 由此获得比由此获得比 1,kkxx和和 2kx更好的近似值更好的近似值 kx，利用利用（2.3.1）序列序列 kx的方法称为的方法称为(3). Steffensen 加速法：加速法： 将将Aitken加速公式与不动点迭代相结合，可得加速公式与不动点迭代相结合，可得(1)(2)(1)1112(1)1(2)(1)111(),(),0,1,2kkkkkkkkkkkx

10、xxxxxxkxxxx （2.3.4） 式构造式构造埃特金（埃特金（AitkenAitken）加速方法）加速方法。利用（利用（2.3.4）式构造序列）式构造序列 kx的方法称为的方法称为Steffensen加速方法。加速方法。即每进行两次不动点迭代，就执行一次即每进行两次不动点迭代，就执行一次Aitken加速。加速。 k xk yk zk 0 1.5000 2.3750 12.3965 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

11、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);% disp(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) br

12、eak; end endend5迭代过程的收敛速度迭代过程的收敛速度 设由某方法确定的序列设由某方法确定的序列xk收敛于方程的根收敛于方程的根x*，如果存在正实数如果存在正实数p，使得，使得Cxxxxpkkk*1*lim（C C为非零常数）为非零常数）定义：定义：则称序列则称序列xk收敛于收敛于x*的收敛速度是的收敛速度是p阶的阶的，或称该方法，或称该方法具有具有p 阶阶收收敛速度敛速度。当。当p = 1时，称该方法为时，称该方法为线性（一次）收敛线性（一次）收敛；当当p = 2时，称方法为时，称方法为平方（二次）收敛平方（二次）收敛；当；当1 p 2或或C=0,p=1时，称方法为时，称方法为

13、超线性收敛超线性收敛。 3 3 牛顿法牛顿法一、牛顿法的迭代公式一、牛顿法的迭代公式 考虑非线性方程考虑非线性方程 0)(xf原理：原理：将非线性方程线性化将非线性方程线性化 Taylor 展开展开取取 x0 x*，将将 f (x)在在 x0 做一阶做一阶Taylor展开展开:20000)(! 2)()()()(xxfxxxfxfxf ， 在在 x0 和和 x 之间之间。将将 (x* x0)2 看成高阶小量，则有：看成高阶小量，则有：)*)()(*)(0000 xxxfxfxf )()(*000 xfxfxx 只要只要 f C1，且每步迭代都有，且每步迭代都有 ， 而且而且*limxxkk 则

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

15、于x0 的选取。的选取。x*x0 x0 x032210200 xxx并得出了并得出了 1.368808107x 例例3 Leonardo于于1225年研究了方程年研究了方程 用牛顿迭代格式用牛顿迭代格式10(), 0,1,2,()1.5 kkkkf xxxkfxx所以，所以， *1.368808107x。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);en

16、d由于由于Newton迭代法的收敛性依赖于初值迭代法的收敛性依赖于初值 0 x的选取，如果的选取，如果 0 x离方程的根离方程的根 x较远，则较远，则Newton迭代法可能发散。为了防止迭迭代法可能发散。为了防止迭代发散，可以将代发散，可以将Newton迭代法与下山法结合起来使用，放宽迭代法与下山法结合起来使用，放宽初值初值0 x的选取范围，即将（的选取范围，即将（2.4.1）式修改为：）式修改为： 1(), 0,1,2,()kkkkf xxxkfx其中，其中， 01称为下山因子，选择下山因子时，希望称为下山因子，选择下山因子时，希望 ()kf x满足下满足下山法具有的单调性，即山法具有的单调

17、性，即1()() , 0,1,2,kkf xf xk这种算法称为这种算法称为Newton下山法。下山法。在实际应用中，可选择在实际应用中，可选择 ,01kk。六、六、牛顿法的变形牛顿法的变形1 1、牛顿下山法、牛顿下山法牛顿下山法的计算步骤：牛顿下山法的计算步骤：（1 1）选取初始近似值）选取初始近似值x x0 0；（2）取下山因子取下山因子 = 1 = 1；)( )(1kkkkxfxfxx（3）计算计算)(1kxf)(kxf（4）计算）计算f (xk+1)，并比较，并比较 与与 的大小，分以下二种情况的大小，分以下二种情况)() 1kkxfxf21kkxx21kkxx1）若）若 ，则当，则当

18、 时，取时，取x* xk+1，计算过程结束，计算过程结束；当；当 时，则把时，则把 xk+1 作为新的作为新的 近似值，并返回到（近似值，并返回到（3）。）。)()1kkxfxf 2）若）若 ，则当，则当 且且|f(xk+1)| ，取，取x* xk，计算过程结束；，计算过程结束；11)(kxf否则若否则若 ，而，而 时，则把时，则把xk+1加上一个适当选定的小正数，加上一个适当选定的小正数，11)(kxf即取即取xk+1+ 作为新的作为新的xk值，并转向（值，并转向（3）重复计算；当）重复计算；当 ；且；且 时时，则将下山因子缩小一半，取，则将下山因子缩小一半，取 /2代入，并转向（代入，并转向（3）重复计算。）重复计算。 1y=f(x)x0 x1x2x*牛顿迭代法每迭代一次都需计算函数值牛顿迭代法每迭代一次都需计算函数值 ()kf x和导数值和导数值 ()kfx计算量比较大；且迭代过程中计算计算量比较大；且迭代过程中计算 1kx时，仅利用了时，仅利用了 kx点的信息，点的信息，而没有充分利用已经求出的而没有充分利用已经求出的 12,kkxx；在导数计算比较麻烦；在导数计算比较麻烦或难以求出时，或难以求出时， 迭代格式构造迭代格式构造 (2) 构造方法：将构造方法：将Newton迭代格