第二章函数方程求根

第二章函数方程的求根11,:,0)(RRbafxf例如:多项式方程0)(0111axaxaxaxfnnnn和函数方程0|sin|log)1cosh()(2xexxfx的求根。本章的主要任务，就是为这些不能套用现成的求根公式的函数方程，提供常用的，有效的，适合于快速数字计算机的求根方法，并研究这些算法的可行性与计算复杂性。函数方程的求根所谓函数方程11,:,0)(RRbafxf(2.1)的求根,即求*x使成立0*)(xf*x即为0)(xf的根,亦称解。*x是否存在?bx1(a,f(a))(b,f(b))ax2x3x1dcbx3ex2a隔离第一个判别定理是:定理2.2若函数在区间ba,上连续，且0)()(bfaf,则函数方程0)(xf在区间ba,上必有根存在。)(xf定理2.3若函数f在区间ba,上连续，0)()(bfaf,且对任意bax,有)0)((0)(xfxf或,则函数方程(2.1.1)在区间ba,上存在唯一解。第二个判别准则定理2.4设函数f于点0x的邻域|)(|||00xfxx(2.1.2）上可微，且导数满足|)(|1xf(2.1.3)则函数方程0)(xf于该邻域有解存在且唯一。图2.3CA(x0,f(x0))X0DB什么时候方程解是存在唯一的?y=-(x-x0)/b+f(x0)f(x0)0,f(x)单调增时y=(x-x0)/b+f(x0)x0+bf(x0)x0-bf(x0)首先注意到0111(i)投点法ixahaha2ha3ha4……)(ixf---++……确定根存在区间的几种简易方法(ii)图解法0cos13)(xxxf*x3122xcos13x(iii)近似方程替代法如级数展开确定根存在区间的几种简易方法4°计算)(21111kkkbacI2I3I4I1(i)二分法1°已知f在[a,b]上满足0)()(bfaf,令ba,=00,ba2°取点)(21000bac计算)(0cf3°若成立0)()(00cfaf，则有1100,,baca，否则，取1100,,babc由此，容易看到，通过1°—3°的计算与判别，我们可获得新的方程根x*的存在区间[a1,b1]，且有babax,,*11这个过程可以继续下去，假定已经求得存在区间11,kkba，则一般形式是确定根存在区间的几种简易方法6°kkbababa,,1,1abababkkkk2121115°若成立0)()(11kkcfaf，则取11,,kkkkbaba否则，取11,,kkkkbcba，直到满足要求的精度为止。7°若令)(21kkkkbacx，,1,0k则)(21)(21*1ababxxkkkk，,1,0kI2I3I4I1)(211abk2log2log)log(abk定理2.5设函数f在区间ba,上连续，0bfaf,则由对分法所得的区间序列kkba,和中间序列hx成立。I1ab设要求的精度为ε要分割几次？I2I3I4（ii）弦位法x*ba(b,f(b))c(a,f(a))(c,f(c))用弦分割存在区间（ii）弦位法1已知f在ba,上满足0bfaf,令00,,baba2计算0c=)()()()(000000afbfafbbfa和0cf3若成立000cfaf,则取1100,,baca，否则取1100,,babc此时新的根存在区间为0,,1111bfafba，故必有根11,*bax，继续这一过程,得算法的一般形式为a(b,f(b))c(a,f(a))(c,f©)（ii）弦位法4对于,1,0k计算kc=)()()()(kkkkkkafbfafbbfa(2.2.4)和kcf5成立0kkcfaf,则取kkkkcaba,,11否则取kkkkbcba,,11，直到满足要求的精确度为止。6kkbax,*且对一切k成立**xbxbabkkk7令kkcx)()()()(kkkkkkafbfafbbfa则成立klim*xxk但未必成立0)(limkkkaba(b,f(b))c(a,f(a))(c,f©)定理2．6假定函数f在区间ba,上连续,0bfaf,x*(c,f(c))(a,f(a))(b,1/2f(b))(b,f(b))dca弦位法的改进图2.1.6则由弦位法产生的分点序列kx收敛于极限bax,*且成立0*xf(b,p*f(b))0=p=101010111xxxxxfxfxfxl1010112xfxfxfxxxx割线法abx*X1X0X2X1X0X2割线法kkkkkkkxfxfxfxxxx111弦位法kkkkkxfxfxfxxxx001,1,0k1x0x4x3x2xx4割线法与弦位法的区别今设序列kx收敛于*x，若存在数1p和0c，使成立cxxxxpkkk**lim1收敛阶的概念:(重点)则称该序列kx为p阶收敛。特别，当1,1cp时，称kx为一阶收敛。当p满足21p时，称kx为超线性收敛。当2p时，序列kx为2阶收敛。定理2.7设bax,*为方程0)(xf的根，函数f在*x的领域**,xxxS上二次连续可微，且满足条件割线法的收敛性定理1)*,,0xSxxf2)xfMxfmmMqxSxxSx*,2*,112min,min,12则对任何*,,10xSxx,由割线法产生的序列kx收敛于*x，且有估计式618.1251,2*151211kqMmxxk（2.3.3）证明利用Newton插值公式，可得100101011**21**xxxxfxxxxxfxfxfxf由于0*xf和01201211xxxxxfxfxf故有10020101**21*xxxxfxxxxxfxf再利用中值公式,上式可表示为10102**21*xxxxffxx(2.3.4)其中1为包含10,xx的最小区间内某一点，(2.3.4)两端取绝对值，即得0121221xxxxMMxx由条件2)，推出*,2xSx，利用同样方法，可以得到,3,2,*,kxSxk…且有估计1121**21*kkkxxxxMMxx(2.3.5)若记kkxxmM*2112则(2.3.5)式可改写成11,1,2,nkkk(2.3.6)由条件(2)，知q10，因此由(2.3.6)用归纳法得到,1,0,kqkk(2.3.7)其中k满足关系式,2,1,11(2.3.8)110今用21,分别表示二次方程12tt的二个根251,25121则(2.3.8)的解可表示为121151kkk由此易得kk151方程由(3.6)得kqk151此即(2.3.3)式，并由此即可得到*xxk。Newton法的几何意义Newton法是求解函数方程RRbafxf,:,0（2.4.1）的经典而又重要的算法，它亦是以近似直线方程替代，不过它不象割线法那样用弦，而是用一个点上的切线替代曲线，如图示X2X3X1X0X4y=f(x)图2.4.1(1)X*Newton法的几何意义X2X4X1X0X7X6X5X3Y=f(x)又如:图2.4.1(2)2)对于,1,0k..计算kkkkxfxfxx11(2.4.2)§2.4Newton法的算法描述X2X3X1X0X4y=f(x)X*1)取初始bax,0和精度3)若kxf,则停止计算00000xxxfxfxl0001xfxfxx1°取初始bax,0和精度X2X3X1X0X4y=f(x)X*2°对于,1,0K计算kkkkxfxfxx113°若kxf，则停止计算不收敛例子初始值原因Y=f(x)X2X3X4X0X1定理2.8设bax,*满足0*)(xf，函数f在*x的某邻域|*|)*,(xxxxS上二次连续可微且满足条件Newton法的收敛性问题（1）)*,(,0)(xSxxf（2）1212mMq，|)(|min)*,(1xfmxSx，|)(|max)*,(2xfMxSx则对任何初始)*,(0xx，由算法产生的序列kx收敛于*x，且有估计式)10(,2|*|221qqMmxxkn(2.4.4)证明由Taylor展式200000)*)((!210))(()(*)(xxfxxxfxfxf及0*)(xf和0))(()(0100xxxfxf得20010)*)((21*))((xxfxxxf于是有20001)*()()(21*xxxffxx及20121|*|21|*|xxmMxx由此即知)*,(1xSx。利用同样的推导，又得,2,1),*,(kxSxk且有估计2121|*|21|*|kkxxmMxx（2.4.5）令|*|2112kkxxmM则由（2.4.5）即得估计式,1,0,21kkk因为q0，故有kqk220于是由(2.4.5)即得估计式kqMmxxk2212|*|。定理2.9设函数f于某初始点bax,0邻域baxxxxS,||),(00上连续可微且满足（1）|)(|0xf（2）),(,|)(|01xSxxf（3）),(,,0|,||)()(|0xSyxLyxLyfxf则当),(0*xSx12002)2(,2kkhLh时，函数方程0)(xf有唯一解，且算法（2.4.2）收敛于该解并有误差估计式kkhhxxk212)2(1)2(|*|(2.4.6)证明利用归纳法，对于0k时，有001||xx表明),(01xSx令假定mk时成立（1）mnxSxk,,2,1,0),,(0（2）2211||21||kkkkxxLxx验证1mk时亦成立，首先可得))(()()(||)(|||11111mmmmmmmmxxxfxfxfxfxx21||21mmxxL其次，由不等式01200101)2(||||kmkkmkkmhLxxxx可得),(01xSxm，于是由归纳法即知，对一切,,1,0k(1)(2)成立。因此，对任何10pk和，亦有1210)2(||kkpjkpkhxx(2.4.7)由于2h，故当p时有0||kpkxx，这表明}{kx为一Caucky序列，因为),(0xS为闭的，故必有一个),(*0xSx，使得下式成立*limxxkk又由不等式|))(()()(|