計算方法7.4-7.6

1、 用迭代法可逐步精確方程 根的近似值，但必須要找到 的等價方程 ,如果 選得不合適,不僅影響收斂速度,而且有可能造成迭代格式發(fā)散。能否找到一種迭代方法,既結(jié)構(gòu)簡單,收斂速度快,又不存在發(fā)散的問題。這就是本節(jié)要介紹的牛頓迭代法。7.4.1 7.4.1 牛頓迭代法的基本思想牛頓迭代法的基本思想 牛頓迭代法一種重要和常用的迭代法, 它的基本思想是借助泰勒展開，將非線性函數(shù)f(x)逐步線性化, 從而將非線性方程 f(x)=0 近似地轉(zhuǎn)化為線性方程求解 0)(xf0)(xf)(xx)(x 7.4 牛頓迭代法牛頓迭代法2022-3-21 對于方程 ,設(shè)其近似根為 , 函數(shù)f(x)可在 附近作泰勒展開 0)

2、(xf0 x0 x 200000)(21)()()(xxxfxxxfxfxf忽略高次項,用其線性部分作為函數(shù)f(x)的近似， )()()(000 xxxfxfxf 設(shè) 的根 ,則有 ,即 0)(xf1x0)(1xf0)()(0100 xxxfxf)()(0001xfxfxx2022-3-22x1是比x0更接近于根x*的近似值。 )()(1kkkkxfxfxx)2,1 ,0(k同樣將f(x)=0在x1附近作泰勒展開，取近似得到)()(1112xfxfxx依此類推，得到牛頓迭代公式牛頓迭代公式 因此得到方程f(x)=0的近似根數(shù)列 xi 。 2022-3-23注：當f(xk )=0時，由于此時在x

3、k處切線是水平的，因此無法計算出xk+1 Newton迭代的等價方程為：)( )()(0)(xfxfxxxxf所以2)( )( )()( )()( xfxfxfxfxfxx若f(x)在a處為單根，則0)( , 0)( , 0)(aafaf所以，迭代格式在根a附近收斂2022-3-247.4.2 牛頓迭代法的幾何解釋牛頓迭代法的幾何解釋 方程f(x)=0的根x*是曲線y=f(x)與x軸交點的橫坐標,設(shè)xk是根x*的某個近似值,過曲線y=f(x)的橫坐標為xk的點Pk=(xk ，f (xk)引切線交x軸于xk+1 , 并將其作為x*的近似值重復(fù)上述過程,每次通過求解切線方程來求解方程f(x)=0的

4、近似根,所以也稱為切線法切線法。2022-3-251x*x)(xfy 0 x2x000:( ) ( )()T a n g e n tlin ey fx f x xx0100()()f xxxfx2022-3-26例7.用牛頓迭代法求方程的根:0133xx解:13)(3xxxf設(shè)33)(2xxf由牛頓迭代法)()(1kkkkxfxfxx得取初值,5 .00 xx0 =0.5x1 =0.3333333333x2 =0.3472222222x3 =0.3472963532x4 =0.3472963553331323kkkkxxxx迭代四次精度達10-8 設(shè)函數(shù) ，且滿足,)(2baCxf定理定理2（

5、牛頓法收斂的充分條件牛頓法收斂的充分條件）1) f (a) f (b) 0；則牛頓迭代法產(chǎn)生的序列 xk 收斂到f (x) 在 a, b 的唯一根。有根有根只有單根，根只有單根，根唯一唯一產(chǎn)生的序列單調(diào)有產(chǎn)生的序列單調(diào)有界，保證收斂。界，保證收斂。2022-3-27 7.4.3 7.4.3 牛頓迭代法的收斂性牛頓迭代法的收斂性yx0B=x0f(x)0ayx0Bf(x)0a=x0yx0B=x0f(x)0ayx0Bf(x)0a =x02022-3-28例例8 用迭代法求 在隔根區(qū)間1.4,1.50123 xx內(nèi)的根，要求準確到小數(shù)點后第4位。（1）牛頓迭代公式為nnnnnnnnnnnnnxxxxx

6、xxxxxfxfxx2312231)()(2232231（2 2）2 . 0)4 . 1 (f2 . 0)5 . 1 (f 5 . 1 , 4 . 1 x當 時有，023)(2xxxf06)( xxf因 ,故取 ,牛頓迭代法收斂。0)5 . 1 ()5 . 1 ( ff5 . 10 x2022-3-29Newtons Method 收斂性依賴于收斂性依賴于x0 的選取。的選取。x*x0 x0 102022-3-2x0 不滿足迭代條件時，可能導(dǎo)致迭代值遠離根的情況而找不到根或死循環(huán)的情況2022-3-2110)arctan()(xxf0 x精確解為牛頓迭代法)1(arctan21kkkkxxxx

7、10 x取初值x0 = 2x1 = -3.54x2 = 13.95x3 = -279.34x4 = 122017如20 x若取初值x0 =1x1 = -0.5708x2 = 0.1169x3 = -0.0011x4 = 7.9631e-010 x5 = 0收斂發(fā)散7.4.4 牛頓迭代法求開方（自己看）的根方程，將開放問題轉(zhuǎn)化為求設(shè)0)(axxfaxnn由牛頓迭代公式) 1(111nkkkxaxnnx，迭代收斂。選初始值axn02022-3-2122、缺點：選定的初值要接近方程的解，否則有可能得不到收斂的結(jié)果。再者，牛頓迭代法計算量比較大。因每次迭代除計算函數(shù)值外還要計算微商值。1、優(yōu)點：牛頓迭

8、代法具有平方收斂的速度，所以在迭代過程中只要迭代幾次就會得到很精確的解。這是牛頓迭代法比簡單迭代法優(yōu)越的地方。2022-3-2132022-3-214本節(jié)作業(yè)P168 （8）2022-3-215 7.5 迭代法的收斂速度迭代法的收斂速度7.5.1 收斂速度的概念 一個具有實用價值的迭代法，不僅要求它收斂，而且還要求它收斂比較快。迭代收斂的速度是指迭代誤差的下降速度。在定理1中我們知道L越小或 迭代法收斂越快，但要準確反映收斂速度，還需要引進收斂階的概念，它是衡量迭代好壞的標志之一。,| )(|上越小在bax局部收斂性局部收斂性 當?shù)瘮?shù)較復(fù)雜時,不能保證在整個域內(nèi)收斂，通常只能設(shè)法使迭代過程

