求解非線性方程的迭代算法研究.doc

陜西理工學(xué)院畢業(yè)論文 第 1 頁 共 18 頁 求解非線性方程的迭代算法研究求解非線性方程的迭代算法研究 XXXX （XXXX 學(xué)院學(xué)院 XXXX 專業(yè)專業(yè) XXXX 班班, ,陜西陜西 XXXX 72X00072X000） 指導(dǎo)教師指導(dǎo)教師:XX:XX 摘要 在利用數(shù)學(xué)工具研究社會現(xiàn)象和自然現(xiàn)象，或解決工程技術(shù)等問題時，很多問題都可以歸結(jié)為非線性 方程的求解問題，無論在理論研究方面還是在實際應(yīng)用中，求解非線性方程都占了非常重要的地位.( )0f x 迭代法是求解非線性方程根的一種最重要的方法，而迭代法的優(yōu)劣對于非線性問題求解速度的快慢( )0f x 和結(jié)果的好壞都有很大的影響，所以從實際出發(fā)，進行高計算效能迭代算法的研究具有重要的科學(xué)價值和實際 意義. 關(guān)鍵詞 牛頓法;迭代法;非線性方程;收斂的階; 陜西理工學(xué)院畢業(yè)論文 第 2 頁 共 18 頁 目錄目錄 1 引言引言.3 2 基礎(chǔ)知識基礎(chǔ)知識 .4 3 NEWTON 迭代法迭代法.5 3.1NEWTON迭代法的推導(dǎo).5 3.2NEWTON迭代法的收斂.7 4 其它迭代格式和變形的牛頓法其它迭代格式和變形的牛頓法.10 4.1 其它的迭代的格式.10 4.2 變形的牛頓法.11 結(jié)束語結(jié)束語.錯誤！未定義書簽。 參考文獻參考文獻 .13 ZUODIAN .14 TUTOR: QUANSHUANGYAN.14 陜西理工學(xué)院畢業(yè)論文 第 3 頁 共 18 頁 1 引言引言 近幾十年來，數(shù)值工作者們不斷在原有的迭代法基礎(chǔ)上的提出一些新的迭代格式，事實上這些 新方法大多是根據(jù)實際情況的需要對經(jīng)典的迭代格式進行修正和變形，因此Newton法等一系列經(jīng)典 的迭代法就成為我們討論新的迭代方法的起點.數(shù)學(xué)家們對這些方法都做了很深入的研究，關(guān)于這 方面的文章著作也是數(shù)不勝數(shù)，其中有非常豐富的理論結(jié)果和證明技巧是可以借鑒的.最基本的迭 代法，自然對我們的討論也是最核心的，所以在就來重點討論Newton迭代法. 陜西理工學(xué)院畢業(yè)論文 第 4 頁 共 18 頁 2 基礎(chǔ)知識基礎(chǔ)知識 非線性方程，就是因變量與自變量之間的關(guān)系不是線性的關(guān)系，這類方程很多，例如平方關(guān)系、 對數(shù)關(guān)系、指數(shù)關(guān)系、三角函數(shù)關(guān)系等等.求解此類方程往往很難得到精確解，經(jīng)常需要求近似解 問題. 在利用數(shù)學(xué)工具研究社會現(xiàn)象和自然現(xiàn)象，解決物理、化學(xué)、生物、工程技術(shù)，甚至社會經(jīng)濟 等實際問題時，往往都可以歸結(jié)為求解某個非線性方程 (11)( )0f x 的根的問題.就方程(11)的形式而言，可能是次多項式：( )F xn 1110 0 nnnn a xaxa xa 也可能是由多種函數(shù)組成的非線性方程.譬如：在人口增長模型中假設(shè)某一地區(qū)人口的數(shù)量隨時間 連續(xù)增長，即 ( ) ( ) dN t N t dt ，其中N(t)表示該地區(qū)在t時刻的人口總數(shù)，為人口增長率常數(shù).該 微分方程的解為 0( ) t N tN e ，其中N0為該地區(qū)的初始人口總數(shù).但上述模型沒有考慮到外部移民 的遷入的情況，若允許移民以某常速率u進入該地區(qū)，則微分方程是 ( ) ( ) dN t N tv dt 其解為： 0( )(1) tt v N tN ee 現(xiàn)假設(shè)某地區(qū)有100萬人口，第一年內(nèi)有435萬移民遷入，第一年末總計人口1564萬.根據(jù) 上述數(shù)據(jù)可以推算出該地區(qū)的增長率常數(shù)滿足方程：、 43.5 156.4100(1) tt ee 上面這個微分方程的解析解比較容易求出，所以求解這類問題就可轉(zhuǎn)化為求解非線性方程的問 題. 談到解非線性方程，就不得不提迭代法，它是最有效最便利的求解方法.迭代法就是從預(yù)知的 解的初始近似值(簡稱初值)開始，采用某種迭代格式構(gòu)造一近似值序列 0121 , kk x x xxx 逐步逼近于所求方程的真解. 對方程(11)求近似根，先將其改寫成等價的方程： ( )xf x (12) 所謂等價就是：如果是方程(11)的根，那么 * ()xf x ；反之如果滿足方程(12)， * x * x 陜西理工學(xué)院畢業(yè)論文 第 5 頁 共 18 頁 那么.最簡單的等價變換是令，當然還可以根據(jù)的特點來變換.( )0f x ( )( )f xxF x( )F x 稱為迭代函數(shù)，為函數(shù)的一個不動點，求的零點就等價于求的不動點.選( )f x * x( )f x( )F x( )f x 擇一個初始近似值，將它代入(1.2)式右端，即可求得 0 x 0 ()xf x 可以如此反復(fù)迭代計算 (13) 1 (),0,1,2,3 kk xf xk 如果得到的序列有極限 k x * lim k k xx 則迭代方程(13)收斂，我們稱(13)為不動點迭代法.不動點迭代法是最簡單的迭代法，它是一 種逐次逼近的方法.其基本思想是將隱式方程(12)歸結(jié)為一組顯示的計算公式(13)，就是說迭 代過程實質(zhì)上是一個逐步顯示化的過程. 但是迭代序列能否作為方程的根的好的近似，或者能否收斂于，以及能否快速的收斂 k x * x * x 到呢?這些都是我們后面所要探討的問題.對于一種解法，為了考察它的有效性，一般都要討論 * x 它的收斂性和收斂速度，即考慮在什么樣的條件下構(gòu)造的序列是收斂的，以及序列中的近似值是按 什么樣的誤差下降速度來逼近真解的.迭代過程的收斂條件，一般與方程的性態(tài)(函數(shù)在解附( )F x 近的性質(zhì)，零點的分布狀態(tài)等)以及初值的近似度有關(guān)，而某些方法僅與初值的近似度有關(guān)，故有 時也稱收斂條件為收斂范圍.迭代過程的收斂速度，是指在接近收斂過程中近似值誤差的下降速度. 一般來說，它主要由方法所決定，方程的性態(tài)也會有一些影響.如果由一種迭代解法構(gòu)造出來的近 似值序列與解的誤差為 123 , k x x xx * x * 1 * lim k r k k xx K xx 或者，當充分接近于解時有關(guān)系式 k x * x * 1 * r kk xxK xx 當r1時，稱該迭代法具有階的收斂速度.通常具有階收斂速度的算法，當接近收斂時其近似值 的誤差將按冪次為r的速度下降.因此越大，誤差就下降的越多，收斂速度就越高；越小，誤差 就下降的越少，收斂速度就越低. 陜西理工學(xué)院畢業(yè)論文 第 6 頁 共 18 頁 3 Newton 迭代法迭代法 3.1Newton 迭代法的推導(dǎo)迭代法的推導(dǎo) 對于求解非線性方程 (21)( )0f x 的零點問題，有很多種迭代方法,其中最為著名的就是Newton迭代法 (22)1 () () n nn n f x xx fx 這些迭代法是如何被取得的呢?事實上迭代法的推導(dǎo)方法也是多種多樣的.下面我們就以Newton迭代 法為例，介紹公式(22)的幾個導(dǎo)出途徑. 方法一方法一，作泰勒級數(shù)展開并取線性部分. 記 * x 是方程(21)的根 于是, *2 * () 0()()()()() 2 k kkkkk xx f xf xfxxxfxxx 將右邊的二次項去掉，即得 * ()()()0 kkk f xfxxx 令滿足 1k x / 1 ()()()0 kkkk f xfxxx ， 即得公式(22). 方法二方法二，重節(jié)點反插值. 可以把方程(21)的根看做函數(shù) ( )yf x 所表示的曲線與x軸的交點.函數(shù) ( )yf x 有反函數(shù) ( )xy ，求根 * x 即為求.在處有函數(shù)值，即 () kk xy .將在作重(0) k x() kk yf x(0) k y 節(jié)點插值，即得 2 (0)()()(0)(,0)(0) kkkkkk yyyyyy 由數(shù)學(xué)分析可知，則得()1/() kk yfx . *2 1 ()(,0) () () kkkkk k xxf xyyf x fx 令 陜西理工學(xué)院畢業(yè)論文 第 7 頁 共 18 頁 , 1 () () k kk k f x xx fx 此即為公式(22). 方法三方法三，為了求曲線與軸的交點，用過()處的切線與軸的交點來近似.( )yf xx , () kk x f xx 因為過的切線方程為 , () kk x f x ，()()() kkk yf xfxxx 它與軸的交點的橫坐標即為x . 1 () () k kk k f x xx fx 不同于以上三種傳統(tǒng)的推導(dǎo)方法，Weerakoon1和Fernando運用Newton-Leibniz公式和Newton- Cots求積公式又提出了一種新的導(dǎo)出Newton法的方法.對于Newton-Leibniz公式 ， (23)( )()( ) n x n x f xf xf t dt 可用零階Newton-Cots求積公式2(矩形公式) ( )()() n x nn x f t dtxxfx 來代替(2，3)式中的定積分，并且令，就可得到Newton公式.類似( )0f x 的，將定積分替換為一階Newton-Cots公式(梯形公式) () ( )()( ) 2 n x n n x xx f t dtfxfx 可得到一個隱格式的迭代法 . 1 1 2 () ()() n nn nn f x xx fxfx 為了把隱式變?yōu)轱@式,這里 * 1 () () n nn n f x xx fx 由此可以得到一個三階方法 1 2 () () ()() () n nn n nn n f x xx f x fxfx fx 顯然這兩種方法的不同之處就在于選擇的求積公式不同，所以得到了不同的收斂階. 后來，F(xiàn)rontini和Sormani又豐富了Weerakoon和Fernando的結(jié)果. 通常的插值型求積公式(高于零階)可以統(tǒng)一記為 ， (24) 1 , 0 ( )()() n m x nii n x i f t dtxxA f 陜西理工學(xué)院畢業(yè)論文 第 8 頁 共 18 頁 其中 , () i nnin xxx ，i=0，1，2，m-1，是區(qū)間0，1上的求積節(jié)點，是相應(yīng)的求積系 1 i i m i A 數(shù)且滿足條件.把(24)式中的換為，代入(23)中.假設(shè) 1 1 m i i A f / f 是的一個根，令，可得到( )f x,x (2.5) 1 * , 0 () () n nm ii n i f x x A f 其中 (26) * , () i nnin xx 顯然這是一個隱格式，那么用Newton迭代來代替上式中的就可 / () () n n n f x x fx 得到一個顯式方法 ， (2.7) 11 . 0 () () n nnm ii n i f x xx A f 這里 (28) , () () () n i nni n f x x fx 只要在(25)式中代入不同的求積公式，就可以得到不同格式的迭代法.顯然這族迭代法的形 式會隨著求積公式的變化而變化，計算代價也會隨之增加.但是已經(jīng)證明了由以上推導(dǎo)方法得出的 迭代法(除Newton法以外)的收斂階是獨立于求積公式的選擇的.換句話說，就是雖然選擇不同的求 積公式可以得到不同的迭代格式，但是這些迭代法的收斂階最高只能達到三階收斂.之所以收斂階 無法提高，我們發(fā)現(xiàn)是因為上面的方法在將隱格式轉(zhuǎn)化為顯式時，是用Newton迭代來代替.于是 我們嘗試使用斂階高于二階的迭代法代替，同時提高求積公式的代數(shù)精度，如此得到的迭代法的 收斂階就會隨之提高. 陜西理工學(xué)院畢業(yè)論文 第 9 頁 共 18 頁 3.2Newton 迭代法的收斂迭代法的收斂 到目前為止，已經(jīng)有很多不同的迭代方法被數(shù)值工作者們提出了.在Ortega和Rheinboldt中已 經(jīng)有了比較詳細的介紹.其中最經(jīng)典的就是二階收斂的Newton迭代法 1 () () n nn n F x xx F x (2.9) 眾所周知，Newton迭代法形式簡單，收斂速度也比較快，在具體計算中一直都是求解非線性方 程(2.9)最重要的迭代方法.數(shù)百年來，雖然新的迭代格式層出不窮，然而幾乎所有的迭代法的研究 都是以Newton迭代法的證明技巧和分析方法為基礎(chǔ)的.有關(guān)Newton迭代法的收斂性方面的研究是數(shù) 不勝數(shù)，其中有很多理論結(jié)果都被借鑒.無論是理論研究還是實際應(yīng)用，Newton迭代在迭代法的歷 史上所起的作用是其它任何迭代法所無法替代的. 關(guān)于Newton迭代法的研究情況已有很長的歷史.十九世紀初，Cauchy就在實數(shù)空間冗中對 Newton法的收斂性進行了初步的研究.但所給的條件涉及求解一階導(dǎo)數(shù)極小值之類的整體條件.1937 年，Ostrowski10在復(fù)數(shù)空間C中對Newton法的收斂性進行了深刻的研究.后來Kantorovich5成功 的給出了Banach空間內(nèi)Newton法的著名的Newton-Kantorovich收斂性定理，關(guān)于這方面的文獻4 和7他給出的收斂條件為： 1.設(shè)F是由Banach空間X的一個非空凸集到同型空間y的Frechet可微算子； 2.存在點 0 x ，假設(shè) 存在，且； 1 0 ()F x 1 00 |()()|FxF xa 3. 1 00|()()( )|F xF xF ybxy ， , x y ； 4. 1 2 ab ； 5. * ( 0,)B xt ，其中 * 11 2ab t b . Kantorovich關(guān)于Newton法收斂性的著名工作可以說是解方程算法現(xiàn)代研究的起點.后來有很多 數(shù)學(xué)家都對此定理進行了改進，他們主要是針對上述條件，給出了一些修正條件，來減弱 Kantorvich9條件.后來，Wang和Guo將這些收斂性和唯一性定理的條件加以了統(tǒng)一(該條件包括了 著名的經(jīng)典Kantorovich條件)，給出了方程(11)解的唯一性及Newton法的收斂性定理.前面列舉 的這些收斂性條件都是僅考慮了P7的Lipschitz條件.Huang指出F的二階的導(dǎo)數(shù)在收斂性條件中也是 有用的，同時彌補了Kantorvoich條件不能判斷從某個指定點出發(fā)的Newton迭代序列是否收斂.后來， Gutierrez，zhang分別又將此條件改進.此外Argyros在文獻中利用了F的高階導(dǎo)數(shù)信息，提出了 兩個收斂條件. Kantorovich關(guān)于Newton法的收斂性定理一直被視為收斂性分析思想的典范，它的特點是對F可 微性要求較弱，但需要F的某階導(dǎo)數(shù)的整體性態(tài).為此在1986年國際數(shù)學(xué)家大會的大報告上，Smale2用 尸的解析性條件取代了Kantorovich的整體性假設(shè)(即F的某些階導(dǎo)數(shù)在某個足夠大的區(qū)域中具有 Lipschitz連續(xù)的假定).完全只用F在初始點的信息來判斷Newton迭代方法的收斂性.這對連續(xù)復(fù)雜 性的研究是極為重要的.為了解脫對F的區(qū)域信息的依賴，Smale假設(shè)F在x解析(并且F在x的Taylor級 陜西理工學(xué)院畢業(yè)論文 第 10 頁 共 18 頁 數(shù)收斂球內(nèi)這種解析性不被人為破壞)，并且令 ( , )a F x : 其中 1 ( , ) |( )( )|F xF xF x 1 1 1 2 ( ) ( , )sup|( )| ! k k k Fx F xF x k Smale證明存在一個絕對常數(shù)，當 0( , )F x 時，從出發(fā)的Newton迭代(14)都有 0 0 xx 意義并且收斂.后來王興華3和韓丹夫4求得了的最好結(jié)果，即.不僅如此，王興華等 0 32 2 人還證明了是半局部行為下的普適常數(shù).這一結(jié)果揭示了關(guān)于零點數(shù)值過程在半局部行為32 2 上的統(tǒng)一性.有關(guān)Newton法的研究，除了上面所列，還有很多的學(xué)者作了大量的研究工作，并且積 累了很多的文獻. 證明迭代法的收斂性的一個很不錯的技巧是優(yōu)函數(shù)技術(shù)，這是Kantorovich為了證明Banach空 間內(nèi)的Newton迭代法的收斂性而提出來的.Kantorvich在中提出利用優(yōu)界函數(shù)原理的新證法，其思 想就是將一個高維迭代過程和另一個一維迭代過程進行比較，由一維過程的收斂性導(dǎo)出原過程的收 斂性.即立足于以下事實： 11|nnnnxxtt 1 010 0 | n njjn j xxxxtt ntN 收斂， nxN 是個Cauchy序列. 在證明的過程中，使用的優(yōu)函數(shù)主要有兩種：一種是代數(shù)多項式.Kantor-vich就是把二次多項 式 2 1 ( ) 2 h tbtt 作為優(yōu)函數(shù)來證明Newton迭代法的收斂性的.當然還可以根據(jù)不同情況使用更高次的代數(shù)多項 式，用代數(shù)多項式作優(yōu)函數(shù)的最大好處是可以得到精確的顯式誤差估計.另一種是有理多項式.最先 被Smale提出，其形式為 2 ( ) 1 t h tt t 此優(yōu)函數(shù)不僅可被用來證明各種迭代法在點估計判據(jù)下的收斂性，更重要的是，能夠在同等條件下 比較不同算法的效率. 除了優(yōu)函數(shù)方法，還有一種證明迭代序列收斂的技巧是遞歸法.對此Gutierrez6和Hernandez7等 人對Halley迭代，Chebyshev迭代，Super-Halley迭代，Jarratt型迭代的收斂性進行了一系列工作.在 早期的文章中，用到的是四個實序列，現(xiàn)在減少到兩個實序列，遞歸關(guān)系在不斷的簡化.不過無論 是優(yōu)函數(shù)方法還是遞歸法，它們實際上都是逐步歸納的方法.逐步歸納法的實質(zhì)就是使后面一步迭 代的逼近誤差小于前一步迭代的逼近誤差，在證明迭代過程的收斂性時，運用了每前進一步迭代都 不會破壞定理假設(shè)條件的技巧. 前面敘述了這么多，都只是理論方面的分析.那么如何具體使用迭代法來求解非線性方程呢?下面我 們就給出Newton迭代法求解方程的具體迭代步驟.以本蘋開頭列舉的非線性方程為例，求解方程： 陜西理工學(xué)院畢業(yè)論文 第 11 頁 共 18 頁 43.5 156.4100(1) tt ee 首先確定迭代初值，利用迭代格式： 0 1.5x 1 43.5 100(1) 156.4 43.543.5 100(1) xx nn n nn xx nn nn ee x xx ee xx 經(jīng)過幾步迭代以后，直到 6 |( )| 10f x ，我們可得方程的解為01009979.其具體過程見下表： 迭代次數(shù)nx() nf x 11.5392.738 20.7311697115.456 30.25735822.5612 40.11200771.48188 50.10105487.62834E-03 60.10099792.04904E-07 陜西理工學(xué)院畢業(yè)論文 第 12 頁 共 18 頁 4 其它迭代格式和變形的牛頓法其它迭代格式和變形的牛頓法 4.1 其它的迭代的格式其它的迭代的格式 自Newton迭代法產(chǎn)生以來，又有很多種迭代方法被構(gòu)造，其中有代表性的迭代法有：三階收斂 的Chebyshev迭代、Halley迭代、Super-Halley迭代(Newton凸加速)迭代及其變形；四階收斂的 Jarratt迭代法及其變形；另外還有實用的導(dǎo)數(shù)超前計值的、導(dǎo)數(shù)滯后計值的、避免導(dǎo)映照求逆等 變形的Newton迭代法：以及階收斂的King-Wemer等兩點迭代格式.12 三階迭代法-Chebyshev迭代、Halley迭代、Super-Haley迭代和四階Jarratt型迭代可以概況為以 下形式此式 1 ()()nnnnyxF xF x (2.10) 1 1( )()()nnnnnxxs F xF x 1 11 0 ()()()()()nnnnnnnnnsF xFxyxt yxdtF xF x , 0,1 , 0,1 . （1）當時，(1.5)式即為Newton迭代法.()1 n s （2）當 1 1 ( )1(1) 2 nnnssas ，時，0,1a (a) . 11 ()()()()n nnnn sF xFx F xF x (2.10)式變?yōu)橐蛔寰哂腥A收斂的迭代,其中包括Cheby-shev(a=0)迭代法，Halley(a=1/2) 迭代法，Super-Haley(a=1)迭代法等. (b) 1 11 0 1 ()()()() 22 () ()(). 33 nnnnnnn nnnnn sF xFxt yxdtF xF x F xF xF xyx 將其代入(2.10)式，迭代法中避免了求二階Frechet導(dǎo)數(shù)，但同時又能保持三階收斂的速 度,所以(b)中方法更有實際意義. （3）當， 1 1 ()1(1) 2 nnn sss 時 (a) 1 11 0 1 ()()()() 22 () ()(). 33 nnnnnnn nnnnn sF xFxt yxdtF xF x F xF xF xyx 陜西理工學(xué)院畢業(yè)論文 第 13 頁 共 18 頁 是具有四階收斂的迭代方法，可將其寫成 (2.11) 1 ()()1 ()2 2() ()3() 3() nn nn n n nn n f xf x xx f x fx fxfx fx 顯然這個方法在每步迭代時，只要計算一個函數(shù)值和兩個導(dǎo)數(shù)值.它最大的優(yōu)勢就在于用較小的計 算代價取得很快的收斂速度，并且(2.11)式可用于求解非線性方程組.我們認為迭代法(2.11)是很 有價值的方法. (b) 11 1 ()()()(). 3 nnnnnnn sF xFxyxF xF x 這也是一個四階收斂的迭代方法. 另外四階收斂的迭代法還有： () () n nn n F x yx F x 1 () 2 ()() nn nnn nn yx xyF x F yF x Ostrowski10和Traub提出的，后來韓給出了其在Smale點估計下的收斂性分析.此迭代法在一 次迭代過程中只需要計算兩個函數(shù)值和一個導(dǎo)數(shù)值，對于求解那些函數(shù)的導(dǎo)數(shù)值比較難計算的方程， 這是個不錯的選擇.從表面看來，這一迭代法似乎比迭代法(2.11)更有優(yōu)勢，但是它僅適用于一維 情形，這就使得此迭代法的實用性大大降低了. 除了以上提到的這些三、四階收斂的迭代法，還有很多變形的Newton迭代法.盡管Newton迭代 是一個很強有力的方法并且收斂很快，但數(shù)值工作者還是從應(yīng)用需要出發(fā)對它做了種種改進.這主 要是因為在各種問題中映照的計值及其求逆的計算代價可能是很大的，所以希望變形的迭代法能夠 盡量少的涉及這種計算而不影響收斂速度，或者雖然做了同樣的計算卻能獲得更快的收斂速度.關(guān) 于這方面的改進最為典型的要數(shù)三個變形的Newton迭代法了，王興華，韓丹夫和孫方裕給出了其詳 細的收斂性分析. 陜西理工學(xué)院畢業(yè)論文 第 14 頁 共 18 頁 4.2 變形的牛頓法變形的牛頓法 一大類在計算實踐中行之有效的變形都可以寫成： 10 (), nnnn xxA F xnN 的形式，這里用以代替的映照有如下一些取法： 1 () n F x : n AFE （1）即 1 / () , nm n m AF x 1 1 ()(),1,1,. nnmkn xxF xF xnmk mkmkmkN 這里是m一個取定的自然數(shù)，而方括號表示取整數(shù)的部分.就是說，我們并不在每步迭代都計算 導(dǎo)映照并求逆，而是每隔m步計算一次，并將其逆保持使用m步.這種方法可以叫做減少導(dǎo)映照計值 次數(shù)的Newton迭代.當m=1時，這就是平常的Newton迭代.設(shè)是減少導(dǎo)映照計算次數(shù)的Newton迭代 n x 產(chǎn)生的收斂于方程(11)的迭代序列，則其子序列的漸近收斂階是m+l.如果用這種方法來求解 mn x 多元非線性方程組，與Newton迭代相比無疑能提高漸近效率. （2）即 11 2(), nnnnn AAA F xA 1 () nnnn xxA F x 1 1 ()(),1,1,. nnmkn xxF xF xnmk mkmkmkN 其中任意指定，使之接近于.這是避免導(dǎo)映照求逆的Newton迭代.其原理是借鑒當年沒 0 A 1 0 ()F x 有除法硬件的計算機中求倒數(shù)的迭代法以求的逆，不過只迭代一次.這已足以達到Newton 1 () n F x 迭代的組合算式中對導(dǎo)映照之逆的精度要求，所以這種避免導(dǎo)映照求逆的Newton迭代仍保持平常的 Newton迭代的漸近收斂階.這一思想后來也被應(yīng)用于變形其它的迭代法，來避免計算導(dǎo)數(shù)的逆. （3）有一個適當?shù)某傲浚?1 () , nnnn AFx 比 111 1 =x-(). 2 nnnn A f x 即 1 1 ()(), nnnn xxFF x 1 111 1 ( )(). 2 nnn xFF x 我們稱這種迭代法為導(dǎo)映照超前計值的Newton迭代.它并沒有增加計值代價，但其漸近收斂階 卻提高到了.12 若令，則上式變?yōu)? 2 nn n xy 陜西理工學(xué)院畢業(yè)論文 第 15 頁 共 18 頁 (2.12) 1 1 1 111 ()(), 2 ()(). 2 nn nnn nn nnn xy xxFF x xy yxFF x 這一兩點迭代格式是WWerner9提出的.事實上，早在發(fā)表的六年之前RFKing8就已經(jīng)在 同一家雜志上提出了一個與(2.12)等價的迭代格式了. 1 1 1 1 () (), 2 ()(). nnnn nnnn yxF yF x xxF yF x 所以迭代法(2.12)被稱為King-Werner迭代法. 對于這三種變形迭代法，已經(jīng)證明它們的收斂條件與Newton迭代是完全相同的，這個結(jié)論排除 了對變形可能影響收斂性的擔心.從而可以只從計算方便的考慮出發(fā)來選擇變形.更重要的是，它們 都可以直接應(yīng)用于解方程組，所以這三種變形的迭代法是非常具有實用價值的. 前面討論的這些迭代方法都是建立在非線性算子F是可導(dǎo)算子的前提之上的，若F是不可導(dǎo)算子， 以上迭代方法便不能使用.一種解決方案便是把F分成兩個算子之和，可導(dǎo)部分記為日，不可導(dǎo)但 Lipschitz連續(xù)部分記為G.由此求解非線性方程(11)就變?yōu)榍蠼夥匠?( )( )0.H xG x 于是Newton迭代法變?yōu)?1 1 () ()(). nnnnn xxH xH xG x 陜西理工學(xué)院畢業(yè)論文 第 16 頁 共 18 頁 小結(jié)小結(jié) 以最經(jīng)典的Newton迭代為例，詳細的給出了它的幾個收斂性條件，以及常用的證明技巧.同時 還介紹了其它一些有代表性的迭代方法，簡略的分析了它們各自的特點.從這些內(nèi)容可以發(fā)現(xiàn)，關(guān) 于迭代法的研究主要是從以下幾個方面進行的：迭代法的提出和推導(dǎo)，即如何構(gòu)造迭代格式;由迭 代格式所產(chǎn)生的序列需要具備什么條件才能收斂到方程的根;迭代法的收斂速度和計算效能等;高階 迭代算法的導(dǎo)出. 陜西理工學(xué)院畢業(yè)論文 第 17 頁 共 18 頁 參考文獻參考文獻 1SWeerakoom，TGIFernando，A variant of NewtonS method with accelerated third-order convergence，ApplMathLett13(2000)8793: 2SSmaie，On the Efficiency of Algorithms of Analysis，Bull(Mew Ser 3王興華，韓丹夫，Newton迭代的區(qū)域估計與點估計，計算數(shù) 學(xué)，12(1990)47-53。 4王興華，韓丹夫，孫方裕，若干變形Newton迭代的點估計，計算數(shù) 學(xué)，2(1990)145156。 )AmerMathSoc13(1985)87-121 5LVKantorovich，On the Newton method for Functional equations Docklady Akademii Nauk SSSR59(1948)1237-1240 6JMGutierrez，A New Semilocal Convergence Theorem for Newton MethodJCompand ApplMath79(1997)131145 7MAHernandez and MASalanova，A family of Newton type iterative proceases， lnern JComputMath51(1994)205-214 8RFKing，Tangent method for nonlinear equations，NumerMath 18(1972)298-304 9WWerner，Uber ein