23数值分析复习---第七章 非线性方程(组)的数值解法

数值分析NumericalAnalysis郑州大学研究生课程（2009-2010学年第一学期）习题课第七章非线性方程（组）的数值解法2/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis二分法求根过程①取有根区间[a,b]之中点,将它分为两半,分点,这样就可缩小有根区间20bax+=yy=f(x)y=f(x)x*ax1x*x0bax0x1ba1b1a1b1a2b2a2b2一、要点回顾3/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis§7.2二分区间法②对压缩了的有根区间施行同样的手法,即取中点,将区间再分为两半,然后再确定有根区间,其长度是的二分之一。[]11,ba2111bax+=[]11,ba[]22,ba[]11,bayy=f(x)y=f(x)x*ax1x*x0bax0x1ba1b1a1b1a2b2a2b24/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis§7.2二分区间法③如此反复下去,若不出现,即可得出一系列有根区间序列：上述每个区间都是前一个区间的一半,因此的长度0)(=kxf[][][][]⊃⊃⊃⊃⊃kkbabababa,,,,2211)(21)(2111abababkkkkk−==−=−−−当k→∞时趋于零,这些区间最终收敛于一点x*即为所求的根。5/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis§7.2二分区间法每次二分后,取有根区间的中点作为根的近似值，得到一个近似根的序列该序列以根x*为极限只要二分足够多次(即k足够大),便有这里ε为给定精度,由于,则[]kkba,)(21kkkbax+=,,,,,210kxxxxε−kxx*[]kkbax,*∈6/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis§7.2二分区间法11122+++−=−=−kkkkkababab∵1*22+−=−≤−kkkkababxx7/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis§7.2二分区间法当给定精度ε＞0后,要想成立,只要取k满足即可，亦即当:ε−kxx*ε−+)(211abklg()lg1lg2bakKε−−≥−时,做到第K+1次二分,计算得到的就是满足精度要求的近似根。kx8/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis例7.2.2证明方程在区间[2,3]内有一个根,使用二分法求误差不超过0.5×10-3的根要二分多少次？证明令0523=−−xx且f(x)在[2,3]上连续,故方程f(x)=0在[2,3]内至少有一个根。又当时时，,故f(x)在[2,3]上是单调递增函数,从而f(x)在[2,3]上有且仅有一根。23)(2−=′xxf[]3,2∈x0)(′xf给定误差限ε＝0.5×10-3,使用二分法时52)(3−−=xxxf016)3(,01)2(=−=ff9/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis§7.2二分区间法误差限为只要取k满足)(211*abxxkk−≤−+311021)(21−+×≤−abk即可，亦即3102≥k97.92110lg3=≥gk所以需二分10次便可达到要求。10/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis§7.3迭代法及其加速为求解非线性方程f(x)=0的根，先将其写成便于迭代的等价方程其中为x的连续函数)(xϕ)(xxϕ=迭代法的基本思想如果数使f(x*)=0,则也有,反之,若,则也有,称为迭代函数，而称x*为的不动点。*x)(**xxϕ=)(**xxϕ=0)(*=xf)(xϕ)(xϕ11/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis§7.3迭代法及其加速任取一个初值,代入式的右端,得到0x)(xxϕ=)(01xxϕ=再将代入式的右端,得到,依此类推,得到一个数列…，其一般表示1x)(xxϕ=)(12xxϕ=)(23xxϕ=),2,1,0()(1==+kxxkkϕ称为求解非线性方程的简单迭代法。12/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis§7.3迭代法及其加速如果由迭代格式产生的序列收敛,即{}nx)(1kkxxϕ=+*limxxnn=∞→则称迭代法收敛。13/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis定理7.3.1设函数在[a,b]上有连续的一阶导数,且满足（1）对所有的x∈[a,b]有∈[a,b]（2）存在0L1,使所有的x∈[a,b]有≤L则方程在[a,b]上的解存在且唯一，对任意的初值∈[a,b]，迭代过程均收敛于。并有误差估计式)(xϕ)(xϕ)(xϕ′)(xxϕ=*x0x)(1kkxxϕ=+*x1*1−−−≤−kkkxxLLxx01*1xxLLxxkk−−≤−①②14/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis由连续函数介值定理知,必有∈[a,b],使所以有解存在,即假设有两个解和,,∈[a,b]，则，由微分中值定理有其中ξ是介于x*和之间的点从而有ξ∈[a,b]，进而有由条件(2)有1,所以-=0，即=，解唯一。证:构造函数,由条件①对任意的x∈[a,b]∈[a,b]有xxx−=)()(ϕψ0)()(0)()(≤−=≥−=bbbaaaϕψϕψ)(xϕ*x0)()(***=−=xxxϕψ*xx~*xx~)(**xxϕ=)~(~xxϕ=)~)(()~()(~***xxxxxx−′=−=−ξϕϕϕx~[]0)(1)~(*=′−−ξϕxx)(xϕ′*xx~*xx~15/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis按迭代过程,有)(1−=kkxxϕ))(()()(1*1**−−−′=−=−kkkxxxxxxξϕϕϕ1*1**))((−−−≤−′=−kkkxxLxxxxξϕ0*2*21**xxLxxLxxLxxkkkk−≤≤−≤−≤−−−由于L1,所以有,可见L越小,收敛越快*limxxkk→∞→再证误差估计式1*1−−−≤−kkkxxLLxx01*1xxLLxxkk−−≤−①②16/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis∵1*1**−−−+−=−≤−kkkkkxxxxLxxLxx)(1*−−+−≤kkkxxxxL1*)1(−−≤−−kkkxxLxxL1*1−−−≤−kkkxxLLxx∴即①得证。2121211))(()()(−−−−−−−−≤−′=−=−kkkkkkkkxxLxxxxxxξϕϕϕ2*11210111kkkkkkLLLxxxxxxxxLLL−−−−≤−≤−≤≤−−−−即②得证。17/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis§7.3迭代法及其加速例7.3.2对方程,构造收敛的迭代格式,求其最小正根。解容易判断[1,2]是方程的有根区间,且在此区间内,所以此方程在区间[1,2]有且仅有一根。将原方程改写成以下两种等价形式0245=−−xx045)(4−=′xxf18/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis§7.3迭代法及其加速①,即不满足收敛条件。②,即此时迭代公式满足迭代收敛条件。425−=xx[]2,1145)(,42)(45∈=′−=xxxxxϕϕ524+=xx,24)(5+=xxϕ[]2,112.0)24(51)24(51)(5454∈≈++=′xxxϕ19/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis§7.3迭代法及其加速迭代法的局部收敛性定理7.3.2设在的根的邻域中有连续的一阶导数,且则迭代过程具有局部收敛性。)(xϕ)(xxϕ=*x1)(*′xϕ)(1kkxxϕ=+定义（局部收敛性）如果存在x*的某个邻域，当初值x0属于此邻域时，迭代过程收敛，则称此迭代过程具有局部收敛性。)(1kkxxϕ=+20/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis§7.3迭代法及其加速证明:由于,存在充分小邻域△:,使成立这里L为某个定数,根据微分中值定理由于,又当时,故有由定理7.3.1知对于任意的都收敛1)(*′xϕδ−*xx1)(*≤′Lxϕ))(()()(**xxxx−′=−ξϕϕϕ**)(xx=ϕΔ∈xΔ∈ξδϕ−≤−≤−***)(xxxxLxx)(1kkxxϕ=+Δ∈0x21/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis例7.3.3设,要使迭代过程局部收敛到,求的取值范围。解：由在根邻域具有局部收敛性时,收敛条件)5()(2−+=xxxαϕ)(1kkxxϕ=+5*=x)5()(2−+=xxxαϕxxαϕ21)(+=′1521)(*+=′axϕ15211+−a0522−a所以051−a5*=xα22/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis例7.3.4已知方程在内有根,且在上满足,利用构造一个迭代函数,使局部收敛于。解:由可得,)(xxϕ=[]ba,*x[]ba,13)(−′xϕ)(xϕ)(xg),2,1,0()(1==+kxgxkk*x)(xxϕ=xxxx3)(3−=−ϕ)()3)((21xgxxx=−−=ϕ1213)(21)3)((21)(−′=−′−=′xxxgϕϕ[]bax,∈故,迭代公式1)(*′xg)3)((21)(1kkkkxxxgx−−==+ϕ局部收敛23/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis§7.3迭代法及其加速定义设迭代过程收敛于的根,记迭代误差若存在常数p（p≥1）和c（c0），使)(1kkxxϕ=+)(xxϕ=*xkkxxe−=*迭代法的收敛速度ceepkkk=+∞→1lim则称序列是p阶收敛的,c称渐近误差常数。特别地,p=1时称为线性收敛,p=2时称为平方收敛。1p2时称为超线性收敛。{}kx24/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis定理7.3.3设迭代过程,若在所求根的邻域连续且则迭代过程在邻域是p阶收敛的。证:由于即在邻域,所以有局部收敛性,将在处泰勒展开)(1kkxxϕ=+)()(xpϕ*x0)(,0)()()(*)(*)1(**≠===′′=′−xxxxppϕϕϕϕ*x0)(*=′xϕ*x1)(*′xϕ)(1kkxxϕ=+)(kxϕ*xpkpkkkxxpxxxxxxxx))((!1))((!21))(()()(*)(2*****−++−′′+−′+=ξϕϕϕϕϕ根据已知条件得pkpkxxpxx))((!1)()(*)(*−=−ξϕϕϕ由迭代公式)(1kkxxϕ=+及)(**xxϕ=有pkpkxxpxx)(!)(*)(*1−=−+ξϕ0!)(lim*)(1≠=+∞→pxeeppkkkϕ⇒25/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalysis§7.3迭代法及其加速例7.3.5已知迭代公式收敛于证明该迭代公式平方收敛。证:迭代公式相应的迭代函数为21132kkkxxx+=+3*3=x2132)(xxx+=ϕ436)(232)(xxxx=′′−=′ϕϕ，根据定理7.3.3可知，迭代公式平方收敛。3*3=x032336)(0)(33**≠==′′=′xxϕϕ，26/38郑州大学研究生2009-2010学年课程数值分析NumericalAnalys