9、在根的鄰域(局部)收斂。定理定理3 3 設(shè) 在 的根 的鄰域中有連續(xù)的一階導(dǎo)數(shù),且 則迭代過程 具有局部收斂性。 證證: :由于 ,存在充分小鄰域: ,使成立 ，這里L為某個定數(shù),根據(jù)微分中值定理 。由于 ,又當 時 ,故有 由定理1知 對于任意的 都收斂 1)(* x*xx1)(*Lx)()()(*xxxx*)(xxx*)(xxxxLxx)(1kkxx0 x)(x)(xx*x1)(* x)(1kkxx2022-3-216注：局部收斂性定理對迭代函數(shù)的要求較弱，但對初始點要求較注：局部收斂性定理對迭代函數(shù)的要求較弱，但對初始點要求較高，即初始點必須選在精確解的附近高，即初始點必須選在精確解的附

10、近例9 設(shè) ,要使迭代過程 局部收斂到 ,求 的取值范圍。解： 由在根 鄰域具有局部收斂性時, 收斂條件 ) 5()(2xxx)(1kkxx5*x)5()(2xxxxx21)(5*x1521)(*ax15211a0522a所以 051a2022-3-2172022-3-218*xxekk設(shè)定義1. 滿足和若存在實數(shù)01cppkkkee|lim1c時稱為平方收斂。時稱為超線性收斂，時稱為線性收斂當別地，稱為漸進誤差常數(shù)。特階收斂，則稱迭代法221 ,1pppcp收斂速度也就越快越大顯然, p 數(shù)數(shù)p p的大小反映了迭代法收斂的速度的快慢，的大小反映了迭代法收斂的速度的快慢，p p愈大，愈大，則收

11、斂的速度愈快，故迭代法的收斂階是對迭代法收斂速則收斂的速度愈快，故迭代法的收斂階是對迭代法收斂速度的一種度量。度的一種度量。 2022-3-219從而確定收斂階呢？如何確定那么,p即處處可導(dǎo)處充分光滑在精確解如果迭代函數(shù),*)(xx有展開作在將,*)(Taylorxx 2*)(! 2*)(*)*)(*)()(xxxxxxxxppppxxpxxpx*)(!)(*)()!1(*)()(1) 1(0*)()1(xp *)(*)(xx如果*)()(xxppxxp*)(!)()(之間和位于其中xx*2022-3-220定理4. )(1kkxxpkpxxpx*)(!)(*)()(pkpxxp*)(!)()

