第2章 非线性方程与方程组的数值解法

1、第2章非线性方程与方程组的数值解法 本章重点介绍求解非线性方程 的几种常见和有效的数值方法,同时也对非线性方程组 求解,简单介绍一些最基本的解法.无论在理论上,还是在实际应用中,这些数值解法都是对经典的解析方法的突破性开拓和补充,许多问题的求解,在解析方法无能为力时,数值方法则可以借助于计算机出色完成.0)(xf), 2 , 1(0),(21nixxxfni2.1二分法求非线性方程0)(xf 确定方程的有根区间 计算根的近似值的根的方法分为两步： 首先确定有限区间：依据零点定理。 设 ，且 ，则方程 在区间 上至少有一个根。如果 在 上恒正或恒负，则此根唯一。,)(baCxf0)()(bfaf

2、0)(xf),(ba)(xf),(ba等步长扫描法求有根区间 用计算机求有根区间：等步长扫描法。 设h0是给定的步长，取 ，若 则扫描成功；否则令 ，继续上述方法，直到成功。如果 则扫描失败。再将h 缩小，继续以上步骤。haxax10,0)()(10 xfxfhxxxx0110,bx 1等步长扫描算法 算法：（求方程 的有根区间）(1) 输入 ；(2) ； (3) ，若 输出失败信息，停机。(4)若 。输出 ，已算出方程的一个根，停机。0)(xfhba,)(0aff )(,1xffhaxbx 01fx等步长扫描算法(5) 若 。输出 为有根区间，停机(6) ，转 3）注：如果对足够小的步长h扫

3、描失败。说明：在 内无根在 内有偶重根010ff, ,xaxaxa ,ba,ba二分法 用二分法(将区间对平分)求解。 令 若 ，则 为有根区间，否则 为有根区间 记新的有根区间为 ， 则 且 )(,1121111bacbbaa0)()(11cfaf,11ca,11bc,22ba,2211baba)(112122abab二分法对 重复上述做法得且 ,22ba.,.,2211nnbababa)(211ababnnn二分法 设 所求的根为 ， 则 即 取 为 的近似解 x.2 , 1,nbaxnn.2 , 1nbxann0)(21lim)(lim1nababnnnnxbannnnlimlim)(2

4、1nnnbacxx求方程f(x)=0的根的二分法算法).(21)4(;endwhile.,;,0)()()2);(),(21)1|)3(;3,10)()()2(;,:)1 (baxbxbaelsexabathenxfafifxfbaxbawhileelsebathenbfafifbaba输出计算令时做步转第值输入重新步返回第值及精度控制量的有根区间输入求方程f(x)=0的全部实根的二分法算法);();(211|while)2endwhile;0)()(while) 1while) 3(;)2(;,:) 1 (11011111111111xfbaxabhabaabfafbbhabaahba计算时

5、做做时做输入求方程f(x)=0的全部实根的二分法算法;endwhile;10;:)3;endwhile.,0)()(if3);3(0)(if2111111111100habhxaxbxbaelsexabathenxfafxf输出转例题例1 设方程 解：取h=0.1,扫描得： 又 即 在 有唯一根。 2 , 1 , , 1)(3baxxxf0344. 0)4 . 1 (061. 0)3 . 1 (ff.4 . 1 , 3 . 1 方程的有根区间为4 . 1 , 3 . 1 , 013)(2xxxf0)(xf4 . 1 , 3 . 1 2.2一般迭代法2.2.1 迭代法及收敛性 对于 有时可以写成

6、 形式 如： 0)(xf)(xx3331101xxxxxxxxxxcos0cos迭代法及收敛性 考察方程 。这种方程是隐式方程，因而不能直接求出它的根，但如果给出根的某个猜测值 ， 代入 中的右端得到 ，再以 为一个猜测值，代入 的右端得 反复迭代得)(xx0 x)(xx)(01xx1x)(xx)(12xx,.1 , 0)(k1kkxx迭代法及收敛性 若 收敛，即 则得 是 的一个根kx xxkklimx)(xx)()lim()(limlim1nxxxxxnnnnn迭代法的几何意义 交点的横坐标 *x)()(xyxyxxy=x2x0 x1x简单迭代法 将 变为另一种等价式 。选取 的某一近似值

7、 ，则按递推关系 产生的迭代序列 。这种方法算为简单迭代法。0)(xf)(xxx,0bax ,.1 , 0)(k1kkxxkx例题 例2 试用迭代法求方程 在区间(1，2)内的实根。 解：由 建立迭代关系 k=10,1,2,3.计算结果如下:31xx01)(3xxxf311kkxx例题精确到小数点后五位5102132472. 1x例题但如果由 建立迭代公式 仍取 ，则有 ， 显然结果越来越大， 是发散序列。1x3x,.2 , 1131kxxkk 5 . 10 x 2.3751x 12.392x kx迭代法的收敛性定理（压缩映像原理）设迭代函数 在闭区间 上满足（1）（2） 满足Lipschit

8、z条件即 有且 。 )(x ,ba,)(,baxbax)(x,21baxx )()(2121xxLxx10 L压缩映像原理则 在 上存在 唯一解 ，且对 ，由 产生的序列 收敛于 。 )(xx,0bax )(k1kxx.1kxx,bax压缩映像原理证明：不失一般性,不妨设 否则 为方程的根。首先证明根的存在性 令 bbaa)(,)(ba或xxx)()(压缩映像原理 则 ， 即 由条件2） 是 上的连续函数 是 上的连续函数。故由零点定理 在 上至少有一根0)()(aaa0)(b0)()(ba)(x,ba)(x所以,ba0)(x,ba),(bax 压缩映像原理再证根的唯一性 设有 均为方程的根

9、则 因为 0L1 ，所以只可能 ， 即根是唯一的。,21baxx| )()(|212121xxLxxxx21xx压缩映像原理最后证迭代序列的收敛性 与n 无关，而0L1 即| )()(|1xxxxnn由于|1xxLn|0 xxLn.xx ,0因为0lim|lim0nnnnLxxxx所以 xxnnlim压缩映像原理误差估计 若 满足定理条件，则 这是事后估计，也就是停机标准。L越小，收敛速度越快。 这是事前估计。选取n，预先估计迭代次数。 )(xx|L1L|1nnxxxxn|L1L|01nxxxxn 对于方程 构造的多种迭代格式 ，怎样判断构造的迭代格式是否收敛？收敛是否与迭代的初值有关？根据数

10、学知识，我们可以直接利用以下收敛条件：（1） 当 有（2） 在a,b上可导，并且存在正数L1时，称为超线性收敛；当p=2时，称为平方收敛或二次收敛。迭代法收敛的阶迭代法收敛的阶定理定理 设 是方程 的不动点， 若为足够小的正数 。如果 且 ，则从任意 出发，由 产生的序列 收敛到 ，当 时敛速是线性的。 *x)(xx,*xxCx)(1| )(|* x0 x)(1kkxx0nx*x0)( x 迭代法收敛的阶迭代法收敛的阶证明：满足压缩映像原理知，及由Cxx)(1|)(|*足够小时，有)(1| )(|xLx|)(| )()(|)(|*xxxxxxxxx有因此，对于迭代法收敛的阶迭代法收敛的阶 敛速

11、是线性的 线性收敛到 。0)()()(limlim*1nxxxxxeennnnn因为。收敛到故*0 xxn满足压缩映像原理，所以即)(,)(xx0nx所以*xSteffensen迭代格式由线性收敛知 当n充分大时有 即0limlim112nCeeeennnnnnnnneeee112*1*1*2xxxxxxxxnnnnSteffensen迭代格式展开有：nnnnnnxxxxxxx1221*2)(2*121*2)(2)(xxxxxxxxnnnn2*1212*2*2)(2)(xxxxxxxxxxxnnnnnn*121*2*22xxxxxxxxxnnnnnn21212*)2(nnnnnnxxxxxxx

12、Steffensen迭代格式已知 ，则 ，改成nx)(1nnxx)(2nnxx nnnnnnnnnnnxyzxyxxyzxy2)()()(21 n=0，1，2，Steffensen迭代格式也可以改写成其中迭代函数,.)1 , 0()(1nxxnnxxxxxxx)(2)()()(2Steffensen迭代法收敛的充要条件定理 ,)(*1xxCx，设函数。件是的不动点的充分必要条是)()(*xxxxx，则为足够小的正数，且1)(* xSteffensen迭代法收敛的充要条件证明：必要性的不动点，是因为)(*xxx)(2)()()(2xxxxxxx由于，所以0)(lim*xxxx，故有0)(lim*

13、xxxx)(*xx即的不动点。是所以)(*xxxSteffensen迭代法收敛的充要条件充分性的不动点有是由)(*xxxxxxxxxxxxxx)(2)()(lim)(lim2*1)(2)()( 1)()( 2lim*xxxxxxxxoo型0 1)( 1)()( 2lim2*xxxxxx的不动点。是所以)(*xxxSteffensen算法的收敛速度 !)()(lim)(0)(0)(.)()(,),1()(,)(*)(*1*010*)1(*)1(*pxxxxxxpxxxxxxxxxxpCxxxxppnnnnkkppp ，且阶收敛速度收敛到，以列产生的序，由，则而如果为足够小的正数的不动点是设定理S

14、teffensen算法的收敛速度定理 在定理2.2.3假设下，若 产生的序列 至少平方收敛到 。,.2, 1 ,02)()()(21nxyzxyxxyzxySteffensennnnnnnnnnnn迭代格式则由 2C)(x0nx*x*xSteffensen算法的收敛速度的不动点，是证明：)(*xxx。即)(*xx1)(11)(lim)(lim*xxxxxxxxooxx型又因为Steffensen算法的收敛速度 *)(2)(lim*xxxxxxx及) 1)(2)()(lim*xxxxxoo型1)(2)()(*xxx2* 1)(xSteffensen算法的收敛速度 *)()(lim)(*xxxxx

15、xx于是有*2)(2)()(lim*xxxxxxxxxxx*2*)(2)()(lim1*xxxxxxxxxxx0 1)( 1)(12*2*xxSteffensen算法的收敛速度 由定理知 至少以平方速度收敛到 。 也就是说：简单迭代法是线性收敛；Steffensen迭代至少平方以上收敛（加速收敛）。0nx*x例题例试用Steffensen算法求解方程解法一、取 ，由013 xx31)(xxnnnnnnnnnnnxyzxyxxyzxy2)()()(21 n = 0，1，2，例题取初值 ，计算结果如下：5 . 10 xN XnYnZn0 1.51.3572088081.3308609591 1.3

16、248991811.3247523791.3247244962 1.3247179571.3247179571.324717957例题解法二、取 ，由对于该迭代函数在一般迭代法中是发散的，而Steffensen格式却是收敛的。1)(3 xxnnnnnnnnnnnxyzxyxxyzxy2)()()(21 n=0，1，2，例题取初值 ，计算结果如下：N XnYnZn0 1.52.3751.2396484371 1.4162929751.8409219155.2388727692 1.3556504421.4913982792.3172706993 1.3289487771.3470628831.4

17、443512244 1.3248044891.3251735441.3271172815 1.3247179441.3247181521.3247189806 1.3247179575 . 10 xSteffensen迭代格式几何解释 Steffensen迭代算法 11002001200100210:)3(;)4);2/()()3;3|2|)2);();() 1| )(|while)2(;,) 1 (xendwhilexxxyzxyxxthenxyzifyzxyxxx输出步做第做输入Steffensen迭代算法 为松弛因子n 时，为直接迭代；n 时，迭代步长加大，加速迭代；n 时，迭代步长减小

18、，适合迭代发散；n 时，迭代反方向进行。 松弛迭代法松弛迭代法通过选择合适的松弛因子,就可以使迭代过程收敛。松弛法的迭代公式如下：)(1nnnkxxxx (2-7) 11100 松弛迭代法松弛迭代法 实例实例例 用（松弛）迭代法求解下面非线性方程组，并分析松弛因子对迭代次数及收敛过程的影响。已知迭代初值x和y均为0，收敛精度=0.001 。0201. 01 . 0011 . 002. 03222yyxyxxn解：取以下迭代表达式：)01. 01 . 02()1 . 002. 01 (321221nnnnnnnnnnyyxyyxyxxx若取松弛因子为1.1，则其迭代过程如表2-2。迭 代 次 数

19、 x y 0 0.0000 0.0000 1 1.1000 2.2000 1.4142 2 1.5490 2.2302 0.2902 3 1.5450 2.3629 0.0562 4 1.6122 2.3714 0.0418 5 1.6146 2.3955 0.0101 6 1.6271 2.3984 0.0078 7 1.6283 2.4031 0.0021 8 1.6308 2.4040 0.0016 9 1.6311 2.4050 0.0005 n若改变松弛因子,迭代过程及迭代所需的次数亦将发生变化，详见表2-3。松弛因子 迭代次数 0.5 21 0.8 13 1 10 1.1 9 1.

20、2 11 1.3 17 1.4 29 1.5 81 1.55 454 1.56 发散 表2-2 迭代过程表2-3 松弛因子及迭代次数的变化，则为直接迭代法12.3 Newton迭代法设x * 是方程f (x ) = 0的根，又x0 为x * 附近的一个值 ，将f (x ) 在x0附近做泰勒展式 令 ，则 之间和在其中020000)()(21)()()()(xxfxxxfxxxfxf *xx )()(21)()()()(020*00*0*fxxxfxxxfxf Newton迭代法去掉 的二次项，有：即以x1代替x0重复以上的过程，继续下去得：0*xx 0)()()(000*0 xfxxfxxf)

