數(shù)值分析lec非線性方程組解法實(shí)用教案

1、第十講非線性方程組的迭代(di di)解法第三章非線性方程(fngchng)與非線性方程(fngchng)組的迭代解法第1頁/共36頁第一頁，共36頁。常用的求非線性方程根的方法(fngf)回顧第2頁/共36頁第二頁，共36頁。計(jì)算(j sun)框圖為：對(duì)分法（二分法）：利用對(duì)分法（二分法）：利用(lyng)連續(xù)函數(shù)的性質(zhì)進(jìn)行對(duì)連續(xù)函數(shù)的性質(zhì)進(jìn)行對(duì)分分第3頁/共36頁第三頁，共36頁。( )0( )f xxx從一個(gè)從一個(gè)(y )初值初值x0出發(fā)，計(jì)算出發(fā)，計(jì)算10()xx21()xx1()kkxx如果如果 xk收斂，即存在收斂，即存在x*, 使得使得 *limkkxx則由則由 1limlim(

2、)kkkkxx得得 *()xx即即 x*是是 (x)(x)的不動(dòng)點(diǎn)，也就是的不動(dòng)點(diǎn)，也就是 f(x) f(x) 的根。的根。第4頁/共36頁第四頁，共36頁。第5頁/共36頁第五頁，共36頁。至少至少(zhsho)二階收斂二階收斂 速度速度第6頁/共36頁第六頁，共36頁。Newton 迭代法迭代法 （二階收斂（二階收斂(shulin)） 非線性問題的最簡(jiǎn)單解法是線性近似(jn s). 將非線性方程線性化，以線性方程的解逐步逼近非線性方程的解，這就是Newton法的基本思想。第7頁/共36頁第七頁，共36頁。110000 ()() ()0)xxxxf xxxff解出 作為近似根 ：1 Newt

3、on ()(), 0, 1, 2, nnnnfnfxxxx依次產(chǎn)生迭代格式，稱法：000 ( )0()()()0 :f xf xfxxx取線性部分近似代替第8頁/共36頁第八頁，共36頁。計(jì)算步驟(bzhu)（框圖）：第9頁/共36頁第九頁，共36頁。Newton 迭代法的變體：割線(gxin)法（簡(jiǎn)化牛頓法）（1.618）11()()kkkkf xf xxx111()()()()kkkkkkkf xxxxxf xf x第10頁/共36頁第十頁，共36頁。Newton 迭代法的變體(bin t)：?jiǎn)吸c(diǎn)割線法（一階）00()()kkf xf xxx010()()()()kkkkkf xxxxxf

4、 xf x第11頁/共36頁第十一頁，共36頁。牛頓下山法：目的是解決初值的選取范圍太小這一困難。構(gòu)造迭代格式為：其中的參數(shù)滿足：這個(gè)方法(fngf)稱為牛頓下山法。其中的參數(shù)稱為下山因子：通常取 ，然后逐步減半。牛頓下山法當(dāng) 時(shí)，只有線性收斂速度，但對(duì)初值的選取卻放的相當(dāng)寬。1()()kkkkf xxxfx1()()kkf xf x11第12頁/共36頁第十二頁，共36頁。第13頁/共36頁第十三頁，共36頁。第14頁/共36頁第十四頁，共36頁。(,.,)01 12(,.,)0212.(,.,)012fx xxnfx xxnfx xxnn第15頁/共36頁第十五頁，共36頁。(,.,)01

5、 12(,.,)0212.(,.,)012fx xxnfx xxnfx xxnn第16頁/共36頁第十六頁，共36頁。()()()()(,.,)12f Xf Xf XTfXxxxn()()()111,.12()().()()(),.12fXfXfXxxxnfXiF Xn nxifXfXfXnnnxxxn第17頁/共36頁第十七頁，共36頁。第18頁/共36頁第十八頁，共36頁。112212140.111408xxxexxx()1(1)( )12(0)(1)( )( )22111(10.1)4(0,0)11() 48kxkkkkkxxexxxx例子(l zi)：第19頁/共36頁第十九頁，共36

