1、机动上页下页首页结束工科研究生公共课程数学系列 内容提要内容提要7.1 方程求根与二分法方程求根与二分法7.2 迭代法及其收敛性迭代法及其收敛性7.3 牛顿法牛顿法7.4 弦截法弦截法第1页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 7.1 方程求根与二分法方程求根与二分法一、引言一、引言.b,aC)x(f,Rx 0)x(f 的求根问题，其中的求根问题，其中考虑单变量非线性方程考虑单变量非线性方程非线性方程的分类非线性方程的分类.0ex :.2.01xx :).n,1,0i(Ra,0a,0axaxaxa .1x3i0n1n1n1n0 如如超越方程超越方程如如其中其中代数方程代数
2、方程第2页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 32 11.138.841.770 xxx例如求方程的有根区间搜搜索索法法求求有有根根区区间间。则则可可用用若若。此此时时重重零零点点。的的为为则则称称为为正正整整数数其其中中可可以以分分解解为为如如果果,0)b(f)a(f,b,aC)x(f0*)x(f,0*)x(f*)x(f*)x(f m)x(f*x .m ,|*)x(g|0),x(g*)xx()x(f )x(f)m()1m(m 由此可知方程的有根区间为由此可知方程的有根区间为1,2 3,4 5,61,2 3,4 5,6求根问题的三个方面：存在性，分布，精确化。求根问题的
3、三个方面：存在性，分布，精确化。x 0 1 2 3 4 5 6f(x)的符号 +第3页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 0000101110()()0,()/2.()(),.()(),;,f af bxabf xf xxf af xax bbaa bx设取假如是的零点，那么输出停止 假若不然，若与同号，则否则。11110111(1),(2)x,x=,x=,22-(3)-,22kkkkkkkka ba bababbab ab ab ababa二分过程中有三个量在变：（区间、近似根、区间长度）二、二分法0 xyX*x0aby=f(x)a1b1第4页，共39页。机动上页下页
4、首页结束工科研究生公共课程数学系列 3()101.0,1.5-2.f xxx 求在内的一个实根，准确到小数点后位例例7 17 1 1k|*|()/2()/2()/2*().xxkkkkkkkxxbab axabxkk收敛性分析：因故有,因此，只要二分的足够多次（即 充分大），便有，这里 为预定的精度。第5页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 k ak bk xkf(xk)符号0123456 1.0 1.25 1.31251.3203 1.5 1.3751.34381.3281 1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.3242 +
5、005.0 xx6k66*度度），便便能能达达到到预预定定的的精精次次（只只要要二二分分第6页，共39页。机动上页下页首页结束工科研究生公共课程数学系列。的的一一个个为为函函数数称称化化为为等等价价形形式式将将非非线线性性方方程程不不动动点点)x(*x;)*x(*x0*)x(f )x(x 0)x(f 二分法的优点是算法简单，且总是收敛的，缺点是收二分法的优点是算法简单，且总是收敛的，缺点是收敛太慢敛太慢,故一般不单独将其用于求根，只用其为根求故一般不单独将其用于求根，只用其为根求得一个较好的近似值。得一个较好的近似值。7.2 迭代法迭代法一、不动点迭代与不动点迭代法一、不动点迭代与不动点迭代法
6、第7页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 0101,()(),0,1,2,.2.2 ()kkxxxxxkx给定初始近似值可以得到如此反复，构造迭代公式（）称为迭代函数。上述迭代法是一种逐次逼近法，其基本思想是将隐式方上述迭代法是一种逐次逼近法，其基本思想是将隐式方程归结为一组显示的计算公式，就是说，迭代过程实质上是程归结为一组显示的计算公式，就是说，迭代过程实质上是一个逐步显示的过程。一个逐步显示的过程。0,2.2 lim()()2.2kkkxa bxxxxxx如果对任何，由式（）得到的序列有极限则称迭代方程收敛，且为的不动点，称式（）为不动点迭代法。第8页，共39页。
7、机动上页下页首页结束工科研究生公共课程数学系列 3 101.5-*xxx求在附近的根。例例7 7 2 2k xkkxkkxk0121.51.357211.3308634 51.325881.32494 1.324766781.324731.324721.32472),2,1,0k(1xx1xx13k1k3 据据此此建建立立迭迭代代公公式式式式）将将方方程程改改写写成成下下列列形形解解：（即即为为所所求求的的根根。实实际际上上已已满满足足方方程程完完全全相相同同，可可以以认认为为与与结结果果787xxx第9页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 331012(2)xx-1
8、11.5,2.375,12.39,.kkxxxxx另一种等价形式建立迭代公式迭代初值仍取则有 继续迭代下去已经没有必要，因为结果显然会越来越大，继续迭代下去已经没有必要，因为结果显然会越来越大，不可能趋于某个极限。这种不收敛的迭代过程称作是发散的。不可能趋于某个极限。这种不收敛的迭代过程称作是发散的。一个发散的迭代过程，纵使进行了千百次迭代，其结果也毫一个发散的迭代过程，纵使进行了千百次迭代，其结果也毫无价值。因此，迭代格式形式不同，有的收敛，有的发散，只无价值。因此，迭代格式形式不同，有的收敛，有的发散，只有收敛的迭代过程才有意义，为此要研究不动点的存在性及迭有收敛的迭代过程才有意义，为此要
9、研究不动点的存在性及迭代法的收敛性。代法的收敛性。即即为为所所求求的的根根。实实际际上上已已满满足足方方程程完完全全相相同同，可可以以认认为为与与结结果果787xxx第10页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 的的不不动动点点。即即为为即即使使在在由由连连续续函函数数性性质质可可知知存存且且满满足足显显然然定定义义函函数数因因上上存存在在不不动动点点。在在，显显然然或或若若性性。证证明明：先先证证不不动动点点存存在在)x(x),x(x0,)x(f)b,a(x0b)b()b(f,0a)a()a(f,b,aC)x(fx)x()x(f,b)x(ab,a)x(b)b(a)a(二
10、、不动点的存在性与迭代法的收敛性二、不动点的存在性与迭代法的收敛性.*xb,a)x(2.4|;yx|L|)y()x(|,b,ay,x ,1L0 (2),b,a)x(,b,ax (1),b,aC)x(上上存存在在唯唯一一的的不不动动点点在在那那么么）（都都有有使使得得常常数数都都有有并并且且设设迭迭代代函函数数 定定理理1 1第11页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 代代替替。可可用用它它表表明明定定理理中中的的条条件件有有则则由由中中值值定定理理可可知知对对有有且且对对任任意意，在在使使用用时时如如果果中中的的条条件件和和定定理理对对定定理理2.7)(2)b,a(,y
11、-xL)yx)()y()x(b,ay,x2.7)(1L)x(b,axb,aC)x(221010 。的的不不动动点点只只能能是是唯唯一一的的引引出出矛矛盾盾。故故得得则则由由的的不不动动点点，都都是是及及再再证证唯唯一一性性。设设)x(xxxxL)x()x(xx2.4)x(b,axx2121121122 第12页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 2/331333321-(x)x1(x)(x1),31 11,2(x)()1,3 412(x)3211(x)x1(x)3x1 2(x)1在例7 2中，当时，在区间中，又因故定理 中条件 成立。所以迭代法收敛。而当时，在区间，中不
12、满足定理条件。(2.5)|(2.2).|1|*,)(,1010 xxLLxxxxbaxkk的的不不动动点点均均收收敛敛于于迭迭代代序序列列对对任任意意初初值值的的条条件件下下在在定定理理定定理理2 2第13页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 具具有有足足够够精精度度。足足够够小小即即可可保保证证近近似似值值次次计计算算结结果果的的偏偏差差由由此此可可见见，只只要要相相邻邻两两将将其其化化为为而而不不便便于于实实际际应应用用。可可由由于于含含有有信信息息但但它它次次数数原原则则上上可可用用于于确确定定迭迭代代误误差差估估计计式式kkkkkkxxxxxLxx|.|1|*1
13、11|L,(2.5).|11|*|,|1|*,*,0)(;1|)(|,10,)(,)(10101kkkkkxxLxxxxLLxxxbaxxbaxfLxbaxLbaxbaxbaCx|4)|3)(2.2)2)1)(2)(1),均收敛于均收敛于迭代序列迭代序列对任意初值对任意初值上有唯一的根上有唯一的根在在方程方程那么那么都有都有使得使得都有都有并且并且如果迭代函数如果迭代函数推论推论第14页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 320122322312 x-x-10 x1.5 11 (1)7-3 1,1;(2)1,111(3),11 kkkkkkxxxxxxxxxxxx 为求
14、在附近的一个根，设奖方程改写成下列等价形式，并建立相应的迭代公式：迭代公式迭代公式迭代公式试分析每种迭代公式的收敛性，并选取一种公式求出具有四位有效数例字的近似根。上上整整体体收收敛敛。在在故故迭迭代代式式，时时当当来来考考察察，的的邻邻域域取取解解6.1,3.1 1113.1226.1,3.1 11)(6.1,3.1 5.1213320kkxxLxxxxx (x)(1)1.61.3 :第15页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 ,L(x)(x)x1(x)32下下表表计计算算结结果果见见取取只只需需数数字字要要求求结结果果具具有有四四位位有有效效中中迭迭代代公公式式计计
15、算算。较较小小，故故取取的的由由于于发发散散。故故上上整整体体收收敛敛。在在故故时时当当5.1105.010211)2()2(11,1)16.1(21)1(21)(,11)3(6.1,3.1 11522.0)3.11(6.132)1(326.1,3.1 6.1,3.1)2(033112/33213/223/22xLLxxxxxxxxxLxxxkkkkkk第16页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 k xk k xk 1 2 31.4842480341.4727057301.468817314 4 5 6 1.4670479731.4662430101.465876820
16、.1x05.取取初初值值kxxk 10 e10 x-20(1)0 1(2)x(2-e)/10,x07 4-.比较求的根到三位小数所需的计算量：在区间，内用二分法；用迭代法取初值例466.1,102163xxxx故故可可取取由由于于第17页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 迭迭代代计计算算结结果果如如下下上上整整体体收收敛敛。取取在在时时，当当具具有有三三位位有有效效数数字字。用用二二分分法法计计算算，此此时时故故因因解解：,0 x0.5,0)e2(101)x(,5.0,0)x(0.5,0 x)2(xx,1021000030517.021xx,1x0,0)1(f,0)0
17、(f,1,0 x)1(0 x14*41514k k xk k xk 1 2 30.10.0894829080.090639135 4 5 6 0.090512616 0.090526468 0.090524951精精确确到到三三位位小小数数。故故此此时时64-566xx,102100000720.0 xxL1Lxx 第18页，共39页。机动上页下页首页结束工科研究生公共课程数学系列.,:.,均均收收敛敛对对于于任任意意初初值值迭迭代代过过程程于于是是依依据据定定理理可可以以断断定定是是因因为为这这总总有有对对于于任任意意此此外外成成立立于于任任意意使使对对的的某某个个邻邻域域存存在在由由连连续
18、续函函数数性性质质证证明明是是局局部部收收敛敛的的则则迭迭代代法法且且的的某某邻邻域域内内有有连连续续在在的的不不动动点点为为迭迭代代函函数数设设RxxxxxxxLxxxxRxRxLxRxxxRxxxxxxkk01)()()()()(.1)(*:*)2.2(,1|*)(|*)(,)(*定定理理3 3.*xb,axk局局部部收收敛敛性性附附近近考考察察收收敛敛性性，称称为为点点。应应用用上上经经常常只只在在不不动动不不容容易易由由定定理理作作出出判判断断局局收收敛敛性性；上上的的收收敛敛性性通通常常称称为为全全在在迭迭代代序序列列三、局部收敛性与收敛阶三、局部收敛性与收敛阶局局部部收收敛敛。法法
19、则则称称迭迭代代且且收收敛敛到到产产生生的的序序列列迭迭代代对对任任意意的的某某个个邻邻域域如如果果存存在在有有不不动动点点设设)2.2(*,)2.2(,:*,0(x)xRxRxxxRxxk定定义义1 1第19页，共39页。机动上页下页首页结束工科研究生公共课程数学系列.0*)x()x31(21)x()x3x(21x4 ;134.0231*)x(2x1)x()3x(41xx3;1*)x(x3)x(x3x2;1132*)x(1x2)x(3xxx12kk1k2kk1k2k1kk2k1k ，）（，）（，）（，）（2 30*3-.xx只用四则运算不用开方求方程的根例例7 57 5kxk迭代法(1)迭代
20、法(2)迭代法(3)迭代法(4)0123?x0 x1 x2 x3?23987?21.521.5?21.751.734751.732631?21.751.7321431.732051?第20页，共39页。机动上页下页首页结束工科研究生公共课程数学系列.p*x,0*)x(0*)x(*)x(*)x(,p*x)x(x)x()p()1p(阶阶收收敛敛的的附附近近是是那那么么迭迭代代过过程程在在，并并且且连连续续导导数数阶阶邻邻近近具具有有的的根根在在如如果果迭迭代代函函数数 定定理理4 4.2p1p1p .p ,C,Ceelim*,xxe*,x)x(x pk1kkkkk1k时时为为平平方方收收敛敛超超线
21、线性性收收敛敛；当当时时为为当当时时迭迭代代法法为为线线性性收收敛敛；特特别别地地，当当收收敛敛阶阶则则称称迭迭代代过过程程为为是是不不等等于于零零的的常常数数若若误误差差收收敛敛于于设设迭迭代代过过程程 定定义义2 2阶收敛阶收敛该迭代法为该迭代法为知知由定理由定理，而，而的的，而迭代法，而迭代法，故它只是线性收敛的，故它只是线性收敛的的的中，迭代法中，迭代法例例平方收敛平方收敛时时当当迭代法线性收敛迭代法线性收敛时时特别地，当特别地，当 2 4 4.,02,032)(0)()4(0)()3(,0*)(,0*)(;1|*)(|pxxxxxx第21页，共39页。机动上页下页首页结束工科研究生公
22、共课程数学系列 12(1)(2-),11(),()2(1),11-2()0()-2a0,11lim()2kkkxxaxxxaxaaxaaaeaea 解:迭代函数为（）且即是（）的不动点。又（），所以，由定理4知，迭代是二阶收敛的，且0102 0,(2-),0,1,2,7-6,01-1kkkkxaxxaxkaxax给定初值以及迭代公式常数证明：(1)该迭代式是二阶收敛的；(2)该迭代产生的序列收敛的充要条件是例第22页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 12-111112421202011(2)-(-1)-1,1 (1-),1(1)1(1)(1)1 11 lim0limk
23、kkkkkkkkkkkkkkkkkkkkkkkkkkexaxraxaaxxreraraxaxrrrrrrrrerreaa 因,令则等价于然而 故由此可知000,lim01,1-1kkkrraxr而又等价于即第23页，共39页。机动上页下页首页结束工科研究生公共课程数学系列(4.1),0)xx)(x(f)x(f 0)x(f ),xx)(x(f)x(f)x(fTaylor,0)x(f,x0)x(f:kkkkkkkk 近近似似表表示示为为于于是是展展开开做做并并假假定定近近似似根根的的设设已已知知方方程程线线性性化化牛牛顿顿迭迭代代公公式式的的推推导导、.4.2 .)x(f)x(fxx ,xkkk1
24、k1k牛牛顿顿迭迭代代法法这这就就是是）（则则有有计计算算公公式式记记 其根为7.3 牛顿法牛顿法一、牛顿法及其收敛性一、牛顿法及其收敛性第24页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 则则进进行行加加速速若若用用迭迭代代收收敛敛，由由定定理理当当解解：,)3.3(.73307.3x ,5.3x2,4,3)x(,4,3x ,132)x(max ,x2)x(1604x3 2 303,-4.xxe求方程在中的解例例7 77 7 kxkykzk0123.53.734443.733073.604143.733813.662023.73347第25页，共39页。机动上页下页首页结束工
25、科研究生公共课程数学系列）（性性牛牛顿顿迭迭代代法法的的局局部部收收敛敛义义牛牛顿顿迭迭代代公公式式的的几几何何意意4.3 .*)x(f2*)x(f*)xx(*xxlim,*)x(f*)x(f*)x(f 0*)x(f*)x(f0*)x(f*)x(f*)x(,)x(f)x(f)x(f)x(f)x(f)x(f)x(f 1)x(,)x(f)x(fx)x(.2k1kk42222 第26页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 0-.xxe用牛顿法求方程的根例例7 87 8.5.0 x ),2,1,0k(x1ex x x 0kxkk1kk 取取初初值值解解：牛牛顿顿迭迭代代公公式式为
26、为;1150Cx ,C 2并并求求，应应用用牛牛顿顿法法解解二二次次方方程程对对于于给给定定正正数数 例例8 8二、牛顿法应用举例二、牛顿法应用举例kxkkxk010.50.57102340.567160.56714第27页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 CxCxqCxC-xCxCxCxC-xCxCx)Cx(2x1Cx )C-x(2x1Cx)xCx(21x.0 x002kk1k1k2kk1k1k2kk1k2kk1kkk1k0k 记记据据此此反反复复递递推推有有以以上上两两式式相相除除得得式式施施行行配配方方手手续续，易易知知事事实实上上，对对迭迭代代公公式式皆皆平平
27、方方收收敛敛证证明明：第28页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 的的结结果果。精精度度为为次次便便得得到到。迭迭代代初初值值取取利利用用60kk1k10301x ,115C)xC x(21 x 即即迭迭代代过过程程恒恒收收敛敛。时时故故由由上上式式推推知知，当当总总有有对对任任意意整整理理上上式式，得得,Cxk1,q,0 xq1qC2Cxk022kk kxkkxk0121010.75000010.7238373410.72380510.723805第29页，共39页。机动上页下页首页结束工科研究生公共课程数学系列.)x(f)x(f 1,(4.12),2,1,0k,)x
28、(f)x(fxx x)1(xx(4.7).)x(f)x(fxx k1kkkk1kk1k1k0kk1k 逐逐次次折折半半直直到到满满足足其其中中下下山山因因子子牛牛顿顿下下山山法法：简简化化牛牛顿顿法法：三、简化牛顿法与牛顿下山法三、简化牛顿法与牛顿下山法.)x(f1C,2)x(fC0 1,)x(fC1)x(g.,2,1,0k,0C )x(Cfxx 0kk1k公公式式局局部部收收敛敛时时即即当当构构造造迭迭代代公公式式 第30页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 3000 101.5*.1.50.60.611/32xxxxxx 如、再求在附近的根：依次用牛顿法，简化牛顿法
29、，折半，计算结果如下：例例 解解kxkxkxk f(xk)012341.51.347831.325201.324720.617.9发散0.6 -1.3841.140625 -0.6566431.36181 0.18661.32628 0.006671.32472 0.0000086第31页，共39页。机动上页下页首页结束工科研究生公共课程数学系列.0)x(*x,)x(g*)xx()x(mg)x(g*)xx()x(m)x(f*x)x(f/)x(f)x(.(4.13),)x(f)x(fmxx )x(g*)xx()x(f,mkkk1km的的单单根根是是故故重重根根，则则的的是是，若若还还可可令令仍仍
30、平平方方收收敛敛可可将将迭迭代代法法改改为为，牛牛顿顿法法不不是是平平方方收收敛敛重重根根情情形形 四、重根情形四、重根情形第32页，共39页。机动上页下页首页结束工科研究生公共课程数学系列.|)x(p)x(f|min|)x(p)x(f|,H)x(p ,b,aC)x(f nHp*nn*nnn或或切切比比雪雪夫夫逼逼近近问问题题此此即即所所谓谓最最佳佳一一致致逼逼近近使使得得误误差差求求多多项项式式本本节节讨讨论论 .(4.14),)x(f)x(f)x(f)x(f)x(fxx )x(kk2kkkk1k仍仍平平方方收收敛敛用用牛牛顿顿法法得得对对 422121212 440*2.21 422 (4
31、.13)2(2)3 (4-.14).2 9kkkkkkkkkkkkkxxxxxxxxxxxxxxxx用上述三种方法求的二重根：（）牛顿法；（）；（）计算结果如下：7 7解解例例 第33页，共39页。机动上页下页首页结束工科研究生公共课程数学系列).xx(xx)x(f)x(f)x(f )xx(x,x f )x(f )x(p xx .1)x(f).x(f)x(f,0)x(fk0k0kkk0kk10kkkk ，得得到到线线性性插插值值函函数数为为插插值值节节点点和和以以单单点点弦弦截截法法的的迭迭代代法法。下下面面介介绍绍避避免免求求要要计计算算外外还还每每步步除除计计算算程程用用牛牛顿顿法法求求解
32、解非非线线性性方方kxk(1)(2)(3)0123x0 x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.4142135627.4 弦截法弦截法第34页，共39页。机动上页下页首页结束工科研究生公共课程数学系列).xx()x(f)x(f)x(fxx )x(fxx)x(f)x(f0k0kkk1kk0k0k ，同样得，同样得代替导数代替导数在牛顿法中用差商在牛顿法中用差商.)xx()x(f)x(f)x(fxx 0)x(p0k0kkk1k1称
33、称为为单单点点弦弦截截法法，得得到到令令 .1*)x(0 ,*)x(f1 0)x*x()x(f*)x(f 0)x(f*)x(f*)x(f1*)x(.00 x*x)x(f*)x(f0200 线线性性收收敛敛的的可可以以证证明明单单点点弦弦截截法法是是第35页，共39页。机动上页下页首页结束工科研究生公共课程数学系列.xx)x(f)x(f)x(f.)xx()x(f)x(f)x(fxx 0)x(p)xx(xx)x(f)x(f)x(f )x(p xx .21kk1kkk1kk1kkkk1k1k1kk1kkk11kk而而得得到到或或在在牛牛顿顿法法中中取取称称为为两两点点弦弦截截法法，得得到到令令，得得
34、到到线线性性插插值值函函数数为为插插值值节节点点和和以以两两点点弦弦截截法法 .线线性性收收敛敛可可以以证证明明两两点点弦弦截截法法超超第36页，共39页。机动上页下页首页结束工科研究生公共课程数学系列.*x618.1p,x,x ,0)x(fx|*xx:|*x)x(f 625110收收敛敛到到按按阶阶充充分分小小时时，两两点点弦弦截截法法那那么么当当又又初初值值有有连连续续导导数数，且且对对任任意意内内具具有有二二阶阶的的邻邻域域在在根根假假设设 定定理理()-10.xf xxe 用两点弦截法求方程的根例例 7 107 10kxk012340.50.60.565320.567090.56714第37页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 知识结构图七方程近似求根基本概念（单根、重根、有根区间、不动点、收敛阶）求根方法二分法及其收敛性不动点迭代法及其收敛性定理（不动点迭代法的加速技巧）牛顿迭代法及其收敛性插值型迭代法（多点迭代）弦截法抛物线法第38页，共39页。机动上页下页首页结束工科研究生公共课程数学系列 第39页，共39页。
