第四章非线性方程数值解法

1、第四章第四章非线性方程数值解法非线性方程数值解法 若在区间若在区间 上方程上方程 有唯一解，则称有唯一解，则称 为为方程的一个方程的一个隔根区间隔根区间。,a b 0f x ,a b 设有非线性方程设有非线性方程 ，若存在，若存在 使得使得 ，则称则称 为方程的一个为方程的一个根根，或，或 为函数为函数 的一个的一个零点零点。方。方程程数值解数值解指对于给定的绝对误差限指对于给定的绝对误差限 ，求，求 使使 0f x xR0f xx yf x0 xRxx 。 （2 2）近似根精确化。用求方程根的数值方法，）近似根精确化。用求方程根的数值方法，使求得的近似根逐步精确化，使其满足给定的精度使求得的

2、近似根逐步精确化，使其满足给定的精度要求。要求。求方程近似根的问题，一般分两步进行：求方程近似根的问题，一般分两步进行： （1 1）求隔根区间。确定根所在的区间，使方程）求隔根区间。确定根所在的区间，使方程在这个小区间有且仅有一个根。所求的隔离区间越在这个小区间有且仅有一个根。所求的隔离区间越小越好。小越好。 二分法的基本思想是：分法的基本思想是： 将将隔根隔根区间二等分，根据分点处函数区间二等分，根据分点处函数 的符的符号逐步将隔根区间缩小，使在足够小的区间内，方号逐步将隔根区间缩小，使在足够小的区间内，方程有且只有一个实根。程有且只有一个实根。( )f x设函数设函数 在在 上连续且严格单

3、调，上连续且严格单调，若若 ，则，则 为为 的一个隔根的一个隔根区间。区间。( )yf x , a b( ) ( )0f a f b , a b( )0f x 1 二分法二分法 首先取首先取 的中点的中点 ，将区间，将区间 分为两半。若分为两半。若 ，则，则 就是就是 的实根的实根 ；否则检查否则检查 与与 是否异号，即是否是否异号，即是否 成立。成立。,a b02abx,a b0()0f x( )0f x 0()f x( )f a0( ) ()0f a f x0 x 如果成立，则如果成立，则 是是隔根隔根区间区间，这时取，这时取110,aa bx ；否则否则 是是隔根隔根区间区间，这时取，这

4、时取101,ax bb 。这样，就得到一个新的是。这样，就得到一个新的是隔根隔根区间区间11,ab ，其长度仅是，其长度仅是 的一半。的一半。,a b0, a x0,x b yf x12bbb0aa1a2a 例例1：用二分法求方程：用二分法求方程2( )sin04xf xx210的非零实根的近似值，使绝对误差不超过的非零实根的近似值，使绝对误差不超过 。( )cos2xfxx解：因为解：因为当当 时，时， 为单调减少函数。为单调减少函数。1.62x( )0,( )fxf x又又 ，因此，因此 在在 有唯一非零实根。有唯一非零实根。(1.6)0, (2)0ff( )0f x 1.6, 2再令再令

5、 ，则，则1111.92abx1()0.0440f x因为因为 ，所以取，所以取11( ) ( ) 0f b f x 21211.9,2axbb如此继续下去，即得计算结果如下表。如此继续下去，即得计算结果如下表。001.6,2ab0()1.82abx0()0.1640f x记记 ，令，令 ，则，则00( ) ()0f b f x10101.8,2axbb因为因为 ，所以取，所以取取取 ，即可满足精度要求。，即可满足精度要求。*6661.934375 1.932abxxkkakxkb 01234561.6(+)1.8(+)1.9(+)1.9(+)1.925(+)1.925(+)1.93125(+

6、)1.8(+)1.9(+)1.95(-)1.925(+)1.9375(-)1.93125(+)1.934375(-)2(-)2(-)2(-)1.95(-)1.95(-)1.9375(-)1.9375(-)( )f x二分法的优点二分法的优点：计算简单，方法可靠，只要求计算简单，方法可靠，只要求 连续，对连续，对函数的性质要求较低。函数的性质要求较低。它的缺点是它的缺点是：不能求偶数重根，也不能求复根，收敛速度与以不能求偶数重根，也不能求复根，收敛速度与以12为公比的等比级数相同，不算太快。为公比的等比级数相同，不算太快。 一般求方程的近似根，不大单独使用，常用一般求方程的近似根，不大单独使用，

