《牛頓迭代法的基本原理及其應(yīng)用（論文）》

牛頓迭代法的基本原理及其應(yīng)用目錄TOC\o"1-2"\h\u23800牛頓迭代法 127137摘要 1262481緒論 1202891.1選題意義和背景 1242191.2牛頓迭代法的優(yōu)點(diǎn)及缺點(diǎn) 2262861.3牛頓迭代法的理論依據(jù) 3133142牛頓迭代算法的基本原理 3172952.1牛頓迭代算法 3301362.2一種修正的牛頓迭代算法 598583牛頓迭代算法在計(jì)算方程中的應(yīng)用 916712例1：用牛頓法求下面方程的根 1083784

利用牛頓迭代法反演漏電位置 1334654.1對(duì)模擬漏電位置的反演 1357264.2對(duì)臺(tái)站實(shí)際漏電位置的反演 1531750(a)一次漏電實(shí)驗(yàn)記錄到的電位差跳變;(b)單次跳變波形圖 1616584參考文獻(xiàn) 17摘要牛頓在17世紀(jì)提出的一種近似求解方程的方法，即牛頓拉夫森迭代法。迭代法是一種不斷的用變量的舊值遞推新值的過程.跟迭代法相對(duì)應(yīng)的是直接法或被稱為一次解法，即一次性解決的問題。迭代法又分為精確迭代以及近似迭代?！芭ｎD迭代法”就屬于近似迭代法，本文主要討論的就是牛頓迭代法，方法本身的發(fā)現(xiàn)到演變到修正的過程，避免二階導(dǎo)數(shù)計(jì)算的Newton迭代法的一個(gè)改進(jìn)，以及用牛頓迭代法解方程，以及通過構(gòu)建漏電偶極源二維地電場模型，正演偶極源對(duì)觀測電極產(chǎn)生的電位差比例系數(shù)，采用牛頓迭代算法，實(shí)現(xiàn)漏電位置的精確求解。關(guān)鍵詞：牛頓迭代法；求解方程；漏電監(jiān)測1緒論1.1選題意義和背景牛頓拉夫森迭代法是牛頓在17世紀(jì)提出的一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法。多數(shù)方程不存在求根公式，因此求精確根非常困難，甚至不可能，從而尋找方程的近似根就顯得特別重要。方法使用函數(shù)f（x）的泰勒級(jí)數(shù)的前面幾項(xiàng)來尋找方程f（x）=0的根。牛頓迭代法是求方程根的重要方法之一，其最大優(yōu)點(diǎn)是在方程f（x）=0的單根附近具有平方收斂，而且該法還可以用來求方程的重根、復(fù)根,此時(shí)線性收斂，但是可通過一些方法變成超線性收斂。

利用牛頓迭代法來解決問題需要做好的工作：

確定迭代變量。在可以用迭代算法解決的問題中，至少存在一個(gè)直接或間接地不斷由舊值遞推出新值的變量，這個(gè)變量就是迭代變量。

建立迭代關(guān)系式。所謂迭代關(guān)系式，指如何從變量的前一個(gè)值推出其下一個(gè)值的公式（或關(guān)系）。迭代關(guān)系式的建立是解決迭代問題的關(guān)鍵，通?？梢允褂眠f推或倒推的方法來完成。

（3）對(duì)迭代過程進(jìn)行控制。在什么時(shí)候結(jié)束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重復(fù)執(zhí)行下去。迭代過程的控制通常可分為兩種情況：一種是所需的迭代次數(shù)是個(gè)確定的值，可以計(jì)算出來；另一種是所需的迭代次數(shù)無法確定。對(duì)于前一種情況，可以構(gòu)建一個(gè)固定次數(shù)的循環(huán)來實(shí)現(xiàn)對(duì)迭代過程的控制；對(duì)于后一種情況，需要進(jìn)一步分析出用來結(jié)束迭代過程的條件。1.2牛頓迭代法的優(yōu)點(diǎn)及缺點(diǎn)迭代法是求方程近似根的一個(gè)重要方法，也是計(jì)算方法中的一種基本方法，它的算法簡單，是用于求方程或方程組近似根的一種常用的算法設(shè)計(jì)方法。牛頓迭代法是求方程根的重要方法之一，其最大優(yōu)點(diǎn)是在方程f（x）=0的單根附近具有平方收斂，而且該法還可以用來求方程的重根、復(fù)根。牛頓法是方程求根的一個(gè)有力方法，常常能快速求出其他方法求不出或者難以求出的解。假定有一個(gè)函數(shù)y=f(x)，方程f(x)=0在x=r處有一個(gè)根，對(duì)于此根，先估計(jì)一個(gè)初始值x0（可以是猜測的）。得到一個(gè)更好的估計(jì)值x1。為此f(x)=x0處作該曲線切線，并將其延長與x軸相交。切線與x軸的交點(diǎn)通常很接近r，我們用它作為下一個(gè)估計(jì)值x1，求出x1后，用x1代替x0。重復(fù)上述過程，在f(x)=x0處作曲線的另一條切線，并將其延長至與x軸相交，用切線的x軸截距作為下一個(gè)近似值x2...這樣繼續(xù)下去，所得出的這個(gè)x軸截距的序列通常迅速接近根r。

缺點(diǎn)：選定的初值要接近方程的解，否則有可能的不到收斂的結(jié)果。再者，牛頓迭代法計(jì)算量比較大。因每次迭代除計(jì)算函數(shù)值外還要計(jì)算微商值。

