数值分析(李庆扬)第七章.ppt

第七章非线性方程求根,本章介绍一些求方程实根的近似值的有效方法，一般来说,使用这些方法求非线性方程的实根可以分两步进行.,第一步是确定某根的所在区间a,b，或给出根的近似值x0.,第二步是对方程的根进一步精确化,得到满足精度要求的近似根.,1.非线性方程实根的对分法(二分法),二分法的收敛性,ax*x0b,a1b1,以上公式可用于估计对分次数k.,分析以上过程不难知道，对分法的收敛速度与公比为1/2的等比级数相同.由于210=1024，可知大约对分10次，近似根的精度可提高三位小数位.对分法的收敛速度较慢，它常用来试探实根的分布区间，或求根的近似值.,例1求x3-3x+1=0的实根分布情况，并求0,1中的实根近似值，精确到三位小数.,解:从-4,4区间以步长为1计算f(x)=x3-3x+1的函数值，列如下表,表7-1,可见，在(-2,-1)区间、(0,1)区间、(1,2)区间各有一实根，,下面求(0,1)区间上的实根,按二分法.,可得x0.347167968,0.347412109若取=0.0005,当k=13时,bk-ak=0.0002441410.0005,此时过程结束,取xk=(0.347167968+0.347412109)/2=0.3472900380.347,可见，对分法的优点是对函数的要求低(只要求f(x)连续)，方法简便、可靠，程序设计容易，事先估计计算次数容易，收敛速度恒定；缺点是不能求出偶重根，收敛速度较慢.,取适当的步长h=(b-a)/m逐一检验小区间a+kh,a+(k+1)h,(k=0,1,2,m-1)的两端函数值是否异号，若异号，则按以上二分法求出其中的根；若同号则不作求根而转入检查下一个区间，只要h选得较小，则可求出本区间内的所有奇重实根(包括单实根).h选得过大，可能漏掉某些根；h选得过小，则计算量增大.,对分法的思想方法还可用于搜索一个较大区间a,b内实根的分布情况(不包括偶重实根)，实际的作法是：,2.迭代法及其收敛性,也称作不动点迭代法P265,迭代过程的几何表示,Ox*x2x1x0 x,y,P266表7-2,不动点的存在性与迭代法的收敛性,（P267定理1，）,连续，且满足,改变定理条件（）可得以下结论,局部收敛性(P269),设有不动点，如存在的某个领域对任意的迭代产生的序列且收敛到，则称迭代法是局部收敛的,定义,定理3,局部收敛,实际用迭代法计算时，先用对分区间法求较好的初值，然后再进行迭代。,迭代法收敛速度定义,(P271),定理4:,3.迭代收敛的加速方法,埃特金(Aitken)方法,(P273),可以证明,表明,即为斯蒂芬森(Steffensen)迭代法(P273),的收敛速度比,的收敛速度快,且为2阶收敛的,4.牛顿(Newton)法,非线性问题的最简单解法是线性近似.将非线性方程线性化，以线性方程的解逐步逼近非线性方程的解，这就是Newton法的基本思想,Newton法的几何解释,故也称切线法,4,Newton法具有收敛快，稳定性好，精度高等优点，是求解非线性方程的有效方法之一。但它每次迭代均需计算函数值与导数值，故计算量较大。而且当导数值提供有困难时，Newton法无法进行。,(见P277表7-5),牛顿法应用举例,注牛顿法每次计算,计算量较大,1。简化牛顿法（平行弦法）,若,即,在根x*附近成立，则迭代为局部收敛。P280,2。牛顿下山法即在牛顿迭代法的基础上附加一个条件,计算公式：,即,5.弦截法与抛物线法,一、弦截法（P283）,弦截法的几何表示,x0,X,x*,x1x2x3,Y,f(x)0,P0,P2,P1,弦截法收敛性定理（P285）,迭代法加速（埃特金方法）,用弦截法给出埃特金算法的几何解释,二、抛物线法（P285）,抛物线法计算公式,三、代数方程的牛顿法,解非线性方程组的牛顿迭代法P287,考虑方程组,或矩阵形式F（X）=O,其中,fi中至少一个是非线性函数时，称作非线性方程组,注：非线性方程组可视作矩阵形式的