計算機科學中的重要數(shù)學思想迭代法畢業(yè)設計論文

1、本科畢業(yè)論文（設計）題目： 計算機科學中的重要數(shù)學思想迭代法 計算機科學中的重要數(shù)學思想迭代法摘要 本文將探討數(shù)學中重要的思想方法迭代的實際應用。主要介紹幾種常見問題的迭代方法如：求解非線性方程f(x)=0的不動點迭代、二分法、牛頓迭代法，還有求解線性方程組及非線性方程組的各種迭代法。并對各種迭代法的收斂性進行討論和比較，討論各種迭代法的優(yōu)缺點。在分析結(jié)果的基礎上我們可以看出迭代法的實際應用性很強，對于計算機上的應用尤為突出。研究結(jié)果告訴我們：在具體的應用中要根據(jù)實際情況來選擇不一樣的迭代法，也可以將幾種方法結(jié)合來運用。關鍵詞迭代；收斂性；牛頓法；雅克比迭代；塞德爾迭代；非線性方程；（非）線性

2、方程組。An important Mathematics thought from the computer science- Iteration Method Abstract In this paper, we will discuss an important mathematics thought of iteration method and discuss its realistic application First, I will introduce a lot of iteration method from some natural question ，for exampl

3、e ：the Fixed-point iteration ，the Bisection Method ，Newton method ，and some iteration method of solving linear equation set or not linear equation set。Second ， we will discuss and compare the astringency of those methods 。We will find out the advantages and disadvantages of several methods for itera

4、tion。From analysis the result of iteration method ，we can find it has lots of action in reality，particularly in computer science。According to the analysis result，we get that we use iteration method must base on reality，and also we can combine different method to deal with some problem around us。Keyw

5、ords：astringency；Newton Method；Jacobi iteration；Gauss-Seidel iteration；nonlinear equation；linear or nonlinear equation set。目錄第一章 迭代法4 1.1 迭代法簡介4 1.2 運用迭代法的前提準備4第二章 不動點迭代法5 2.1 不動點的尋找5 2.2 絕對誤差與相對誤差6第三章 二分法8 3.1 波爾查諾二分法8 3.2 試值法的收斂性9第四章 牛頓-拉夫森法與割線法11 4.1 求根的斜率法11 4.2 收斂速度與缺陷13 4.3 割線法與加速收斂16第五章 求線性方程

6、組的迭代法19 5.1 雅克比迭代19 5.2 高斯-塞德爾迭代與收斂性20第六章 非線性方程組的迭代法24 6.1 理論與廣義微分24 6.2 接近不動點處的收斂性25 6.3 賽德爾迭代法與牛頓法26結(jié)束語29主要參考文獻30致謝31 計算機科學中的重要數(shù)學思想迭代法第一章 迭代法1.1 迭代法簡介迭代法也稱輾轉(zhuǎn)法，是一種不斷用變量的舊值遞推新值的過程,跟迭代法相對應的是直接法（或者稱為一次解法），即一次性解決問題。迭代法又分為精確迭代和近似迭代?！岸址ā焙汀芭ｎD迭代法”屬于近似迭代法。迭代法常用于求方程或方程組的近似根。1.2 運用迭代法的前提準備一、確定迭代變量。在可以用迭代算法解決

7、的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量。 二、建立迭代關系式。所謂迭代關系式，指如何從變量的前一個值推出其下一個值的公式（或關系）。迭代關系式的建立是解決迭代問題的關鍵，通?？梢允褂眠f推或倒推的方法來完成。 三、迭代過程進行控制。在什么時候結(jié)束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重復執(zhí)行下去。迭代過程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數(shù)是個確定的值，可以計算出來；另一種是所需的迭代次數(shù)無法確定。對于前一種情況，可以構(gòu)建一個固定次數(shù)的循環(huán)來實現(xiàn)對迭代過程的控制；對于后一種情況，需要進一步分析出用來結(jié)束迭代過程的條件

8、第二章 不動點迭代法2.1 不動點的尋找 我們先探討不動點的存在性和介紹不動點迭代的方法。定義2.1 函數(shù)g（x）的一個不動點是指一個實數(shù)P，滿足P=g（P）。定義2.2 迭代Pn+1=g(Pn),其中n=0，1，稱為不動點迭代定理 2.1 g（x）為連續(xù)函數(shù)且a,b 我們有 g（x）a,b 任意xa,b 則g(x)一定有不動點 則g（x）不動點唯一證明：如果g（a）=a或g（b）=b，則為真；否則g（a）必須滿足g（a） ,g(b)的值必須滿足g（b）。f（x）有如下特性： 對應用中值定理，而且由于常量L=0，可推斷出存在數(shù)P。因此，P=g（P），且P為不動點。 我們可以采用反證法。設存在兩

