6.2迭代法

1第二节迭代法2©2009,HenanPolytechnicUniversity2§2迭代法第六章方程求根它是一种逐次逼近的方法,用某个固定公式反复校正根的近似值,使之逐步精确化，最后得到满足精度要求的结果。3©2009,HenanPolytechnicUniversity3§2迭代法第六章方程求根6.2.1迭代法的基本思想为求解非线性方程f(x)=0的根，先将其写成便于迭代的等价方程)(x)(xx其中为x的连续函数。4©2009,HenanPolytechnicUniversity4§2迭代法第六章方程求根即如果数使f(x)=0,0x)(xx)(01xx任取一个初值,代入式的右端,得到则也有反之,若,则也有再将代入式的右端,1x)(xx得到)(12xx0)(f)()(5©2009,HenanPolytechnicUniversity5§2迭代法第六章方程求根),(),(3423xxxx上式称为求解非线性方程的简单迭代公式,依此类推,得到一个数列其一般表示)(x称为迭代函数。),2,1,0(),(1nxxnn6©2009,HenanPolytechnicUniversity6§2迭代法第六章方程求根例1试用迭代法求方程在区间(1，2)内的实根。31xx01)(3xxxf311kkxx解：由建立迭代关系计算结果如下:k=0,1,2,3…….7©2009,HenanPolytechnicUniversity7§2迭代法第六章方程求根精确到小数点后五位kk01.551.3247611.3572161.3247321.3308671.3247231.3258881.3247241.324945102132472.1xkxkx8©2009,HenanPolytechnicUniversity8§2迭代法第六章方程求根但如果由建立迭代公式13xx,...2,1131kxxkk5.10x2.3751x12.392x}{kx仍取，则有显然结果越来越大，是发散序列9©2009,HenanPolytechnicUniversity9§2迭代法第六章方程求根（全局收敛定理）],[)(bax在设为常数）LLxbax(1|)('|],,[)2(0111011||3(],,[)2(],[)()1(xxLLxxLLxxxbaxbaxxnnnnnn）（）收敛到；有唯一根在方程则：;)(1bxabxa时，）当（6.2.2收敛性分析10©2009,HenanPolytechnicUniversity10§2迭代法第六章方程求根①存在唯一性做辅助函数)()(xxx，则有0)(,0)(ba所以，存在点*)(*0*)(.,.*,xxxtsx若*)*(**xx，则有：***xx又，1L***xx*)*(*)(xx*)**)(('xx***xxL11©2009,HenanPolytechnicUniversity11§2迭代法第六章方程求根②],[0bax则*1xxk*1xxk所以，任意的初值都收敛*)()(xxk*))(('xxk*12xxLk*xxLk*01xxLk12©2009,HenanPolytechnicUniversity12§2迭代法第六章方程求根③误差估计nnxx1)()(1nnxx212nnxxL1nnxxL01xxLn　nnxx1)()(1nnxx　1nnxxnnxLxnxL)1(13©2009,HenanPolytechnicUniversity13§2迭代法第六章方程求根　　－nnnxxLx111注：L越小，收敛越快。11nnxxLL－011xxLLn－14©2009,HenanPolytechnicUniversity14§2迭代法第六章方程求根例2证明函数在区间[1，2]上满足迭代收敛条件。31)(xx上严格单调增函数。是区间所以因为],[)(]2,1[0)1(31)(32'baxxxx证明：15©2009,HenanPolytechnicUniversity15§2迭代法第六章方程求根]2,1[1431|)1(31||)(|332'xLxx又23)2(12)1(33，而）。满足条件（，所以即1)(]2,1[)]2(),1([x）。满足条件（所以2)(x满足收敛条件。在故]2,1[1)x(3x16©2009,HenanPolytechnicUniversity16§2迭代法第六章方程求根若取迭代函数不满足定理，故不能肯定收敛到方程的根。1)x(3x]2,1[3|3||)(|2'xxx因为,....1,0)(1nxxnn17©2009,HenanPolytechnicUniversity17§2迭代法第六章方程求根定理设是方程的根，如果满足条件：（1）迭代函数在的邻域可导；（2）在的某个邻域，对于任意，有)(xx局部收敛性)(xSx}{xxS1)(Lx18©2009,HenanPolytechnicUniversity18§2迭代法第六章方程求根则对于任意的初始值，由迭代公式产生的数列收敛于方程的根。（这时称迭代法在的S邻域具有局部收敛性。）nx)(1nnxxSx019©2009,HenanPolytechnicUniversity19§2迭代法第六章方程求根例3设，要使迭代过程局部收敛到,求的取值范围。解：由在根邻域具有局部收敛性时，收敛条件)5()(2xaxx)(1kkxx5*xa)5()(2xaxxaxx21)(5*x20©2009,HenanPolytechnicUniversity20§2迭代法第六章方程求根1521)(*ax15211a0522a所以051a21©2009,HenanPolytechnicUniversity21§2迭代法第六章方程求根实际计算中当然不可能也没必要无穷多步地做下去,对预先给定的精度要求ε，只要某个n满足即可结束计算并取当然，迭代函数的构造方法是多种多样的。)(x1nnxxnx22©2009,HenanPolytechnicUniversity22§2迭代法第六章方程求根xyy=xx*y=g(x)x0p0x1p1xyy=xx*y=g(x)x0p0x1p1简单迭代收敛情况的几何解释23©2009,HenanPolytechnicUniversity23§2迭代法第六章方程求根定义设迭代过程收敛于的根,记迭代误差若存在常数p（p≥1）和c（c0），使)(1kkxx)(xx*xkkxxe*ceepkkk1lim则称序列是p阶收敛的,c称渐近误差常数。特别地,p=1时称为线性收敛,p=2时称为平方收敛。1p2时称为超线性收敛。kx6.2.3迭代法的收敛速度24©2009,HenanPolytechnicUniversity24§2迭代法第六章方程求根数p的大小反映了迭代法收敛的速度的慢，p愈大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。25©2009,HenanPolytechnicUniversity25§2迭代法第六章方程求根定理设迭代过程,若在所求根的邻域连续且则迭代过程在邻域是p阶收敛的。)(1kkxx)()(xp*x0)(,0)()()(*)(*)1(**xxxxpp*x0)(*x*x1)(*x)(1kkxx)(kx*x证:由于所以有局部收敛性,将在处泰勒展开即在邻域,26©2009,HenanPolytechnicUniversity26§2迭代法第六章方程求根pkpkkkxxpxxxxxxxx))((!1))((!21))(()()(*)(2*****根据已知条件得pkpkxxpxx))((!1)()(*)(*由迭代公式)(1kkxx及)(**xx有pkpkxxpxx)(!)(*)(*10!)(lim*)(1pxeeppkkk27©2009,HenanPolytechnicUniversity27§2迭代法第六章方程求根例4已知迭代公式收敛于证明该迭代公式平方收敛。21132kkkxxx3*3x2132)(xxx436)(232)(xxxx，证:迭代公式相应的迭代函数为将代入，根据定理可知，迭代公式平方收敛。3*3x032336)(0)(33**xx，28©2009,HenanPolytechnicUniversity28§2迭代法第六章方程求根为了使迭代过程收敛或提高收敛的速度,可设法①提高初值的精度以减少迭代的次数②提高收敛的阶数p29©2009,HenanPolytechnicUniversity29§2迭代法第六章方程求根（1）迭代-加速公式（加权法）设是根的某个近似值,用迭代公式校正一次得kx*x)(1kkxx)(**xx))(()()(**1*kkkxxxxxx),(*kxx6.2.4迭代过程的加速又根据中值定理有30©2009,HenanPolytechnicUniversity30§2迭代法第六章方程求根可见,若将迭代值与加权平均,则可得到的1kxkxkkkxLLxLx11111是比更好的近似根1kx)(*1*kkxxLxxkkxLLxLx1111*则有：当范围不大时,设变化不大,其估计值为L)(*kxx)(31©2009,HenanPolytechnicUniversity31§2迭代法第六章方程求根迭代：改进：或合并写成：)(1_kkxxkkkxLLxLx1111_1kkkLxxLx)(11132©2009,HenanPolytechnicUniversity32§2迭代法第六章方程求根例5用加权法加速技术求方程在0.5附近的一个根。xex5.00x6.0'5.05.05.0eexx取L=-0.6，建立如下迭代公式解：因为在附近33©2009,HenanPolytechnicUniversity33§2迭代法第六章方程求根仍取,逐次计算得=0.56658…=0.56714。迭代4次便可得到精度的结果,而不用加速技术需迭代18次,效果显著。5.00x1x4x410kxkxkxexexkk6.06.116.0)6.0(11134©2009,HenanPolytechnicUniversity34§2迭代法第六章方程求根（2）埃特金（Aitken）方法在加权法中,估计L的值有时不太方便。假设在求得以后,先求出kx)(~1kkxx)(**xx)()()(~***1xxLxxxxkkk由利用中值定理可得(在求根区间变化不大,用某个定值L近似地替代之))(35©2009,HenanPolytechnicUniversity35§2迭代法第六章方程求根将迭代值再迭代一次,得新的迭代值)~()()~(*1*1*1xxLxxxxkkkkkkkkkxxxxxxx112111*~2)~(1~kx)~(11kkxx将上述两个方程联立消去常数L化简可得则36©2009,HenanPolytechnic