数值分析--第7章-非线性方程与方程组的数值解法

第7章非线性方程与方程组的数值解法7.1方程求根与二分法7.2不动点迭代法及其收敛性7.3迭代收敛的加速方法7.4牛顿法7.5弦截法与抛物线法7.6求根问题的敏感性与多项式的零点7.7非线性方程组的数值解法27.1方程求根与二分法7.1.1引言0)(xf（1.1）本章主要讨论求解单变量非线性方程其中也可以是无穷区间.],[],,[)(,RbabaCxfx如果实数满足，则称是方程(1.1)的根，或称是的零点.*x)(xf0*)(xf*x*x3若可分解为)(xf),(*)()(xgxxxfm其中为正整数，且则称为方程(1.1)的重根，或为的重零点，时为单根.m.0*)(xg1m*xm若是的重零点，且充分光滑，则*x)(xfm)(xg,0*)(*)(*)()1(xfxfxfm.0*)()(xfm*x)(xfm如果函数是多项式函数，即),0()(01110aaxaxaxaxfnnnn（1.2）其中为实数，则称方程(1.1)为次代数方程.),,1,0(,00niaai)(xfn4它在整个轴上有无穷多个解，若取值范围不同，解也不同，因此讨论非线性方程(1.1)的求解必须强调的定义域，即的求解区间5n时的求根公式是熟知的，时的求根公式可在数学手册中查到，但比较复杂不适合数值计算，当时就不能用公式表示方程的根，所以时求根仍用一般的数值方法2,1n4,3n根据代数基本定理可知,次方程在复数域有且只有个根（含重根，重根为个根）.,010sine10/xxmmnn3nx另一类是超越方程，例如xxx].,[ba5迭代法要求先给出根的一个近似，若且，根据连续函数性质可知在内至少有一个实根，这时称为方程(1.1)的有根区间.非线性问题一般不存在直接的求解公式，故没有直接方法求解，都要使用迭代法.*x],[)(baCxf0)()(bfaf0)(xf),(ba],[ba通常可通过逐次搜索法求得方程的有根区间.0)(xf6例1求方程的有根区间.解根据有根区间定义，对的根进行搜索计算，结果如下：0)(xf077.418.381.11)(23xxxxf的符号)(65432101-7表xfx计算结果由此可知方程的有根区间为].6,5[],4,3[],2,1[7检查与是否同号，如果同号，说明所求的根在的右侧,这时令否则必在的左侧，这时令见图7-1.*x0x考察有根区间，取中点将它分为两半，],[ba2/)(0bax7.1.2二分法假设中点不是的零点，然后进行根的搜索.0x)(xf)(0xf)(af*x0x,01xa;1bb,1aa.01xb图7-1不管出现哪一种情况，新的有根区间的长度仅为的一半.],[11ba],[ba8对压缩了的有根区间又可施行同样的手续，即用中点将区间再分为两半，然后通过根的搜索判定所求的根在的哪一侧，从而又确定一个新的有根区间，其长度是的一半.2/)(111bax],[11ba],[11ba1x],[22ba],[11ba如此反复二分下去，即可得出一系列有根区间,],[],[],[],[2211kkbabababa其中每个区间都是前一个区间的一半，因此的长度],[kkbakkkabab2/)(当时趋于零.k9就是说，如果二分过程无限地继续下去，这些区间最终必收缩于一点，该点显然就是所求的根.*x作为根的近似，则在二分过程中可以获得一个近似根的序列,,,,,210kxxxx该序列必以根为极限.*x每次二分后，设取有根区间的中点],[kkba2/)(kkkbax10由于2/)(*kkkabxx只要二分足够多次（即充分大），便有k,*kxx这里为预定的精度.（1.3）,2/)(1kab11例2求方程01)(3xxxf在区间内的一个实根，要求准确到小数点后第2位.]5.1,0.1[解这里，而5.1,0.1ba取的中点，将区间二等分，由于，即与同号，故所求的根必在右侧，这时应令，而得到新的有根区间],[ba25.10x0)(0xf)(0xf)(af*x0x5.1,25.1101bbxa如此反复二分下去,按误差估计（1.3）式,欲使0)(,0)(bfaf].,[11ba（1.3）,2/)(*1kkabxx只需，即只要二分6次，便能达到预定的精度.6k2/)(*kkkabxx12/)(kab,005.021211k12计算结果如表7-2.3242.13203.063203.13281.153281.13438.143438.13125.133125.1375.12375.125.1125.15.10.10符号)(27kkkkxfxbak表13二分法是计算机上的一种常用算法，计算步骤为：步骤1准备计算在有根区间端点处的值)(xf).(),(bfaf],[ba步骤2二分计算在区间中点处的值)(xf2ba).2(baf步骤3判断若，则即是根，计算过程结束，否则检验.0)2(baf2ba若，则以代替，否则以0)()2(afbaf2bab代替.2baa14此时中点即为所求近似根.2ba误差，反复执行步骤2和步骤3，直到区间长度小于允许],[ba157.2不动点迭代法及其收敛性7.2.1不动点与不动点迭代法将方程（1.1）改写成等价的形式).(xx（2.1）若满足，则；反之亦然，称为函数的一个不动点.*x0*)(xf*)(*xx*x)(x求的零点就等价于求的不动点.)(xf)(x选择一个初始近似值，将它代入(2.1)右端，即可求得0x).(01xx0)(xf（1.1）16如此反复迭代计算).,1,0()(1kxxkk（2.2）称为迭代函数.)(x如果对任何，由（2.2）得到的序列有极限],[0bax}{kx.*limxxkk则称迭代方程(2.2)收敛，且为的不动点，故称（2.2）为不动点迭代法.*)(*xx)(x17方程的求根问题在平面上就是要确定曲线与直线的交点)(xxxy)(xyxy.*P对于的某个近似值，在曲线上可确定一点，它以为横坐标，而纵坐标则等于*x0x)(xy0P0x.)(10xx就是说，迭代过程实质上是一个逐步显示化的过程.过引平行轴的直线，设此直线交直线于点，0Pxxy1Q然后过再作平行于轴的直线，1Qy与曲线的交点)(xy上述迭代法是一种逐次逼近法，其基本思想是将隐式方程归结为一组显式的计算公式.)(xx)(1kkxx18则点的横坐标为，1P1x图7-21P记作，.)(21xx纵坐标则等于按图7-2中箭头所示的路径继续做下去.在曲线上得到点列，)(xy21,PP其横坐标分别为19例3求方程01)(3xxxf（2.3）在附近的根5.10x.*x解设将方程（2.3）改写成下列形式.13xx依公式求得的迭代值)(1kkxx.,21xx如果点列趋向于点，则相应的迭代值收敛到所求的根}{kP*Pkx.*x据此建立迭代公式2032494.1432472.1832588.1332472.1733086.1232473.1635721.1132476.155.1037表kkxkxk).,2,1,0(131kxxkk各步迭代的结果见表7-3.这时可以认为实际上已满足方程(2.3)，即为所求的根.7x如果仅取6位数字，那么结果与完全相同，7x8x01)(3xxxf（2.3）21但若采用方程（2.3）的另一种等价形式13xx建立迭代公式.131kkxx仍取迭代初值，则有5.10x.39.12,375.221xx结果会越来越大，不可能趋于某个极限.这种不收敛的迭代过程称作是发散的.如图7-3.一个发散的迭代过程，纵使进行了千百次迭代，其结果也是毫无价值的.图7-3227.2.2不动点的存在性与迭代法的收敛性首先考察在上不动点的存在唯一性.],[ba)(x定理1设满足以下两个条件：],[)(baCx1.对任意有],[baxbxa)(2.存在正常数，使对任意都有1L],[,bayx.)()(yxLyx（2.4）则在上存在唯一的不动点)(x],[ba.*x23因，bxa)(以下设及，aa)(bb)(若或，则不动点为或，aa)(bb)(ab存在性得证.定义函数.)()(xxxf显然，],[)(baCxf,0)()(aaaf由连续函数性质可知存在,),(*bax*),(*xx且满足,0)()(bbbf使,0*)(xf即即为的不动点.)(x*x证明先证不动点存在性.24再证唯一性.设都是的不动点，],[,21baxx)(x)()(2121xxxx引出矛盾.故的不动点只能是唯一的.)(x则由(2.4)得.2121xxxxL.)()(yxLyx（2.4）25.1*01xxLLxxkk（2.5）定理2设满足定理1中的两个条件，则对任意，由（2.2）得到的迭代序列收敛到的不动点，并有误差估计],[)(baCx],[0bax}{kx)(x*x证明设是在上的唯一不动点，由条件，可知，再由（2.4）得],[ba],[*bax)(x],[}{baxk*)()(*1xxxxkk因，故当时序列收敛到.10Lk}{kx*x*1xxLk.*0xxLk.)()(yxLyx（2.4）).,1,0()(1kxxkk（2.2）26再证明估计式（2.5），)()(11kkkkxxxx由（2.4）有（2.6）.1kkxxL反复递推得.011xxLxxkkk于是对任意正整数有pkkpkpkpkpkkpkxxxxxxxx12110121)(xxLLLkpkpk.101xxLLk.1*01xxLLxxkk（2.5）.)()(yxLyx（2.4）27在上式令，注意到即得式（2.5）.p*limxxpkp迭代过程是个极限过程.在用迭代法实际计算时，必须按精度要求控制迭代次数.原则上可以用误差估计式（2.5）确定迭代次数，但由于它含有信息而不便于实际应用.L根据式（2.6），对任意正整数有pkkppkpkxxLLxx121)1(.111kkxxL在上式中令知p)()(11kkkkxxxx（2.6）.1kkxxL.1*01xxLLxxkk（2.5）28.11*1kkkxxLxx由此可见，只要相邻两次计算结果的偏差kkxx1足够小即可保证近似值具有足够精度.kx对定理1和定理2中的条件2，如果且对任意有],[bax,1)(Lx（2.7）则由中值定理可知对有],[,bayx))(()()(yxyx表明定理中的条件2可用（2.7）代替.],,[)(1baCx).,(,bayxL29例3中，当时，,在区间中，，故（2.7）成立.31)(xx3/2)1(31)(xx]2,1[14131)(3/1x又因，故定理1中条件1也成立.所以迭代法是收敛的.23)(2133x而当时，，在区间中不满足定理条件.1)(3xx23)(xx]2,1[1)(x,1)(Lx（2.7）307.2.3局部收敛性与收敛阶上面给出了迭代序列在区间上的收敛性，}{kx],[ba定理的条件有时不易检验，实际应用时通常只在不动点的邻近考察其收敛性，即局部收敛性.*x定义1设有不动点，如果存在的某个邻域对任意，迭代（2.2）产生的序列且收敛到，