9、個不動點P1與P2.根據(jù)均值定理，可推斷出存在數(shù)d 根據(jù)假設，有，對前式子簡化得。但這與題意矛盾，故得證P點唯一。下面我們給定一個定理來判斷，迭代所產(chǎn)生的序列是收斂的還是發(fā)散的。定理 2.2 設有如果對于所有將收斂到唯一的不動點P .在這種情況下，P稱為吸引不動點。如果對于所有，有1,則迭代將不會收斂到P，此時P點稱為排斥不動點。我們可以證明定理中的吸引不動點。證：首先要證明Pn都位于（a，b）內(nèi)。從P0開始，可推導出存在一個值C滿足滿足因此，P1比P0更接近于P。同上可以歸納出Pn比Pn-1更接近于P點。所以所有的點都在中。接下來證明。首先用數(shù)學歸納法證明可建立下面的不等式。因此，的極限壓縮

10、在左右2邊的0之間，故=0，這樣就有=p,，所以得證迭代Pn=g（Pn-1）收斂到不動點P例題：設=，且P0=4，找去函數(shù)的不動點。解：設迭代，由P0=4得 P1=3.5 P2=3.25 P3=3.125 由此序列，不難得出P=32.2 絕對誤差與相對誤差 在迭代運算中，迭代結(jié)果與真實值間總存在誤差，我們算誤差方法分為：絕對誤差和相對誤差 絕對誤差： 相對誤差： （其中為真實的結(jié)果，為迭代計算的結(jié)果）第三章 二分法3.1 波爾查諾二分法 先介紹連續(xù)函數(shù)的零點 定義3.1 設是連續(xù)函數(shù)。滿足的任意r成為方程的一個根。也稱r為函數(shù)的零點 二分法是將連續(xù)函數(shù)的區(qū)間進行對分取舍，從而逐步逼近到零點，直

11、到一個任意小的包含零點的間隔 定理3.1 設，且存在實數(shù)滿足。如果與的符號相反，且表示二分法生成的中點序列，則 其中n=0，1 這樣，序列收斂到零點即可表示為 證明：由于零點r和中點都位于區(qū)間內(nèi)，與r之間的距離不會比這個區(qū)間的一半寬度范圍大。這樣，對于所有的n， ，觀察連續(xù)的區(qū)間寬度范圍，可得到 b1-a1=(b0-a0)/2 b2-a2=(b0-a0)/4,使用數(shù)學歸納法很容易得證，結(jié)合上面的式子，我們有 綜上可得證收斂到r，定理得證。 例題：利用二分法尋找函數(shù)的零點，區(qū)間為0,2. 解：起始值=0，=2.計算f（0）=-1 f（2）=0. 所以f（x）的一個根位于0,2內(nèi)在中點C0=1，可

12、發(fā)現(xiàn)f（1）=-0.，因此區(qū)間改變?yōu)镃0,b0=1,2, 接下來從左邊壓縮，使得a1=c0 b1=b0. 中點為c1=1.5按照這種方法，可得到序列，他收斂于1.3.2 試值法的收斂性下面探討試值法又叫試位法。試值法是對二分法的改造，使收斂速度變快。與上述條件一樣，假設和符號相反，如果找到經(jīng)過點和的割線L與x軸的交點（c，0），則可得到一個更好的近似值。為了尋找值x，定義了線L的斜率m的的兩種表示方法，一種為： 另一種方法為：于是我們有= 所以，這樣如果f（a）和f（c）符號相反，則在a，c內(nèi)有一個零點如果f（b）和f（c）符號相反，則在c，b內(nèi)有一個零點如果f（c）=0 ，則c是零點結(jié)合上述