12、(*1xxkpkkxxxx*1!)()(pppxxkk的收斂階是即迭代法)(1附近滿足：在根如果迭代法迭代函數(shù)*)(xx階導(dǎo)數(shù)且連續(xù)；存在px)() 1 (,0*)()1(xp *)(*)()2(xx0*)()(xp而pxxkk的收斂階是則迭代法)(1( )*1()lim!pkpkkexep例10 已知迭代公式 收斂于 證明該迭代公式平方收斂。證: 迭代公式相應(yīng)的迭代函數(shù)為21132kkkxxx3*3x2132)(xxx436)(232)(xxxx ，將 代入，根據(jù)定理4可知，迭代公式平方收斂。3*3x032336)(0)(33* xx，為了使迭代過程收斂或提高收斂的速度為了使迭代過程收斂或提

13、高收斂的速度, , 可設(shè)法可設(shè)法 提高初值的精度以減少迭代的次數(shù)提高初值的精度以減少迭代的次數(shù) 提高收斂的階數(shù)提高收斂的階數(shù) p p2022-3-2217.5.2 牛頓迭代法的收斂性定理定理5 5 設(shè) 是方程 的單根, 且 f(x) 在 的某鄰域內(nèi)有連續(xù)的二階導(dǎo)數(shù), 則牛頓法在 附近局部收斂, 且至少二階收斂, 有*x0)(xf*x*x)(2)(limlim*2*1*1xfxfxxxxeekkkkkk 證: 牛頓迭代公式對應(yīng)的迭代函數(shù)為 若 是方程 的單根,則有 , 從而 )()()(xfxfxx*x0)(xf0)(*xf0)(* xf0)()()()(2* xfxfxfx由定理3知,牛頓迭代

14、法在 附近局部收斂。又由定理4知, 迭代公式至少具有二階收斂速度。 *x2022-3-222利用泰勒公式kkkkkxxxxfxxxfxfxf,)(2)()()()(0*2* 2*)()(2)()()(kkkkkxxxffxfxfxx 2*)()(2)()()(kkkkkxxxffxxfxfx 2*1)()(2)(kkkxxxffxx )(2)(lim*2*1*xfxfxxxxkkk 所以 證畢2022-3-223 7.6 弦截法弦截法 牛頓迭代法牛頓迭代法具有收斂快，穩(wěn)定性好，精度高具有收斂快，穩(wěn)定性好，精度高等優(yōu)點，等優(yōu)點，是它在實際中被廣泛應(yīng)用的主要原因。是它在實際中被廣泛應(yīng)用的主要原因。

15、然而，牛頓法要求求出導(dǎo)數(shù)然而，牛頓法要求求出導(dǎo)數(shù)f ，這是它的缺點。，這是它的缺點。如果如果f 復(fù)雜，求導(dǎo)可能很困難，當復(fù)雜，求導(dǎo)可能很困難，當f 只是隱含地定只是隱含地定義時，求導(dǎo)則是不可能的。義時，求導(dǎo)則是不可能的。如果用不計算導(dǎo)數(shù)的如果用不計算導(dǎo)數(shù)的迭代方法，往往只有線性收斂的速度。迭代方法，往往只有線性收斂的速度。2022-3-224問題： 保證收斂速度 避免求導(dǎo)弦截法弦截法 弦截法弦截法（割線法）（割線法）牛頓迭代法牛頓迭代法一步要計算一步要計算 f 和和 f ，相當于，相當于2個函數(shù)值，比較個函數(shù)值，比較費時?，F(xiàn)用費時?，F(xiàn)用 f 的值近似的值近似 f ，可少算一個函數(shù)值。，可少算一

16、個函數(shù)值。x0 x1切線切線 割線割線 切線斜率切線斜率 割線斜率割線斜率01011)()()(xxxfxfxf收斂比切線法慢，且收斂比切線法慢，且對初值要求同樣高。對初值要求同樣高。2022-3-225262022-3-2 本節(jié)介紹的弦截法弦截法則是避開了求導(dǎo)數(shù)運算，具體又分為單點弦截法和雙點弦截法。 圖上不變號，如在區(qū)間內(nèi)有一個單根，在區(qū)間條件：設(shè)方程P64),()(),(0)(baxfbaxf 單點弦截法單點弦截法)()()()()(101011xxxxxfxfxfxf此弦與x軸交點的橫坐標設(shè)為 的弦的方程：及，則過，取)(,()(,(11100010 xfxPxfxPbxax)()()

17、()(1010112xfxfxfxxxx2022-3-227在作弦和點否則選取點即為所求根。，則如果)(,)(,0)(002222xfxxfxxxxf)()()()()(202022xxxxxfxfxfxf此弦與x軸交點的橫坐標設(shè)為 )()()()(2020223xfxfxfxxxx重復(fù)上述過程。是否等于零，否則繼續(xù)判斷)(3xf依此類推寫成一般迭代格式)()()()(001kkkkkxfxfxfxxxx，3 , 2 , 1 , 0k2022-3-228x2x30)()(0)(0000 xfxfxxfx必須滿足，因此選擇本例中果。的選擇會影響迭代的結(jié)樣，注意：與牛頓迭代法一x*a=x0b=x1

18、)(xfy 單點弦截法的幾何意義單點弦截法的幾何意義是用過曲線上兩點 、 的割線來代替切線,用割線與x軸交點的橫坐標作為方程的近似根 再過P0點和點 作割線)(,(000 xfxP)(,(111xfxP2x求出 ,依此類推，可求出滿足精度要求的 。)(,(222xfxP3xkx計算中計算中P P0是不變的，因此單點弦截法又稱為是不變的，因此單點弦截法又稱為定端點弦截法定端點弦截法。29誤差絕對值不超過0.510-2解:由迭代公式進行迭代得，滿足精度要求。2022-3-2令 ，得408)(3xxxf例11 用單點弦截法求方程在區(qū)間4,6內(nèi)的根04083 xx83)(2xxfxxf6)( 代入端點值8)4(f24)4( f128)6(f36)6( f4, 60)6()6(10 xxff取，1877674. 46xx 雙點弦截法雙點弦截法)()()()(001xxxfxfxfxxkkkkk3 , 2 , 1 , 0k單點弦截法單點弦截法固定一個端點x0，若在作第k+1次迭代時，將迭代公式中的點(x0，f(x0)換成(xk-1，f(xk-1),即得到雙點弦雙點弦截法截法。迭代公式為)()()()(111kkkkkkkxfxfxfxxxx3 , 2 , 1 , 0k2022-3-230需要需要2個初值個初值 x0 和和 x12022-3-