數(shù)值分析迭代法

1、1第二節(jié)第二節(jié) 迭代法迭代法2 2009, Henan Polytechnic University2 它是一種逐次逼近的方法它是一種逐次逼近的方法, ,用某個固定公式反用某個固定公式反復(fù)校正根的近似值復(fù)校正根的近似值, ,使之逐步精確化，最后得到滿足使之逐步精確化，最后得到滿足精度要求的結(jié)果。精度要求的結(jié)果。3 2009, Henan Polytechnic University36.2.1 迭代法的基本思想迭代法的基本思想 為求解非線性方程為求解非線性方程f(x)=0的根，先將其寫成便于的根，先將其寫成便于迭代的等價方程迭代的等價方程)(x )(xx 其中其中 為為x的連續(xù)函數(shù)的連續(xù)函數(shù)。

2、4 2009, Henan Polytechnic University4 即如果數(shù)即如果數(shù) 使使 f(x)=0, , 0 x)(xx )(01xx 任取一個初值任取一個初值 , ,代入式代入式 的的右端右端, , 得到得到則也有則也有反之反之, , 若若 ,則也有則也有再將再將 代入式代入式 的右端的右端, , 1x)(xx 得到得到 )(12xx 0)( f)( )( 5 2009, Henan Polytechnic University5),(),(3423xxxx 上式稱為求解非線性方程的簡單迭代公式上式稱為求解非線性方程的簡單迭代公式, , 依此類推依此類推, , 得到一個數(shù)列得到

3、一個數(shù)列其一般表示其一般表示 )(x 稱稱 為迭代函數(shù)為迭代函數(shù) 。), 2 , 1 , 0(),(1 nxxnn 6 2009, Henan Polytechnic University6 例例1 1 試用迭代法求方程試用迭代法求方程 在區(qū)間在區(qū)間(1，2)內(nèi)的實(shí)根。內(nèi)的實(shí)根。31 xx01)(3 xxxf311 kkxx解：由解：由 建立迭代關(guān)系建立迭代關(guān)系計算結(jié)果如下計算結(jié)果如下: :k=0,1,2,3.7 2009, Henan Polytechnic University7精確到小數(shù)點(diǎn)后五位精確到小數(shù)點(diǎn)后五位kk01.551.3247611.3572161.3247321.33086

4、71.3247231.3258881.3247241.324945102132472. 1 xkxkx8 2009, Henan Polytechnic University8但如果由但如果由 建立迭代公式建立迭代公式13 xx,.2 , 1131 kxxkk 5 . 10 x 2.3751 x 12.392 x kx仍取仍取 ，則有，則有顯然結(jié)果越來越大，顯然結(jié)果越來越大， 是發(fā)散序列是發(fā)散序列9 2009, Henan Polytechnic University9（全局收斂定理）（全局收斂定理）,)(bax 在在設(shè)設(shè) 為為常常數(shù)數(shù)）LLxbax(1| )( |,)2( 0111011|3

5、(,)2( ,)()1(xxLLxxLLxxxbaxbaxxnnnnnn ）（）收收斂斂到到；有有唯唯一一根根在在方方程程則則：;)(1bxabxa 時時，）當(dāng)當(dāng)（6.2.2 收斂性分析收斂性分析10 2009, Henan Polytechnic University10存在唯一性存在唯一性做輔助函數(shù)做輔助函數(shù))()(xxx ，則有，則有0)(, 0)( ba 所以，存在點(diǎn)所以，存在點(diǎn)*)(*0*)(.,.*,xxxtsx 若若*)*(*xx ，則有：則有：*xx 又，又，1 L*xx *)*(*)(xx *)*)( xx *xxL 11 2009, Henan Polytechnic Un

6、iversity11,0bax 則則*1xxk *1xxk 所以，任意的初值都收斂所以，任意的初值都收斂*)()(xxk *)( xxk *12xxLk *xxLk *01xxLk 12 2009, Henan Polytechnic University12誤差估計誤差估計nnxx 1)()(1 nnxx 212 nnxxL1 nnxxL01xxLn nnxx 1)()(1 nnxx 1nnxx nnxLx nxL)1(13 2009, Henan Polytechnic University13nnnxxLx 111 注：注：L越小，收斂越快。越小，收斂越快。11 nnxxLL011xxL

7、Ln 14 2009, Henan Polytechnic University14例例2 2 證明函數(shù)證明函數(shù) 在區(qū)間在區(qū)間11，22上滿足迭代收斂條件。上滿足迭代收斂條件。31)( xx 上上嚴(yán)嚴(yán)格格單單調(diào)調(diào)增增函函數(shù)數(shù)。是是區(qū)區(qū)間間所所以以因因?yàn)闉?)(2 , 1 0)1(31)(32baxxxx 證明：證明：15 2009, Henan Polytechnic University15 2 , 11431|)1(31| )(|332 xLxx 又又23)2(12)1(33 ，而而）。滿滿足足條條件件（，所所以以即即1)(2 , 1)2(),1(x ）。滿滿足足條條件件（所所以以2)(x

8、 滿滿足足收收斂斂條條件件。在在故故2 , 11)x(3 x 16 2009, Henan Polytechnic University16若取迭代函數(shù)若取迭代函數(shù) 不滿足定理，故不能肯定不滿足定理，故不能肯定 收斂到方程的根。收斂到方程的根。 1)x(3 x 2 , 13|3| )(|2 xxx 因?yàn)橐驗(yàn)?.1 , 0)(1 nxxnn 17 2009, Henan Polytechnic University17 定理定理 設(shè)設(shè) 是方程是方程 的根，如果滿足的根，如果滿足條件條件 ：（1 1）迭代函數(shù)）迭代函數(shù) 在在 的鄰域可導(dǎo)；的鄰域可導(dǎo)；（2 2）在）在 的某個鄰域的某個鄰域 ，對于任

9、，對于任意意 ，有，有 )(xx 局部收斂性局部收斂性 )(x Sx xxS1)( Lx 18 2009, Henan Polytechnic University18 則對于任意的初始值則對于任意的初始值 ，由迭代公式，由迭代公式 產(chǎn)生的數(shù)列產(chǎn)生的數(shù)列 收斂于方程的根。收斂于方程的根。（這時稱迭代法在（這時稱迭代法在 的的S S鄰域具有局部收斂性。）鄰域具有局部收斂性。） nx)(1nnxx Sx 0 19 2009, Henan Polytechnic University19例例3 3 設(shè)設(shè) ，要使迭代過程，要使迭代過程 局部收斂到局部收斂到 , ,求求 的取值范圍。的取值范圍。解：解：

10、 由在根由在根 鄰域具有局部收斂性時，鄰域具有局部收斂性時， 收斂條件收斂條件 )5()(2 xaxx )(1kkxx 5* xa)5()(2 xaxx axx21)( 5* x20 2009, Henan Polytechnic University201521)(* ax 15211 a0522 a所以所以 051 a21 2009, Henan Polytechnic University21 實(shí)際計算中當(dāng)然不可能也沒必要無窮多步地做實(shí)際計算中當(dāng)然不可能也沒必要無窮多步地做下去下去, , 對預(yù)先給定的精度要求對預(yù)先給定的精度要求，只要某個，只要某個n滿足滿足即可結(jié)束計算并取即可結(jié)束計算并

11、取 當(dāng)然，迭代函數(shù)當(dāng)然，迭代函數(shù) 的構(gòu)造方法是多種多樣的。的構(gòu)造方法是多種多樣的。)( x 1nnxxnx 22 2009, Henan Polytechnic University22xyy = xx*y=g(x)x0p0 x1p1 xyy = xx*y=g(x)x0p0 x1p1簡單迭代收斂情況的幾何解釋簡單迭代收斂情況的幾何解釋23 2009, Henan Polytechnic University23定義定義 設(shè)迭代過程設(shè)迭代過程 收斂于收斂于 的的根根 , ,記迭代誤差記迭代誤差若存在常數(shù)若存在常數(shù)p（p1）和和c（c0），），使使 )(1kkxx )(xx *xkkxxe *ce

12、epkkk 1lim則稱序列則稱序列 是是 p 階收斂的階收斂的, ,c稱漸近誤差常數(shù)。特別稱漸近誤差常數(shù)。特別地地, ,p=1時稱為線性收斂時稱為線性收斂, ,p=2時稱為平方收斂。時稱為平方收斂。1 p 2時稱為超線性收斂。時稱為超線性收斂。 kx6.2.3 迭代法的收斂速度迭代法的收斂速度24 2009, Henan Polytechnic University24 數(shù)數(shù)p的大小反映了迭代法收斂的速度的慢，的大小反映了迭代法收斂的速度的慢，p愈大，則收斂的速度愈快，故迭代法的收斂階是愈大，則收斂的速度愈快，故迭代法的收斂階是對迭代法收斂速度的一種度量。對迭代法收斂速度的一種度量。 25

13、2009, Henan Polytechnic University25定理定理 設(shè)迭代過程設(shè)迭代過程 , ,若若 在所求根在所求根 的鄰域連續(xù)且的鄰域連續(xù)且 則迭代過程在則迭代過程在 鄰域是鄰域是p階收斂的。階收斂的。)(1kkxx )()(xp *x0)(, 0)()()(*)(*)1(* xxxxpp *x0)(* x *x1)(* x )(1kkxx )(kx *x證證: : 由于由于所以所以 有局部收斂性有局部收斂性, , 將將 在在 處處泰勒展開泰勒展開即在即在 鄰域鄰域 , ,26 2009, Henan Polytechnic University26pkpkkkxxpxxxx

14、xxxx)(!1)(! 21)()()(*)(2* 根據(jù)已知條件得根據(jù)已知條件得 pkpkxxpxx)(!1)()(*)(* 由迭代公式由迭代公式 )(1kkxx 及及)(*xx 有有pkpkxxpxx)(!)(*)(*1 0!)(lim*)(1 pxeeppkkk 27 2009, Henan Polytechnic University27例例4 4 已知迭代公式已知迭代公式 收斂于收斂于證明該迭代公式平方收斂。證明該迭代公式平方收斂。21132kkkxxx 3*3 x2132)(xxx 436)(232)(xxxx ，證證: : 迭代公式相應(yīng)的迭代函數(shù)為迭代公式相應(yīng)的迭代函數(shù)為將將 代入

15、，代入，根據(jù)定理可知，迭代公式平方收斂。根據(jù)定理可知，迭代公式平方收斂。3*3 x032336)(0)(33* xx ，28 2009, Henan Polytechnic University28為了使迭代過程收斂或提高收斂的速度為了使迭代過程收斂或提高收斂的速度, , 可設(shè)法可設(shè)法 提高初值的精度以減少迭代的次數(shù)提高初值的精度以減少迭代的次數(shù) 提高收斂的階數(shù)提高收斂的階數(shù) p29 2009, Henan Polytechnic University29（1 1）迭代）迭代- -加速公式（加權(quán)法）加速公式（加權(quán)法）設(shè)設(shè) 是根是根 的某個近似值的某個近似值, ,用迭代公式校正一次得用迭代公式校

16、正一次得 kx*x)(1kkxx )(*xx )()()(*1*kkkxxxxxx ),(*kxx 6.2.4 迭代過程的加速迭代過程的加速又又根據(jù)中值定理有根據(jù)中值定理有30 2009, Henan Polytechnic University30可見可見, ,若將迭代值若將迭代值 與與 加權(quán)平均加權(quán)平均, ,則可得到的則可得到的 1 kxkxkkkxLLxLx 11111是比是比 更好的近似根更好的近似根1 kx)(*1*kkxxLxx kkxLLxLx 1111*則有：則有：當(dāng)當(dāng) 范圍不大時范圍不大時, ,設(shè)設(shè) 變化不大變化不大, ,其估計值為其估計值為L L )(*kxx )( 31

17、2009, Henan Polytechnic University31迭代：迭代： 改進(jìn)：改進(jìn)： 或合并寫成：或合并寫成： )(1_kkxx kkkxLLxLx 1111_1 kkkLxxLx )(111 32 2009, Henan Polytechnic University32例例5 5 用加權(quán)法加速技術(shù)求方程用加權(quán)法加速技術(shù)求方程 在在0.50.5附近的一個根。附近的一個根。xex 5 . 00 x 6 . 05 . 05 . 05 . 0 eexx 取取L=-0.6=-0.6，建立如下迭代公式建立如下迭代公式解：解： 因?yàn)樵谝驗(yàn)樵?附近附近33 2009, Henan Polyte

18、chnic University33仍取仍取 , ,逐次計算得逐次計算得 =0.56658 =0.56714 。迭代迭代4 4次便可得到精度次便可得到精度 的的結(jié)果結(jié)果, ,而不用加速技術(shù)需迭代而不用加速技術(shù)需迭代1818次次, ,效果顯著。效果顯著。 5 . 00 x1x4x410 kxkxkxexexkk6 . 06 . 116 . 0)6 . 0(111 34 2009, Henan Polytechnic University34（2 2）埃特金）埃特金（Aitken）方法方法 在加權(quán)法中在加權(quán)法中, , 估計估計L L的值有時不太方便。假的值有時不太方便。假設(shè)在求得設(shè)在求得 以后以后, , 先求出先求出kx)(1kkxx )(*xx )()()(*1xxLxxxxkkk 由由 利用中值定理可得利用中值定理可得( ( 在求根區(qū)間變化不大在求根區(qū)間變化不大,