牛頓迭代法資料

洛陽師范學(xué)院本科畢業(yè)論文PAGEPAGE15牛頓迭代法李保洋數(shù)學(xué)科學(xué)學(xué)院信息與計算科學(xué)學(xué)號：060424067指導(dǎo)老師：蘇孟龍摘要：牛頓在17世紀(jì)提出的一種在實數(shù)域和復(fù)數(shù)域上近似求解方程的方法，即牛頓迭代法.迭代法是一種不斷用變量的舊值遞推新值的過程.跟迭代法相對應(yīng)的是直接法或者稱為一次解法，即一次性解決問題.迭代法又分為精確迭代和近似迭代.“牛頓迭代法”屬于近似迭代法，本文主要討論的是牛頓迭代法，方法本身的發(fā)現(xiàn)和演變和修正過程，避免二階導(dǎo)數(shù)計算的Newton迭代法的一個改進，并與中國古代的算法，即盈不足術(shù)，與牛頓迭代算法的比較.關(guān)鍵詞：Newton迭代算法；近似求解；收斂階；數(shù)值試驗；中國古代數(shù)學(xué)；九章算術(shù)；方程；非線性方程；收斂速度；漸進性0引言：迭代法也稱輾轉(zhuǎn)法，是一種不斷用變量的舊值遞推新值的過程，跟迭代法相對應(yīng)的是直接法或者稱為一次解法，即一次性解決問題.迭代法又分為精確迭代和近似迭代.“二分法”和“牛頓迭代法”屬于近似迭代法.迭代算法是用計算機解決問題的一種基本方法.它利用計算機運算速度快、適合做重復(fù)性操作的特點，讓計算機對一組指令（或一定步驟）進行重復(fù)執(zhí)行，在每次執(zhí)行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值.具體使用迭代法求根時應(yīng)注意以下兩種可能發(fā)生的情況：(1)如果方程無解，算法求出的近似根序列就不會收斂，迭代過程會變成死循環(huán)，因此在使用迭代算法前應(yīng)先考察方程是否有解，并在程序中對迭代的次數(shù)給予限制.(2)方程雖然有解，但迭代公式選擇不當(dāng)，或迭代的初始近似根選擇不合理，也會導(dǎo)致迭代失敗.所以利用迭代算法解決問題，需要做好以下三個方面的工作：1、確定迭代變量.在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量.2、建立迭代關(guān)系式.所謂迭代關(guān)系式，指如何從變量的前一個值推出其下一個值的公式(或關(guān)系).迭代關(guān)系式的建立是解決迭代問題的關(guān)鍵，通?？梢允褂眠f推或倒推的方法來完成.3、對迭代過程進行控制，在什么時候結(jié)束迭代過程？這是編寫迭代程序必須考慮的問題.不能讓迭代過程無休止地重復(fù)執(zhí)行下去.迭代過程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數(shù)是個確定的值，可以計算出來;另一種是所需的迭代次數(shù)無法確定.對于前一種情況，可以構(gòu)建一個固定次數(shù)的循環(huán)來實現(xiàn)對迭代過程的控制;對于后一種情況，需要進一步分析出用來結(jié)束迭代過程的條件.1牛頓迭代法：牛頓迭代法(Newtonmethod)又稱為牛頓-拉夫遜方法(Newton-Rapfsonmethod)，它是牛頓在17世紀(jì)提出的一種在實數(shù)域和復(fù)數(shù)域上近似求解方程的方法.多數(shù)方程不存在求根公式，因此求精確根非常困難甚至不可能，從而尋找方程的近似根就顯得特別重要.方法使用函數(shù)的泰勒級數(shù)的前面幾項來尋找方程的根.牛頓迭代法是求方程根的重要方法之一，其最大優(yōu)點是在方程的單根附近具有平方收斂性，而且該法還可以用來求方程的重根、復(fù)根.另外該方法廣泛用于計算機編程中：解非線性方程的牛頓(Newton)法是把非線性的方程線性化的一種近似方法.把的點附近展開泰勒(Taylor）級；取其線性部分作為非線性方程的近似方程，則有：；設(shè)，則其解為：；再把在附近展開泰勒(Taylor)級數(shù)，也取其現(xiàn)行部分作為的近似方程.若，則得：；yxyxOx*x1x0；牛頓迭代有十分明顯的幾何意義，如圖所示：當(dāng)選取初值以后，過做的切線，其切線方程為：；求此切線方程和軸的交點，即得：；牛頓法正因為有這一明顯的幾何意義，所以也叫切線法.例：用牛頓法求下面方程的根；解：因，所以迭代公式為：；選取計算結(jié)果列表：N牛頓法弦位法拋物線法011111.4117647058823531.5000000000000001.50000000000000021.3693364705882351.3544303797468361.25000000000000031.3688081886175321.3682702596546871.36853585772136741.3698081078213751.3688103503938871.36880790682018051.3688081078213731.3688081074722171.36880810782168161.3688081078213731.3688081078213731.36880810782137371.3688081078213731.368808107821373從結(jié)果可以看出，牛頓法的收斂是很快的，誤差.但用牛頓法計算工作量比較大，因每次計算迭代除了計算函數(shù)值外還要計算微商值.為此我們提出了簡化牛頓法：其公式為；用上面的公式計算，不再需要每步重新計算微商值，所以計算量小一些，但收斂也要慢一些.為了避免計算導(dǎo)數(shù)還可以采用差商代導(dǎo)數(shù)的方案：；關(guān)于牛頓迭代的收斂有下面結(jié)果：如果在零點附近存在連續(xù)的二階微商，是的一重零點，且初始充分接近于，那么牛頓迭代是收斂的，且有；這表明牛頓法是二階收斂的（平方收斂的）.最后考慮是多項式的特殊情況，此時，在某個值，比如時的計算可用綜合除法.設(shè)，除以，得商，余：；（1）其中：；；比較(1)式兩邊的系數(shù)便知這些可以按下表進行：這一過程其實就是秦九韶算法，計算多項式值的嵌套算法：；每個括號的值就是這里的.至于導(dǎo)數(shù)的計算，注意到(1)式可得：；于是：；因此再對進行上述過程，或者再用一次秦九韶算法即可.2一種修正的牛頓迭代法：給出了牛頓迭代法的一種修正形式，并證明了當(dāng)時修正的牛頓迭代法是二階收斂的，當(dāng)參數(shù)時是三階收斂的，數(shù)值實驗表明，與經(jīng)典牛頓迭代法相比，該修正牛頓迭代法具有一定的優(yōu)勢.眾所周知，數(shù)值求解非線性方程的根的方法很多.經(jīng)典的牛頓迭代法是非線性方程組求根的一個基本方法，它二次收斂到單根，線性收斂到重根.牛頓法因收斂速度快而得到廣泛應(yīng)用，也倍受學(xué)者的重視，近年來很多文獻中提出各種改進的牛頓方法.文獻［8］中利用Newton迭代法和微分中值定理“中值點”的漸進性，提出了一種多點迭代法.設(shè)滿足下述條件：，；，在上保號.(A)根據(jù)微分中值定理，存在，使得：，而.因此，當(dāng)與的距離無限接近時有：.也就是說，在區(qū)間不甚大時，中值點一定在其漸近位置附近，并隨區(qū)間變小而趨于其漸近位置.圖所示迭代法構(gòu)造圖本方案基于上述考慮，給出一種通過迭代點選取另一個點，利用兩個點進行迭代求近似根的新方法.這種方法雖然在迭代中又只利用了一個其它點，但其計算精度卻相當(dāng)高，它的某一種特殊情形恰是通常的Newton迭代法.為了更加直觀起見，我們通過幾何直觀圖來構(gòu)造這種迭代法.設(shè)滿足條件(A)，當(dāng)選定初值(僅要求)，如圖所示，作交點的切線交軸于，線段的斜率為：.由微分中值定理知，存在使得：；而，因此，我們?nèi)?shù)，在點作切線，圖中平行于.即用點的導(dǎo)數(shù)代替點的導(dǎo)數(shù)，而仍用點的迭代格式得到點的坐標(biāo)；重復(fù)上述過程，得到多點迭代公式；(2)其中，.下面我們對上述事實，從理論上加以嚴(yán)格證明.定理設(shè)滿足條件(A)，則由多點迭代公式(1)產(chǎn)生的序列{}必收斂于上的唯一，這里，.證明函數(shù)在上連續(xù)，由連續(xù)函數(shù)根的存在定理，從知道在上根存在，又由條件及保號知道，在上不變號，故在上是單調(diào)函數(shù)，因此在上根存在且唯一.由定理條件曲線可有如下四種不同情況：(1)，則單調(diào)上升，；(2)，則單調(diào)下降，；(3)，則單調(diào)上升，；(4)，則單調(diào)下降，.通過對自變量的變號或?qū)瘮?shù)的變號可將四種情況歸結(jié)為一種情況，所以我們只需對情況(一)證明迭代過程(1)收斂就可以了.若初值所以，故有；；一方面，，且.下證.若，由的單調(diào)性有，，，又因為，因此有，與Newton迭代法的收斂性矛盾.由(一)的假設(shè)及可得：；一般地，若，同樣可以證明由式(2)得到的滿足.所以由式(1)產(chǎn)生的迭代序列{}單調(diào)下降且有下界.依極限理論必有極限.對式(2)兩邊取極限，由極限理論可以求得.再由，，可知函數(shù)方程在上的根是唯一的，因此有.當(dāng)時，式(2)即為Newton迭代公式.本文給出的這種多點迭代方法不僅可以被廣泛應(yīng)用于方程的近似求根，更重要的是它為人們提供了一種新的迭代思想，拓寬人們在方程近似求根方面的思路.例計算在區(qū)間內(nèi)的一個實根.我們已知有一個精確到十二位有效數(shù)字的實根.取，以Newton迭代法計算(記作)，取，以式(1)計算(記作)，其結(jié)果列表如表1.表1計算結(jié)果：迭代次數(shù)N01234532.362.0951360372.0945516742.9455148232.184684462.0947263042.094551482從這個數(shù)值例子，我們可以看出，式(2)比Newton迭代法的收斂速度快得多，只進行三次迭代就已得滿足精度要求的值了，而Newton迭代法需迭代5次才可得到滿足精度要求的值.式(2)可以被廣泛應(yīng)用，特別是編成數(shù)學(xué)軟件后，用計算機求解方程近似根效果會更加顯著.3另外一種牛頓迭代法的修正：Newton迭代法是方程求根的一種簡單而直觀的近似方法，但在實際運用中，我們常常覺察到，這種方法僅僅是利用了迭代點及該點的導(dǎo)數(shù)值，而沒有充分利用其他點及其導(dǎo)數(shù)值.是否存在可利用的點，這些點我們應(yīng)怎樣確定.文[1]給出了一種方法，但這種方法求根的關(guān)鍵在適當(dāng)?shù)剡x取和或.選取不適當(dāng)，就會出現(xiàn)某次迭代的值不是迭代序列中的值.因此，我們會問這些值特別是能否不依靠人為選取，而通過迭代點來選取，本文將利用Newton迭代法和微分中值定理“中值點”的漸近性，來尋找除迭代點以外的可利用點，給出一種多點迭代方法.設(shè)滿足下述條件：；在上保號.(A)根據(jù)微分中值定理，存在，使得而.因此，當(dāng)與的距離無限接近時有：.也就是說，在區(qū)間不甚大時，中值點一定在其漸近位置附近，并隨區(qū)間變小而趨于其漸近位置.本方案基于上述考慮，給出一種通過迭代點選取另一個點，利用兩個點進行迭代求近似根的新方法.設(shè)滿足下列條件(A)：(1)在區(qū)間在區(qū)間上存在二階導(dǎo)數(shù)；(2)在上不等于零；(3)在上不變號；(4)；為了更為直觀，我們通過幾何直觀圖來構(gòu)造多點迭代法.設(shè)滿足條件(A)，當(dāng)選定初值（僅要求），如圖所示：做點的切線交軸于，線段的斜率為：；由微分中值定理知，存在使得：；而，因此，我們?nèi)?shù)，在點作切線，圖中平行于.即用點的導(dǎo)數(shù)代替點的導(dǎo)數(shù)，而仍用點的迭代格式得到點的坐標(biāo)；(3)主要對(3)式的分子用與的和代替，這樣就得到新的迭代公式：；(4)如果令；；則：；從而可知(4)式中迭代函數(shù)為：；引理1[5]對于迭代公式，如果在所求的根的鄰近連續(xù)并且：，，則該公式在的鄰近是階收斂的.定理1設(shè)方程的根為，函數(shù)在的的鄰域內(nèi)有至少四階連續(xù)導(dǎo)數(shù)，且，則迭代公式(4)在的鄰近至少是三階收斂的.證明迭代公式(4)的迭代函數(shù)為：，其中，由于方程的根為所以，從而可知，；對求導(dǎo)數(shù)得：；同理可得：.由引理知迭代公式(4)在鄰近至少是三階收斂的.引理2（[4]）假設(shè)函數(shù)在區(qū)間上存在二階導(dǎo)數(shù)，且滿足下列條件(1)在上不等于零；(2)在上不變號；(3)；(4)設(shè)，且滿足條件；則由Newton迭代法得到的序列收斂于的惟一根.定理2假設(shè)函數(shù)在區(qū)間上存在二階導(dǎo)數(shù)，且滿足下列條件(1)在上不等于零；(2)在上不變號；(3)；(4)設(shè)，且滿足條件.則由多點迭代公式(4)得到的序列收斂于的惟一根.證明函數(shù)在上連續(xù)，由連續(xù)函數(shù)根的存在定理，從知道在上根存在，又由條件及的保號性知道，在上不變號，故在上是單調(diào)函數(shù)，因此在上的根存在且惟一.由定理條件，曲線可有如下四種不同情況：(a)，則單調(diào)上升，；(b)，則單調(diào)下降，；(c)，則單調(diào)上升，；(d)，則單調(diào)下降，.通過對自變量的變號或?qū)瘮?shù)的變號可以將四種情況歸結(jié)為一種情況，所以我們只需對其中一種情況證明迭代過程(4)是收斂的就可以了.下面僅就情況(a)證明定理2，其余情況的證明類似.對情況(a)來說此時在上的根存在且惟一，且在上單調(diào)遞增.首先證明，對任何初始近似，由迭代公式(4)求出的逐次近似都屬于，并且單調(diào)遞減.事實上，由引理2的證明我們可知，只要，就有，即，再由(3)式得，另一方面(3)式可化為：；其中.由單調(diào)遞增且知，故因而由(4)式產(chǎn)生的序列單調(diào)遞減并有下界，故存在.設(shè)，(4)式兩邊當(dāng)時求極限得：；；可知；，在上單調(diào)遞增，且所以：；因此得：.本方法代方法比Newton和文[4]的迭代法的收斂速度明顯要快，而且對于，越大效果越差！對于例1，用MATLAB程序運算格式(4)，當(dāng)時，在之前迭代格式會產(chǎn)生負(fù)值.所以，格式(4)的收斂速度和的選取有關(guān).對于定理2中的四個條件，在MATLAB中通過簡單的程序即可驗證.4中國古代算法盈不足術(shù)與牛頓迭代算法的比較：首先介紹盈不足術(shù)九章算術(shù)中的第七章是盈不足術(shù)，這是求解方程的一種最古老的方法.為了說明該方法的基本思想，我們考慮該章的第一個例子：今有共買物，人出8，盈3；人出7，不足4，問人數(shù)、物價各幾何？其求解過程為(見圖1)：(1)把出率(8)和(7)放在第一行；(2)把盈數(shù)(3)和不足數(shù)(4)放置在出率下面；(3)計算維積(交差積)得(32)和(21)，得和為(53)；(4)盈減去不足數(shù)為；(5)從而得物價為；用現(xiàn)代數(shù)學(xué)的觀點，盈不足術(shù)可表示為：設(shè)和為兩個近似物價，和分別表示為盈或不足數(shù)，則物價為：;人數(shù)為；正如白尚恕[7]指出的那樣，在隋唐(581～618年AD)盈不足術(shù)在中東被廣泛流傳，最早的阿拉伯算術(shù)書是由al-Khowarizmi在公元825年寫的，英文中的算術(shù)一詞(algorithm)來自他的名字，他應(yīng)該對九章算術(shù)和其他古代中國巨著很了解，并把盈不足術(shù)稱為中國方法.Khitai指China，類似的寫法有Khatai，Chatayn，Chataain等等.普遍認(rèn)為中國算法是通過古代著名的意大利數(shù)學(xué)家LeonardoFibonacci(1170?～1250?年)傳給西方的，據(jù)記載Fibonacci隨他父親周游了埃及、西西里、希臘和敘利亞，這次周游使他接觸了東方和阿拉伯的計算方法.在1202年，即他回家后不久他就出版了著名的《算經(jīng)LiberAbaci》.該書也介紹了盈不足術(shù)，并把這種方法稱為中國規(guī)則，這個名字來自中東，在那里中國算法稱為Hisabl-Chatin，里Chation指China該書中的一些例子和算法和中國古代數(shù)學(xué)巨著完全一樣.如在4世紀(jì)的孫子算經(jīng)：今有物不知其數(shù)，三三數(shù)之勝二，五五數(shù)之勝三，七七數(shù)之勝二，問物幾何？該問題的解題方法就是數(shù)論中的中國余數(shù)定理：在Fibonacci的《算經(jīng)》中阿拉伯語DeRegulisel-Chatavn被譯成拉丁文DuarumFalsdrumPosicionumRegula所以在西方這種方法被稱作雙假定方法，這實際上是九章算術(shù)中的盈不足術(shù)，即中國算法，它起源于中國是毫無疑問的，這正如錢寶琮[8]指出的那樣可惜的是很多西方人認(rèn)為這種方法起源于印度，并被阿拉伯人所掌握所以本作者強烈建議把雙假設(shè)法改稱為中國算法或中國方法.中國算法與牛頓迭代算法考慮方程設(shè)為方程的兩個近似解，于是我們得殘量和應(yīng)用中國算法，我們可得；（5）在九章算術(shù)中給出了在下列情況下的一些不等式：(1)雙盈，即和(2)雙虧，即和；(3)一盈一虧，即；上述算法可以根據(jù)不等式的性質(zhì)確定更合適的兩個數(shù)或，再進行計算定更精確的近似解，為了與牛頓迭代算法比較，我們把(5)寫成如下形式：；如果引入導(dǎo)數(shù)，它定義為；那么我們馬上可得：；這就是著名的牛頓迭代法，當(dāng)兩個近似值和位于真解的兩側(cè)時，即，中國算法比牛頓迭代算法具有很大的優(yōu)勢，牛頓迭代算法可以更進一步的優(yōu)化發(fā)展，可參考文獻[10，11].中國算法的改進：中國算法可以看成是通過兩個近似解的線性近似方法，見圖2為了提高中國算法的精度，我們用三點，而不用兩點，用拋物線擬合該曲線，我們得近似解為：；式中；綜合概述：迭代算法是一種用途非常廣泛的方法，本文不僅介紹了這個方法很好的詮釋這個方法，而且做了牛頓迭代法的兩種修正，更做了牛頓迭和與中國古代算法的比較，不僅試讀者更好理解了這個方法，更開闊了讀者的視野，使讀者更能留下研究的空間.參考文獻：[1]徐萃薇，孫繩武.計算方法引論（第三版）[M].北京：高等教育出版社，2007.[2]龍愛芳.避免二階導(dǎo)數(shù)計算的迭代法[J].浙江工業(yè)大學(xué)學(xué)報，2005，33(5):602～604.[3]李慶揚，王能超.數(shù)值分析[M].武漢：華中科技大學(xué)出版社，1986.[4]張新東，王秋華.避免二階導(dǎo)數(shù)計算的Newton迭代法的一個改進[J].山東大學(xué)學(xué)報，2007，42（7）：72～76.[5]何吉歡.盈不足術(shù)與牛頓迭代算法的比較[J].應(yīng)用數(shù)學(xué)和力學(xué)，2002，23（12）：1256～1259.[6]王曉峰.一種修正的牛頓迭代法[J]，2010，33（1）長春理工大學(xué)學(xué)報，178～179.[7]白尚恕.九章算術(shù)注釋[M].北京：科學(xué)出版社，1983.[8]錢寶琮.中國數(shù)學(xué)史[M].北京：科學(xué)出版社，1992.[9]陳新一.一種多點迭代方法[J].甘肅教育學(xué)報（自然科學(xué)版），2001，15（1）：13～16.[10]HeJi-huan.ImprovementofNewtoninterationmenthod[J].InternationalJournalofNonlinearScienceandNumericalSimulation2000，1(3):239～240.[11]HeJi-huan.Newton-likeiterationmenthodforsolvingalgebraicequations[J].CommunicationNumSimulation，1998，3(2):106～109NewtoniterationLIBaoYangMathematicalSciencesInformationandComputingScienceNO：060424067Instructor:SUMenglongSummary：Inthe17thcentury，Newtonintroducedamethodofsolveequationsapproximatelyinrealnumberdomainandcomplex