第七讲二分法与迭代过程的收敛性复习过程.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,第七讲二分法与迭代过程的收敛性,本讲主要问题,一、二分法,二、迭代法的一般知识,本讲讨论:求一元非线性方程,f,(,x,)=0,的根的近似值.,例如,e,x,x,=0,x,8,x,3,+5,x,3=0,x,sin,x,=0,等等,求根的大致步骤:,若,f,(,x,*,)=,f,(,x,*,)=,f,(,x,*,)=,f,(,m,-1),(,x,*,)=0,但,f,(,m,),(,x,*,)0,其中,m,是正整数,如果,f,(,x,*,)=0,则,x,*,是方程,f,(,x,)=0,的,根,也称它是函数,f,(,x,),的,零点,.,方程的1重根称为,单根,这时,f,(,x,*,)=0,而,f,(,x,*,)0.,(1)判定根的存在性;,(2)确定根的初始近似值(初始近似根);,(3)根的精确化.,则称,x,*,为方程,f,(,x,)=0,的,m,重根,-函数,f,(,x,),的,m,重零点,.,初始近似根的确定:,定理,如果函数,f,(,x,),在区间,a,b,上连续,严格单调,且,f,(,a,),f,(,b,)0,则在(,a,b,),内方程有且,仅有一个实根.,假设,f,(,x,),在某区间(,a,b,),内有且仅有一个实根,x,*,若,b,a,较小,则可在(,a,b,),上任取一点,x,0,作为初始近似根.一般情形,也可用,逐步扫描法,等.,(1),x,0,a,;,(2),若,f,(,x,0,),f,(,x,0,+h,)0,则结束,否则做下步.,(3),x,0,x,0,+h,转(2),（其中,h,为预选的步长）,求初始近似根的,逐步扫描法:,（设(,a,b,),内有根）,一、,二分法,1.,二分法的基本思想,二分法的基本思想,将含方程根的区间平分为两个小区间,然后判断根在哪个小区间,舍去无根的区间,而把有根的区间再一分为二,再判断根属于哪个更小的区间,如此周而复始,直到求出满足精度要求的近似根.,条件,:函数,f,(,x,),在,a,b,上连续,严格单调,且,f,(,a,),f,(,b,)0,这时方程在区间内有且仅有一个实根,x,*,.,具体计算过程,第1次二分,取中点,新的有根区间为(,a,1,b,1,),长度是原来的一半.,若,f,(,a,),f,(,x,0,)0,则,x,*,(,a,x,0,),令,a,1,=,a,b,1,=,x,0,;,令,a,1,=,x,0,b,1,=,b,.,否则,x,*,(,x,0,b,),x,*,x,*,一、,二分法,2.,计算过程,第2次二分,取中点,若,f,(,a,1,),f,(,x,1,)0),(1)当|,b,k,+1,a,k,+1,|,时结束二分计算,取,x,*,x,k,;,(2)事先由,估计出二分的最小次数,k,+1,取,x,*,x,k,.,二分法的计算流程,例 求方程,f,(,x,)=,x,3,x,1=0,在区间(1,1.5)内的根,要求用二分法,取四位小数计算,精确到10,2,.,答案:计算结果见列表：,1.324 3,1.328 2,1.320 4,6,1.320 4,1.328 2,1.312 5,5,1.328 2,1.343 8,1.312 5,4,1.343 8,1.37 5,1.312 5,3,1.312 5,1.375,1.25,2,1.375,1.5,1.25,1,1.25,1.5,1,0,f,(,x,k,),的符号,x,k,b,k,a,k,k,得,x,6,=,1.3243,所以根,x,*,1.32,二、,迭代法的一般知识,1.,迭代法的基本思想,方程,f,(,x,)=0,化为,等价形式,的方程,x,=g(,x,),取初始近似根,x,0,迭代计算,x,1,=,g,(,x,0,),x,2,=,g,(,x,1,),.,得到,迭代序列,x,k,.,构造,迭代公式,x,k,+1,=g(,x,k,),k,=0,1,2,例,f,(,x,)=,x,e,x,-1=0,可化为等价形式,x,=e,x,迭代公式,x,k,+1,=e,x,k,当,g,(,x,),(,称为,迭代函数,)连续，,若,，则由,得 .,等价地有,f,(,x,*,)=0,故,x,*,即为方程的根.,实际计算到,|,x,k,x,k,-1,|,(,是预定的精度),取,x,*,x,k,.,迭代公式收敛(发散),问题：迭代公式是否一定收敛？,指迭代序列,x,k,收敛(发散).,例 求方程,f,(,x,)=,x,10,x,+2=0,的一个根,取4位有效数字计算.,答案:,方程改写为两种等价形式：,对应的迭代公式分别为,用迭代公式(1)取,x,0,=1,算得,x,1,=lg3=0.4771,x,2,=lg(,x,1,+,2),=0.3939,.,x,6,=0.3758,x,7,=lg(,x,6,+2)=0.3758,x,6,、,x,7,重合，所以,迭代公式(1)是收敛的,x,*,0.3758.,用迭代公式(2)取,x,0,=1,算得,x,1,=10-2=8,x,2,=10,8,-210,8,x,3,=10,10,8,-2 10,10,8,，,迭代公式(2)发散.,二、,迭代法的一般知识,2.,迭代法的几何意义,问题,：迭代函数,g,(,x,),满足什么条件时，迭代序列才收敛?,x,1,=g,(,x,0,),x,2,=g,(,x,1,),二、,迭代法的一般知识,3.,迭代法的收敛条件及误差估计式,定理,(1)当,x,a,b,时,g,(,x,),a,b,;,设方程,x=g,(,x,),在,a,b,上有一阶导数,如果,(2),存在正数,q,1，,使对任意,x,a,b,都有,|,g,(,x,),|,q,1,则方程,x=g,(,x,),在,a,b,上有惟一的根,x,*,;,还有误差估计式,且对于,a,b,上任意初始近似根,x,0,迭代公式,x,k+,1,=g,(,x,k,),均收敛于方程的根,x,*,;,推论,设在区间,a,b,上方程,x=g,(,x,),有,根,x,*,且,g,(,x,),有连续的一阶导数。如果有正数,q,1,使得对任意,x,a,b,都有,|,g,(,x,),|,q,1,，,则存在,x,*,的某个邻域,只要,x,0,属于此邻域,迭代公式,x,k+,1,=g,(,x,k,),必收敛于,x,*,.(,也称迭代公式有,局部收敛性,),定理,设在区间,a,b,上方程,x=g,(,x,),有根,x,*,且对,x,a,b,都有,|,g,(,x,),|,1，,则对于该区间上任意,x,0,(,x,*,),迭代公式,x,k+,1,=g,(,x,k,),一定发散.,迭代法的计算步骤,(1)确定方程,f,(,x,)=0,的一个等价形式,x=g,(,x,),要求在某个含根区间,a,b,内满足,|,g,(,x,),|,q,1,.,(2)构造迭代公式,x,k+,1,=g,(,x,k,),选取初始近似根,x,0,进行迭代计算.,(3)当,|,x,k,+1,x,k,|,(,是预定的精度)时停止计算,取,x,*,x,k,+1,.,迭代法的计算框图,例 求方程,x=,e,x,在,x,=0.5,附近的一个根,按5位小数计算，结果的精度要求为,=10,3,.,答案:,方程等价于,f,(,x,)=,x,e,x,=0.,由于,f,(0.5)0,故,x,*,(0.5,0.6),令,g,(,x,)=e,x,在(0.5,0.6)内,g,(,x,),的一阶导数连续，且有,所以用迭代公式,x,k+,1,=,e,x,k,进行计算是收敛的。,x,0,=0.5,迭代结果:,0,1,2,3,4,5,0.5,0.606 53,0.545 24,0.579 70,0.560 07,0.571 17,0.106 53,0.061 29,0.034 46,0.019 63,0.011 10,6,7,8,9 10,0.564 86,0.568 44,0.566 41,0.567 56,0.566 91,0.006 31,0.003 58,0.002 03,0.001 15,0.000 65,k,x,k,x,k,x,k-,1,x,k,x,k-,1,k,x,k,|,x,10,-,x,9,|,=0.00065,故,x,*,x,10,0.567,例 方程,f,(,x,)=,x,3,-2,x,-5=0,在(1.5,2.5)内有一实根，分别取,作为迭代函数,试判断对应的迭代公式是否收敛,并用一个收敛的迭代公式求方程的根,精度要求为,=10,4,.,答案:,(1),单调,且,所以迭代公式,收敛.,取,x,0,=2,计算,结果列表：,0,1,2,3,4,5,2,2.08008,2.09235,2.0942,2.09449,2.09454,0.08008,0.01227,0.00187,0.00027,0.00005,k,x,k,x,k,-x,k-,1,因为,|,x,5,-,x,4,|,=0.0000510,-4,所以,x,*,x,5,=2.09454,例 方程,f,(,x,)=,x,3,-2,x,-5=0,在(1.5,2.5)内有一实根，分别取,作为迭代函数,试判断对应的迭代公式是否收敛,并用一个收敛的迭代公式求方程的根,精度要求为,=10,4,.,(2),迭代函数,根据定理,迭代函数对应的迭代公式,是发散的.,答案:,此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢,