6.09級7.5-2牛頓修正.ppt

1、5.2 Newton法收斂定理,5 牛頓迭代法,定理6和定理7都要求滿足,初值選取較困難.,在實(shí)際應(yīng)用中可以放寬對初值的要求,即有以下的非局部收斂定理.,注, 證Newton序列是單調(diào)序列,且是有界序列,因此有極限；, 證f(x)=0在a,b上,有唯一解x*；,分析,分以下幾步證明:,需要證明為什么Newton序列單調(diào)二階收斂于,的唯一解x*.,定理中,x0容易選取，,只要滿足,即可., 證明Newton序列的極限值就是f(x)=0的唯一解x*，,最后由定理10得Newton序列二階收斂于唯一解x*.,在a,b上,定理11,（Newton法非局部收斂定理）,且滿足：,在a,b上不變號；,則對,

2、滿足,Newton序列單調(diào)二階收斂于,在a,b上的唯一解x*.,在a,b上不取零，,證明, 先證f(x)=0有唯一解., 證Newton序列單調(diào),有界,從而有極限.,考慮由牛頓法得到的x1的特性,因?yàn)閒(x)連續(xù),所以f(x)=0在a,b上至少有一個,解,設(shè)為x*.,又因?yàn)閒 (x)連續(xù),則f (x)在a,b上,恒正或恒負(fù),從而f(x)在a,b上,嚴(yán)格單調(diào)上升或下降,f(x)=0在a,b,上最多只有一個解.,因此f(x)=0在a,b,內(nèi)有唯一解x*.,(考慮x1與x0、x*的大小關(guān)系,進(jìn)一步討論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*之間,從而,且,又單調(diào)、有界序列必有極限，,設(shè)極限為,并有界,是單調(diào)序列, 證,由于,從而,又由f(x)=0在a,b,上只有唯一解x*.,得,即,最后,由定理7知xk二階收斂于x*.,#,例4,用Newton法求解,解,首先可以判斷解在(0,1)內(nèi).,在(0,1)上,(恒正),(不變號),則Newton迭代序列單調(diào)二階收斂到,在(

4、0,1)內(nèi)的唯一根, Newton迭代的計(jì)算結(jié)果如下表,表4-2,優(yōu)點(diǎn),收斂速度快 .,缺點(diǎn),1. 需要每次計(jì)算導(dǎo)數(shù)值 f (x)，如果函數(shù)f (x)比較復(fù)雜，,使用牛頓公式不方便 .,2. 對初值x0要求苛刻.,5.3 Newton切線法的修正算法,1.簡化牛頓切線法,思想方法,用常數(shù)c 代替牛頓切線法中的 f (xk),簡化牛頓切線法公式,至少是線性收斂，,收斂性,當(dāng)取c = f (xk)時，是二階收斂.,在初始值x0，取c = f (x0) ,c的選取方法,在xk附近的一些點(diǎn)上,可取c = f (xk) .,這樣即保證了計(jì)算簡單又使收斂較快，在某些點(diǎn)上,接近平方收斂.,2.Newton下

5、山法(修正的Newton法),用牛頓切線法求方程x 3-x-1= 0在x=1.5附近的一個根 .,解,取迭代初值x0=1.5，用牛頓公式,計(jì)算結(jié)果如表4-3所示 .,表4-3,其中x3=1.32472 的每一位數(shù)字都是有效數(shù)字.,例5,如果改用 x0=0.6作為初值，迭代一次得x1=17.9, 這個結(jié)果反而比x0,更偏離了所求的根 x*.,為了防止迭代發(fā)散，對迭代過程附加一基本,要求,即保證函數(shù)值單調(diào)下降,，滿足這項(xiàng)要求的算,法稱下山法.,(1) 下山序列的定義,若視|f(x)|為f(x)在x點(diǎn)的高度,則,是山谷最低點(diǎn).,定義,下山序列.,下山序列的極限點(diǎn),不一定是f(x)0的解.,方程f(x

6、)0的解 滿足：,，稱 是|f(x)|,的最小點(diǎn).,注,(2) 收斂的牛頓序列除去有限點(diǎn)外一定是下山序列,因?yàn)?中值定理,(3) 下山法,引理1,則一定存在,成立,分析,該式子實(shí)際上是兩個函數(shù)值的比較,即是點(diǎn)x與鄰近點(diǎn),的函數(shù)值,而點(diǎn)x與點(diǎn),只差,且含有,f(x)的導(dǎo)數(shù),由已知考慮用導(dǎo)數(shù)的定義,時,形如:,的導(dǎo)數(shù)定義.,證明,由導(dǎo)數(shù)的定義,得,即,引理1,則一定存在,成立,于是由極限的概念,只要,有,存在,于是由極限的概念,從而,即,存在,牛頓下山法的定義,說明,牛頓下山法為標(biāo)準(zhǔn)的,牛頓法；,因此為保證收斂性, tk 不能太小.,(2)下山因子tk的一種常用取法先取,若已滿足,若不滿足,則取,

7、再判斷是否滿,該方法稱為牛頓下山法.,例6,解,若取初值1.5,滿足收斂條件.但若取,計(jì)算得,與可能值的差距加大,即使能收斂速度也會很慢.,此時用牛頓下山,法,設(shè)下山因子為t ,則計(jì)算結(jié)果如下表,此時,計(jì)算方法,表4-4,3. 重根加速收斂法(推廣),定理9、10、11中，,假設(shè),是f(x)=0的m(m1)重根,Newton法能否用?,怎樣用?,是否收斂?,(1) 重根處Newton法是收斂的,則,到第4次時近似值的精度已經(jīng)相當(dāng)高了.,如表所示,用牛頓下山法,第1次就落入了局部收斂的領(lǐng)域,說明,重根處Newton法局部線性收斂 .,且重?cái)?shù)越大,收斂越慢.,結(jié)論,m =1時即是牛頓法，此時 是超

8、線性收斂，即二階收斂.,(2) 加速法,以Newton法為基本簡單迭代 ,用Steffenson方法進(jìn)行計(jì)算可,得二階收斂迭代序列.,若m已知取迭代函數(shù),注 需要預(yù)知m的大小.,，此時可以證明,即迭代是平方收斂.,（見牛頓迭代的加速法）,（自己證）,若m未知取定義新函數(shù),則,因此,可用Newton法求h(x)=0的單根.,即,h(x)=0的單根即為f(x)=0的重根.且該迭代是二階收斂的.,事實(shí)上，,注,這種方法不需要知道重根數(shù)，但迭代格式稍微復(fù)雜.,已知,解,牛頓切線法,取x0=1.5,計(jì)算結(jié)果如表4-5所示 .,表4-5,例7,經(jīng)過3次迭代，重根法達(dá)到了 10-9, 精確度，是平方收斂速度，而牛,頓法是一階的，要30次迭代才能得到相同的結(jié)果.,是方程x 4-4x2+4= 0的二重根，用牛頓切線法和重,根修正公式求解.,重根數(shù) m=2時,2.