13、過程可構(gòu)造區(qū)間序列，其中每個序列包涵零點。在每一步中，零點r的近似值為 ，而且可以證明序列將收斂到r下面我們來用試值法求解，在區(qū)間0，2中，并觀察它是否比二分法收斂得快解：根據(jù)初始值，可得到f（0）=-1 f（2）=0.，因此在區(qū)間中有一個根。利用試值法，可得到： 。函數(shù)在區(qū)間內(nèi)改變符號，因此從左邊壓縮，設，根據(jù)上面結(jié)論可得到下一個近似值=1.和，下一個判定從右邊壓縮，設我們可以得到通過4次運算，就能算出r1.通過計算我們可以看到試值法比二分法收斂速度快.第四章 牛頓-拉夫森法與割線法4.1 求根的斜率法如果在根p附近連續(xù)，則可將它作為的特性，用于開發(fā)產(chǎn)生收斂到根p的序列的算法。而且這種算法比

14、二分法和試值法產(chǎn)生的序列的速度快，牛頓拉夫森法是這類方法中最好的方法之一設初始值在根P附近。則函數(shù)y=f（x）的圖形與x軸相交于點（p，0），而且點位于靠近點（p，0）的曲線上，將定義為曲線在點的切線與x軸的交點，通過下圖的顯示可以看出比更靠近于p，寫出切線L的兩種表達式，則可得到與的相關方程，如下所示： 解出。重復上述過程可得到序列收斂到p O 定理 4.1 設，且存在數(shù)，滿足。如果，則存在一個數(shù)。對任意初始近似值，使得由如下迭代定義的序列收斂到p： 其中k=1，2注：函數(shù)由如下公式定義 ，并稱為牛頓-拉夫森迭代函數(shù)。由于，這樣尋找函數(shù)的不動點，可以實現(xiàn)尋找方程根的牛頓-拉夫森迭代證明：我們

15、從1階泰勒多項式和它的余項開始分析 這里，位于與x之間。用x=p代入上式，并利用，可得 0=如果足夠逼近p，上式右邊的最后一項比前兩項的和小。因此最后一項可以被忽略，而且可以利用如下近似表達式：，推出。這可以用來定義下一個根的近似值 ，當用在上式的時候，就可以建立一般規(guī)律，即可得證！推論 4.1 求平方根的牛頓迭代：設A為實數(shù)，且A0，而且令0為的初始近似值，使用下列遞推規(guī)則 ，k=1，2定義序列，則序列收斂到，也可表示為。證明：從函數(shù)開始，方程-A=0的根為?，F(xiàn)在利用牛頓-拉夫森函數(shù)中的和，可寫出牛頓-拉夫森迭代公式 簡化為，用此式中的來定義牛頓-拉夫森定理中的遞歸迭代時，結(jié)果得證。例題：用

16、牛頓平方根算法求的近似值。從開始。運用公式計算得： 設，從開始，求 ，所以=2. 都是無限接近與2。4.2 收斂速度與缺陷 通過上面的討論，我們可以得到一個很顯著的性質(zhì)：如果p是f（x）=0的單根，則牛頓法收斂很快，如果p是重根，每個連續(xù)的近似值誤差是前一個誤差的一小部分，我們可以定義收斂階來測量序列的收斂速度定義4.1 設序列收斂到p，并令，。如果兩個常量存在，而且，則該序列稱為以收斂階R收斂到p，數(shù)A稱為漸進誤差常數(shù)。R=1，2的情況為特殊情況如果R=1，稱序列的收斂性為線性收斂如果R=2，稱序列的收斂性為二次收斂。如果R很大，則序列很快收斂到p；這意味著，關系式中對于大的值n，有近似值。

17、例如R=2且，則下面我們用2個例題給出比較（單根的二次收斂）從=-2.4開始，用牛頓-拉夫森迭代求多項式的根p=-2.計算的迭代公式是：解：用R=2并利用收斂階檢查二次收斂，可得到下表中的值0-2.40.0.40.1-2.0.0.0.2-2.0.0.0.3-2.0.0.4-200通過分析上面的收斂速度，可發(fā)現(xiàn)每個連續(xù)迭代的誤差是前一個迭代誤差的一小部分，即，其中，為了檢查上式，利用 和 而且很容易看出（在二重根處線性收斂）從開始用牛頓-拉夫森迭代求多項式的二重根p=1.用收斂階公式檢查線性收斂，可得到下表中的值01.2-0.-0.20.11.-0.-0.0.21.-0.-0.0.31.-0.-

