第七章 非线性方程的数值解法.ppt

1,第七章非线性方程的数值解法,求f(x)=0的根,第一节方程求根的二分法,第二节一元方程的不动点迭代法,第三节一元方程的常用迭代法,上一页下一页返回,2,本章要讨论的问题：,（非线性）方程f(x)=0的数值解法,首先引入定义：,1.f(x)=0的解x*称为方程f(x)=0的根或函数f(x)的零点.,若f(x)=(x-x*)mg(x),g(x*)0，其中m为正整数，则称x*为方程f(x)=0的m重根，或称x*为函数f(x)的m重零点.,上一页下一页返回,3,1方程求根的二分法,方程求根步骤：,根的隔离,确定根所在的区间a,b,使在a,b内至少有方程的一个根.,有根区间,近似根的精确化,已知根的一个近似值后,构造某种算法,将此近似值精确化,使其满足给定的精度要求.,越小越好,上一页下一页返回,4,下面介绍方程求根的二分法,在确立了有根区间a,b后,需要逐步缩小有根区间.,取a,b的中点x0=(a+b)/2,将区间一分为二.若f(x0)=0,则x0就是方程的根,否则判别根x*在x0的左侧还是右侧.,不论出现哪种情况,(a1,b1)均为新的有根区间,它的长度只有原有根区间长度的一半,达到了压缩有根区间的目的.,上一页下一页返回,5,重复以上过程,继续进行二分,可得一系列有根区间,由于每个小区间都是有根区间,所以这个点就是所求方程的根.,同时,在每次二分时,所求出的中点形成一个无穷数列,这个数列必定收敛于x*.,上一页下一页返回,6,b,x0,x1,a1,b2,whentostop?,x*,b1,上一页下一页返回,a2,7,误差分析：,第k步产生的xk1有误差,对于给定的精度,可估计二分法所需的步数k：,算法简单;对f(x)要求不高(只要连续即可)，收敛性总能得到保证,无法求复数根及偶数重根（函数值的正负号相同）；要计算很多次函数值，收敛慢,二分法的误差估计式,上一页下一页返回,8,例1用二分法求f(x)=x3-x-1=0在区间1,1.5内的一个实根,要求误差不超过0.005.,解：由题可知x*(1,1.5),要想,解之得,取n6.按二分法计算的过程见下表,x6为所求之近似根.,上一页下一页返回,9,上一页下一页返回,10,逐步搜索法,从区间a，b的左端点a出发,按选定的步长h0一步步向右搜索,若：,则区间a+jh,a+(j+1)h内必有根.,上一页下一页返回,于是可确定一个缩小了的有根区间a+jh,a+(j+1)h.,再对新的有根区间，取新的更小的预定步长，继续搜索，直到有根区间的长度足够小。,搜索过程也可从b开始,这时应取步长h0.,11,2一元方程的不动点迭代法,迭代格式,一、不动点迭代法及其收敛性,1.迭代法的基本思想,将方程f(x)=0化为等价方程然后在有根区间内取一点x0,按下式计算,计算结果生成数列xk,上一页下一页返回,12,如果这个数列有极限,x*就是方程的根.,迭代式（1）称为基本迭代法.,称为迭代函数,x0称为迭代初值,数列(2)称为迭代序列.,上一页下一页返回,如果迭代序列收敛,则称迭代格式收敛,否则称为发散.,x*称为的不动点。,迭代过程中，xk+1仅由xk决定，因此，这是一种单步法。,13,例2用迭代法求方程x4+2x2-x-3=0在区间1,1.2内的实根.,解：对方程进行如下三种变形,分别按以上三种形式建立迭代格式,并取x0=1进行迭代计算,结果如下：,准确根x*=1.124123029,可见迭代格式不同,收敛情况也不同,收敛速度也不同.,上一页下一页返回,14,上一页下一页返回,例3,解：把f(x)=0转换成等价形式,对应的迭代法为,取初值x0=1,迭代结果分别收敛到x*=,计算结果见下表,从而可见，基本迭代法的收敛性取决于迭代函数和初值x0的选取。,15,问题,2.迭代格式应该满足什么条件才能保证收敛？,3.如何判断迭代收敛的速度,建立收敛快的迭代格式？,上一页下一页返回,1.迭代函数如何构造？,16,定理1,2.收敛条件与误差估计,上一页下一页返回,迭代格式的收敛性与迭代函数密切相关.,方程x=，ca,b,满足条件,(1)当xa,b时，a,b；(2)0l1使得|l1对xa,b成立.,则,(1)函数在a,b上有唯一不动点x*;(2)对任意迭代初值x0a,b,迭代序列xk+1收敛于x*.,（3）有下列误差估计式：,17,(k=1,2,),反之,若在区间r内,则迭代必发散.,上一页下一页返回,l越小收敛越快,尚未计算时便估计出第k次迭代近似值的误差,称为事先误差估计.,18,由定理1的误差估计式可看出,只要相邻两次迭代近似值xk与xk-1的偏差|xkxk-1|充分小,就可以保证迭代值xk足够精确.,这种用前后两次迭代结果估计误差的办法称为事后误差估计,上一页下一页返回,因此对于给定的允许误差,当l较小时,常用前后两次迭代是否满足|xkxk-1|来终止迭代.,19,不但可以估计迭代k次时的误差,也可以用来确定达到误差精度要求的迭代次数k.,当要求误差精度为,即要求,只要,即可,从中解出k为,实际应用中,控制迭代结束的条件也常取为e,其中,上一页下一页返回,20,上一页下一页返回,迭代过程的几何解释如下图,21,上一页下一页返回,例4对于例2中的三种迭代法，讨论它们的收敛性。,解：对于下面三种迭代函数,其导函数在1,1.2内分别有,根据定理1，例2中的第三种迭代法发散，第一、二种迭代格式收敛，而且第二种迭代法比第一种迭代法收敛快得多。这与实际计算结果完全吻合。,22,迭代法的流程图如下：,上一页下一页返回,23,上一页下一页返回,例5,解：,即可得等价的方程,有时，对于不满足定理条件的问题，可以通过转化，化为适合于迭代的形式。,令,则有,故,24,上一页下一页返回,二、局部收敛性和加速收敛法,定理1中，迭代法在区间a,b上的收敛性，称之为全局收敛性.,定义:若在x*的某邻域r=x|xx*|,使迭代过程xk+1=(xk),k=0,1,2,对于任意x0r均收敛,则称该迭代过程在x*处具有局部收敛性.,定理2,25,迭代过程的收敛速度,定义,p的大小反映了迭代过程收敛的快慢,p越大收敛速度越快.,上一页下一页返回,26,定理3,上一页下一页返回,设x*为函数的不动点,在x*的邻域内有连续的p阶导数(p1),那么,(1)0|1,则迭代过程在x*的邻近为线性收敛；,27,例6证明迭代公式是求的三阶方法.假设xo充分靠近x*,求,解：,此迭代格式的迭代函数为,方程两边对x求导,得,上一页下一页返回,28,再将上式两边对x求导,得,上式再对x求导,得,上一页下一页返回,所以，迭代格式是3阶收敛的.,29,加速收敛的steffensen迭代法,对于线性收敛的迭代法，收敛很慢。,上一页下一页返回,设xk是方程根x*的一个近似值，由xk开始相继迭代两次,将其结果记作,30,于是得到如下迭代格式,称之为steffensen迭代法(其他教材也称之为埃特金(aitken)外推加速法).,上一页下一页返回,它的不动点迭代格式是,其中迭代函数为,31,若对此格式用steffensen法,则,上一页下一页返回,例7,32,上一页下一页返回,33,上一页下一页返回,例8,现在用函数构造steffensen迭代法,可见，steffensen迭代法对这种不收敛的情形同样有效。,34,3一元方程的常用迭代法,一、newton迭代法,设x*是方程f(x)=0的实根。取x0x*，将f(x)在x0做一阶taylor展开:,，在x0和x之间。,将(x*x0)2看成高阶小量，则有：,上一页下一页返回,由图示，可见xk+1为函数f(x)在点xk处的切线与横坐标轴的交点，所以，newton迭代法也称切线法。,newton迭代格式,35,上一页下一页返回,与上一节例7相比，牛顿法的收敛速度快很多。,例9,36,上一页下一页返回,牛顿迭代法的流程图,37,注：牛顿迭代法的收敛性依赖于x0的选取。,x*,上一页下一页返回,38,定理,上一页下一页返回,（收敛的充分条件）设fc2a,b，若(1)f(a)f(b)0；则牛顿迭代法产生的序列xk收敛到f(x)在a,b的唯一根。,定理,有根,根唯一,产生的序列单调有界，保证收敛。,保证f(x)上凸或下凸,39,上一页下一页返回,10,40,q1:若，牛顿迭代法是否仍收敛？,设x*是f的m重零点,则：且,a1:有局部收敛性，但仅为线性收敛.,下面介绍计算重根的牛顿迭代法,上一页下一页返回,41,因此,求f(x)=0之m重根x*等价于求(x)=0的单根x*。,而对(x)=0用牛顿迭代法求根则是平方收敛的,其迭代格式为,令，则f的重零点就是的单零点。,a2:方法1：将求f的重零点转化为求另一函数的单零点。,q2:如何加速求重根的收敛速度？,上一页下一页返回,42,方法2：采用如下迭代格式,可以证明它是求m重根x*的具有平方收敛的迭代格式.,如何确定根的重数m?,则：,上一页下一页返回,43,例11用牛顿迭代法求方程,解：,上一页下一页返回,44,上一页下一页返回,45,例12用3种方法求解方程,解：,上一页下一页返回,都取x0=1.5，计算结果见下表：,46,方法（2）和方法（3）都是二阶方法，x3都精确到了小数点后第9位，方法（1）即普通牛顿迭代法，解重根是一阶方法，要近30次迭代才能有相同的精度。,上一页下一页返回,47,牛顿法的优点,收敛速度快,牛顿法的缺点,每次迭代要计算一次导数值，当表达式复杂或无明显表达式时求解困难。,48,简化牛顿迭代法,此式称简化牛顿迭代法.,简化newton法的收敛速度为线性.,几何意义：用平行线代替牛顿法中的切线.,此法收敛较慢.,上一页下一页返回,主要思路：,49,二、割线法,称之为（双点）割线法.,这样的迭代格式称之为单点割线法.,它的收敛速度是线性的.,上一页下一页返回,注：计算之前必需给出两个初值x0和x1.,50,例13用双点割线法求方程f(x)=x3+10 x20=0在区间1.5,2内之根的近似值。,解显然f(x)=x3+10 x20在区间1.5,2内连续且有零点。,取x0=1.5，x1=2，建立双点割线法的迭代公式,计算结果如下：,上一页下一页返回,51,例14用牛顿迭代法