7、常用来为其它方法求方程近似根提供好的初值。方程来为其它方法求方程近似根提供好的初值。方程求根最常用的方法是迭代法。求根最常用的方法是迭代法。 迭代法是数值计算中一类典型方法，不仅用迭代法是数值计算中一类典型方法，不仅用于方程求根，而且用于方程组求解。于方程求根，而且用于方程组求解。 迭代法的基本思想是一种逐次逼近的方法，迭代法的基本思想是一种逐次逼近的方法，首先构造一个迭代公式，对于给定的初值，用迭首先构造一个迭代公式，对于给定的初值，用迭代值反复校正，直到满足预先给出的精度要求。代值反复校正，直到满足预先给出的精度要求。 下面研究如何构造一个合适的迭代公式。下面研究如何构造一个合适的迭代公式

8、。2 简单迭代法简单迭代法一、简单迭代法一、简单迭代法设有非线性方程设有非线性方程 （1)1)( )0,f xxa b,a b是其一个隔根区间。将其改写成等价形式是其一个隔根区间。将其改写成等价形式（2 2）( ),xx xa b取取 ，得到递推公式，得到递推公式0 , xa b（3 3）1(),0,1,2,kkxxk012,xxxk kx由此得到数列由此得到数列 ，如果当，如果当 时，当时，当*x( )x*x*()xx有极限有极限 ，且，且 在在 连续，则得连续，则得 ，*x因而因而 是方程（是方程（1）的根。）的根。这种求方程近似根的方法称为这种求方程近似根的方法称为简单迭代法简单迭代法。

9、( ) x称为称为迭代函数迭代函数0 x称为根的称为根的初始近似值初始近似值kx称为根的称为根的k次近似值次近似值kx称为称为迭代序列迭代序列解：因为解：因为 210,20,( )31fffxx(1,2)x( )0fx 当当 时时,将原方程转化为等价方程将原方程转化为等价方程(1) ，这时这时 , 取取 31xx3( )1xx01.5x 311kkxx1,2,3k 由迭代公式由迭代公式求得求得( )f x1,2上单调增加函数上单调增加函数 有一个实根有一个实根所以在所以在例例2：求方程：求方程 的根。的根。3( )10f xxx 33103321333233433354336533763387

10、12.51.3572112.35721.3308612.330861.3258812.325881.3249412.324941.3247612.324761.3247312.324731.3247212.324721.32472xxxxxxxxxxxxxxxxk当当 越来越大时，越来越大时， 收敛。收敛。 kx（2） ，这时，这时31xx3( )1xx仍取初值仍取初值 ，得迭代公式，得迭代公式01.5x 311kkxx1,2,3k 123942.37512.39651904.016.90252 10 xxxx迭代序列发散。迭代序列发散。 按这一迭代公式计算下去，当按这一迭代公式计算下去，当