18、0.0.41.-0.-0.0.51.-0.-0.0. 可以看出，牛頓-拉夫森法收斂到二重根，但收斂速度很慢。的值趨近于0更快，因此當時，有定義。序列線性收斂，而且在每次迭代后，誤差以1/2的比例下降。我們總結(jié)下牛頓法在單根和二重根上的性能。定理4.2 （牛頓-拉夫森迭代的收斂速度）設牛頓-拉夫森產(chǎn)生的序列，收斂到函數(shù)的根p，如果p是單根，則是二次收斂，而且對于足夠大的n有如果p是M階多重根，則是線性收斂的，而且對于足夠大的n有值得注意的是：有時序列并不一定收斂，因為并不可能在N此迭代后總能找到結(jié)果，我們可以盡量的通過畫圖等各種方法來選擇P0.例如：設，而且，則 ， ， 而且緩慢發(fā)散到無窮大。4

19、.3 割線法與加速收斂割線法是對牛頓-拉夫森法的改進，它采用了試值法一樣的思想。我們需要2個靠近點的初始點和。定義為經(jīng)過兩個初始點的直線與x軸相交的橫坐標，由圖可以看出P2比P0或P1更靠近于P。p2，p1，p0相關的表示斜率方程為： 所以，根據(jù)兩點迭代公式可得到一般項為單根上的割線法：從=-2.6和=-2.4開始，利用割線法求多項式函數(shù)的根p=-2.解：根據(jù)迭代公式我們得我們得如下的迭代序列0-2.60.20.60.1-2.40.0.40.2-2.0.0.0.3-2.0.0.0.4-2.0.0.0.5-2.0.0.0.6-2.0.0.7-200其中收斂階為R=（）/2=1.618；當P是一個

20、M階根時，我們可以通過對牛頓法改進，使得其在多重根的情況下的收斂階為2定理4.3（牛頓-拉夫森迭代的加速收斂）設牛頓-拉夫森算法產(chǎn)生的序列線性收斂到根x=p，其中M1，則牛頓-拉夫森迭代公式 將產(chǎn)生一個收斂序列二次收斂到p。（二重根情況下的加速收斂）從p0=1.2開始，使用加速牛頓-拉夫森迭代求函數(shù)的二重根p=1 解：由于M=2，加速公式變?yōu)?可得到下表中的值K01.2-0.-0.20.11.-0.-0.0.21.-0.-0.31.0.0.很容易看出收斂速度變快。第五章 求線性方程組的迭代法下面來探討將解非線性方程的迭代擴展到更高維數(shù)中，有什么規(guī)律與方法？5.1 雅克比迭代首先我們考慮線性方程

21、組的不動點迭代的擴展考慮如下方程組：4x- y+z= 7 4x-8y+z=-21 -2x+ y+5z=15 上述方程可表示成如下形式：x=y= 這樣我們就可以提出下列雅克比迭代過程：z= 如果從p0=（x0，y0，z0）=（1，2，2）開始，則上式中的迭代將收斂 到解（2，4，3）上述迭代過程將會產(chǎn)生序列，并收斂于原方程組的解。我們稱這個過程為雅克比迭代在求解偏微分方程時，線性方程組經(jīng)常多達10000個變量。這些方程組的系數(shù)矩陣是稀疏矩陣，這時用迭代過程是求解這些大型方程組的有效方法。定理5.1 設有維矩陣A，如果 其中k=1，2，N，則稱A具有嚴格對角優(yōu)勢。 這表示在矩陣的每一行中，主對角線

22、上的元素的絕對值大于其他元素的絕對值的和?，F(xiàn)在使雅克比迭代過程一般化。設有如下線性方程組： 設第k點為，則下一點為。坐標的上標（k）可用來標識屬于這一點的坐標。迭代公式根據(jù)前面的值，使用上面的線性方程組中的第j行求解式。雅克比迭代：=其中j=1，2，N。 雅克比迭代使用所有舊坐標來生成新坐標，而我們下面介紹的高斯-賽德爾迭代盡可能使用新坐標得到更新的坐標。定理5.2（雅克比迭代） 設矩陣A具有嚴格對角優(yōu)勢，則AX=B有唯一解X=P。迭代式可產(chǎn)生一個向量序列，而且對于任意初始向量，向量序列都將收斂到5.2 高斯-塞德爾迭代與收斂性有時通過其他方法可以使收斂速度加快。我們觀察雅克比迭代。由于比更加

