数值分析lec非线性方程组解法实用教案

1、第十讲非线性方程组的迭代(di di)解法第三章非线性方程(fngchng)与非线性方程(fngchng)组的迭代解法第1页/共36页第一页，共36页。常用的求非线性方程根的方法(fngf)回顾第2页/共36页第二页，共36页。计算(j sun)框图为：对分法（二分法）：利用对分法（二分法）：利用(lyng)连续函数的性质进行对连续函数的性质进行对分分第3页/共36页第三页，共36页。( )0( )f xxx从一个从一个(y )初值初值x0出发，计算出发，计算10()xx21()xx1()kkxx如果如果 xk收敛，即存在收敛，即存在x*, 使得使得 *limkkxx则由则由 1limlim(

2、)kkkkxx得得 *()xx即即 x*是是 (x)(x)的不动点，也就是的不动点，也就是 f(x) f(x) 的根。的根。第4页/共36页第四页，共36页。第5页/共36页第五页，共36页。至少至少(zhsho)二阶收敛二阶收敛 速度速度第6页/共36页第六页，共36页。Newton 迭代法迭代法 （二阶收敛（二阶收敛(shulin)） 非线性问题的最简单解法是线性近似(jn s). 将非线性方程线性化，以线性方程的解逐步逼近非线性方程的解，这就是Newton法的基本思想。第7页/共36页第七页，共36页。110000 ()() ()0)xxxxf xxxff解出 作为近似根 ：1 Newt

3、on ()(), 0, 1, 2, nnnnfnfxxxx依次产生迭代格式，称法：000 ( )0()()()0 :f xf xfxxx取线性部分近似代替第8页/共36页第八页，共36页。计算步骤(bzhu)（框图）：第9页/共36页第九页，共36页。Newton 迭代法的变体：割线(gxin)法（简化牛顿法）（1.618）11()()kkkkf xf xxx111()()()()kkkkkkkf xxxxxf xf x第10页/共36页第十页，共36页。Newton 迭代法的变体(bin t)：单点割线法（一阶）00()()kkf xf xxx010()()()()kkkkkf xxxxxf

4、 xf x第11页/共36页第十一页，共36页。牛顿下山法：目的是解决初值的选取范围太小这一困难。构造迭代格式为：其中的参数满足：这个方法(fngf)称为牛顿下山法。其中的参数称为下山因子：通常取 ，然后逐步减半。牛顿下山法当 时，只有线性收敛速度，但对初值的选取却放的相当宽。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收敛于迭代序列对则存在开球可导在且内有一不动点在设knnSDSSDRRD定定理理第22页/共36页第二十二页，共36页。

7、(1)( )( )1( )()()kkkkXXF XF X第23页/共36页第二十三页，共36页。),()( )(1)()() 1(kkkkXFXFXX牛顿迭代公式：.Jacobi)( )( 212221212111)(矩阵的称为其中XFXFnnnnnnkxfxfxfxfxfxfxfxfxf)( 局部二阶收敛性定定理理第24页/共36页第二十四页，共36页。计算步骤(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.逐次迭代得结果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 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页。简化牛顿法。目的是避免(bmin)计算迭代公式中繁杂的导数，解决方法与一元函数牛顿法类似，即将所有导数取为固定值，如迭代初值的导数值。(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页。与单个方程的情形类似，牛顿法中 f 的导数的元素用合适(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的简单修正，且满足( )(1)( )(1)()()()kkkkkA xxf xf x则得到Broyden算法。特别，若取1TkkAAuv，其中u,v 是待定的列向量，使其满足上式，则得到秩一Broyden算法。比如( )(1)( )(1)11()(,()()TkkkkkkkTyAs sAAsxxyf xf xs s其中第31页/共36页第三十一页，共36页。小结 1、本章的目的是求解形如 f (x)=0 的方程，而其核心方法是将所要求(yoqi)解的方程变形为 x = (x)，利用 (x) 为压缩映射，通过迭代求出其解。2、变形中切记要恒等变形！3、在恒等变形中，为使变形得到的函数 (x) 为压缩映射，一个技巧是利用待定参数。4、恒等变形的一种重要格式是牛顿迭代，证明其迭代收敛阶的一个常用技巧是泰勒展开。5、n维空间