牛顿法抛物线法.ppt

单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,,,*,第七章,非线性方程,(,组,),的数值解法,——,Newton,法,,——,弦截法、抛物线法,1,本讲内容,,Newton,法及其收敛性,,牛顿下山法,,弦截法与抛物线法,2,,Newton,法,基本思想,将非线性方程,线性化,设,x,k,,是,f,(,x,)=0,的近似根，将,f,(,x,),在,x,k,,处,Taylor,展开,令：,条件：,,f,’,(,x,), 0,3,,Newton,法,x,y,x*,x,k,x,k,+1,4,,Newton,法,算法 ：,(,Newton,法 ),(1),任取迭代初始值,,x,0,(2),对,k,= 1, 2, ... , maxit,，计算,判断收敛性，若收敛，则停止计算，输出近似解,5,,收敛性,k,= 0, 1, 2, . . .,迭代函数,牛顿法至少二阶,局部收敛,6,,举例,例：,用,Newton,法求,f,(,x,) =,x,e,x,,– 1=0,,的解,ex75.m,7,,举例,例：,用,Newton,法求,f,(,x,) =,x,2,,– C=0,,的正根,解：,对任意,x,0,>0,，,,总有,|,q,|<1,，,,即牛顿法收敛,8,,牛顿,法,,牛顿,的,优点,牛顿,法是目前求解非线性方程,(,组,),的主要方法,至少二阶局部收敛，收敛速度较快，特别是当迭代点充分靠近精确解时。

牛顿,的缺点,,对重根收敛速度较慢（线性收敛）,,,对初值的选取很敏感，要求初值相当接近真解,先用其它算法获取一个近似解，然后使用牛顿法,,需要求导数！,9,,简化的,Newton,法,线性收敛,简化的,Newton,法,,基本思想：,用,f,’,(,x,0,),,替代所有的,f,’,(,x,k,),10,,Newton,下山法,下山因子的取法：,从,,=1,开始，逐次减半，直到满足下降条件,基本思想：,要求每一步迭代满足下降条件,具体做法：,加,下山因子,,,,Newton,下山法,保证全局收敛,11,,重根情形,且,,解法一,：直接使用,Newton,法,线性收敛,,解法二,：改进的,Newton,法,二阶收敛,缺点：,需要知道,m,,的值,重根情形,12,,重根情形,令,x,*,是,,(,x,)=0,的,单重根,,解法三,：用,Newton,法解,,(,x,) = 0,迭代格式：,13,,举例,例：,求,x,4,-,4,x,2,＋,,4=0,,的二重根,(1),普通,Newton,法,ex76.m,(2),改进的,Newton,法,(3),用,Newton,法解,,(,x,) = 0,14,,弦截法与抛物线法,弦截法与抛物线法,,目的,：避免计算,Newton,法中的导数，且具有较高的收敛性（超线性收敛）,,弦截法（割线法）：,用差商代替微商,,抛物线法：,用二次多项式近似,f,(,x,),15,,弦截法,弦截法迭代格式：,k,= 1, 2, 3, . . .,注：弦截法需要提供,两个迭代初始值,16,,收敛性,定理：,设,x,*,是,f,(,x,),,的零点,，,,f,(,x,),在,x,*,,的某邻域,U,(,x,,,),,内有二阶连续导数，且,f,’,(,x,),0,，若初值,x,0,，,x,1,,U,(,x,,,),，,则当,U,(,x,,,),充分小时，弦截法具有,p,,阶收敛性，其中,17,,弦截法几何含义,x,y,x*,x,k,-,1,x,k,x,k,+1,18,,抛物线法,基本思想：,用二次曲线与,x,,轴的交点作为,x*,的近似值,,抛物线法,19,,抛物线法,y,x,k,-,2,x,k,-,1,x,k,x,k,+1,20,,抛物线法,计算过程,二次曲线方程,(,三点,Newton,插值多项式,),,问题：,p,2,(,x,),与,x,,轴有,两个交点,，取哪个点？,解决方法：,取靠近,x,k,的那个点,!,21,,抛物线法,取靠近,x,k,的那个点,22,,收敛性,在一定条件下可以证明：抛物线法的收敛阶为,23,,作业,教材,238,页，习题,7,,教材,239,页，习题,9,、,15,24,,。