11、变大时，变大时， 远离的远离的 精确根。精确根。kkx( )0f x 若迭代函数若迭代函数 满足条件：满足条件：( )x(1) 0,1 ,;lxlxa b 则对任意初始近似值则对任意初始近似值 ，迭代法，迭代法0 , xa b1()kkxx定理定理1 1（迭代法收敛的充分条件）（迭代法收敛的充分条件）kx( )xx ,a b产生的迭代序列产生的迭代序列 都收敛于方程都收敛于方程 在11011kkkkllxxxxxxll。*x上的唯一实根上的唯一实根 , ,且有且有(2),xa bxa b，则，则证证 （1）令）令,)(baCxF由定理条件可知由定理条件可知 xxxF , 0, 0bbbFaaa

12、F若上面两个不等式中有一个等号成立，则方程若上面两个不等式中有一个等号成立，则方程有根有根ax 或或 否则，根否则，根, bx 据连续函数的介值定理，必存在据连续函数的介值定理，必存在),(bax ，使，使，即方程，即方程有根有根。bax, xx 0 xxxF 0 xxxF则由微分中值定理和定理条件有则由微分中值定理和定理条件有若存在若存在,21bxxa , 2 , 1, ixxii 21212121,xxxxxxxx121212xxl xxxx上式出现的矛盾说明上式出现的矛盾说明xxx21（2）因）因0 , xa b，则由定理条件有，则由定理条件有,baxk其中其中 在在之间，之间，xxk与

13、1k因而因而),(bak因因01l 故有故有 xxkklim1110kkkkkkxxxxxxl xxlxx 1,1nnnnnnnnnnnnxxxxxxxxxxxxxxxxxxl xx 在 与 之间（3）证明误差估计不等式）证明误差估计不等式111112122121011111111111nnnnnnnnnnnnnnnnxxxxlxxlxxllxxlllxxxxllllxxxxll所以，对于所以，对于 ，迭代法，迭代法 收敛。收敛。如例如例2 2中中 在区间在区间1,21,2上满足该定理条件上满足该定理条件3( )1xx01.5x 311kkxx 从误差估计式（2）知， 越小，收敛得越快，且可用

14、来估计迭代次数。 l例例2 2中要求近似根中要求近似根 的误差不超过的误差不超过kx510由由23311( )(1)1334xxl510,101klxxl求得求得6.28k ，迭代，迭代7 7次即可。次即可。( )xx*x定理定理2 2（迭代法的局部收敛性）（迭代法的局部收敛性）若存在区间（若存在区间（c，d），使），使1 1、方程、方程 在（在（c，d）内有实根）内有实根 ；( ) x()1x2 2、 在（在（c，d）内连续，且）内连续，且 。则迭代法则迭代法1() (0,1,2,)kkxxk在在 附近附近具有局部收敛性。具有局部收敛性。*x证明：（略）例例3 方程方程 有唯一实根有唯一实根

15、xxe*(0,1)x 试分析迭代过程试分析迭代过程 的收敛性。的收敛性。1kxkxe(0,1,2,)k 解：这里解：这里 ，在区间（，在区间（0 0，1 1）内）内( ),( )xxxexe ( ) x连续，且连续，且 ，由定理，由定理2 2知，迭代法知，迭代法0( )1xxee1kxkxe在在 附近具有局部收敛性，迭代过程收敛。附近具有局部收敛性，迭代过程收敛。*x1r 当时称迭代法有时称迭代法有线性敛速线性敛速；2r时称迭代法有时称迭代法有平方敛速平方敛速。当当1r时称迭代法有时称迭代法有超线性敛速超线性敛速；当当二、简单迭代法的收敛速度二、简单迭代法的收敛速度0,0rC1,limkrkk

16、xxCxx使得使得 nxr则则称称 是是 阶收敛的，阶收敛的，r称迭代法有称迭代法有阶敛速阶敛速。 nxx，若存在若存在 定义定义1 1 设迭代数列设迭代数列 收敛到方程的根收敛到方程的根在在 mxxxx定理定理3 3 设设的某领域内连续，的某领域内连续，若，若 nxm迭代迭代数列数列有有阶收敛速度。阶收敛速度。 0,ix1,2,1,im 0,mx0则存在则存在，对，对 0,xxxx1nnxx于任意于任意，由迭代，由迭代产生的产生的 0mx知知 mxx在在的某领域内连续的某领域内连续和和证明证明. 若若 存在存在 使使 110,mxxxx10。由。由0,0 xx知，存在知，存在 ， 在在 上连

17、续，且存在上连续，且存在 10 x,xx01l 使使 ,xl xxx。 xxxxxxl xxxx ，,xxx ，则则 由定理由定理1知，对于任意知，对于任意 ,xxx。 0,xxxx 111 !mmmmmnnnnnxxxxxxxxxxxo xxmm 1!mmmnnnxxxxxo xxm 10!limmnmnnxxxCmxx由迭代由迭代 产生的数列产生的数列 收敛于收敛于 ，且，且 1nnxx nxx,nxxx x满足定理满足定理1 1 xx在在的某领域内连续，的某领域内连续，推论推论. 若若 0 x1nnxx，则，则有线性敛速。有线性敛速。全部条件，全部条件， 1020 xf xx410nxx

18、。例例4.4.求求的一个根，要求的一个根，要求 010,170,lg2ffxxx 解. 10.217,0,12 ln10 xxx10lg2 ,0nnxxx0126700.4771 0.39390.3758 0.3758kkx4770.3758,10 xxxx。作一阶泰勒展开，即用前两项近似代替作一阶泰勒展开，即用前两项近似代替( )( )( )()kkkf xf xf x x x则近似方程转化为则近似方程转化为 ()()()0kkkf xfxxx设设 ，上式解为，上式解为( )0fx ()()kkkf xxxfx方程方程 的新的近似根的新的近似根 ，则得牛顿迭代的计算公式，则得牛顿迭代的计算公

19、式( )0f x 1kx1()0,1,2,()kkkkf xxxkfx3 3 牛顿迭代法与弦截法牛顿迭代法与弦截法kx( )0f x ( )f xkx设设 是非线性方程是非线性方程 的一个近似根，把的一个近似根，把 在在 处处一、牛顿迭代公式一、牛顿迭代公式曲线曲线 在点在点 处的切线方程为处的切线方程为: :( )yf x(,()kkP xf x因此，牛顿迭代法又称为因此，牛顿迭代法又称为切线法切线法。牛顿迭代公式具有明显的几何意义牛顿迭代公式具有明显的几何意义:()()()kkkl yf xfxxx切线与切线与 轴交点的横坐标为轴交点的横坐标为 。x1kxkx1kxP yf xlx二、二、

20、牛顿迭代法收敛的充分条件牛顿迭代法收敛的充分条件具有相同的根。因此，牛顿迭代法是一种以具有相同的根。因此，牛顿迭代法是一种以( )( )( )f xxxfx为迭代函数的迭代法。为迭代函数的迭代法。( )0fx ( )0f x ( )( )f xxxfx当当 时，方程时，方程 与与定理定理3 3 对方程对方程 ，若存在区间，若存在区间 ，使，使( ) 0f x , a b（3）对任意对任意 ，都有，都有 ； , xa b( )0fx ( )fx , a b（2） 在在 上不变号；上不变号；( ) ( )0f a f b （1） ；000 , ,()()0,xa bf xfx（4） 在在 上的唯一

21、实根上的唯一实根 。 , a b*xkx( )0f x 则牛顿迭代公式产生的迭代序列则牛顿迭代公式产生的迭代序列 收敛于方程收敛于方程 满足定理条件只有四种情况满足定理条件只有四种情况; ;证明证明.以下仅证明第一种情况以下仅证明第一种情况: 0,0,0f af bfx ,fxC a b，由微分中值定理，由微分中值定理， ,0f bf aa bfba 。由条件（由条件（2）和（）和（3）知）知 0,;fxxa b 由条件（由条件（4）知）知000,f xxx。01000,fxxxxfx 001000000000fxfxfxfxxxxxxxxxxfxfxfx10 xxx。同理可证同理可证 严格单

22、调递减且有下界收敛，严格单调递减且有下界收敛， nx不妨设不妨设,nxx n 。1,limlimlimnnnnnnnf xxxfxfxxxfx 00fxf x由知，则xx。1,0,1,nnnnfxxxnfx0fxx 0,fxfx定理定理4 4 设设，若在，若在的某邻域内的某邻域内Newton迭代法迭代法 nxx产生的数列产生的数列以不低于以不低于二阶二阶收敛速度收敛于收敛速度收敛于00,xxx连续，则存在连续，则存在，对于任意对于任意，由，由 ，则则 ，得到牛顿迭代公式，得到牛顿迭代公式01 0,2x 00()()0f xfx解：设解：设 ，则，则 ，( )cosf xxx( )1 sin ,

23、( )cosfxx fxx 1cos,0,1,2,1 sinkkkkkxxxxkx计算结果如下计算结果如下10.750364x 20.739113x 30.739086x 40.739085x 因为因为 ，所以，所以5430.000001 10 xx40.739085x为满足精度要求的近似根。为满足精度要求的近似根。准确到准确到 。 5110kkxxcos0 xx例例5 5 用牛顿迭代法求方程用牛顿迭代法求方程 的实根，要求的实根，要求易验证，易验证， 在在 上满足定理上满足定理3 3的条件。取的条件。取( )f x2,000()()()kkkf xf xfxxx100()(),1,2,3,(

24、)()kkkkkf xxxxxkf xf x三、单点弦截法三、单点弦截法得到如下迭代公式：得到如下迭代公式：01,x x给定初值给定初值称公式为称公式为单点单点弦截法弦截法。单点弦截法具有单点弦截法具有线性线性敛速。敛速。单点弦截法使用条件与单点弦截法使用条件与Newton迭代法一样迭代法一样( (包括初值选取包括初值选取) )。公式的几何意义是：公式的几何意义是：00()()()()kkkkf xf xyf xxxxx不如不如牛顿法，且需提供两个初始值牛顿法，且需提供两个初始值 。01,x x单点单点弦截法的优点是避弦截法的优点是避免了求导数。不足是收敛速度免了求导数。不足是收敛速度000(

25、 , ( )P x f x(,()kkkP xf x过过 ， 的弦为的弦为: yf x0 x1x2x3xx0P1P11()()()kkkkkf xf xfxxx111()(),1,2,3,()()kkkkkkkf xxxxxkf xf x四、双点弦截法四、双点弦截法得到如下迭代公式：得到如下迭代公式：01,x x给定初值给定初值称公式为称公式为双点双点弦截法弦截法。双点弦截法具有双点弦截法具有1.6181.618阶阶敛速敛速。双点弦截法使用条件与双点弦截法使用条件与Newton迭代法一样迭代法一样( (包括初值选取包括初值选取) )。公式的几何意义是：公式的几何意义是：11()()()()kkkkkkf xf xyf xxxxx牛顿法与单点牛顿法与单点弦截法弦截法之间，且需提供两个初始值之间，且需提供两个初始值 。01,x x双点双点弦截法的优点是避弦截法的优点是避免了求导数。收敛速度介于免了求导数。收敛速度介于111(, ()kkkPxf x(,()kkkP xf x过过 ， 的弦为的弦为: yf x0 x1x2x3xx0P1P2P例例6 6 设有非线性方程设有非线性方程 , ,写出写出Ne