数值计算方法(第2章).

第2章非线性方程与方程组的数值解法本章重点介绍求解非线性方程的几种常见和有效的数值方法,同时也对非线性方程组求解,简单介绍一些最基本的解法.无论在理论上,还是在实际应用中,这些数值解法都是对经典的解析方法的突破性开拓和补充,许多问题的求解,在解析方法无能为力时,数值方法则可以借助于计算机出色完成.0)(xf),,2,1(0),,,(21nixxxfni2.1二分法求非线性方程0)(xf确定方程的有根区间计算根的近似值的根的方法分为两步：首先确定有限区间：依据零点定理。设，且，则方程在区间上至少有一个根。如果在上恒正或恒负，则此根唯一。],[)(baCxf0)()(bfaf0)(xf),(ba)('xf),(ba等步长扫描法求有根区间用计算机求有根区间：等步长扫描法。设h0是给定的步长，取，若则扫描成功；否则令，继续上述方法，直到成功。如果则扫描失败。再将h缩小，继续以上步骤。haxax10,0)()(10xfxfhxxxx0110,bx1等步长扫描算法算法：（求方程的有根区间）(1)输入；(2)；(3)，若输出失败信息，停机。(4)若。输出，已算出方程的一个根，停机。0)(xfhba,,)(0aff)(,1xffhaxbx01fx等步长扫描算法(5)若。输出为有根区间，停机(6)，转3）注：如果对足够小的步长h扫描失败。说明：在内无根在内有偶重根010ff],[,,xaxaxa],[ba],[ba二分法用二分法(将区间对平分)求解。令若，则为有根区间，否则为有根区间记新的有根区间为，则且)(,,1121111bacbbaa0)()(11cfaf],[11ca],[11bc],[22ba],[],[2211baba)(112122abab二分法对重复上述做法得且],[22ba......],[......],[],[2211nnbababa)(211ababnnn二分法设所求的根为，则即取为的近似解x......2,1],[nbaxnn......2,1nbxann0)(21lim)(lim1nababnnnnxbannnnlimlim)(21nnnbacxx求方程f(x)=0的根的二分法算法).(21)4(;endwhile].,[],[];,[],[0)()()2);(),(21)1||)3(;3,,10)()()2(;,],[:)1(baxbxbaelsexabathenxfafifxfbaxbawhileelsebathenbfafifbaba输出计算令时做步转第值输入重新步返回第值及精度控制量的有根区间输入求方程f(x)=0的全部实根的二分法算法);();(211||while)2endwhile;;;0)()(while)1while)3(;;)2(;,,,:)1(11011111111111xfbaxabhabaabfafbbhabaahba计算时做做时做输入求方程f(x)=0的全部实根的二分法算法;endwhile;;10;:)3;endwhile].,[],[],[],[0)()(if3);3(0)(if2111111111100habhxaxbxbaelsexabathenxfafxf输出转例题例1设方程解：取h=0.1,扫描得：又即在有唯一根。]2,1[],[,1)(3baxxxf0344.0)4.1(061.0)3.1(ff].4.1,3.1[方程的有根区间为]4.1,3.1[,013)(2'xxxf0)(xf]4.1,3.1[2.2一般迭代法2.2.1迭代法及收敛性对于有时可以写成形式如：0)(xf)(xx3331101xxxxxxxxxxcos0cos迭代法及收敛性考察方程。这种方程是隐式方程，因而不能直接求出它的根，但如果给出根的某个猜测值，代入中的右端得到，再以为一个猜测值，代入的右端得反复迭代得)(xx0x)(xx)(01xx1x)(xx)(12xx,......1,0)(k1kkxx迭代法及收敛性若收敛，即则得是的一个根}{kxxxkklimx)(xx)()lim()(limlim1nxxxxxnnnnn迭代法的几何意义交点的横坐标*x)()(xyxyxxy=x2x0x1x简单迭代法将变为另一种等价形式。选取的某一近似值，则按递推关系产生的迭代序列。这种方法算为简单迭代法。0)(xf)(xxx],[0bax,......1,0)(k1kkxx}{kx例题例2.2.1试用迭代法求方程在区间(1，2)内的实根。解：由建立迭代关系k=10,1,2,3…….计算结果如下:31xx01)(3xxxf311kkxx例题精确到小数点后五位5102132472.1x例题但如果由建立迭代公式仍取，则有，显然结果越来越大，是发散序列1x3x,...2,1131kxxkk5.10x2.3751x12.392x}{kx迭代法的收敛性定理2.2.1（压缩映像原理）设迭代函数在闭区间上满足（1）（2）满足Lipschitz条件即有且。)(x],[ba],[)(],[baxbax)(x],[,21baxx)()(2121xxLxx10L压缩映像原理则在上存在唯一解，且对，由产生的序列收敛于。)(xx],[0bax)(k1kxx}.{1kxx],[bax压缩映像原理证明：不失一般性,不妨设否则为方程的根。首先证明根的存在性令bbaa)(,)(ba或xxx)()(压缩映像原理则，即由条件2）是上的连续函数是上的连续函数。故由零点定理在上至少有一根0)()(aaa0)(b0)()(ba)(x],[ba)(x所以],[ba0)(x],[ba),(bax压缩映像原理再证根的唯一性设有均为方程的根则因为0L1，所以只可能，即根是唯一的。],[,21baxx|||)()(|||212121xxLxxxx21xx压缩映像原理最后证迭代序列的收敛性与n无关，而0L1即|)()(|||1xxxxnn由于||1xxLn||0xxLn......xx,0因为0lim||||lim0nnnnLxxxx所以xxnnlim压缩映像原理误差估计若满足定理2.2.1条件，则这是事后估计，也就是停机标准。L越小，收敛速度越快。这是事前估计。选取n，预先估计迭代次数。)(xx||L1L||1nnxxxxn||L1L||01nxxxxn例题例2.2.2证明函数在区间[1，2]上满足迭代收敛条件。证明：31)x(x上严格单调增函数。是区间所以因为],[)(]2,1[0)1(31)x(32'baxxx例题]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例题若取迭代函数，不满足压缩映像原理，故不能肯定收敛到方程的根。1)x(3x]2,1[3|3||)(|2'xxx因为,....1,0)(1nxxnn简单迭代收敛情况的几何解释2.2.2Steffensen加速收敛法迭代法收敛的阶定义2.2.1设序列收敛到，若有实数和非零常数C，使得其中，，则称该序列是p阶收敛的，C称为渐进误差常数。0n}x{*x1pCeepnnn1lim*xxenn迭代法收敛的阶当p=1时，称为线性收敛；当p1时，称为超线性收敛；当p=2时，称为平方收敛或二次收敛。迭代法收敛的阶定理2.2.2设是方程的不动点，若为足够小的正数。如果且，则从任意出发，由产生的序列收敛到，当时敛速是线性的。*x)(xx],[**xxCx)(1|)(|*x0x)(1kkxx0}{nx*x0)(x迭代法收敛的阶证明：满足压缩映像原理知，及由Cxx)(1|)(|'*足够小时，有)(1|)(|xLx|||||)(||)()(||)(|****xxxxxxxxx有因此，对于迭代法收敛的阶敛速是线性的线性收敛到。0)()()(limlim***1nxxxxxeennnnn因为。收敛到故*0}{xxn满足压缩映像原理，所以即)(,)(xx0}{nx所以*xSteffensen迭代格式由线性收敛知当n充分大时有即0limlim112nCeeeennnnnnnnneeee112**1*1*2xxxxxxxxnnnnSteffensen迭代格式展开有：nnnnnnxxxxxxx1221*2)(2**121**2)(2))((xxxxxxxxnnnn2**1212**2*2)(2)(xxxxxxxxxxxnnnnnn*121*2*22xxxxxxxxxnnnnnn21212*)2(nnnnnnxxxxxxxSteffensen迭代格式已知，则，改成nx)(1nnxx))((2nnxxnnnnnnnnnnnxyzxyxxyzxy2)()()(21n=0，1，2，…Steffensen迭代格式也可以改写成其中迭代函数,......)1,0()(1nxxnnxxxxxxx)(2))((])([)(2Steffensen迭代法收敛的充要条件定理2.2.3],,[)(**1xxCx，设函数。件是的不动点的充分必要条是)()(***xxxxx，则为足够小的正数，且1)(*xSteffensen迭代法收敛的充要条件证明：必要性的不动点，是因为)(*xxx])(2))(()][([])([2xxxxxxx由于，所以0))((lim*xxxx，故有0))((lim*xxxx)(**xx即的不动点。是所以)(*xxxSteffensen迭代法收敛的充要条件充分性的不动点有是由)(*xxxxxxxxxxxxxx)(2))((])([lim)]([lim2**1)(2)())((]1)(][)([2lim*xxxxxxxxoo型0]1)([]1)(][)([2lim2*****xxxxxx的不动点。是所以)(*xxxSteffensen算法的收敛速度!)()(lim}{)(0)(0)(...)()(,],,[),1()(,)(4.2.2*)(**1*010*)1(*)1(*****pxxxxxxpxxxxxxxxxxpCxxxxppnnnnkkppp，且阶收敛速度收敛到，以列产生的序，由，则而如果为足够小的正数的不动点是设定理Steffensen算法的收敛速度定理2.2.5在定理2.2.3假设下，若产生的序列至少平方收敛到。,....2,1,02)()()(2