1、2022-2-21簡單迭代法簡單迭代法 簡單迭代法也稱逐次代換法逐次代換法，是非線性方程求根中各類迭代法的基礎(chǔ)，其涉及的處理方法、概念、和理論都易于推廣。 基本思想基本思想 利用對(duì)方程做等價(jià)變換根不發(fā)生變化的特點(diǎn)，將方程f(x)=0等價(jià)變形為x=(x)，而獲得迭代計(jì)算公式 xk+1= (xk)由它算出逼近根x*的數(shù)列xk2022-2-22要求出 f(x)=0的根，直接從函數(shù) f(x)著手求之是不容易的，因?yàn)楦鵻* 是“隱藏”在函數(shù)f(x)中，直接找根會(huì)感到無從下手，但若把f(x)0變?yōu)閤= (x),這樣求根就變得易于操作了。設(shè)它的迭代格式為xk+1= (xk) ，當(dāng)給定處值x0 后, 由迭代格

2、式可求得數(shù)列xk。如果xk收斂于x*，則它就是方程的根。因?yàn)椋?上面 x= (x)稱為不動(dòng)點(diǎn)方程， (x)稱為迭代函數(shù)。相的數(shù)列xk稱為迭代數(shù)列。 )()()(*1*limlimlimxxxxxkkkkkk2022-2-23定理定理1：假定迭代函數(shù)假定迭代函數(shù) (x) 滿足下列條件：滿足下列條件： 1. 對(duì)任意對(duì)任意 xa,b時(shí)時(shí),有有 (x) a,b 2. 存在正常數(shù)存在正常數(shù) L1，使對(duì)任意，使對(duì)任意x1,x2 a,b 有有 | (x1) - (x2 )| L| x1 - x2 | (1) 則則 (x)在在a,b內(nèi)有唯一的不動(dòng)點(diǎn)內(nèi)有唯一的不動(dòng)點(diǎn)x*，且對(duì)于任意初值，且對(duì)于任意初值 x0 a

3、,b 由迭代公式由迭代公式 xk+1= (xk)產(chǎn)生的數(shù)列產(chǎn)生的數(shù)列xk均收斂于方程根均收斂于方程根x*。實(shí)用中條件實(shí)用中條件2常用常用 ),(1| )(|baxLx2022-2-24證明：做輔助函數(shù) g(x) = x- (x) 顯然g(x) a,b 由條件1有 g(a)g(b) 0, 利用中值定理，存在 a,b 使g() = 0 ，即 = (), 是一個(gè)不動(dòng)點(diǎn)，如果還有一個(gè)不動(dòng)點(diǎn) （ = ()）由條件2有 | - |=|() - ( )|L| - | | - | 矛盾。 故 (x)在在a,b內(nèi)有唯一的不動(dòng)點(diǎn)記為x*下面證 xk+1= (xk)產(chǎn)生的數(shù)列xk收斂性2022-2-25 設(shè)方程 x

4、= (x) 在區(qū)間 a,b內(nèi)的根 為 x*則有 x* = (x* )， 由 xk+1= (xk)據(jù)此反復(fù)遞推有故當(dāng) 時(shí)迭代值| )()(|*1xxLxxxxkkk*1xxLxxkk*0*xxLxxkkk*xxk2022-2-26定理2：在定理1的條件下，有如下估計(jì)式1、 | x* - xk | | xk - xk-1 | L /(1-L)2、 | x* - xk | | x1 - x0 | Lk /(1-L)證明：證明：由迭代格式和定理1，有| xk+1 - xk |= | (xk) - xk |= | (xk) - (x* ) + (x* ) - xk | = |(xk) - (x* ) +

5、 x* - xk |=| x* - xk + (xk) - (x* ) | |x* - xk |-| (xk) - (x* ) |x* - xk |- L | x* - xk | =(1- L) |x* - xk |2022-2-27 | x* - xk | | xk+1 - xk | /(1-L) （2）另一方面 | xk+1 - xk |= | (xk) - ( xk-1 ) | L | xk - xk-1 | （3）代入（2）式，得 | x* - xk | | xk - xk-1 | L /(1-L)反復(fù)利用（3）式有代入（2）式，得結(jié)論2。011xxLxxkkk2022-2-28定理3

6、：設(shè)x*是迭代函數(shù) (x)的不動(dòng)點(diǎn)，m為正整數(shù)，且 （m）(x)在x*的鄰域N(x*)內(nèi)連續(xù),并有如下關(guān)系 （k）(x*) = 0 ,k=0,1,m-1, （m）(x*) 0則由 xk+1= (xk)產(chǎn)生的數(shù)列xk在鄰域N(x*)內(nèi)是m階收斂的，且有極限 k 時(shí) （ x* - xk+1 )/ （ x* - xk ) m （m）(x*) /m!證明見書證明見書2022-2-29在定理3中，當(dāng)m =1時(shí)，有k （ x* - xk+1 )/ （ x* - xk ) (x*)由于一般 (x*) 0，故簡單迭代法的收斂階一般是線性的，當(dāng) (x*) =0時(shí)，對(duì)應(yīng)的簡單迭代法就是超線性的了。它可以提示我們對(duì)

