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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,7.1,方程求根与二分法,设非线性方程为,f,(,x,)=0 (7-1),方程,(2-1),的解 称为方程的根或函数,f,(,x,),的零点。,其中,m,为大于,1,的整数,且,g,(,x,)0,称 为方程,(7-1),的,m,重根,或函数,f,(,x,),的,m,重零点,.,若,f,(,x,),为,n,次多项式,则称,f,(,x,)=0,为,n,次代数方程,.,若,f,(,x,),为超越函数,则称,f,(,x,)=0,为超越方程。,若,f,(,x,),可表示为,第,7,章 非线性方程求根,2,一、求有根区间的一般方法,若,f,(,x,),满足条件,:,(1),在,a,b,内连续,(2),f,(,a,),f,(,b,)0,f,(0),=,10,f,(3),=,-,260,f,(,x,),在此三区间的符号分别为,“,-,”,、“,-,”,、“,+”,由,f,(,x,),=,4,x,2,(,x,-,3)=0,得驻点,x,1,=0,x,2,=3,。,6,以上分析可用下表表示,x,(-,0),0,(0,3),3,(3,4),4,(4,+),f,(,x,),f,(,x,),-,0,+,-,0,-,+,+,+,隔根区间,(0,3),(3,4),可见,f,(,x,),仅有两个实根,分别位于,(0,3),(3,+),又,f,(4),=,10,所以第二根的隔根区间可缩小为,(3,4),。,7,2.,逐步搜索法,(,增值寻根法,),搜索过程,可从,a,开始,也可从,b,开始,这时应取步长,h,0,。,增值寻根法的基本思想是,:,从初值 开始,按规定的一个初始步长,h,来增值。,同时计算,.,可能遇到三种情形：,此时 即为方程的根,说明区间 内无根,说明区间 内有根,8,图,2-1,图,2-2,9,三、二分法,设,方程,f,(,x,)=0,在区间,a,b,内有且只有一个实根,x,*,。,即,f,(,x,),满足条件,:,(1),在,a,b,内连续,(2),f,(,a,),f,(,b,)0,(3),f,(,x,),在,a,b,内严格单调。,10,二分法的步骤：,(2),若,则 令,a,2,=a,b,2,=,x,1,;,(3),若,则,令,a,2,=x,1,b,2,=,b,。,记,a,b,=,a,1,b,1,中点 计算,f,(,x,1,),(1),若,f,(,x,1,),=,0,则,x,1,就是方程的根,x,*,计算结束,;,对压缩了的有根区间,a,2,b,2,实行同样的步骤,.,若每次二分时所取区间中点都不是根，则上述过程将无限进行下去。,11,如此反复进行,可得一系列有根区间套,由于每一区间都是前一区间的一半，因此区间,a,n,b,n,的长度为,当,n,时,区间必将最终收缩为一点,x,*,显然,x,*,就是所求的根,。,12,只要,n,足够大,即区间二分次数足够多,误差就可足够小。,若取区间,的中点,作为,的近似值，则有下述误差估计式,13,由于在偶重根附近曲线,y=f,(,x,),为上凹或下凸,即,f,(,a,),与,f,(,b,),的符号相同,因此不能用二分法求偶重根,.,解,可知,要想满足题意，即,：,例,2,用二分法求方程,f,(,x,),=x,3,-x-,1,=,0,在 上的,实根,要求误差不超过,0.005,。,14,为所求之近似根。即,x,*,1.3242,(1),f,(,a,)0,(2),根据精,度要求,取到小数,点后四位,即可,.,-,+,-,+,+,-,-,1.25,1.375,1.3125,1.3438,1.3281,1.3203,1.3242,1.5,1.5,1.375,1.375,1.3438,1.3281,1.3281,1.0,1.25,1.25,1.3125,1.3125,1.3125,1.3203,1,2,3,4,5,6,7,a,n,n,15,例,3,用二分法求 在 内的一个实根，且要求满足精度,解,用二分法计算结果如表,2-1,：,16,0.000072,1.364746094,1.3671875,1.36328125,9,-0.03215,1.364257813,1.3671875,1.359375,8,0.03236,1.36328125,1.375,1.359375,7,-0.09641,1.359375,1.375,1.34375,6,-0.35098,1.34375,1.375,1.3125,5,-0.84839,1.3125,1.375,1.25,4,0.16211,1.375,1.5,1.25,3,-1.79867,1.25,1.5,1.0,2,2.375,1.5,2.0,1.0,1,n,17,-0.00799,1.364746094,1.365234375,1.364257813,11,-0.01605,1.364257813,1.365234375,1.36328125,10,n,接上图,迭代,11,次，,近似根,即为所求，,其误差,18,7.2,不动点迭代法及其收敛性,一、迭代法的基本思想,迭代法是一种重要的逐次逼近法,其基本思想是：,将方程,f,(,x,),=,0,化为等价方程,然后在隔根区间内取一点,x,0,，,按下式计算,计算结果生成数列,如果这个数列有极限,19,这种求根方法称为不动点迭代法。,如果迭代序列收敛,则称迭代格式收敛,否则称为发散。,当,(,x,),连续时,显然,就是方程,x=,(,x,),之根。,于是,可以从数列,中求得满足精度要求的近似根。,称为迭代格式,(,x,),称为迭代函数,x,0,称为迭代初值,数列,称为迭代序列。,20,对方程进行如下三种变形：,用迭代法求方程,x,4,+2,x,2,-,x,-3=0,在区间,1,1.2,内,的 实根,。,解,例,1,21,分别按以上三种形式建立迭代格式，并取,x,0,=,1,进行迭代计算，结果如下：,22,第二种格式比第一种格式收敛快得多,而第三种格式不收敛。,可见迭代格式不同,收敛情况也不同。,准确根,=,1.124123029,。,23,例,2,用迭代法求方程,在,内的一个近似根，取初始近似值,解,原方程的等价方程可以有以下不同形式,24,对应的迭代公式有：,取,列表计算如下,25,1.36523002,1.36591673,8,1.36522994,1.36388700,7,1.365223058,1.36784697,6,1.36522559,1.36009419,5,1.36526475,1.37517025,4,1.36495701,1.34545838,-469.7,3,1.36737637,1.40254080,2.9969,6.732,2,1.34839973,1.28695377,0.8165,-0.875,1,1.5,1.5,1.5,1.5,0,(4),(3),(2),(1),n,表,2-2,26,二、迭代法的几何意义,一般来说从,构造,不止一种，有的,收敛，有的不收敛，这取决于 的性态。,方程 的根，在几何上就是直线,与曲线 交点的横坐标,如图,2-3,所示,27,28,29,30,三、不动点的存在性与迭代法的收敛性,定理,1,(1),当,x,a,b,时,，,(2),存在正数,L,1,，,使对任意的,x,a,b,方程,在,a,b,存在唯一根,且满足条件,：,设,则,31,证方程,之解存在且唯一,.,由于,在,a,b,上存在,f,(,x,),在,a,b,上连续。,作函数,由条件,连续,。,所以,证,使,即,则,(1),f,(,a,)0,f,(,b,)0,故存在,32,则由微分中值定理及条件值定理及条件,(2),有,此式仅当,才能成立,，,因此,则由微分中值定理及条件,(2),有,设方程,还有一不动点,33,定理,2,(1),当,x,a,b,时,，,(2),存在正数,L,1,，,使对任意的,x,a,b,对任意迭代初值,x,0,a,b,迭代序列,且满足条件,：,设,收敛于,。,则,且有下列误差估计式,34,即迭代过程收敛，,且,反复用此不等式，并注意,0,L,1,因此,先证迭代格式,收敛,任取,x,0,a,b,，,由微分中值定理，有,35,提示,：,定理的证明利用定理,1,以及微分中值定理。,36,37,则任取,x,0,U,迭代格式,均收敛于,定理,3,若方程,之根的某邻域,L,1,时称为超线性收敛,.,利用微分中值定理及泰勒展式可得下面的定理,3.,显然,收敛阶越大,收敛越快,.,p=,2,时称为,二阶,(,平方,),收敛,特别地,令,若,44,则迭代过程在,的邻近为,p,阶收敛,。,(1),若,为线性收敛,；,则迭代过程在 的邻近,(2),若,定理,4,之根,在,的邻域,U,内,有连续的,p,阶导数，,则,设,为,45,46,由泰勒展式可得,解,的三阶方法。假设,x,0,充分靠近,求,证明迭代公式,x,k+,1,=,x,k,(,x,k,2,+,3,a,)/(3,x,k,2,+,a,),，,试求,例,2,47,加速迭代法,松弛法迭代公式：,为松弛因子,7.3,迭代收敛的加速方法,48,称为斯蒂芬森,(,Steffensen,),加速法,.,则埃特金法为平方收敛；,若,为,p,(,p,1),阶收敛,，,导数连续,的,p,阶,可以证明,:,若,为线性收敛,则埃特金法为,2,p,1,阶收敛。,迭代格式,49,求方程,x,=,e,x,在,x,=,0.5,附近的根,.,x,25,=,x,26,=0.5671433,若对此格式用,斯蒂芬森,法,则,取,x,0,=0.5,迭代格式,得,解,例,3,50,仍取,x,0,=0.5,得,由此可见,斯蒂芬森,法加速收敛效果是相当显著的,.,51,例,4,分别用松弛法、,斯蒂芬森,法求方程,在初值 附近的一个根，取迭代格式,解,用松弛法计算，取,52,因此松弛法的迭代公式为,列表计算如下：,1.365230013,1.365230012,1.364953916,1.5,0.887130869,0.887130869,0.890803686,3,2,1,0,n,53,用,斯蒂芬森,方法计算，迭代格式为：,54,列表计算如下：,1.365230583,1.367376372,1.365225534,1.348399725,1.365230013,1.365265224,1.5,2,1,0,n,55,7.4,牛顿法,一、牛顿法的基本思想,设已知方程,f,(,x,)=0,的近似根,x,0,，,且在,x,0,附近,可用一阶泰勒多项式近似，表示为,方程,f,(,x,)=0,可用线性方程近似代替，即,56,解此线性方程得,取此,x,作为原方程的新近似根,x,1,，,重复以上步骤,，,得迭代公式,此式称为牛顿,(Newton),迭代公式,。,57,例,1,用牛顿法求方程,在 内一个实根，取初始近似值,解,所以迭代公式为：,列表计算如下：,1.36523001,1.36526201,1.3733333,1.5,3,2,1,0,n,58,二、牛顿法的几何意义,方程 的根就是曲线 与 轴交点的横坐标 ，当初始值 选取后，过,作切线，其切线方程为：,它与,x,轴交点的横坐标为：,59,一般地，设 是 的第,n,次近似值，过,作 的切线，其切线与,x,轴交点的横坐标为：,即用切线与,x,轴交点的横坐标近似代替曲线,与,x,轴交点的横坐标，如图,2-4,。,60,若过曲线,y,=,f,(,x,),上的点,P,(,x,k,f,(,x,k,),引切线，,该切线与,x,轴交点的横坐标即为由牛顿迭代公式,求得的,x,k,+1,因此牛顿迭代法也称牛顿切线法。,图,2-4,61,将原方程化为,x,e,x,=0,，,则,牛顿迭代格式为,取,x,0,=0.5,，,迭代得,x,1,=0.566311,x,2,=0.5671431,x,3,=0.5671433,f,(,x,)=,x,e,x,，,f,(,x,)=1+,e,x,用牛顿迭代法求方程,x,=,e,x,在,x=,0.5,附近的根。,例,4,解,62,三、牛顿迭代法的收敛速度,牛顿迭代法的迭代函数为,不为,0,由于,所以当,时,63,只是收敛速度将大大减慢,。,1,、,当 为单根时，牛顿迭代法在根 的附近,是二阶收敛的；,2,、,当,为重根时，设为,m,重根，则,f,(,x,),可表为,其中,此时用牛顿迭代法求,仍然收敛,，,64,事实上，因为,令,则,65,可见用牛顿法求方程的重根时仅为线性收敛。,66,3,、,计算重根的牛顿迭代法,有两种方法可以提高求重根的收敛速度：,1,）,采用如下迭代格式,67,2,）,将求重根问题化为求单根问题，注意函数,所以化为求,u,(,x,)=0,的单根是平方收敛的。,格式为,68,用牛顿迭代法求,f,(,x,)=(,x,-1)sin(,x,-1)+3,x,-,x,3,+1=0,在,0.95,附近之根,。,取,x,0,=0.95,用牛顿迭代法求得的,x,k,见右表,。,解,例,5,k,x,k,k,m,0,1,2,3,4,5,6,0.95,0.9744279,0.9870583,0.9934878,0.9967328,0.9983576,0.9991901,0.5090,0.5047,0.5007,0.5125,2.0369,2.0190,2.0028,2.0511,可见,x,k,收敛很慢。,69,由重根数,m,为,2,用加速法,x,0,=0.95,x,1,=0.9988559,x,2,=,x,3,=1,收敛速度大大加快于直接用牛顿迭代公式,.,求得,70,4,、,简化牛顿迭代法,此式称为简化牛顿迭代公式。,只要,M,选择得当,，,上式总是线性收敛的。,在牛顿迭代公式中用一常数,M,代替,得,71,72,牛顿下山法,73,用常数,M,来代替,f,(,x,k,),虽然简单，但没充分,利用,f,(,x,),本身的特性,，,因此收敛较慢。,若在牛顿迭代公式中改用差商,代替导数,f,(,x,k,),，,得迭代公式,1,、,割线（弦截）法,7.5,弦截法与抛物线法,74,每步只用一新点，此格式为弦截法（双点割线法）。,可以证明它的收敛阶为,确实比式,收敛快。,75,76,将式,每步只用一新点，此格式为单点割线法。,中的,x,k,-1,改为,x,0,，,即,77,3,、割线法的几何意义,双点割线法是用过点 和 两点的割线与,x,轴交点的横坐标 作为 的新近似值。重复此过程，用过点 和,的两点的割线法与,x,轴交点的横坐标,来作为 的下一新的近似值。,如图表,2-5,78,图,2-5,图,2-6,单点割线法则是用过点 和,的两点的割线与,x,轴交点的横坐标 来作为,的近似值，如图,2-6,。,79,用牛顿迭代法和弦截法求方程,f,(,x,)=,x,4,+2,x,2,x,3=0,在区间,（,1,1.5,）,内之根（误差为,10,-9,）。,取,x,0,=1.5,用牛顿法,可得,x,6,=1.12412303030,；,而采用单点割线法，则迭代,18,次得,x,18,=1.124123029.,例,6,解,取,x,0,=1.5,x,1,=1,用双点割线法,迭代,6,次得到同样,的结果，,80,例,7,用弦截法求 在,0.5,附近的根。精确到小数点后第六位。,解,令,即,81,取 列表计算如下：,0.347296,0.347295,0.347731,0.356322,0.2,0.347695,0.347731,0.356322,0.2,0.5,5,4,3,2,1,n,82,4,、割线法收敛的速度,定理,这说明它是线性收敛的,(,p,=1.6181),。而单点割线法在单根附近是线性收敛的。,设 的根为 。若 在 附近有连续的二阶导数，而初值,充分接近 ，则双点割线法的迭代过程收敛，收敛速度为,83,5,。抛物线法,84,85,86,7.6,解非线性方程组的牛顿迭代法,87,88,迭代格式,89,