1.3牛頓迭代法的理論依據(jù)牛頓迭代法是用于求解非線性方程根的一種很有效的方法,該方法既可以通過中值定理推出來,也可以通過Taylor單調(diào)有界數(shù)列必有極限定理推出,因此下面將給出2種證明。首先說明該方法的使用條件是函數(shù)在區(qū)間[a,b]上有連續(xù)的二階導(dǎo)函數(shù),其中a,b為區(qū)間的2個(gè)端點(diǎn),并且滿足:<0，表示在區(qū)間[a,b]上一定有根,，等價(jià)于且。對(duì)于方程f(x)=0,如果f(x)是線性函數(shù),那么它的根是很容易求的。解非線性方程的牛頓迭代法實(shí)質(zhì)上是一種將非線性方程線性化的方法,基本思想是將非線性方程f(x)=0逐步歸結(jié)為某種線性方程來求解。非線性方程f(x)=0,根據(jù)Taylor中值定理有:(ξ介于x與xk之間)為了簡化問題用直線代替曲線，得，若，則，如果把x作為xk+1，用它作為非線性方程的進(jìn)一步近似解，即:從計(jì)算過程看出，方程的根是經(jīng)過一次次迭代計(jì)算出來的，因此取名為牛頓迭代法，式(1)這就是牛頓迭代公式.對(duì)于開方的問題可以歸納為求非線性方程根的問題，把f(x)和代入牛頓迭代公式，整理后得：2牛頓迭代算法的基本原理2.1牛頓迭代算法牛頓迭代法(Newtonmethod)又稱為牛頓-拉夫森方法(Newton-Rapfsonmethod)，它是牛頓在17世紀(jì)提出的一種近似求解方程的方法.多數(shù)方程不存在的求根公式，因此求精確根相當(dāng)困難甚至不可能，從而尋找方程的近似根就會(huì)顯得特別重要。方法在使用函數(shù)的泰勒級(jí)數(shù)的前面幾項(xiàng)來尋找方程的根.牛頓迭代法是求方程的根的重要方法之一，其最大的優(yōu)點(diǎn)是在方程的單根附近具有平方收斂性，而且該法還可以用來求方程的重根、復(fù)根。牛頓迭代法方法簡單，每次迭代都是簡單的去重復(fù)運(yùn)算，易于編制程序；與求解線性方程的精確法相比較，簡單迭代法對(duì)于字長位數(shù)較少的計(jì)算機(jī)更加的適用，它可以用增加迭代的次數(shù)來彌補(bǔ)字長位數(shù)少的不足。初值可以任意的取，因而中間結(jié)果偶然的錯(cuò)誤不影響最后結(jié)果的獲得。多數(shù)情況下是得不到一般的數(shù)學(xué)方法所需的函數(shù)表達(dá)式，或者難以找到原函數(shù)。線性方程組中的求解更是讓人望而生畏，往往因?yàn)橛?jì)算機(jī)的工作量太大而無法實(shí)施。對(duì)于這些問題，都可以利用數(shù)值的方法來求解，在計(jì)算機(jī)中實(shí)現(xiàn)的數(shù)值方法也被稱之為數(shù)值算法。牛頓迭代法是數(shù)值分析中一個(gè)重要的計(jì)算方法和思想。迭代法的一個(gè)主要功能：計(jì)算方程時(shí)可以比較的快速。解非線性方程的Newton-Rapfson算法是把非線性的方程線性化為一種近似方法.把的點(diǎn)附近展開泰勒(Taylor）級(jí)取其線性部分用來作為非線性方程的近似方程，則有：設(shè)，則其解為：再把在附近展開泰勒(Taylor)級(jí)數(shù)，取其現(xiàn)行部分作為的近似方程。若，則得：這樣，得到牛頓(Newton-Rapfson)算法的一個(gè)迭代的序列：.牛頓迭代法有十分明顯的幾何意義，如下圖所示：圖2.1當(dāng)選取初值以后，過（，）做的切線，其切線的方程為：求此切線方程和軸的交點(diǎn)，即得：牛頓迭代法正因?yàn)橛羞@一明顯的幾何意義，所以也叫切線法。2.2一種修正的牛頓迭代算法給出了牛頓(Newton-Rapfson)算法的一種修正的形式，并證明了當(dāng)時(shí)修正的牛頓(Newton-Rapfson)算法是二階收斂的，當(dāng)參數(shù)時(shí)是三階收斂時(shí)，數(shù)值實(shí)驗(yàn)得出結(jié)果，與經(jīng)典牛頓迭代法相比，該修正牛頓(Newton-Rapfson)算法具有一定的優(yōu)勢。眾所周知的，數(shù)值求解非線性方程的根的方法很多.經(jīng)典的牛頓迭代法是非線性方程組求根的一個(gè)基本的方法，它二次收斂到單根，線性收斂到重根。牛頓法因收斂速度快而得到廣泛應(yīng)用，也倍受學(xué)者的重視，近年來很多文獻(xiàn)中提出各種改進(jìn)的牛頓方法。文獻(xiàn)中利用Newton-Rapfson迭代法和微分中值定理“中值點(diǎn)”的漸進(jìn)性，提出的一種多點(diǎn)迭代的算法.設(shè)滿足下述條件：，。，在上保號(hào)。根據(jù)微分中值定理，即存在，使得：，而。因此，當(dāng)與的距離無限接近時(shí)有：OOADCPyx圖2.2，也就是說，在區(qū)間不甚大的時(shí)候，中值點(diǎn)一定在其漸近的位置附近，并隨區(qū)間變小而趨于其漸近的位置。圖所示的迭代算法構(gòu)造圖本方案基于上述考慮，給出一種通過迭代點(diǎn)而選取另一個(gè)點(diǎn)，利用兩個(gè)點(diǎn)進(jìn)行迭代求近似根的新方法.這種方法雖然在迭代中又只利用了一個(gè)其它的點(diǎn)，但其計(jì)算精度卻相當(dāng)?shù)母?，它的某一種特殊情形恰是通常的Newton-Rapfson迭代算法.為了更加直觀起見，我們通過幾何直觀圖來構(gòu)造這種迭代算法.設(shè)滿足條件(A)，當(dāng)選定初值。(僅要求)，如圖所示，作交點(diǎn)的切線交軸于B，AQ線段的斜率為：由微分中值定理得知，存在使得：而，因此，我們?nèi)?shù)，在點(diǎn)作切線PC，圖中AD平行于PC.即用點(diǎn)P的導(dǎo)數(shù)取代點(diǎn)A的導(dǎo)數(shù)，而繼續(xù)用點(diǎn)的迭代格式得到的點(diǎn)D的坐標(biāo).重復(fù)上述過程，得到多點(diǎn)迭代公式：.(1)其中，下面我們對(duì)上述事實(shí)，從理論上加以嚴(yán)格的證明.定理設(shè)滿足條件(A)，則由多點(diǎn)迭代公式(1)產(chǎn)生的序列{}必收斂于上的唯一，這里，。證明:函數(shù)在上連續(xù)，由連續(xù)函數(shù)根的存在定理，從知道在上的根存在，又由條件以及保號(hào)知道，在上不變號(hào)，故在上是單調(diào)函數(shù)，因此在上的根存在且唯一。由定理?xiàng)l件曲線可有如下四種不同的情況：(1)，，，則單調(diào)上升，；(2)，，，則單調(diào)下降，；(3)，，，則單調(diào)上升，；(4)，，，則單調(diào)下降，.通過對(duì)自變量的變號(hào)或者對(duì)函數(shù)的變號(hào)可將四種情況歸結(jié)為一種情況，所以我們只需對(duì)其情況(一)證明迭代過程(1)收斂就可以了。若初值，，所以，故有.一方面，，且.下證.若，由的單調(diào)性有：，，又因，因此就有，與Newton迭代算法的收斂性矛盾。由(一)的假設(shè)及可得：一般地，若，同樣可以證明由式(1)得到滿足。依極限理論的必有極限。對(duì)式(1)兩邊取極限，由極限理論可求得.再由，，可知函數(shù)方程在上的根是唯一的，因此有。當(dāng)時(shí)，式(1)即為Newton-Rapfson迭代公式。本文給出的這種多點(diǎn)迭代方法不僅可以廣泛應(yīng)用于方程的近似求根，更重要的是它為人們提供了一種新的迭代算法思想，拓寬人們求方程近似求根方面的思路。