21、()(0001*xfxfxxxNewton迭代法,.1 , 0)()(1nxfxfxxnnnn以此产生的序列Xn得到f(x)=0的近似解，称为Newton法，又叫切线法。Newton迭代法几何解释几何意义例题例2.3.1 用Newton法求 的近似解。解：由零点定理。0cos)(xxxf内有根。在)2, 0(0cosxx迭代公式得及由Newtonxxfsin1)(,.1 , 0sin1cos1nxxxxxnnnnn例题085133739. 0739085133. 0739085133. 0739085178. 0;73936133. 044*43210 xxxxxxx故取得取例题例2.3.2

22、用Newton法计算 。解：220)(2aaxxf其中迭代公式得及由Newtonxxf2)(,.1 , 0)2(212221nxxxxxxnnnnnn。有十位有效数的近似值是已的精确值相比，。与，则取332102414213562. 1414215686. 11.416666675 . 1xxxxxNewton迭代法算法框图Newton迭代法算法。输出）转（做输入1101001001000:)4(;2) 3;)2;/) 1|while(3);();()2(;,) 1 (xendwhilexxffxxfxffxffxNewton迭代法收敛性定理2.3.1 设函数 ，且满足 若初值 满足 时，由N

23、ewton法产生的序列收敛到 在a,b上的唯一根。,)(2baCxf上恒正或恒负。在,)() 3);,( , 0)()2; 0)()() 1baxfbaxxfbfaf ,0bax 0)()(00 xfxf0)(xfNewton迭代法收敛性证明： 根的存在性根的唯一性内至少有一个根。在知）及由条件（),(0)(,)(1baxfbaCxf。记此根为内有唯一根在上严格单调函数，因此是故保号，知及由*,),(0)(,)()(,bCa,)(, 0)(xbaxfbaxfxfxfxfNewton迭代法收敛性收敛性)()(0)()(0)(, 0)(, 0)(,0)()(0)(, 0)(, 0)(, 0)(01

24、0000001000*000 xxxfxfxxfxfxxxfxfxfbxxxfxfxfxfbfaf 即有，所以知，由，不妨设Newton迭代法收敛性 继续上述推理有代替。再以因此有两式相减展式由另一方面0101*20*01*20*0*00*0)()()(21)(21)()()(0 Taylor,xxxxxxxxffxxxxfxxxfxfxf Newton迭代法收敛性。，由根的唯一性知可得时当由。故必有极限，记。是单调减有下界的序列故序列*10011*0)(,.2 , 1)()(lim.xaafnnxfxfxxaxxxxxxxnnnnnnnnnNewton迭代法收敛性推论 在定理2.3.1条件下

25、， Newton迭代法具有平方收敛速度。故结论成立。之间，则与介于其中，证明，一般有类似定理证明0)()(21lim)()()(211 . 3 . 2* 21*2*1n* xfxfeexxxxxffxxnnnnnnnn代数方程的Newton迭代法代数方程的Newton迭代法推导设n次代数方程用Newton迭代法求有限区间的实根，则要计算 ，一般采用秦九韶算法。,.2 , 1)()(1nxfxfxxnnnn)0(0)(0110 aaxaxaxfnnn)(),(nnxfxf代数方程的Newton迭代法由Taylor展式)2(!)()(.! 2)()()()( ) 1 ()()()(!)()(.!

26、2)()()()()()()(1)(2nxfxxxfxxxfxQxQxxxfnxfxxxfxxxfxxxfxfnnnnnnnnnnnnnnnnnn 其中代数方程的Newton迭代法 )3()()()()(),()()2(12110 nnnnnnnbxbxbxQxQxxxfxfxQ的余式，令除以为且式知，由);()(1)() 1 (nnxfxQnxfxx，余式为次多项式为，得商）去除式表示，用（ nnnnnnnnnaxaxaxabxbxbxxxfxf 111012110.)()()(1)3(）式得式代入（),.,2 , 1()(100nkxxfbbababxnnnkkk的同次幂系数得比较等式两边

27、代数方程的Newton迭代法同理 )()()()()(xRxxxfxQxQxxnnn有取除以用)4()(23120 nnncxcxcxR令12211023120.)()()() 3 () 4( nnnnnnnnnbxbxbxbcxcxcxxxfxQ式得式代入代数方程的Newton迭代法比较x的同次幂系数得：故代数方程的Newton迭代公式) 1,.,2 , 1()(1100nkxxfccbcbcnnnkkk,.)2 , 1(11ncbxxnnnn代数方程的Newton迭代法算法步。返回第停止计算输出做对计算输入2)(,;,|(4);)(3;1,.,2 , 1)2;) 1);(),()2(;,)