6、頁。x=0.0y=0.010 x1=x y1=y x=0.25*(1+y1-0.1*exp(x1) y=0.25*(x1-0.125*x1*x1) write(10,*) x,y if (abs(x-x1)+abs(y-y1).lt.0.00000001) then goto 15endif goto 1015 end第20頁/共36頁第二十頁，共36頁。第21頁/共36頁第二十一頁，共36頁。. * , ,)*,( , 1*)( ,* * : )()0(XXXXXGXGXG收斂于迭代序列對(duì)則存在開球可導(dǎo)在且內(nèi)有一不動(dòng)點(diǎn)在設(shè)knnSDSSDRRD定定理理第22頁/共36頁第二十二頁，共36頁。

7、(1)( )( )1( )()()kkkkXXF XF X第23頁/共36頁第二十三頁，共36頁。),()( )(1)()() 1(kkkkXFXFXX牛頓迭代公式：.Jacobi)( )( 212221212111)(矩陣的稱為其中XFXFnnnnnnkxfxfxfxfxfxfxfxfxf)( 局部二階收斂性定定理理第24頁/共36頁第二十四頁，共36頁。計(jì)算步驟(bzhu)（框圖）：第25頁/共36頁第二十五頁，共36頁。.)0 . 1 , 5 . 1 (, 052),(, 032),( )0(222121221211Txxxxfxxxxfx初值用牛頓法求解方程組 例例,1422821)(

8、 ,2421)(1212121xxxxxxxFxF：解解.)4(25128)(2)(,453)(2)( )(1)(2)(2)(2)(12)(12)(2)(2) 1(2)(1)(2)(2)(2)(12)(12)(2)(1) 1(1kkkkkkkkkkkkkkkkkkxxxxxxxxxxxxxxxxxx.逐次迭代得結(jié)果kx (k)0123(1.5, 1.0)T(1.5, 0.75)T(1.488095, 0.755952)T(1.488034, 0.755983)T第26頁/共36頁第二十六頁，共36頁。2221( )23xyxyzF xxyzyxeze2( )21xyyxzF xyzxzyxze

9、e222123xyxyzxyzyxeze例：用牛頓法解方程組第27頁/共36頁第二十七頁，共36頁。取初始值（取初始值（1 1，1 1，1 1），計(jì)算），計(jì)算(j (j sun)sun)如下如下N x y z0 1.0000000 1.0000000 1.0000000012.1893260 1.5984751 1.393900621.8505896 1.4442514 1.278224031.7801611 1.4244359 1.239292441.7776747 1.4239609 1.237473851.7776719 1.4239605 1.237471161.7776719 1.4

10、239605 1.2374711第28頁/共36頁第二十八頁，共36頁。簡(jiǎn)化牛頓法。目的是避免(bmin)計(jì)算迭代公式中繁雜的導(dǎo)數(shù)，解決方法與一元函數(shù)牛頓法類似，即將所有導(dǎo)數(shù)取為固定值，如迭代初值的導(dǎo)數(shù)值。(0)(0)(0)( )( )( )( )1121121(0)(0)(0)( )( )( )( )2122121(0)(0)(0)( )( )( )( )12121(,)(,)0(,)(,)0(,)(,)0nkkkknniiinkkkknniiinkkkknnnniiif xxxf xxxxxfxxxfxxxxxfxxxfxxxxx(1)( )( )(1,2, )kkkiiixxxin(1)

11、( )(0)1( )()()kkkxxfxf x第29頁/共36頁第二十九頁，共36頁。與單個(gè)方程的情形類似，牛頓法中 f 的導(dǎo)數(shù)的元素用合適(hsh)的差商來近似，如就可得到(d do)擬牛頓法或弦截法。( )( )( )12( )( )( )( )( )( )11( )( )( )( )(1)( )11( )(1)(,)(,)(,)2(,)(,)kkkjnikkkkkkjiinjiinikkkkkkjinjinkkiifxxxxfxxhxfxxhxhfxxxfxxxxx或第30頁/共36頁第三十頁，共36頁。若用格式(g shi)(1)( )( )1( )( ()()kkkkkxxf xf

12、 x其中下山(xi shn)因子(0,1k合適地選取(xunq)使得(1)( )()()kkf xf x就得到牛頓下山法。若用格式1(1)( )( )()kkkkxxA f x，其中kA是1kA的簡(jiǎn)單修正，且滿足( )(1)( )(1)()()()kkkkkA xxf xf x則得到Broyden算法。特別，若取1TkkAAuv，其中u,v 是待定的列向量，使其滿足上式，則得到秩一Broyden算法。比如( )(1)( )(1)11()(,()()TkkkkkkkTyAs sAAsxxyf xf xs s其中第31頁/共36頁第三十一頁，共36頁。小結(jié) 1、本章的目的是求解形如 f (x)=0 的方程，而其核心方法是將所要求(yoqi)解的方程變形為 x = (x)，利用 (x) 為壓縮映射，通過迭代求出其解。2、變形中切記要恒等變形！3、在恒等變形中，為使變形得到的函數(shù) (x) 為壓縮映射，一個(gè)技巧是利用待定參數(shù)。4、恒等變形的一種重要格式是牛頓迭代，證明其迭代收斂階的一個(gè)常用技巧是泰勒展開。5、n維空間