3牛頓迭代算法在計(jì)算方程中的應(yīng)用非線性方程求根最為常用的是迭代法。迭代法是計(jì)算方法中的一種基本方法,主要有簡單迭代法、牛頓迭代法和弦割法。本文主要通過借助非線性方程求解,介紹優(yōu)化程序的方法,能夠提高數(shù)值計(jì)算程序的質(zhì)量。它對(duì)處理科學(xué)工程問題或企事業(yè)管理中的數(shù)值計(jì)算問題有一定的啟發(fā)意義。首先，常用非線性方程解法的對(duì)比與分析對(duì)于收斂的迭代過程，只要迭代足夠多次，就可以得到滿足制定精度要求的結(jié)果。但有時(shí)迭代過程收斂緩慢，計(jì)算效率很低。如何改進(jìn)迭代法使之加快收斂速度，是實(shí)際應(yīng)用中需要解決的問題。弦截法與牛頓迭代法都是線性化方法;但兩者有本質(zhì)的區(qū)別。牛頓迭代法與一般迭代法在計(jì)算時(shí)只用到前一步的值，故稱之為單點(diǎn)迭代法；而弦截法在求時(shí)要用到前兩步的結(jié)果和，使用這種方法必須給出兩個(gè)初始近似根，，這種方法稱為多點(diǎn)迭代法。另外，弦截法比牛頓迭代法收斂速度較慢，但它的計(jì)算量比牛頓迭代法小。例1：用牛頓法求下面方程的根；解：因?yàn)?，所以其迭代公式為：；選取計(jì)算結(jié)果列表如下：N牛頓法弦位法拋物線法0123456711.4117647058823531.3693364705882351.3688081886175321.3698081078213751.3688081078213731.36880810782137311.5000000000000001.3544303797468361.3682702596546871.3688103503938871.3688081074722171.3688081078213731.36880810782137311.5000000000000001.2500000000000001.3685358577213671.3688079068201801.3688081078216811.3688081078213731.368808107821373從結(jié)果可以看出，牛頓法的收斂是明顯很快的，誤差.但用牛頓法計(jì)算工作量會(huì)比較大，因每次計(jì)算迭代除了計(jì)算函數(shù)值外還要計(jì)算微商值.為此我們提出了簡化的牛頓迭代算法：其公式為；用上面的公式計(jì)算，不再需要每步重新去計(jì)算微商值，所以計(jì)算量要小一些，但收斂也要慢一些.為了避免計(jì)算導(dǎo)數(shù)還可以采用差商代導(dǎo)數(shù)的方案來算：；關(guān)于牛頓迭代算法的收斂有下面結(jié)果：如果在零點(diǎn)附近存在的連續(xù)的二階微商，是的一重零點(diǎn)，并且初始充分接近于，那么牛頓迭代算法是收斂的，并且有；這表明牛頓法是二階收斂的（平方收斂的）.最后考慮是多項(xiàng)式的特殊的情況，而此時(shí)，在某個(gè)值，比如時(shí)的計(jì)算可以用綜合除法.設(shè)，除以，得商，余：；（4）其中：；；比較(4)式兩邊的系數(shù)便知這些可以按下表來進(jìn)行：這一過程就是秦九韶算法，計(jì)算多項(xiàng)式值的嵌套算法：；每個(gè)括號(hào)的值就是這里的.至于導(dǎo)數(shù)的計(jì)算，我們注意到(4)式可得：；于是：；因此再對(duì)進(jìn)行上述的過程，或者再用一次秦九韶算法即可.例2:計(jì)算在區(qū)間內(nèi)的一個(gè)實(shí)根.我們已知有一個(gè)精確到十二位有效數(shù)字的實(shí)根.取，以Newton迭代法計(jì)算(記作)，取，以式(4)計(jì)算(記作)，其結(jié)果列表如表1.表3.1計(jì)算結(jié)果：迭代次數(shù)N01234532.3600000000002.1271967801592.0951360369342.0945516738242.094551482154從這個(gè)數(shù)值例子，我們能看出，式(4)比Newton迭代算法的收斂速度快得多，只進(jìn)行三次迭代就可以得到滿足精度要求的值了，而Newton迭代算法需迭代5次才可以得到滿足精度要求的值.式(4)可以被廣泛應(yīng)用，特別是編成數(shù)學(xué)軟件后，用計(jì)算機(jī)求解方程近似根時(shí)效果會(huì)更加顯著。例3：計(jì)算的近似值。解：令問題轉(zhuǎn)化為求的正根由牛頓迭代公式迭代結(jié)果迭代次數(shù)迭代結(jié)果012345670.8800000.8836300.8844460.8846250.8846640.8846730.8846750.884675滿足了精度要求=0.884675例4：用牛頓迭代法球方程=a（a>0）的近似正實(shí)根。由此我們建立一種求平方根的計(jì)算方法。解：首先計(jì)算可知迭代公式為通過編寫matlab程序計(jì)算得出，比如5的平方根，初始值取做2，只需輸入命令：it(5,2)，立即可得結(jié)果y=2.2361。4