28、,.,2 , 1 , 0(:) 1 (101*01100101010000100000 xxelsexxthenxxifffxxxfffxfafnkffafxfxfxniaki 2.4弦截法Newton迭代法有一个较强的要求是 且存在。因此，用弦的斜率 近似的替代 。 0)( xf)(xf )()()()()(,(P)(,(P,)(10101111100010*xxxxxfxfxfyxfxxfxbxaxxbaxf得弦的方程及则过，取上有唯一零点在设弦截法令y=0,解得弦与x轴的交点是坐标x2.,.)2 , 1()()()(.,)()()(0)()()()(0013201010112120101

29、1称之为定端点弦截法计算再由解得nxfxfxfxxxxxxxxfxfxfxxxxxxxxxfxfxfnnnnn弦截法.,.)2 , 1()()()(,111321又称快速弦截法称之为变端点弦截法以此类推计算若由nxfxfxfxxxxxxxnnnnnnn弦截法的几何解释例题例2.4.1 用快速弦截法求方程在区间（1，2）内的实根。解：取x0=1,x1=2,代入公式2.4.2计算结果,如表2.4.1所示。01)(3xxxfkxkf(xk)01-112521.166666667-0.5787036931.253112023-0.2853630241.3372064440.05388057951.32

30、3850096-0.003698116861.324707936-4.273521*10E-571.3247179653.79*10E-8弦截法收敛定理则其中如果的根是为足够小的正数设定理0| )(|max|,)(|max12,0)(, , ,)(1 . 4 . 21212*2 xfmxfMmMqxfxxxbabaCxfbxabxa弦截法收敛定理。的敛速收敛到以确定的序列由线性收敛到确定的序列由*011*001215,.2 , 1)()()()2(;,.2 , 1)()()() 1 (xpxnxfxfxfxxxxxxnxfxfxfxxxxnnnnnnnnnnnnn求解方程f(x)=0的快速弦截

31、法。输出停止计算输出失败信息时做输入LxNLffffxxxxLLxfffffxxxxfxffxffLNxx,)4(;endwhile,thenif)3;)2; 1);(;) 1|while)3();(),(, 0)2(;,:) 1 (2211021022101011211100102.5 非线性方程组的牛顿方法非线性方程组的牛顿方法设二阶方程组0),(0),(21yxfyxfyxuyxfyxfuF其中,),(),()(21),(),(21yxfyxf，n其中x,y为自变量。为了方便起见，将方程组写成向量形式：n将 在（x0,y0）附近进行二元泰勒展开，并取其线性部分，得到下面方程组：0),()

32、(),()(),(0),()(),()(),(0020002002001000100010yyxfyyxyxfxxyxfyyxfyyxyxfxxyxf2.5 非线性方程组的牛顿方法非线性方程组的牛顿方法令 则有,0000yyyxxx),(),(),(),(),(),(0020020002000100100010yxfyyxfyxyxfxyxfyyxfyxyxfx如果,0| ),(|00),(22110000yxyfxfyfxfyxJyx，解出00000001yyxxyxuu再将原方程组在u1处进行二元泰勒展开，并取其线性部分2.5 非线性方程组的牛顿方法非线性方程组的牛顿方法得到下面方程组： ),()(),()(),(),()(),()(),(1121112111211111111111yxfyyyyxfxxxyxfyxfyyyyxfxxxyxf解出,1111yyyxxx11112yyxxukkkkkkkkk