23、接近于x，所以在計算時用來替換是合理的，同理，可以用和計算，這種迭代方法就是高斯-賽德爾迭代我們運用式中給定的一般線性方程組有： 其中j=1，2，N。例題：利用上面給的線性方程組用高斯-賽德爾迭代過程求解 如果從P0=（x0，y0，z0）=（1，2，2）開始，用上式中的迭代可收斂到解（2，4，3）我們把計算結(jié)果列表得：KXkYkZk 0 1.0 2.0 2.0 1 1.75 3.75 2.95 2 1.95 3.96875 2.98625 3 1. 3. 2. 8 1. 3. 2. 9 1. 3. 3. 10 2. 4. 3. 下面我們來探討收斂性：比較向量之間的距離是很重要的，它可以用來判斷

24、是否收斂到P。P=(x1,x2,xn)和Q（y1,y2,yn）之間的歐幾里得距離為它的缺點是需要相當大的計算量，因此引入另一種范數(shù)，： 下面的結(jié)論保證了上述范數(shù)具有度量的數(shù)學結(jié)構(gòu)，因此適合作為一個一般化的距離公式。根據(jù)線性代數(shù)的理論可知，如果兩個向量的范數(shù)接近，則它們的歐幾里得范數(shù)也接近定理5.3 設X和Y是N維向量，c是一個標量。則函數(shù)有如下性質(zhì)： ； =0，當且僅當X=0 ； 。上面很容易證明，我們證一下最后一個。證明：對于每個j，實數(shù)的三角不等式表示為。根據(jù)這些不等式可以得證上述不等式?？梢杂弥械亩x的范數(shù)來定義兩點之間的距離定義5.1 設X和Y是N維空間中的中點?？啥xX和Y的距離為范

25、數(shù)，表示為 例題：計算點P=（2，4，3）和Q=（1.75，3.75，2.95）的歐幾里得距離和距離解：歐幾里得距離為=0.3570 距離為=0.55 更容易計算，常用來確定N維空間的收斂性第六章 非線性方程組的迭代法6.1 理論與廣義微分定義6.1（雅克比矩陣） 設和是包含自變量x和y的函數(shù)，則它們的雅克比矩陣J（x，y）表示為 同理如果，是包含自變量x，y，z的函數(shù)，則雅克比矩陣J（x，y，z）定義為 。 例題：對下列函數(shù)求解在點（1，3，2）處的維雅克比矩陣J（x，y，z） 解：雅克比矩陣為 這樣在點（1，3，2）處的雅克比矩陣為矩陣下面介紹廣義微分對于含多個變量的函數(shù)，微分用來表示自變

26、量的變化情況如何影響因變量。設有如下表達式， ， 設已知表達式中函數(shù)在點處的值，現(xiàn)在希望可以預測在臨近點（x，y，z）處的值。設 。如果使用向量表示，則關系式可通過雅克比矩陣進行簡化。函數(shù)的變化用表示，變量的變化用表示。6.2 接近不動點處的收斂性定義6.2 包含2個方程， 的方程組的不動點是點（p，q），滿足。在三維情況下，方程組，的不動點是點（p,q,r）滿足定義6.3 對于方程組中的函數(shù)，不動點迭代為 ， 對于方程組中的函數(shù)，不動點迭代為 ， 其中k=0，1定理6.1（不動點迭代）設方程組中的函數(shù)和它們的一階偏導數(shù)分別在包含（p，q）或（p，q，r）的區(qū)域內(nèi)連續(xù)。如果初始點值足夠接近不動

27、點，則有下面2種情況（二維）如果足夠接近（p，q）而且 則迭代收斂到不動點（p，q）（三維）如果足夠接近（p，q，r），而且 則迭代將收斂到不動點（p，q，r）如果上述條件不滿足，則迭代可能發(fā)散6.3 賽德爾迭代法與牛頓法現(xiàn)在可以構(gòu)造一個與高斯-賽德爾法類似的改進型不動點迭代法，設用計算（在三維情況下，用和，計算），并將這些改進融入公式和中時，這個方法稱為賽德爾迭代 以及 下面我們把牛頓法擴展到二維空間設有方程組 它意味著從xy平面到w平面的轉(zhuǎn)換。這里只關心在點處的變換行為，即點。如果兩個函數(shù)有連續(xù)的偏導，則在點處用微分表示下列線性近似方程組是合法的 方程組是一個局部線性變換，它將自變量的微小變化聯(lián)系起來。當使用雅克比矩陣時，這個關系可更容易地表示為： 如果方程組用向量函數(shù)V=F（X）表示，這個雅克比矩陣是導數(shù)的二維