利用牛頓迭代法反演漏電位置4.1對(duì)模擬漏電位置的反演為驗(yàn)證本算法反演的有效性及精度，我們?cè)?km2范圍內(nèi)隨機(jī)選取用以正演電位差比例系數(shù)的漏電位置。這些位置坐標(biāo)既包括有理數(shù)，也包括小數(shù)點(diǎn)后保留六位的無理數(shù)。測量電極坐標(biāo)采用O(0，0)，A1(250，0)，A2(400，0)，B1(0，-250)，B2(0，-400)，C(450，-450)。由表4.1可見，本算法對(duì)四次隨機(jī)位置的模擬實(shí)驗(yàn)均顯示出極佳的收斂效果，反演精準(zhǔn)度高，所有模擬實(shí)驗(yàn)均在10步迭代內(nèi)獲得漏電位置的精確數(shù)值解，最大誤差小于10-6，計(jì)算時(shí)間小于20s(初值網(wǎng)格步長設(shè)為50m)。這里需要說明的是，在對(duì)模擬位置的反演過程中我們發(fā)現(xiàn)，計(jì)算可能出現(xiàn)多解的情況(一般不超過三組解)，這主要是由于K值通常為無理數(shù)，計(jì)算產(chǎn)生舍入誤差所致。表4.1四次隨機(jī)位置模擬實(shí)驗(yàn)數(shù)值解及每次實(shí)驗(yàn)迭代步數(shù)及最大誤差模擬實(shí)驗(yàn)漏電點(diǎn)迭代步數(shù)x1y1x2y2最大誤差1.模擬點(diǎn)742.718281830.000000742.718281910.0000006數(shù)值解742.718281830.000000742.718281910.0000000.0000002.模擬點(diǎn)-543.141593325.414214-312.732051432.7182815數(shù)值解-543.141593325.414214-312.732051432.7182810.0000003.模擬點(diǎn)-407.400000-704.800000-443.141593-761.3000004數(shù)值解-407.400000-704.800000-443.141593-761.3000000.0000004.模擬點(diǎn)314.666666-89.222222389.777777-189.2222226數(shù)值解314.666666-89.222222389.777777-189.2222220.000000表4.2高郵漏電實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果漏電電極實(shí)驗(yàn)時(shí)間:6月7日9:00供電時(shí)長:5s觀測次數(shù):5次采樣頻率:10Hz供電電流:2.17AA3B3WE漏電附加電極N1電位差理論K計(jì)算KK差值差值百分比/%a1長26.58964-1.31175640-1.266359730.0453973.46a2短18.33447-0.88125093-0.873198510.0080520.91b1長1.799018-0.08446471-0.085680170.0012151.44b2短2.155615-0.11130994-0.102663450.0086467.77實(shí)際漏電點(diǎn)坐標(biāo)理論K值反演結(jié)果理論誤差(m)計(jì)算K值反演結(jié)果實(shí)際誤差(m)4.2對(duì)臺(tái)站實(shí)際漏電位置的反演為檢驗(yàn)本算法在臺(tái)站實(shí)際漏電定位中的應(yīng)用效能，我們于2016年6月赴江蘇高郵地震臺(tái)做了相關(guān)漏電實(shí)驗(yàn)。高郵地震臺(tái)觀測環(huán)境優(yōu)良，受電磁干擾小，地下介質(zhì)較為均勻，是開展漏電實(shí)驗(yàn)的理想場所。根據(jù)漏電定位模型的原理，實(shí)驗(yàn)采用高郵臺(tái)地電場觀測已有電極作為測量極，同時(shí)借用地電阻率同場觀測的兩個(gè)測量極為附加測量電極(圖4.1中M3、N1電極。注:本方法僅需一個(gè)附加電極，實(shí)驗(yàn)用兩個(gè)電極是為了多獲得一組觀測數(shù)據(jù))進(jìn)行輔助測量;利用電阻率同場觀測的供電極對(duì)地漏電;使用中國地震局地殼應(yīng)力研究所研制的六通道MCDAU-1型數(shù)字采集儀對(duì)測量電極間電位差進(jìn)行采集，該數(shù)字采集儀的采樣頻率為10Hz。目前我國地震臺(tái)站地電阻率觀測采用雙向直流供電，一般單次供電時(shí)長為5～10s。圖4.2為本次實(shí)驗(yàn)使用的數(shù)字采集儀記錄到的由于供電引起的測量電極的電位差跳變。其中圖4.2a為一次漏電實(shí)驗(yàn)的波形記錄圖，每次實(shí)驗(yàn)我們均進(jìn)行5次測量;圖4.2b為單次跳變的波形放大圖，從圖中可以看出，在漏電瞬間的前后0.5s內(nèi)數(shù)據(jù)抖動(dòng)較大，因此在處理跳變電位差時(shí)，選擇變化幅值較小的平