第二章 求方程根的近似方法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,f,(,x,),=0,的根,(,或,f,(,x,),的零点,),，当,f,(,x,),复杂时，很难求（需要找到有效简单的近似方法去求）。,第二章 求方程根的近似方法,2.1,二分法,理 论,:,f,(,x,),Ca,b,单调,f,(,a,),f,(,b,),0,f,(,x,),=0,在,(a,b),中有惟一根。,a,b,x,1,x,2,a,b,何时停下来,?,或,不能保证,x,的精度,x*,2,x,x*,解,：,f(1)=-50 -(1,2)+,x,1,=,1.5,f(1.5)0 (1,1.5),x,21.25,f(1.25)0 (1.25,1.375),x,4,=,1.313,f(1.313)0 (1.313,1.375),x,5,=,1.344,f(1.344)0 (1.344,1.375),x,6,=,1.360,f(1.360)0 (1.360,1.368),x,8,=,1.364,例,2.1.1,用二分法求 在,(1,2),内,的根，要求绝对误差不超过,，,则,（,事后估计,）,误差,分析：,第,1,步产生的,有,误差,第,k,步产生的,x,k,有,误差,对于给定的精度,可估计二分法所需的步数,k,：,缺点：收敛速度慢，,不易求偶数重根,.,如图,注：,用二分法求根，最好先给出,f,(,x,),草图以确定根的大概位置。或用搜索程序，将,a,b,分为若干小区间，对每一个满足,f,(,a,k,),f,(,b,k,)0,的区间调用二分法程序，可找出区间,a,b,内的多个根，且不必要求,f,(,a,),f,(,b,)0,。,y,x,优点：条件和方法简单,(,只要求,f,(,x,),连续即可,),，方法收敛；,一,.,迭代法的建立与收敛性,所以,为,f,的根的充要条件是,为,的不动点。,2.2,迭代法,前者收敛,：,1.5;1.35721;1.33086;1.32588;1.32494;,1.32476;1.32473;1.32472;1.32472;,后者发散,:,1.52.375;12.39;,问题：何时收敛？,x,y,y=x,x,y,y=x,x,y,y=x,x,y,y=x,y=,(,x,),y=,(,x,),y=,(,x,),y=,(,x,),x,0,p,0,x,1,p,1,x,0,p,0,x,1,p,1,x,0,p,0,x,1,p,1,x,0,p,0,x,1,p,1,2.,收敛定理,定理,2.2.1,注,1,：,L,越小，收敛越快。,由定理结论,(3),或,(2.2.2),，只要前后两次迭代值的差值足,够小，就可使近似值 达到任意的精度。在实际计算,中，一般用 来控制迭代过程结束,。,注,2,：,定理条件非必要条件，可将,a,b,缩小，定义,局部收敛性定义,2.2.1,若存在,的某,邻域,B,=,x,|,|,x,|,使,由,x,0,B,开始的迭代都收敛,则称迭代法具有,局部收敛性,。,定理,2.2.2,设,(,x,),在,的某,邻域内具有连续的一阶导数，,且,|,()|1,，,则迭代法,x,n+1,=,(,x,n,),具有局部收敛性,。,证明 省略,。,3,编程停机判断,时，由（,2.2.2,）式知,比较小，此时停机，,（取定初值,x,0,）,计算，当,由,二,.,迭代法的收敛阶,(,收敛速度,),则称,x,n,p,阶收敛,相应的迭代法称为,p,阶方法,.,特别,p,=1,时叫线性收敛,此时要求,0,C,0,使,定义,2.2.2,:,设,定理,2.2.3,设,(,x,),在,的某邻域 内有充分多阶连续导数，则迭代法,x,n,+1,=,(,x,n,),为,p,阶收敛,的充要条件是,()=,()=,=,(,p,-1),()=0,，,(,p,),()0,.,证明,利用,Taylor,展开式（略）,2.3,牛顿（,Newton,）,法,Taylor,展开线性化,近似于,将,f,(,x,),在,x,n,点,Taylor,展开,解出,记为,，,则,一,.,Newton,迭代法,1.,迭代公式的建立：,2.Newton,迭代法的几何意义,与,求交点，解出,则,的切线,过,3.Newton,迭代法的收敛定理（,定理,2.3.1,）,（,1,）,连续，且分别不变号；,则,Newton,迭代法（,2.1,）产生的数列,收敛到根,。,在,a,b,上有根,且,在,a,b,上,满足,设,使,（,2,）,取初值,解：设,取,，则由（,2.1,）,例,2.3.1,用,Newton,迭代法求,4,.Newton,迭代法的收敛阶,(,收敛速度,),（,定理,2.3.2,）,在,a,b,有单根,，且,在,a,b,上有,设,直到二阶的连续导数。,本章基本要求：,1.,熟悉区间二分法；,2.,熟悉迭代法的建立，会使用收敛定理；,3.,熟悉,Newton,迭代法及其几何意义,;,4.,熟悉收敛阶的定义；,5.,熟悉,Newton,迭代法的收敛阶,;,