一元方程的不動(dòng)點(diǎn)迭代法

1、第六章非線性方程組的迭代解法 6.2 一元方程的不動(dòng)點(diǎn)迭代法一元方程的不動(dòng)點(diǎn)迭代法6.2.2 局部收斂性和加速收斂法局部收斂性和加速收斂法6.2.1 不動(dòng)點(diǎn)迭代法及其收斂性不動(dòng)點(diǎn)迭代法及其收斂性第六章非線性方程組的迭代解法 6.2.1 不動(dòng)點(diǎn)迭代法及其收斂性不動(dòng)點(diǎn)迭代法及其收斂性非線性方程是連續(xù)的，為了求一元設(shè)一元函數(shù))(xf0)(xf（6.2.1）的實(shí)根，先將它轉(zhuǎn)化成等價(jià)形式的實(shí)根，先將它轉(zhuǎn)化成等價(jià)形式),(kxx（6.2.2）構(gòu)造迭代公式是一個(gè)連續(xù)函數(shù)。然后其中)(x。,.1 ,0),(1kxxkk（6.2.3）第六章非線性方程組的迭代解法 ）的根。也是方程（按等價(jià)性，），從而滿(mǎn)足方程（既

2、則有有極限，若由此迭代生成的序列對(duì)于給定的初值1 . 2 . 62 . 2 . 6),(,lim,*0 xxxxxxxxkkk,)(3 . 2 . 6稱(chēng)為迭代函數(shù)）稱(chēng)為基本迭代法，迭代式（x單步法。決定，因此，這是一種僅由迭代過(guò)程中，。）也稱(chēng)為不動(dòng)點(diǎn)迭代法的不動(dòng)點(diǎn)，式（稱(chēng)為kkxxxx1*3 . 2 . 6)(第六章非線性方程組的迭代解法 把（6.2.1）轉(zhuǎn)換成等價(jià)形式（6.2.2）的方法很多，迭代函數(shù)的不同選擇對(duì)應(yīng)不同的迭代法，它們的收斂性可能有很大的差異。當(dāng)方程有多個(gè)解時(shí)，同一迭代法的不同初值，也可能收斂到不同的根。舉例說(shuō)明如下。第六章非線性方程組的迭代解法 的一個(gè)實(shí)根。求01)(3xxx

3、f例6.2解解 轉(zhuǎn)換成兩種等價(jià)形式把0)(xf, 1)(, 1)(3231xxxxxx對(duì)應(yīng)的迭代法分別為對(duì)應(yīng)的迭代法分別為。,.1 , 0, 1, 13131kxxxxkkk。斂，第二個(gè)迭代法發(fā)散。顯然第一個(gè)迭代法收。此方程有唯一實(shí)根迭代結(jié)果列于表點(diǎn)為初值，既令為有根區(qū)間。取它的中，從而內(nèi)變號(hào)，在區(qū)間既連續(xù)函數(shù)由于57244753247179. 126, 5 . 121 21 )(, 5)2(, 1) 1 (*0 xxxfff第六章非線性方程組的迭代解法 表表 6-2012111.51.51.357208812.375000001.3308609612.39648441.32471796113

4、3kkxxk例例 6.3的根。求02)(2 xxf解解轉(zhuǎn)換成等價(jià)形式把0)(xf),2(21)(xxxx第六章非線性方程組的迭代解法 對(duì)應(yīng)的迭代法為。,.1 , 0),2(211kxxxkkk所示。果如表計(jì)算結(jié)迭代結(jié)果分別收斂到取初值36,2, 1*0 xx表表6-311.41421356-1.414213561.41421356-1.414213561.41421569-1.414215691.416666671.416666671.5-1.51-154320kkxxk第六章非線性方程組的迭代解法 上連續(xù)，并且滿(mǎn)足在閉區(qū)間設(shè)函數(shù),)(bax定理定理6.1 ;,)(,) 1 (baxbax，有

5、對(duì)任意有。使對(duì)任意存在正數(shù), 1)2(bayxL。yxLyx)()(6.2.4)函數(shù)的收斂性質(zhì)取決于迭代由此可見(jiàn)，基本迭代法基本定理。的收斂性法的選取。下面給出迭代和初值)3 . 2 . 6()(0 xx第六章非線性方程組的迭代解法 則對(duì)方程（則對(duì)方程（6.2.2）有）有。上存在唯一的不動(dòng)點(diǎn)在閉區(qū)間函數(shù)*,)() 1 (xbax）生成的序列由迭代法（對(duì)于任何初值3 . 2 . 6,)2(0bax 。收斂到不動(dòng)點(diǎn)*xxk有誤差估計(jì)式) 3(。1*1kkkxxLLxx（6.2.5）證證 )(, 0)(,)()()(babaxxxx知，則由令則有上有兩個(gè)相異的不動(dòng)點(diǎn)在。若上有不動(dòng)點(diǎn)在上有零點(diǎn)，既是連

6、續(xù)函數(shù)，故它在。因?yàn)?)(,)(,)(0*2*1*xxbaxxbaxbax第六章非線性方程組的迭代解法 進(jìn)而顯然有,.,1 , 0,kbaxk。*0*1*1*)()(xxLxxLxxxxkkkk。既從而*lim, 0limxxxkkk顯然有，111)()(kkkkkkxxLxxxx上只有一個(gè)不動(dòng)點(diǎn)。在這是個(gè)矛盾式子，因此,)(bax*12121212()(),xxxxL xxxx第六章非線性方程組的迭代解法 ,p進(jìn)而 對(duì)任意的正整數(shù) ，同理可得kkkkpkpkkpkxxxxxxxx1121。kkpxxLL11) 1(,1)1 (10101pkkLLLLL，從而因?yàn)椤?1111kkkkkpkxx

