数值分析课件第二章22

数值分析第二章解非线性方程的数值方法一、二分法二、迭代法三、Newton法对给定方程f(x)=0,可以用各种方法转化成等价方程()(12.)xx二、迭代法1迭代法的基本思想若x*是f(x)的根,即若,则有*()0fx**()xx称x*为函数的一个不动点.()x设x0是一个近似解，可以构造序列1()0,1,22(2.)kkxxk迭代法(2.2)称为简单迭代法或单点迭代法.称函数为迭代函数.()x1()0,1,22(2.)kkxxk简单迭代法(2.2),若迭代序列{xk}保持有界,全在定义域内称为适定的;若进一步有()x*limkkxx称为是收敛的.若收敛，即存在x*使得则由的连续性和可得x*=(x*)，即x*是的不动点，也就是f(x)的零点。0kkx*lim,kkxx1limlimkkkkxx30111.51,(0,1,2,).kkxxxk（），kxk012345671.51.357211.330861.325881.324941.324761.324731.3247231012(2)1,1.5,2.375,12.39,.kkxxxxx例求x3-x-1=0在1.5附近的根x*解xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1x22收敛定理和误差估计定理1设在[a,b]上有连续的一阶导数,且()x(1)有[,],xab();axb(2)|()|1,xL[,];xab则有(1)函数在[a,b]上存在唯一的不动点x*()x由迭代公式(2.2)得到的序列(2)0[,],xab{}kx都收敛到方程的根x**10||||1kkLxxxxL(3)*11||||1kkkxxxxL(4)证明(1)先证明存在性,作函数()()hxxx由条件(1)可知()()0,()()0haaahbbb由连续函数根的存在定理可知,必有*[,]xab使得h(x*)=0，即**()xxx再证明唯一性,设也是一个解,即()xx那么****|||()()||()()|||xxxxxxLxx因为L1,所以有*xx(2)由条件(2)和Lagrange中值定理得***11*2*12*0||||()()||()()|||||||kkkkkkxxxxxxLxxLxxLxx因为L1,所以当时,有k0.kL(3)和(4)利用(2)的方法2111210|||||||||kkkkkkkxxLxxLxxLxx1121121010||||||||()||||1kpkkpkpkpkpkkkpkpkkxxxxxxxxLLLxxLxxL令即分别得,p*10||||1kkLxxxxL1211||(1)||1||1ppkpkkkkkxxLLLxxxxL*11||||1kkkxxxxL定理1的几点说明(i)通常将条件(1)称为映内性；(ii)条件(2)也可以改为：存在常数L且0L1使得|()()|||,,[,]xyLxyxyab结论仍然成立,这个条件通常称为压缩性；(iii)结论(3)说明的误差大概是常数*||kxx乘上Lk,但是一般L未知;(iv)结论(4)说明与有关*||kxx1||kkxx因此得到迭代法的终止条件1||kkxx3一般迭代法的算法算法：(1)取初始点x0,最大迭代次数N和精度要求,并置k=0；(2)计算1();kkxx(3)若则停止计算；1||,kkxx(4)若k=N,则停止计算；否则k=k+1,转(2).4局部收敛定理迭代序列{xk}在区间[a,b]上的收敛性通常称为全局收敛性.实际应用只在不动点x*的邻近考察收敛性，称为局部收敛性.定义设有不动点x*,如果存在x*的某个邻域()x*:||,Rxx对任意的迭代(2.2)产生的0xR序列且收敛到x*,则称(2.2)局部收敛.{}kxR证明由连续函数的性质,存在x*的某个邻域*:||,Rxx对任意的有xR|()|1xL而****|()||()()|||||xxxxLxxxx根据定理1可以断定迭代过程(2.2)对任意初值均收敛.0xR定理2若x*为迭代函数的不动点,在x*()x()x的某个邻域内有连续导数,且则*|()|1,x迭代法(2.2)局部收敛.21(1)3(*)2311;kkkxxxx，13(2)(*)1;kkxxx，2113(3)(3)(*)10.134;42kkkxxxx，113(4)()(*)0.2kkkxxxx，例只用四则运算不用开方求方程x2-3=0的根*3x解kxk迭代法(1)迭代法(2)迭代法(3)迭代法(4)0123׃x0x1x2x3׃23987׃21.521.5׃21.751.734751.732631׃21.751.7321431.732051׃例设2()(5),xxax试讨论a的取值范围使迭代公式(2.2)局部收敛到*5x解因为2()(5)xxax所以由定理2可知只需()12,xax*|()|1x即|125|1a105a所以当时,迭代公式收敛.105a1()()|()3|1,(),()kkxxxxxxx已知方程的满足试构造迭代函数使得迭代收敛。例5迭代收敛的阶则称该迭代为r阶收敛.(C为常数)(1)当r=1时称为线性收敛，此时C1；(2)当r=2时称为二次收敛，或平方收敛；(3)当r=1,C=0时称为超线性收敛.二分法线性收敛;定义设迭代收敛到的不动点x*.记ek=xkx*，若1||lim0||krkkeCe1()kkxx()x不动点迭代中，若则线性收敛*()0x敛，反之不一定成立。阶收敛一定是超线性收)1(rr，判断它们收敛的阶。个序列都收敛到设例04).10(,,2,22aaxkwvkukkkkkkk****(1)*()*(1)(),(2)'()''()()0,(3)()0ppxxxxxx()*11lim()!pkpkkexpe则迭代公式是p阶收敛的，且定理3设迭代若在x*的某1(),kkxx()()px邻域内连续，且***1()*()()'()()()...()!kkkppkkxxxxxxxxp证明：根据泰勒展开有()**1()()!ppkkkxxxxp()*11lim()!pkpkkexpe是平方收敛。证次此迭代用迭代法求其根，并验分别取化为等价形式将方程例,1),2(029.20212xxxxx6迭代加速若则迭代公式(2.2)只是线性收敛的*()0,x取初始点x0,令那么00()yx****0000()()()()()yxxxxxLxx*00111LxyxLL由此得迭代公式1()1kkkkLxyyxL),(kkxy如何求L?再令得到0000(),()yxzy****0000(),()yxLxxzxLyx**00**00yxxxzxyx2*000000()2yxxxzyx由此得Steffensen加速法21(),()()2kkkkkkkkkkkyxzyyxxxzyx0,1,kSteffensen加速法是平方收敛的.三、Newton法1Newton法基本思想2()()()()()()2!kkkkffxfxfxxxxx设xk是f(x)=0的近似根,将f(x)在xk一阶Taylor展开:(在xk和x之间)*0()fx*()()()kkkfxfxxx*()()kkkfxxxfx当f‘(x)0时,即将非线性方程线性化1()()kkkkfxxxfx于是xyx*xkxk+1Newton法的几何意义()()()kkkyfxfxxxNewton法的本质就是不断用切线来近似曲线，因此Newton法也成为切线法.2Newton法的算法(1)取初始点x0,最大迭代次数N和精度要求ε置k=0;(2)计算1();()kkkkfxxxfx(3)若则停止计算;1||kkxx(4)若k=N则停止计算;否则置k=k+1,转(2).Newton法可以看作下面的不动点迭代：1()kkxx其中()()()fxxxfx2()''()'()'()fxfxxfx’(x*)=0Newton法至少二阶局部收敛3Newton法收敛性证明(略)Newton法也可以看作一类特殊的加速迭代1()'()1'()kkkkkxxxxx取(x)=x-f(x)定理4设f(x)在其零点x*的某个邻域内二阶连续可导且0，则存在x*的某个邻域N(x*)=[x*-,x*+],使得对x0N(x*)，Newton法产生的序列以不低于二阶的收敛速度收敛到x*.)(*xf例设计一个二阶收敛算法计算(a0).a解：转化为求x2-a=0的正根Newton迭代：21()1()22kkkkkkkkkfxxaaxxxxfxxx212kkkxaxaax22222kkkkkxaxaxaxx1212kkkxaxxa12a二阶收敛设x*是f(x)的m(m2)重根,Newton法是否收敛？**(1)*()*()'()()0,()0mmfxfxfxfx4重根情况)()()(*xgxxxfm)()()()()(*1*xgxxxgxxmxfmm)()()()(2)())(1()(*1*2*xgxxxgxxmxgxxmmxfmmm所以Newton迭代：()()()fxxxfx*2**()''()'()lim'()lim'()xxxxfxfxxxfx11m线性收敛,且重数m越高,收敛越慢.提高收敛速度但m通常无法预先知道！法一：取()()()fxxxmfx*'()0x二阶收敛法二：将求f(x)的重根转化为求另一个函数的单根.构造针对(x)的具有二阶收敛的Newton迭代：2()()'()()'()'()()''()xfxfxxxxxfxfxfx令，则x*是(x)的单重根.()()()fxxfx例取初始点x0=1.5,分别用Newton法和求重根的两种方法计算f(x)=(x+1)(x-1)2=0解(1)Newton法迭代公式1(1)(1)(1)2(1)kkkkkkxxxxxxk012345xk1.51.27271.14411.07441.03781.0191k6789……13xk1.00961.00481.00241.0012……1.0001(2)方法一：取,m=2()()()fxxxmfx迭代公式为21()22()31kkkkkkkfxxxxxfxx方法二:迭代公式为2()()'()()'()'()()''()xfxfxxxxxfxfxfx取2122()'()61323'()()''()kkkkkkkkkkkfxfxxxxxxxfxfxfxk0123方法一xk1.51.04551.