數(shù)值分析方程求根

1、數(shù)值分析第二章 方程求根（2） 2014年11月2日 yxy *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.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

2、(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求方程求方程在在內(nèi)的根內(nèi)的根例：例：。解：解：原方程可以等價變形為下列三個迭代格式原方程可以等價變形為下列三個迭代格式2313111040,1,2,.1100,1,2,.22100,1,2,.34kkkkkkkkxxxxkxxkxkx （1）

3、 （ ） （ ）由迭代格式由迭代格式 （1） 231104kkkkxxxx01.25x 取初值取初值得得 123.04687526.04005xx 311102kkkxxx01.25x 1021324354657687981091.418351.336661.379481.357861.368981.363311.366211.364731.365491.36510 xxxxxxxxxxxxxxxxxxxx，10 x由迭代格式由迭代格式 （2） 取初值取初值得得 結(jié)果精確到四位有效數(shù)字，迭代到結(jié)果精確到四位有效數(shù)字，迭代到得到收斂結(jié)果。得到收斂結(jié)果。 1104kkxxx01.25x 10213

4、2431.380131.363341.365471.36512xxxxxxxx4x 由迭代格式（由迭代格式（3） 取初值取初值得得 結(jié)果精確到四位有效數(shù)字，迭代到結(jié)果精確到四位有效數(shù)字，迭代到得到收斂結(jié)果。得到收斂結(jié)果。 23104xxxx 21 83xxx 1,1.5x 2381101xxx 迭代格式（迭代格式（1 1）的迭代函數(shù)為）的迭代函數(shù)為 求導(dǎo)得求導(dǎo)得 當(dāng)當(dāng)時時故迭代格式（故迭代格式（1 1）是發(fā)散的。）是發(fā)散的。分析分析: : 31102xx1,1.5x 33111.5 ,110 1.5 ,10 1221.287,1.51,1.5x 2330,410 xxx 33323401008

5、xxxx 迭代格式（迭代格式（2 2）的迭代函數(shù)為）的迭代函數(shù)為 當(dāng)當(dāng)時時由由1,1.5x 2231.51.50.65561410 1.5x知知當(dāng)當(dāng)時，時， 所以迭代格式（所以迭代格式（2 2）是收斂的。）是收斂的。 104xx1,1.5x 10101.5 ,1,1.54141.348,1.4141,1.5x 迭代格式（迭代格式（3 3）的迭代函數(shù)為）的迭代函數(shù)為當(dāng)當(dāng)時時 2532131040,1040,24xxxx 由由1,1.5x 3212110 140.1414210 x時，時， 知知當(dāng)當(dāng)所以迭代格式（所以迭代格式（3 3）也是收斂的。）也是收斂的。結(jié)論結(jié)論: : x x 通過以上算例可

6、以看出對迭代函數(shù)通過以上算例可以看出對迭代函數(shù)所得到的所得到的若小于若小于1 1，則收斂；且上界越小收斂速度越快。，則收斂；且上界越小收斂速度越快。求導(dǎo)，求導(dǎo)，的上界若是大于的上界若是大于1 1，則迭代格式發(fā)散；，則迭代格式發(fā)散；構(gòu)造不同迭代方法求 X2-3=0的根x*=sqrt(3) 4. 加速收斂技術(shù)加速收斂技術(shù) L越小迭代法的收斂速度越快，因此，可以從越小迭代法的收斂速度越快，因此，可以從尋找較小的尋找較小的L來改進(jìn)迭代格式以加快收斂速度。來改進(jìn)迭代格式以加快收斂速度。思思路路(1). 松弛法松弛法引入待定參數(shù)引入待定參數(shù) 1 ，將將 ( )xx作等價變形為作等價變形為 1( )11xx

7、x將方程右端記為將方程右端記為 ( )x，則得到新的迭代格式，則得到新的迭代格式 1()kkxx由定理由定理2知知 ( )1xL為了使新的迭代格式比原來迭為了使新的迭代格式比原來迭代格式收斂得更快，只要滿足代格式收斂得更快，只要滿足( )( )xx且且 11xx|( )|( )越小，所獲取的越小，所獲取的L就越小，就越小，迭代法收斂的就越快，因此我們希望迭代法收斂的就越快，因此我們希望 0 x( )。可取可取 =()1kkx ，若記，若記 11kk則則上上式可改寫為式可改寫為1kkkkkxxx =(1-)+()n 稱為稱為松弛因子松弛因子，這種方法稱為，這種方法稱為松弛法松弛法。為使迭代速度加

8、快，。為使迭代速度加快，需要邊計(jì)算邊調(diào)整松弛因子。由于計(jì)算松弛因子需要用到微商，需要邊計(jì)算邊調(diào)整松弛因子。由于計(jì)算松弛因子需要用到微商，在實(shí)際應(yīng)用中不便使用，具有一定局限性。若迭代法是線性收在實(shí)際應(yīng)用中不便使用，具有一定局限性。若迭代法是線性收斂的，當(dāng)計(jì)算斂的，當(dāng)計(jì)算 不方便時，可以采用不方便時，可以采用埃特金加速公式。埃特金加速公式。 ( )x(2). 埃特金加速公式埃特金加速公式設(shè)迭代法是線性收斂，由定義知設(shè)迭代法是線性收斂，由定義知*1* lim0kkkxxcxx成立，故當(dāng)成立，故當(dāng) k 時有時有 *12*1kkkkxxxxxxxx由此可得由此可得 的近似值的近似值 x2121()2kk

9、kkkkkxxxxxxxx（2.3.1） 由此獲得比由此獲得比 1,kkxx和和 2kx更好的近似值更好的近似值 kx，利用利用（2.3.1）序列序列 kx的方法稱為的方法稱為(3). Steffensen 加速法：加速法： 將將Aitken加速公式與不動點(diǎn)迭代相結(jié)合，可得加速公式與不動點(diǎn)迭代相結(jié)合，可得(1)(2)(1)1112(1)1(2)(1)111(),(),0,1,2kkkkkkkkkkkxxxxxxxkxxxx （2.3.4） 式構(gòu)造式構(gòu)造埃特金（埃特金（AitkenAitken）加速方法）加速方法。利用（利用（2.3.4）式構(gòu)造序列）式構(gòu)造序列 kx的方法稱為的方法稱為Steff

10、ensen加速方法。加速方法。即每進(jìn)行兩次不動點(diǎn)迭代，就執(zhí)行一次即每進(jìn)行兩次不動點(diǎn)迭代，就執(zhí)行一次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 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

11、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) break; end endend5迭代過程的收斂速度迭代過程的收斂速度 設(shè)由某方法確定的序列設(shè)由某方法確定的序列xk收斂于方程的根收斂于方程的根x*，如果存在正實(shí)數(shù)如果存在正實(shí)數(shù)p，使得，使得Cxx

