6.09级7.5-2牛顿修正.ppt

1、5.2 Newton法收敛定理,5 牛顿迭代法,定理6和定理7都要求满足,初值选取较困难.,在实际应用中可以放宽对初值的要求,即有以下的非局部收敛定理.,注, 证Newton序列是单调序列,且是有界序列,因此有极限；, 证f(x)=0在a,b上,有唯一解x*；,分析,分以下几步证明:,需要证明为什么Newton序列单调二阶收敛于,的唯一解x*.,定理中,x0容易选取，,只要满足,即可., 证明Newton序列的极限值就是f(x)=0的唯一解x*，,最后由定理10得Newton序列二阶收敛于唯一解x*.,在a,b上,定理11,（Newton法非局部收敛定理）,且满足：,在a,b上不变号；,则对,

2、满足,Newton序列单调二阶收敛于,在a,b上的唯一解x*.,在a,b上不取零，,证明, 先证f(x)=0有唯一解., 证Newton序列单调,有界,从而有极限.,考虑由牛顿法得到的x1的特性,因为f(x)连续,所以f(x)=0在a,b上至少有一个,解,设为x*.,又因为f (x)连续,则f (x)在a,b上,恒正或恒负,从而f(x)在a,b上,严格单调上升或下降,f(x)=0在a,b,上最多只有一个解.,因此f(x)=0在a,b,内有唯一解x*.,(考虑x1与x0、x*的大小关系,进一步讨论f (x1)的符号.),另外,比较以上两式,并考虑到 f(x0)与,同号,得x1介于x0与x*,首先

3、由,f (x1)与 f (x0),同号,(否则 f(x)=0不是有唯一解)，,同时可得,同理由,得由牛顿法得到的x2,必介于x1与,x*之间，且,f (x2)与f (x1)同号，,，由此得到的牛顿序列,之间，,(若,则,若,则,)且,则有,满足,xk+1介于xk与x*之间,从而,且,又单调、有界序列必有极限，,设极限为,并有界,是单调序列, 证,由于,从而,又由f(x)=0在a,b,上只有唯一解x*.,得,即,最后,由定理7知xk二阶收敛于x*.,#,例4,用Newton法求解,解,首先可以判断解在(0,1)内.,在(0,1)上,(恒正),(不变号),则Newton迭代序列单调二阶收敛到,在(

4、0,1)内的唯一根, Newton迭代的计算结果如下表,表4-2,优点,收敛速度快 .,缺点,1. 需要每次计算导数值 f (x)，如果函数f (x)比较复杂，,使用牛顿公式不方便 .,2. 对初值x0要求苛刻.,5.3 Newton切线法的修正算法,1.简化牛顿切线法,思想方法,用常数c 代替牛顿切线法中的 f (xk),简化牛顿切线法公式,至少是线性收敛，,收敛性,当取c = f (xk)时，是二阶收敛.,在初始值x0，取c = f (x0) ,c的选取方法,在xk附近的一些点上,可取c = f (xk) .,这样即保证了计算简单又使收敛较快，在某些点上,接近平方收敛.,2.Newton下

5、山法(修正的Newton法),用牛顿切线法求方程x 3-x-1= 0在x=1.5附近的一个根 .,解,取迭代初值x0=1.5，用牛顿公式,计算结果如表4-3所示 .,表4-3,其中x3=1.32472 的每一位数字都是有效数字.,例5,如果改用 x0=0.6作为初值，迭代一次得x1=17.9, 这个结果反而比x0,更偏离了所求的根 x*.,为了防止迭代发散，对迭代过程附加一基本,要求,即保证函数值单调下降,，满足这项要求的算,法称下山法.,(1) 下山序列的定义,若视|f(x)|为f(x)在x点的高度,则,是山谷最低点.,定义,下山序列.,下山序列的极限点,不一定是f(x)0的解.,方程f(x

6、)0的解 满足：,，称 是|f(x)|,的最小点.,注,(2) 收敛的牛顿序列除去有限点外一定是下山序列,因为,中值定理,(3) 下山法,引理1,则一定存在,成立,分析,该式子实际上是两个函数值的比较,即是点x与邻近点,的函数值,而点x与点,只差,且含有,f(x)的导数,由已知考虑用导数的定义,时,形如:,的导数定义.,证明,由导数的定义,得,即,引理1,则一定存在,成立,于是由极限的概念,只要,有,存在,于是由极限的概念,从而,即,存在,牛顿下山法的定义,说明,牛顿下山法为标准的,牛顿法；,因此为保证收敛性, tk 不能太小.,(2)下山因子tk的一种常用取法先取,若已满足,若不满足,则取,

7、再判断是否满,该方法称为牛顿下山法.,例6,解,若取初值1.5,满足收敛条件.但若取,计算得,与可能值的差距加大,即使能收敛速度也会很慢.,此时用牛顿下山,法,设下山因子为t ,则计算结果如下表,此时,计算方法,表4-4,3. 重根加速收敛法(推广),定理9、10、11中，,假设,是f(x)=0的m(m1)重根,Newton法能否用?,怎样用?,是否收敛?,(1) 重根处Newton法是收敛的,则,到第4次时近似值的精度已经相当高了.,如表所示,用牛顿下山法,第1次就落入了局部收敛的领域,说明,重根处Newton法局部线性收敛 .,且重数越大,收敛越慢.,结论,m =1时即是牛顿法，此时 是超

8、线性收敛，即二阶收敛.,(2) 加速法,以Newton法为基本简单迭代 ,用Steffenson方法进行计算可,得二阶收敛迭代序列.,若m已知取迭代函数,注 需要预知m的大小.,，此时可以证明,即迭代是平方收敛.,（见牛顿迭代的加速法）,（自己证）,若m未知取定义新函数,则,因此,可用Newton法求h(x)=0的单根.,即,h(x)=0的单根即为f(x)=0的重根.且该迭代是二阶收敛的.,事实上，,注,这种方法不需要知道重根数，但迭代格式稍微复杂.,已知,解,牛顿切线法,取x0=1.5,计算结果如表4-5所示 .,表4-5,例7,经过3次迭代，重根法达到了 10-9, 精确度，是平方收敛速度，而牛,顿法是一阶的，要30次迭代才能得到相同的结果.,是方程x 4-4x2+4= 0的二重根，用牛顿切线法和重,根修正公式求解.,重根数 m=2时,2.