7、簡單迭代法進(jìn)行加速。 如果簡單迭代格式xk+1= (xk) 收斂的較慢，引入?yún)?shù)C對(duì)誤差做調(diào)控 xk+1= (xk)+C( (xk) - xk)為選擇合適的參數(shù)C，考慮如上簡單迭代格式對(duì)應(yīng)的迭代函數(shù) (x) = (x)+C( (x) - x)因?yàn)?(x) = (x)+C( (x) - 1)選擇 (x*) = 0，可以獲得超線性收斂的迭代公式，此時(shí)有C簡單迭代法的收斂階與加速簡單迭代法的收斂階與加速xk+1 - xk2022-2-210 (x*) (xk) C = - - 1 - (x*) 1 - (xk) 記記 k = (xk) ，可以得到如下加速迭代公式，可以得到如下加速迭代公式 k x k

8、+1= (xk) + - ( (xk) - xk) 1 - k 2022-2-211定義定義1：如果存在如果存在x* 的某個(gè)鄰域的某個(gè)鄰域 N(x*)：| x* - x | ，使迭代過程使迭代過程 xk+1= (xk)對(duì)于任意初值對(duì)于任意初值 x0 N(x*) 均收斂，則稱迭代過程均收斂，則稱迭代過程xk+1= (xk) 在根在根 x* 鄰近具有鄰近具有局部收斂性局部收斂性。2022-2-212Newton迭代法也稱切線法切線法，是非線性方程求根方法中收斂的最快的方法，其涉及的近似處理方法很有代表性。 基本思想基本思想 將方程f(x)=0 線性化處理為近似方程，然后用近似方程獲得求根的迭代計(jì)算