7、LLxxLxx定理得證。由收斂性既得令),5 . 2 . 6(,p第六章非線性方程組的迭代解法 中的）內(nèi)可導(dǎo)，那么定理在區(qū)間（如果函數(shù)1 . 6,)(bax）可用更強(qiáng)的條件條件（2),(, 1)( baxLx（6.2.6）理，對(duì)任何成立，則由微分中值定代替。事實(shí)上，若上式都有,bayx),()( )()(yxLyxyx）成立。之間，從而條件（與在其中4 . 2 . 6yx第六章非線性方程組的迭代解法 由估計(jì)式（由估計(jì)式（6.2.5）可知，只要相鄰兩次計(jì)算結(jié)果的偏差）可知，只要相鄰兩次計(jì)算結(jié)果的偏差 足夠小，且足夠小，且 不很接近不很接近1，既可保證近似值，既可保證近似值 具有足夠的精度。因具有

8、足夠的精度。因 此，可以通過(guò)檢查此，可以通過(guò)檢查 的大小來(lái)判斷迭代過(guò)程是否終止。并的大小來(lái)判斷迭代過(guò)程是否終止。并 且，由（且，由（6.2.5）有）有1kkxx1kkxxkxL。01*1xxLLxxKk（6.2.7）的次數(shù)。的精度確定出需要迭代），我們可對(duì)給定的值，則由（如果能恰當(dāng)計(jì)算出7 . 2 . 6L)(,)(*xyxyxx 與曲線在幾何上是直線的不動(dòng)點(diǎn)函數(shù)是發(fā)散的情形。圖）是收斂的情形其中圖（所示，的幾何解釋如圖，定理的交點(diǎn)的橫坐標(biāo)。因此)(,262 . 6ba第六章非線性方程組的迭代解法 4 . 6例們的收斂性。的兩種迭代法，討論它對(duì)于例 2 . 6解。其導(dǎo)數(shù)對(duì)于迭代函數(shù)32131)

