数值分析-非线性方程求根教材课件.ppt

1、1 1 方程求根与方程求根与二分法二分法第第7 7章章 解非线性方程的迭代法解非线性方程的迭代法一、引言一、引言.,)(,(1.1)0)(baCxfRxxf的求根问题，其中考虑单变量非线性方程非线性方程的分两类：.01 :).,1,0(R,0,0 ,.1301110 xxniaaaxaxaxainnnn如其中代数方程.0 :,.2xex如超越方程.)(*.,|*)(|0),(*)()()(重零点的为则称为正整数其中可以分解为如果mxfxmxgxgxxxfxfm.0*)(,0*)(*)(*)()()1(xfxfxfxfmm此时,0)()(,)(bfafbaCxf若 则可用搜索法求有根区间.0 的

2、有根区间求方程xex例1例1 x 1 0 1 2f(x)的符号 +方程根的数值计算大致可分三个步骤进行:(1)判定根的存在性。(2)确定根的分布范围,即将每一个根用区间隔离开来。(3)根的精确化,即根据根的初始近似值按某种方法逐步精确化,直至满足预先要求的精度为止。设f(x)为定义在某区间上的连续函数,方程(1.1)存在实根。虽然方程(1.1)的根的分布范围一般比较复杂,但我们不难将函数f(x)的定义域分成若干个只含一个实根的区间。例如考虑方程 x2-2x-1=0 由图7.1所示,该方程的一个负实根在-1和0之间,另一个正实根在2和3之间。图 7.1 这样,我们总可以假设方程(1.1)在(a,

3、b)内有且仅有一个单实根x*。由连续函数的介值定理知 f(a)f(b)0 若数值b-a较小,那么我们可在(a,b)上任取一点x0作为方程的初始近似根。例如,方程 f(x)=x3-x-1=0 由于f(1)0,f(1.5)0,又f(x)在区间(1,1.5)上单调连续,故可知在(1,1.5)内有且仅有一个实根。于是可取某个端点或区间内某一个点的值作为根的初始近似值。设函数f(x)在区间a,b上单调连续,且 f(a)f(b)0 则方程(1.1)在区间(a,b)内有且仅有一个实根x。二、二分法二、二分法二分法简述.,;,)()(.,)()(.2/)(,0)()(0111010000 xbaabbxaxf

4、afxxfxfbaxbfaf否则同号，则与若假若不然，停止那么输出的零点，是假如取设,11kkbababa故*,2/)(xbaxkkk(1.3).2/)(2/)(|*|1kkkkababxx 11()2kkxxba(1.3)对于确定的精度,从式(1.3)易求得需要二等分的次数k。二分法具有简单和易操作的优点。其计算步骤如下,框图如图7.2所示。1.计算步骤 输入有根区间的端点a,b及预先给定的精度;(a+b)/2 x;若f(a)f(x)0,则x=b,转向;否则x=a,转向。若b-a,则输出方程满足精度的根x,结束;否则转向。2.计算框图(见下页）例1 求方程 f(x)=x3-x-1=0在区间(

5、1,1.5)内的根。要求用四位小数计算,精确到小数点后两位。解 这里a=1,b=1.5，取区间(1,1.5)的中点01(1 1.5)1.252x 图 7.2 由于f(1)0,f(1.25)0,则令 a1=1.25,b1=1.5得到新的有根区间(1.25,1.5)取x6=1.3242，误差限|x6-x*|0.5/(27)0.005,故x6即为所求近似根，实际上根x*=1.324717二分法优点：计算简单，收敛性有保证；缺点：收敛不够快，特别是精度要求高时，工作量大，而且不能够求复根及双重根。2 2 迭代法迭代法一、不动点迭代一、不动点迭代(2.1).(0)(xxxf 化为等价形式将非线性方程.)

6、(*;)*(*0*)(不动点不动点的一个为函数称xxxxxf ).(,010 xxx可以得到给定初始近似值 .)(2.2).,2,1,0 ),(1为迭代函数称式如此反复，构造迭代公xkxxkk.)2.2()(*)(*(2.2)*,lim )2.2(,0不动点迭代法不动点迭代法为故称的不动点，是收敛，且则称迭代公式有极限得到的序列由如果对任何初值xxxxxxbaxkkk.几何意义是一种逐次逼近法；隐式化为显式，迭代法：说明说明.*5.101 3xxx附近的根在求 例3例3).,2,1,0(,15.11310kxxxkk，）解：（kxk012345671.51.357211.330861.3258

7、81.324941.324761.324731.32472虽然迭代法的基本思想很简单,但效果并不总是令人满意的。对于上例,若按方程写成另一种等价形式 x=x3-1 (29)建立迭代公式 xk+1=x3k-1,k=0,1,2,仍取初始值x0=1.5,则迭代结果为 x1=2.375 x2=12.3976这种不收敛的迭代过程称作是发散的。如下图：.*,)(2.4|;|)()(|,10 (2),)(,(1),)(xbaxyxLyxbayxLbaxbaxbaCx上存在唯一的不动点在那么）（都有使得常数都有并且如果迭代函数定理1定理1二、不动点的存在性与迭代法的收敛性二、不动点的存在性与迭代法的收敛性*,

8、)(2.2),1 0 xxbax的不动点均收敛于迭代序列对任意初值的条件下在定理定理2定理2并有误差估计(2.5).|1|*|01xxLLxxkk.|11|*|1kkkxxLxx还有.|11|*|4)|,|1|*|3)*,(2.2),2)*,0)(1);1|)(|,10 (2),)(,(1),)(10101kkkkkxxLxxxxLLxxxbaxxbaxfLxbaxLbaxbaxbaCx均收敛于迭代序列对任意初值上有唯一的根在方程那么都有使得都有并且如果迭代函数推论推论.12 ;11 1,2 3131kkkkxxxx）散性：内考查如下迭代法的敛在三、局部收敛性与收敛阶三、局部收敛性与收敛阶.*

9、,局部收敛性附近考察收敛性，称为点。应用上经常只在不动不容易由定理作出判断局收敛性；上的收敛性通常称为全在迭代序列xbaxk.*),(*(2.2)*,(),*,(0则称迭代序列局部收敛均收敛于迭代序列使得如果xxxUxxU定义1定义1.)2.2(,1|*)(|,*)(,)(*是局部收敛的则迭代法且内有连续导数的某邻域在的不动点为迭代函数若 xxxxx定理3定理3.3*03 2xx的根求方程只用四则运算不用开方例4例4;1132*)(12)(3121xxxxxxkkk，）（;1*)(3)(3221xxxxxkk，）（;134.0231*)(21)()3(41321xxxxxxkkk，）（.0*)

10、()31(21)()3(214 21xxxxxxkkk，）（kxk迭代法(1)迭代法(2)迭代法(3)迭代法(4)0123?x0 x1 x2 x3?23987?21.521.5?21.751.734751.732631?21.751.7321431.732051?.211 .,lim*,*,)(11时为平方收敛超线性收敛；当时为当时迭代法为线性收敛；特别地，当收敛阶则称迭代过程为是不等于零的常数若误差收敛于设迭代过程ppppCCeexxexxxpkkkkkkk定义2定义2.*,0*)(0*)(*)(*)(,*)()()()1(阶收敛的附近是那么迭代过程在，并且连续导数阶邻近具有的根在如果迭代函

11、数pxxxxxpxxxxpp 定理4定理4.,0*)(,0*)(;,1|*)(|0平方收敛时当迭代法线性收敛时特别地，当 xxx3 3 迭代收敛的加速方法迭代收敛的加速方法一、埃特金加速收敛方法一、埃特金加速收敛方法),(01xx由迭代公式校正一次得对于收敛的迭代过程，).(12xx再校正一次得则变化不大如果 ,)(,)(Lxx(3.1)*).-(*)()(*),-(*)()(*112001xxLxxxxxxLxxxx*1021xxxxxxxx,*2202022121xxxxxxxxxxx.2)(222*0122010012210220100200122102xxxxxxxxxxxxxxxxx

12、xxxxxxxx)()(:Aitken)(1212kkkkxxxx加速迭代方法于是得到埃特金*1021xxxxxxxxkkkkkkkxxxxxxx122112)(3.2)./)(22kkkxxx二、斯蒂芬森迭代法二、斯蒂芬森迭代法迭代法蒂芬森加速技巧结合，得到斯把不动点迭代与埃特金)(Steffensen(3.3),2,1,0(2)(),(),(21kxyzxyxxyzxykkkkkkkkkkk(3.4),2,1,0()(1其中代法改写为另一种不动点迭kxxkk(3.5).)(2)()()(2xxxxxxx.2)3.3()(*1)*(,)()(*.)(*,)(*阶收敛的是迭代法的不动点，且斯蒂

13、芬森为，则存在的不动点，设为反之，的不动点为则的不动点为若xxxxxxxxxx 定理5定理5.1 01 313kkxxxx的迭代将斯蒂芬森法用于解 例5例5.,)3.3(.1331有收敛结果计算现用发散指出：例kkxx解解kxkykzk0123451.51.416291.355651.329851.324801.324722.375001.840921.491401.347101.3251812.39655.238882.317281.444351.32714说明说明:(2.2)不收敛,(3.3)可能收敛;(2.2)线性收敛,(3.3)平方收敛!.4,303 2中的解在求方程xex 例6例6l

14、n3ln2 构造迭代法，)(3lnln2：1kkxxxgxx取对数得解解.2,4,3)(,4,3 ,132)(max ,2)(43迭代收敛由定理当xxxxxx.73307.3,5.3 160 xx则进行加速若用,)3.3(kxkykzk0123.53.734443.733073.604143.733813.662023.733474 4 牛顿法牛顿法一、牛顿法及其收敛性一、牛顿法及其收敛性.牛顿迭代公式的推导:线性化展开做并假定近似根的设已知方程Taylorxfxxfkk,0)(,0)(),)()()(kkkxxxfxfxf(4.1),0)()(0)(kkkxxxfxfxf近似表示为于是.4.

15、2 .)()(,其根为11)牛顿迭代法(牛顿迭代法(切线法这就是）（则有计算公式记kkkkkxfxfxxx 牛顿法是非线性方程线性化的方法。其计算步骤为:给出初始近似根x0及精度。计算 若x1-x0,则转向;否则,转向。输出满足精度的根x1,结束。牛顿法的计算框图见图7.4。0010()()f xxxfx图 7.4.义牛顿迭代公式的几何意.性牛顿迭代法的局部收敛,)()()(xfxfxx ,)()()()()()()(1)(222xfxfxfxfxfxfxfx ,*)(*)(*)(0*)(*)(0*)(*)(*)(42xfxfxfxfxfxfxfx ）（4.3 .*)(2*)(*)(*lim

16、21xfxfxxxxkkk 二、牛顿法应用举例二、牛顿法应用举例.0 的根用牛顿法求方程xex例7例7.5.0 ),2,1,0(1 01xkxexxxkxkkkk取初值解：牛顿迭代公式为kxk01230.50.571020.567160.56714，应用牛顿法解二次方程对于给定正数0 ,2CxC例例8 8;115并求.00迭代公式皆平方收敛证明x(4.5).(212 21kkkkkkxCxxCxxx解：.01,1150 xC初值取kxk012341010.75000010.72383710.72380510.723805三、简化牛顿法与牛顿下山法三、简化牛顿法与牛顿下山法.,2,1,0,0 )

17、(1kCxCfxxkkk构造迭代公式.,2)(0 1,)(1)(公式局部收敛时即当xfCxfCxg(4.7).)()(01xfxfxxkkk简化牛顿法：)(10 xfCkkkxxx)1(11(4.12),2,1,0,)()(1kxfxfxxkkkk牛顿下山法：.)()(1,1kkxfxf逐次折半直到满足其中下山因子.*5.101 33xxx附近的根在再求、例例，计算结果如下：，折半，简化牛顿法，：依次用牛顿法32/116.06.05.1000 xxx解解kxkxkxk f(xk)012341.51.347831.325201.324720.617.9发散0.6 -1.3841.140625 -

18、0.6566431.36181 0.18661.32628 0.006671.32472 0.0000086四、重根情形四、重根情形.(4.13),)()()(*)()(,1仍平方收敛可将迭代法改为，牛顿法不是平方收敛重根情形kkkkmxfxfmxxxgxxxfm.0)(*,)(*)()()(*)()()(*)(/)()(的单根是故重根，则的是，若还可令xxxgxxxmgxgxxxmxfxxfxfx.(4.14),)()()()()()(21仍平方收敛用牛顿法得对kkkkkkkxfxfxfxfxfxxx.2*044 924xxx的二重根用上述三种方法求 例例；）牛顿法：（kkkkxxxx42

19、121解解；）（kkkkxxxx22 )13.4(221.2)2(4.14)3221kkkkkxxxxx）（计算结果如下：kxk(1)(2)(3)0123x0 x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.4142135625 5 弦截法弦截法的迭代法。下面介绍避免求要计算外还每步除计算程用牛顿法求解非线性方)().()(,0)(kkkxfxfxfxf单点弦截法 .1).()()()()(,)()(00010kkkkkkkkxxxx

20、xfxfxfxxxxfxfxpxx，得到线性插值函数为插值节点和以.)()()()(0)(0011称为单点弦截法，得到令xxxfxfxfxxxpkkkkk)()()(00，同样得代替导数在牛顿法中用差商kkkxfxxxfxf).()()()(001xxxfxfxfxxkkkkk.几何意义.线性收敛的可以证明单点弦截法是这是因为，,*)(1 0)*()(*)(0)(*)(*)(1*)(00*)(*)(0200 xxxfxfxfxxxfxfxfxfxfx.1*)(0 x两点弦截法 .2)()()()()(1111kkkkkkkkxxxxxfxfxfxpxx，得到线性插值函数为插值节点和以.)()(

21、)()(0)(1111称为两点弦截法，得到令kkkkkkkxxxfxfxfxxxp.)()()(11而得到或在牛顿法中取kkkkkxxxfxfxf.几何意义.线性收敛可以证明两点弦截法超.*618.1,0)(|*:|*)(625110 xpxxxfxxxxxf收敛到按阶充分小时，两点弦截法那么当又初值有连续导数，且对任意内具有二阶的邻域在根假设定理定理.01)(的根用两点弦截法求方程xxexf 例10例10kxk012340.50.60.565320.567090.56714抛物线法 .3)(,)(,)()(,1211221kkkkkkkkkkkkxxxxxxxfxxxxfxfxpxxx，得到插值函数为插值节点和以).(,)(4)(2 0)(12112112kkkkkkkkkkkkkkxxxxxfxxfxxxfxfxfxxxp式中，得到两个零点：令.,)(4)sgn()(2 211kkkkkkkxxxfxfxfxx.*840.1xp收敛到抛物线法按阶