《计算方法》第二章方程求根

1计算方法华中科技大学数学与统计学院第二章方程求根计算方法课程组2§2方程求根§2.0引言§2.1二分法§2.3牛顿(Newton)法§2.4迭代过程的加速方法§2.2迭代法3方程是在科学研究中不可缺少的工具,方程求解是科学计算中一个重要的研究对象.几百年前就已经找到了代数方程中二次至四次方程的求解公式;但是,对于更高次数的代数方程目前仍无有效的精确解法;对于无规律的非代数方程的求解也无精确解法.因此,研究非线性方程的数值解法成为必然.()0fx本节主要研究单根区间上方程求根的各种近似算法.§2方程求根—引言4320xaxbxc2323231/33/21123329279540(||);sgn()()32cos(),3arccos(/);322cos(),3342cos(),33AaxBaabaabcAandBifBAobtainwhereBABelsewxAaxAaxAhereBA令求根公式5本章讨论非线性方程的求根问题，()0fx1110()(0)nnnnnfxaxaxaxaa1.其中一类特殊的问题就是多项式方程的求根。2.另一类就是超越方程的求根。()()10cosxcoshx6方程的根又称为的零点,它使若,可表示为，其中为正整数，且。当时，称为单根，若称为的重根，或的重零点。若是的重零点且充分光滑，则()0fx()0fx*x()fx*()0fx*()0fx*()()()mfxxxgxm*()0gx1m*x1m*xm()fx()fx**(1)*()*()()()0,()0mmfxfxfxfxm*xm()gx()fx()fx基本概念7求f(x)=0的根原理：若fC[a,b]，且f(a)·f(b)0，则f在(a,b)上必有一根。§2.1二分法yxbaf(x)x*称为方程的有根区间。[,]ab8给定有根区间[a,b](f(a)·f(b)0)和精度或1.令x=(a+b)/22.如果b–a或f(x),停机，输出x3.如果f(a)f(x)0,则令b=x，否则令a=x,返回第1步用二分法求根，通常先给出f(x)草图以确定根的大概位置。§2.1二分法—算法构造abx1x2abx*9记a1=a,b1=b,第k步的有根区间为[ak,bk]11224kkkkkkkbababaxxx112kba对于给定的精度,可估计二分法所需的步数k：2kbaε2log,bak取2logbak简单易用无法求复根及偶重根对f(x)要求不高，只要连续即可收敛收敛速度慢§2.1二分法—误差分析10例1:用二分法求方程在区间(1,2)内的实根,要求误差限为。01523xx210§2.1二分法—例题分析11.11.21.31.41.51.61.71.81.92-4-3-2-10123453()251fxxx11解：令f(1)0,f(2)0记I0=[1,2],x0=(1+2)/2=1.5因为f(x0)f(1)0得I1=[1.5,2],x1=(1.5+2)/2=1.75f(x1)f(1.5)0得I2=[1.5,1.75],x2=(1.5+1.75)/2=1.625…….I6=[1.681875,1.6875],I7=[1.671875,1.679688]b7-a7=0.781310-210-2x*x7=1.6758例1:用二分法求方程在区间(1,2)内的实根,要求误差限为。01523xx210152)(3xxxf§2.1二分法—例题分析12例2：求在(1,1.5)的实根,要求误差不超过0.005。3()10fxxx§2.1二分法—算法步骤11.051.11.151.21.251.31.351.41.451.5-1-0.8-0.6-0.4-0.200.20.40.60.813()10fxxx13例2：求在(1,1.5)的实根,要求误差不超过0.005。3()10fxxxSTEP0输入a,b,eps,delta,fa=f(a),fb=f(b)STEP1x=(a+b)/2,fx=f(x)STEP2判断：|b-a|epsor|fx|delta若是，gotostep4;否则，执行下一步STEP3若fb*fx0,则a=x否则b=x.gotostep1STEP4输出x,fx,停机.§2.1二分法—算法步骤14function[xvect,xdif,fx,nit]=bisect(a,b,toll,nmax,fun)err=toll+1;nit=0;xvect=[];fx=[];xdif=[];while(nitnmax&errtoll)nit=nit+1;c=(a+b)/2;x=c;fc=feval(fun,x);xvect=[xvect;x];fx=[fx;fc];x=a;if(fc*feval(fun,x)0)a=c;elseb=c;end;err=abs(b-a);xdif=[xdif;err];endreturnfun=inline('2*x.^3-5*x-1');[xvect,xdif,fx,nit]=bisect(1,2,0.01,50,fun)x值区间长函数值1.25000.2500-0.29691.37500.12500.22461.31250.0625-0.05151.34380.03130.08261.32810.01560.01461.32030.0078-0.01871.32420.0039-0.002115abab1kkxxε()fx或不能保证x的精度x*xx*程序算法说明:16f(x)=0等价变换f(x)的根的不动点()xx()x§2.2方程求根—不动点迭代法基本原理00.20.40.60.811.21.41.61.8201020304050606()xfex32371gxxfg323716(0)xxxex17f(x)=0等价变换f(x)的根的不动点思路从一个初值x0出发，计算x1=(x0),x2=(x1),…,xk+1=(xk),…若收敛，即存在x*使得，且连续，则由可知x*=(x*)，即x*是的不动点，也就是f的根。0kkx*limxxkk1limlimkkkkxx()xx()x§2.2方程求根—不动点迭代法基本原理18将转化为的方法有多种多样，例：在上可有以下方法：(1)(2)(3)(4)取,有的收敛、有的发散、有的快、有的慢。()0fx()xx32()4100fxxx[1,2]32410xxxx31/2(1/2)(10)xx1/2(10/4)xxx1/2[10/(4)]xx01.5x19xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p120123xx将原方程化为等价方程12301xx112312xx312323xx55§2.2迭代法—算例分析3210xx例如:用迭代法求解方程解1:00x取初值显然迭代法发散2100x30121xx仍取初值3217937.031221xx327937.19644.0x2=0.9644x3=0.9940x4=0.9990x5=0.9998x6=1.0000x7=1.0000依此类推,得已经收敛,故原方程的解为0000.1x同样的方程不同的迭代格式有不同的结果什么形式的迭代法能够收敛呢?迭代函数的构造有关312xx(2)如果将原方程化为等价方程3210xx22例如：求方程在附近的根3()10fxxx01.5x*x§2.2迭代法—算例分析223解：将方程改写为，由此建立迭代公式：计算结果如下表例如：求方程在附近的根3()10fxxx01.5x*x311(0,1,2,)kkxxk0123456781.51.357211.330861.325881.324941.324761.324731.324721.32472kxk311kkxx§2.2迭代法—算例分析2这是一个收敛的不动点迭代格式.24这是一个收敛的例子，也有不收敛的迭代公式，如对于同样的问题，如果将方程改写为令一种迭代公式，仍取初值，则迭代发散。为此，研究存在性及迭代法的收敛性。解：将方程改写为，由此建立迭代公式：计算结果如下表例如：求方程在附近的根3()10fxxx01.5x*x31xx311(0,1,2,)kkxxk0123456781.51.357211.330861.325881.324941.324761.324731.324721.32472kxk311kkxx01.5x()x§2.2迭代法—算例分析225设满足以下两个条件：(1)对任意的，有(2)存在，使对任意都有则在上存在唯一的不动点。§2.2方程求根—迭代法的收敛性定理(存在性)[,]xab()axb01L,[,]xyCab()()xyLxy()x*x[,]ab()[,]xCab26证明：先证不动点的存在性。若或，则或就是不动点。因此由可设及，定义函数，显然且满足由函数的连续性可知,存在使，即，即为的不动点。§2.2方程求根—迭代法的收敛性*x()aa()bbab()axb()aa()bb()()fxxx()()0,()()0faaafbbb()[,]fxCab*(,)xab*()0fx*x()x27再证唯一性。设及都是的不动点，则由定理的条件(2)，得到矛盾，故的不动点是唯一的。证毕*1x*2[,]xab()x********12121212()()xxxxLxxxx()x28定理2：(收敛的充分条件)设满足定理1的两个条件，则对任意，由得到的迭代序列收敛到的不动点，并有误差估计()[,]xCab0[,]xab1()kkxxkx*x()x*101kkLxxxxL29证明：设是在上的唯一不动点，由条件1可知，再由条件2得因，故当时，序列收敛到。由迭代公式可得据此反复递推，得到于是对任意正整数，有在上式令，注意到即得到结果。证毕111()()kkkkkkxxxxLxx110kkkxxLxx1121121010()1kpkkpkpkpkpkkkpkpkkxxxxxxxxLLLxxLxxLp*limkppxx*[,]xab()x[,]ab[,]kxab****110()()kkkkxxxxLxxLxx01Lkkx*x30根据定理2的结论，对于给定的计算精度，迭代次数是可以预先确定的，但由于公式中含有常数，使得计算迭代次数较为复杂，根据估计式我们得到：令，得到由此可知，只要相邻两次计算结果的偏差足够小即可保证近似值有足够的精度。111()()kkkkkkxxxxLxxL112112111(1)1kpkkpkpkpkpkkppkkkkxxxxxxxxLLxxxxLp*111kkkxxxxL1kkxxkx31对于定理中的条件2，在实际使用时，如果且对任意的有则由中值定理可知有它表明定理中条件2可由替代。1()[,]xCab[,]xab()1xL,[,]xyab()()()(),(,)xyxyLxyab