9、 1(31)(, 1)(xxxxa1x*x0 xabybxxy )(xy)(a1x*x0 xabybxxy )(xy)(b26 圖aa第六章非線性方程組的迭代解法 有容易驗(yàn)證，對(duì)任意2 , 1 x。121. 0)(,2 , 1 45. 1 ,26. 1 )(11xx。上的唯一不動(dòng)點(diǎn)，都收斂到區(qū)間給出的迭代法由因此，對(duì)于任何初值*1021 )(,2 , 1 xxx。顯然，其導(dǎo)數(shù)對(duì)于迭代函數(shù)22323)(, 1)(xxxx該迭代法發(fā)散。要初值從幾何上可以說(shuō)明，只的條件。不滿(mǎn)足定理，有對(duì),1 . 6, 1)(70)(2 , 1 *022xxxxx 有時(shí)，對(duì)于一些不滿(mǎn)足定理有時(shí)，對(duì)于一些不滿(mǎn)足定理6.

10、1的條件問(wèn)題，可以的條件問(wèn)題，可以通過(guò)轉(zhuǎn)化，化為適合于迭代的形式。這要針對(duì)具體情通過(guò)轉(zhuǎn)化，化為適合于迭代的形式。這要針對(duì)具體情況進(jìn)行討論況進(jìn)行討論。第六章非線性方程組的迭代解法 5 .6例試問(wèn)如何滿(mǎn)足的已知, 13)( )( )(xxxx代函數(shù)？構(gòu)造一個(gè)收斂的簡(jiǎn)單迭利用)(x解，可得由)(xx,3)(3xxxx即可得等價(jià)方程。)(3(21xxx因此，令)(3(21)(xxx則有,21)( 321)(xx)(1kkxx因此，迭代式收斂。), 1 , 0(k第六章非線性方程組的迭代解法 6.2.2 局部收斂性和加速收斂法局部收斂性和加速收斂法上的收討論的是迭代法在區(qū)間由于定理,16. ba，給出如

11、下定義。近的收斂性問(wèn)題。為此附根檢驗(yàn)。所以常常討論在全局收斂性的情形不易說(shuō)來(lái)，上收斂的情形。但一般斂性也包括在無(wú)窮區(qū)間局收為全局收斂性定理。全斂性，因而，可以稱(chēng)之*x6.1定義的一個(gè)鄰域的不動(dòng)點(diǎn)，若存在是設(shè)*)(xxx 收斂的。）是局部，則稱(chēng)迭代法（且收斂到）生成的序列滿(mǎn)足），有迭代法（，（使得對(duì)任何初值3 .2 .6),(3 .6.2, 0,),(*0*xxsxxsxxxxsk第六章非線性方程組的迭代解法 定理定理 6.2的某個(gè)鄰域在的一個(gè)不動(dòng)點(diǎn)，是設(shè)*)( )(xxxx）局部收斂。則迭代法（上連續(xù)，并且有3 . 2 . 6, 1)( *x證所以存在處連續(xù)，且在因?yàn)? 1)( )( *xxx

12、并且有在其上的一個(gè)閉鄰域, 1)( ,*Lxxxx,)()()(*xxLxxxx 收斂。定理得證。）迭代法（，對(duì)任意根據(jù)定理。，有即對(duì)一切3 . 2 . 6,1 . 6,*0*xxxxxxxxx上述定理稱(chēng)為局部收斂定理，它給出了局部收斂的一個(gè)上述定理稱(chēng)為局部收斂定理，它給出了局部收斂的一個(gè)第六章非線性方程組的迭代解法 充分條件。當(dāng)?shù)諗繒r(shí)，收斂的快慢用下述收斂階段來(lái)充分條件。當(dāng)?shù)諗繒r(shí)，收斂的快慢用下述收斂階段來(lái)衡量。衡量。若存記誤差收斂到設(shè)序列*,xxexxkkk定義定義6.2，使得和在實(shí)數(shù)01cpceepkkk1lim（6.2.8）方收斂。時(shí)，稱(chēng)為平當(dāng)時(shí)，稱(chēng)為超線性收斂。斂。當(dāng)時(shí)，稱(chēng)為