12、xxpkkk*1*lim（C C為非零常數(shù)）為非零常數(shù)）定義：定義：則稱序列則稱序列xk收斂于收斂于x*的收斂速度是的收斂速度是p階的階的，或稱該方法，或稱該方法具有具有p 階階收收斂速度斂速度。當(dāng)。當(dāng)p = 1時，稱該方法為時，稱該方法為線性（一次）收斂線性（一次）收斂；當(dāng)當(dāng)p = 2時，稱方法為時，稱方法為平方（二次）收斂平方（二次）收斂；當(dāng)；當(dāng)1 p 2或或C=0,p=1時，稱方法為時，稱方法為超線性收斂超線性收斂。 3 3 牛頓法牛頓法一、牛頓法的迭代公式一、牛頓法的迭代公式 考慮非線性方程考慮非線性方程 0)(xf原理：原理：將非線性方程線性化將非線性方程線性化 Taylor 展開展

13、開取取 x0 x*，將將 f (x)在在 x0 做一階做一階Taylor展開展開:20000)(! 2)()()()(xxfxxxfxfxf ， 在在 x0 和和 x 之間之間。將將 (x* x0)2 看成高階小量，則有：看成高階小量，則有：)*)()(*)(0000 xxxfxfxf )()(*000 xfxfxx 只要只要 f C1，且每步迭代都有，且每步迭代都有 ， 而且而且*limxxkk 則則 x*就是就是 f (x)的根。的根。公式（公式（9.4.19.4.1）稱為）稱為牛頓迭代公式。牛頓迭代公式。)()(1kkkkxfxfxx 構(gòu)造迭代公式構(gòu)造迭代公式()0kfxx*x0 x1x

14、2xyf(x)二、牛頓法的幾何意義二、牛頓法的幾何意義三、牛頓法的收斂性三、牛頓法的收斂性定理定理4： 設(shè)設(shè)f (x)在在a, b上存在二階連續(xù)導(dǎo)數(shù)且滿足下列條件上存在二階連續(xù)導(dǎo)數(shù)且滿足下列條件：（1）f (a) f (b) 0則由則由（2.4.1）確定的牛頓迭代序列確定的牛頓迭代序列xk二階收斂于二階收斂于f (x)在在a, b上的唯一單根上的唯一單根x*。Newton法的收斂性依賴于法的收斂性依賴于x0 的選取。的選取。x*x0 x0 x032210200 xxx并得出了并得出了 1.368808107x 例例3 Leonardo于于1225年研究了方程年研究了方程 用牛頓迭代格式用牛頓迭

15、代格式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);end由于由于Newton迭代法的收斂性依賴于初值迭代法的收斂性依賴于初值 0 x的選取，如果的選取，如果 0 x離方程的根離方程的根 x較遠(yuǎn)，則較遠(yuǎn)，則Newton迭代法可能發(fā)散。為了防止迭迭代法可