9、公式 Newton迭代法迭代法2022-2-213 設(shè)xk是f(x) = 0的一個(gè)近似根，把f(x)在 xk 處作泰勒展開若取前兩項(xiàng)來近似代替f(x)(稱為f(x)的線性化)，則得近似線性方程設(shè) (xk ) 0 ,令其解為 xk+1 ,得 （4)稱為求f(x)=0根的牛頓迭格式牛頓迭格式。 2)(! 2)()()()(kkkkkxxxfxxxfxfxf0)()()(kkkxxxfxfxf)()(1kkkkxfxfxx2022-2-214顯然顯然Newton迭代迭代法也法也是簡單迭代法的一種迭代格式，它對(duì)應(yīng)的不動(dòng)點(diǎn)方程和迭是簡單迭代法的一種迭代格式，它對(duì)應(yīng)的不動(dòng)點(diǎn)方程和迭代函數(shù)分別為代函數(shù)分別為

10、 因?yàn)橐驗(yàn)?在在 f(x)=0的根的根 x* 的某個(gè)鄰域內(nèi)成立的某個(gè)鄰域內(nèi)成立, 因此因此Newton迭代迭代法具有局部收斂性法具有局部收斂性)()()(xfxfxx1)()()()(2 Lxfxfxfx)()(xfxfxx)0)( xf2022-2-215定理3告訴我們，迭代過程的收斂速度依賴于迭代函數(shù)。對(duì)于牛頓迭代公式(4)，其迭代函數(shù)為其導(dǎo)數(shù)為由于 f(x*) = 0 ,假定 f(x*) 0 ，則x*是f(x)的一個(gè)單根， (x*)=0 依據(jù)定理3可知牛頓法在根 x* 的鄰近是平方收斂的。)()()(xfxfxx2)()()()(xfxfxfx Newton迭代法的收斂階迭代法的收斂階2

11、022-2-216 由（4）式知xk+1是函數(shù)y=f(x)在點(diǎn)（xk ,f(xk )）處的切線與X軸的交點(diǎn)的橫坐標(biāo)（如圖）。也就是說，新的近似值xk+1是用代替曲線y=f(x)的切線與x 軸相交得到的。繼續(xù)做下去可以得到一個(gè)收斂于根 x*點(diǎn)列。由圖可見，只要初值x0取的充分靠近 x* ,產(chǎn)生的點(diǎn)列就會(huì)很快收斂于根 x* 。2022-2-217y2022-2-218例1:用牛頓迭代法求方程 f(x)=x3+2x2+10 x-20 = 0 的根.解 因 , 所以迭代公式為 選取 x0 =1，計(jì)算結(jié)果列于下表 n 1 2 3 4 xn 1.411764706 1.369336471 1.368808

12、189 1.368808189從計(jì)算結(jié)果可以看出,牛頓法的收斂速度是很快的,進(jìn)行了四次迭代就得到了較滿意的結(jié)果.)1043/()20102(2231nnnnnnnxxxxxxx 例題例題1043)(2xxxf2022-2-219例2 計(jì)算 的近似值。 =10 -6 x0=0.88 解： 令x= 問題轉(zhuǎn)化為求(x)= x2-0.78265=0的正根由牛頓迭代公式 xk+1= xk-(xk)/(xk)= xk/2+0.78265/2xk 迭代結(jié)果 k 0 1 2 3 xk 0.880000 0.884688 0.884675 0.884675 滿足了精度要求 =0.884675 )(/)(01xf

13、xfxxnnn0.782650.782650.782651 1、 單點(diǎn)弦截法單點(diǎn)弦截法 ：牛頓法一步要計(jì)算牛頓法一步要計(jì)算 f 和和 f ，相當(dāng)于，相當(dāng)于2個(gè)函數(shù)值。現(xiàn)用個(gè)函數(shù)值?，F(xiàn)用 f 的值近似的值近似 f :x0 x1切線切線 割線割線 切線斜率切線斜率 割線斜率割線斜率00)()()(xxxfxfxfkkk)()()()(001xxxfxfxfxxkkkkkx22022-2-221Newton法通常依賴初值的選取，如果選擇不當(dāng)，將導(dǎo)致迭代發(fā)散或產(chǎn)生無限循環(huán)；此外，每一步迭代都需要計(jì)算導(dǎo)數(shù)值，有時(shí)計(jì)算是不方便的。基于這兩點(diǎn)，產(chǎn)生了幾種Newton迭代法的變形。1、 割線法割線法（收斂階為

14、1.618） 用過點(diǎn)的割線的斜率來代替導(dǎo)數(shù)，得到迭代公式：Newton迭代法的變形迭代法的變形2、 Newton下山法下山法 Newton下山法是為了防止因選取不當(dāng)造成迭代發(fā)散或無限循環(huán)的情況。在迭代中加入函數(shù)絕對(duì)值單調(diào)減少的條件：。對(duì)應(yīng)的迭代格式為：=，其中稱為下山因子。Newton下山法只有線性斂速。)()()()(111kkkkkkkxxxfxfxfxx2022-2-2221）當(dāng)用 Newton 法求重根時(shí)，不妨設(shè)f（x）= xgxxm* 0 xg*f （x）= xgxxxgxxmm*1m* = xg*xxxmgxx1m*kkk*1kxxfxfxxx=k*kkk*kk*kxgxxxmgx

15、gxxxmgxx klim*k*1kxxxx=klimk*kkk*kkxgxxxmgxgxxxmg = 0m1mxmgxg1m*此此時(shí)時(shí)，Newton 法法具具有有線線性性斂斂速速。2022-2-223七、牛頓迭代法的優(yōu)缺點(diǎn)七、牛頓迭代法的優(yōu)缺點(diǎn)1、優(yōu)點(diǎn)：牛頓迭代法具有平方收斂的速度，所以在迭代過程中只要迭代幾次就會(huì)得到很精確的解。這是牛頓迭代法比簡單迭代法優(yōu)越的地方。2、缺點(diǎn)：選定的初值要接近方程的解，否則有可能的不到收斂的結(jié)果。再者，牛頓迭代法計(jì)算量比較大。因每次迭代除計(jì)算函數(shù)值外還要計(jì)算微商值。2022-2-224迭代法的一般概念 迭代法可分為單點(diǎn)迭代法單點(diǎn)迭代法與多點(diǎn)迭代法多點(diǎn)迭代法。

16、 單點(diǎn)迭代法的一般形式單點(diǎn)迭代法的一般形式為： x xi i+1+1= = (x(xi i) ) i=0,1,2,需一個(gè)初始點(diǎn) x0啟動(dòng) 多點(diǎn)迭代法的一般形式多點(diǎn)迭代法的一般形式為： x xi i+1+1= = (x(xi i，x xi i-1-1, ,x,xi i-k+1-k+1) ) 需多個(gè)初始點(diǎn) x0 ，x1, x2 ,xk啟動(dòng)2022-2-225 求方程 x3+x=2x2+3 在x0=4 附近的根。解：函數(shù)(x)=x3-2x2+x-3寫成嵌套形式 (x)=x3-2x2+x-3=(x-2)x+1)x-3, (x)=3x2-4x+1=(3x-4)x+1用Newton迭代公式計(jì)算結(jié)果如下： N X N X 0 4.0000000000