13、線性收階收斂的，當(dāng)是則稱(chēng)序列211ppppxk階無(wú)窮小量的是時(shí)，）表明，當(dāng)式（peekkk 18 . 2 . 6。）中的常數(shù)滿(mǎn)足（是線性收斂的，越大，收斂越快。如果因此，階數(shù)108 .2 .6 cp則滿(mǎn)足即中，還有如果在定理, 1)( 0)( , 0)( 2 . 6*xxx第六章非線性方程組的迭代解法 對(duì)對(duì) ，必有，必有 ,k=1,2,，而且，而且*0 xx*xxkkkkkkexxxxe)()()(*11其中在其中在 與與 之間。于是之間。于是k*x。0)()(limlim*1xeekkkkk 從而，在這種情況下，從而，在這種情況下，x k 是線性收斂的。可見(jiàn)，提高收斂是線性收斂的?？梢?jiàn)，提高

14、收斂階的一個(gè)途徑是選擇迭代函數(shù)階的一個(gè)途徑是選擇迭代函數(shù) ，使它足，使它足 。下。下面給出整數(shù)階超線形收斂的一個(gè)充分條件。面給出整數(shù)階超線形收斂的一個(gè)充分條件。)(x0)(*x定理定理6.3 設(shè)設(shè) 是是 的一個(gè)不動(dòng)點(diǎn)，若有正整數(shù)的一個(gè)不動(dòng)點(diǎn)，若有正整數(shù)p 2,使得使得 在在 的領(lǐng)域上連續(xù)，并且滿(mǎn)足的領(lǐng)域上連續(xù)，并且滿(mǎn)足*x)(x)(xp*x, 0*)(, 0)()()()(*) 1(* *xxxxpp第六章非線性方程組的迭代解法 則由迭代法生成的序列在的領(lǐng)域是則由迭代法生成的序列在的領(lǐng)域是p階收斂的，且有階收斂的，且有!)(*)(1limpxeepkkk證證 因因 ，由定理，由定理6.2知迭代

15、法知迭代法(6.2.3)是局部收斂的。是局部收斂的。取充分接近取充分接近 的的 , 設(shè)設(shè) 有有 ， k=1,2,。由。由Taylor展開(kāi)式有展開(kāi)式有0)(*x*x0 x*0 xx*xxk,)(!)()()!1()()()()(*)(1*1*1pkkppkpkkkxxpxxpxxxxxxx其中其中 在在 與與 之間。由之間。由(6.2.9)有有kxk*x第六章非線性方程組的迭代解法 ).(!(*1)(*1xxpxxkkpk由由 的連續(xù)性可得的連續(xù)性可得(6.2.10)。定理得證。定理得證。)(xp 對(duì)于線形收斂的迭代法，常常收斂的很慢，所以要在這些對(duì)于線形收斂的迭代法，常常收斂的很慢，所以要在這

16、些迭代法的基礎(chǔ)上考慮加速收斂的方法。迭代法的基礎(chǔ)上考慮加速收斂的方法。*,xxexxkkk滿(mǎn)足則迭代誤差線性收斂到設(shè).0*11limlimcxxxxeekkkkkk因此，當(dāng)因此，當(dāng)k充分大時(shí)有充分大時(shí)有,*1*2*1xxxxxxxxkkkk第六章非線性方程組的迭代解法 .2)(*122122kkkkkkxxxxxxx從中解出從中解出 得得*x所以，我們?cè)谟?jì)算了所以，我們?cè)谟?jì)算了 之后，之后， 可以用可以用上式右端作為的一個(gè)修正值。這樣，我們可將迭代法改造上式右端作為的一個(gè)修正值。這樣，我們可將迭代法改造成下述過(guò)程，稱(chēng)為成下述過(guò)程，稱(chēng)為Steffensen迭代法迭代法：21,kkkxxx和2kx