16、能發(fā)散。為了防止迭代發(fā)散，可以將代發(fā)散，可以將Newton迭代法與下山法結(jié)合起來使用，放寬迭代法與下山法結(jié)合起來使用，放寬初值初值0 x的選取范圍，即將（的選取范圍，即將（2.4.1）式修改為：）式修改為： 1(), 0,1,2,()kkkkf xxxkfx其中，其中， 01稱為下山因子，選擇下山因子時，希望稱為下山因子，選擇下山因子時，希望 ()kf x滿足下滿足下山法具有的單調(diào)性，即山法具有的單調(diào)性，即1()() , 0,1,2,kkf xf xk這種算法稱為這種算法稱為Newton下山法。下山法。在實(shí)際應(yīng)用中，可選擇在實(shí)際應(yīng)用中，可選擇 ,01kk。六、六、牛頓法的變形牛頓法的變形1 1

17、、牛頓下山法、牛頓下山法牛頓下山法的計(jì)算步驟：牛頓下山法的計(jì)算步驟：（1 1）選取初始近似值）選取初始近似值x x0 0；（2）取下山因子取下山因子 = 1 = 1；)( )(1kkkkxfxfxx（3）計(jì)算計(jì)算)(1kxf)(kxf（4）計(jì)算）計(jì)算f (xk+1)，并比較，并比較 與與 的大小，分以下二種情況的大小，分以下二種情況)() 1kkxfxf21kkxx21kkxx1）若）若 ，則當(dāng)，則當(dāng) 時，取時，取x* xk+1，計(jì)算過程結(jié)束，計(jì)算過程結(jié)束；當(dāng)；當(dāng) 時，則把時，則把 xk+1 作為新的作為新的 近似值，并返回到（近似值，并返回到（3）。）。)()1kkxfxf 2）若）若 ，則

18、當(dāng)，則當(dāng) 且且|f(xk+1)| ，取，取x* xk，計(jì)算過程結(jié)束；，計(jì)算過程結(jié)束；11)(kxf否則若否則若 ，而，而 時，則把時，則把xk+1加上一個適當(dāng)選定的小正數(shù)，加上一個適當(dāng)選定的小正數(shù)，11)(kxf即取即取xk+1+ 作為新的作為新的xk值，并轉(zhuǎn)向（值，并轉(zhuǎn)向（3）重復(fù)計(jì)算；當(dāng)）重復(fù)計(jì)算；當(dāng) ；且；且 時時，則將下山因子縮小一半，取，則將下山因子縮小一半，取 /2代入，并轉(zhuǎn)向（代入，并轉(zhuǎn)向（3）重復(fù)計(jì)算。）重復(fù)計(jì)算。 1y=f(x)x0 x1x2x*牛頓迭代法每迭代一次都需計(jì)算函數(shù)值牛頓迭代法每迭代一次都需計(jì)算函數(shù)值 ()kf x和導(dǎo)數(shù)值和導(dǎo)數(shù)值 ()kfx計(jì)算量比較大；且迭代過程中計(jì)算計(jì)算量比較大；且迭代過程中計(jì)算 1kx時，僅利用了時，僅利用了 kx點(diǎn)的信息，點(diǎn)的信息，而沒有充分利用已經(jīng)求出的而沒有充分利用已經(jīng)求出的 12,kkxx；在導(dǎo)數(shù)計(jì)算比較麻煩；在導(dǎo)數(shù)計(jì)算比較麻煩或難以求出時，或難以求出時， 迭代格式構(gòu)造迭代格式構(gòu)造 (2) 構(gòu)造方法：將構(gòu)造方法：將Newton迭代格式中的導(dǎo)數(shù)