17、, 1 , 02)(),(),(21kxyzyzzxyzxykkkkkkkkkkk它的不動(dòng)點(diǎn)形式是, 1 ,0),1kxxkk（第六章非線性方程組的迭代解法 K 0 1 28 29Xk 0.5 0.606530660 0.567143282 0.567143295表表64其中的迭代函數(shù)為xxxxxxxxxxxxx)(2)()()(2)()()()22（例例6.6 求方程的根。求方程的根。 。01)(xxexf解解 此方程等價(jià)于此方程等價(jià)于 。由。由y=x和和 可以看出可以看出 ， 只有一個(gè)不動(dòng)點(diǎn)只有一個(gè)不動(dòng)點(diǎn)x*0,都有都有 ,所以迭代法所以迭代法 線性收斂。取初始值線性收斂。取初始值 =0.

18、5，迭代結(jié)果列于表，迭代結(jié)果列于表64。準(zhǔn)確解。準(zhǔn)確解是是=0.56714329040978，可見(jiàn)線性收斂的速度是很慢的。，可見(jiàn)線性收斂的速度是很慢的。 10 xexkxkex1)(x*xxexx)(xey0 x第六章非線性方程組的迭代解法 如果使用如果使用Steffensen迭代法，仍取初值迭代法，仍取初值x0=0.5.則則。,1 ,0,2)(,21,kxyzyzzxezeykkkkkkkykxkkk計(jì)算結(jié)果列于表計(jì)算結(jié)果列于表65。與表。與表64比較，可見(jiàn)比較，可見(jiàn)Steffensen迭代法比迭代法比原方法收斂快得多，僅迭代原方法收斂快得多，僅迭代4次就達(dá)到了原方法次就達(dá)到了原方法29次的

19、結(jié)果。次的結(jié)果。K 0 1 2 3 4 Xk 0.5 0.567623876 0.567143314 0.567143290 0.567143290表表65定理定理6.4 設(shè)函數(shù)按（設(shè)函數(shù)按（6.2.13）定義。）定義。第六章非線性方程組的迭代解法 （1）若）若x*是是 的不動(dòng)點(diǎn)，的不動(dòng)點(diǎn)， 在在x*處連續(xù)，且處連續(xù)，且 ，則，則x*也是的不動(dòng)點(diǎn)；反之，若也是的不動(dòng)點(diǎn)；反之，若x*是是 的不動(dòng)點(diǎn)，則的不動(dòng)點(diǎn)，則x*也是也是 的的 的不動(dòng)點(diǎn)。的不動(dòng)點(diǎn)。)x（)(x1)*x（)(x)x（ （2）若）若x*是是 的不動(dòng)點(diǎn)，的不動(dòng)點(diǎn)， 在在x*處連續(xù)，且處連續(xù)，且 ,則則Steffensen迭代法迭代

20、法(6.2.11）至少具有二階局部收斂性。）至少具有二階局部收斂性。1)*x（)(x)( x證證 （1）若）若x*= ，則當(dāng)，則當(dāng)x=x*時(shí)，（時(shí)，（6.2.13）式的分子）式的分子分母都為零。對(duì)它的極限用分母都為零。對(duì)它的極限用LHospitale法則，由法則，由于于 ，得知，得知)(*x1)(*x*2*2* 1)( 1)(1)(2)()()()(2)()()()(limlim*xxxxxxxxxxxxxxxxxx從而從而 。反之，若。反之，若 ，則由（，則由（6.2.13）得）得 知知 。)(*xx)(*xx)(*xx第六章非線性方程組的迭代解法 于是，由 對(duì)（6.2.14）的兩邊求極限，因?yàn)閤*至少是 p(x)和q(x)二重根，所以，使用兩次LHospitale法則得 。可知（0)()(, 1)*xqxpx)()()(1xqxpx 其中（2）由（1）可知x* 是 的不動(dòng)點(diǎn)，于是，由定理6.3，