非線性方程的數(shù)值解法

1、 計(jì) 算 方 法 期 末 論 文論文題目非線性方程的數(shù)值解法學(xué) 院 專 業(yè) 班 級 姓 名 學(xué) 號 指 導(dǎo) 教 師 日 期 目 錄摘要第1 章 緒論1.1 問題的提出和研究目的和意義1.2 國內(nèi)外相關(guān)研究綜述1.3 論文的結(jié)構(gòu)與研究方法第2 章 非線性方程的數(shù)值解法2.1 二分法2.2 迭代法2.3 迭代法的局部收斂性及收斂的階2.4 牛頓迭代法 2.5 牛頓法的改進(jìn)2.6 插值摘要數(shù)值計(jì)算方法，是一種研究解決數(shù)學(xué)問題的數(shù)值近似解方法，它的計(jì)算對象是那些。在理論上有解而又無法用手工計(jì)算的數(shù)學(xué)問題。在科學(xué)研究和工程技術(shù)中都要用到各種計(jì)算方法。例如在地質(zhì)勘探、汽車制造、橋梁設(shè)計(jì)、天氣預(yù)報(bào)和漢字設(shè)計(jì)

2、中都有計(jì)算方法的蹤影。本文討論了非線性方程的數(shù)值解法：非線性方程的二分法、迭代法原理、牛頓迭代法，迭代法的收斂性條件及適合非線性方程的插值法等等。第1 章 緒論可以證明插值多項(xiàng)式L (x) n 存在并唯一。拉格朗日插值多項(xiàng)式的算法step1.輸入插值節(jié)點(diǎn)控制數(shù)n插值點(diǎn)序列 i i x , y i=0,1,n要計(jì)算的函數(shù)點(diǎn)x。step2. FOR i =0,1,n i 制拉格朗日基函數(shù)序列問題的提出和研究目的和意義非線性方程的問題在工程實(shí)踐中有很多用途研究其數(shù)值解法是當(dāng)前一個(gè)研究方向。目前已有相當(dāng)一部分算法在廣泛使用于工程實(shí)踐中。非線性方程組和無約束最優(yōu)化的數(shù)值解法一直是數(shù)值優(yōu)化領(lǐng)域中熱門的研究

3、課題。本文對傳統(tǒng)的方法進(jìn)行改進(jìn)和提出新的算法該算法不僅有重要的論價(jià)值，而且有很高的實(shí)用價(jià)值。例如在天體力學(xué)中，有如下Kepler開普勒方程x-t- sin x=0,0 1,其中t 表示時(shí)間x 表示弧度，行星運(yùn)動(dòng)的軌道x 是t 的函數(shù)。也就是說，對每個(gè)時(shí)刻i t 上述方程有唯一解i x ，運(yùn)動(dòng)軌道位置。國內(nèi)外相關(guān)研究綜述隨著科學(xué)技術(shù)的高速發(fā)展和計(jì)算機(jī)的廣泛應(yīng)用求解形如F(x)=0 的非線性方程組問題越來越多的被提出來了其中F 是的連續(xù)可微函數(shù)。例如非線性有限元問題、非線性斷裂問題、彈塑性問題、電路問題、電子系統(tǒng)計(jì)算以及經(jīng)濟(jì)與非線性規(guī)劃問題等都可轉(zhuǎn)化為非線性方程組的求解問題。只要包含有未知函數(shù)及其

4、導(dǎo)函數(shù)的非線性項(xiàng)的微分方程，無論是用差分方法或有限元方法，離散化后得到的方程組都是非線性方程組。與線性方程組相比,非線性方程組的求解問題無論在理論上還是在解法上都不如線性方程組成熟和有效.例如,非線性方程組是否有解,有多少解,理論上都沒有很好的解法,而對于非線性方程組,除了形式極為特殊的小型方程組以外,直接解法幾乎是不可能的.因而,我們主要考慮迭代解法.一般都是采用線性化的方法去構(gòu)造各種形式的迭代系列.通常都要討論以下幾個(gè)基本問題:第一個(gè)問題是,迭代點(diǎn)列的適定性問題,即要求迭代點(diǎn)列是有意義的.例如對于牛頓法,Jacobi 矩陣必須是非奇異的.第二個(gè)問題,也是最基本的問題,生成的迭代點(diǎn)列的收斂性

5、以及極限點(diǎn)是否為方程組的解.最后一個(gè)問題是,迭代點(diǎn)列的收斂速度問題.早在七十年代以前,許多學(xué)者在理論上和數(shù)值解法上都對非線性方程組做了大量的研究.Ortega Rheinboldt 系統(tǒng)的介紹了n 階非線性方程組的基本理論成果,并對牛頓法,延拓法等幾種主要迭代法作了詳盡的分析.另外,也有一些學(xué)者把非線性方程組的求解問題轉(zhuǎn)化為極小化問題, 得到一類稱為極小化方法的迭代法, 如下降法, 共軛方向法,Gauss-Newton 法等,李,莫&祁詳細(xì)介紹了一些適合在計(jì)算機(jī)上求解的有效算法,如Broyden 算法,以及近十幾年來發(fā)展的新方法,如區(qū)間迭代法,單調(diào)迭代法和單純形法等.論文的結(jié)構(gòu)與研究方法1.欲

6、解決的主要問題是：綜合當(dāng)前各類非線性方程的數(shù)值解法，通過比較分析，二分法，迭代法，牛頓雷扶生方法，迭代法的收斂階和加速收斂方法，解非線性方程的插值方法，這以上五種的算法應(yīng)用對某個(gè)具體實(shí)際問題選擇相應(yīng)的數(shù)值解法。2.比較各類數(shù)值算法分析其優(yōu)缺點(diǎn)并應(yīng)用到具體的實(shí)際問題中。3利用計(jì)算機(jī)MATLAB 語言對非線性方程的數(shù)值解法進(jìn)行程序設(shè)計(jì)。研究的基本思路是結(jié)合目標(biāo)所提出的問題針對各種方法來具體分析比較(1) 二分法 起始區(qū)間a,b必須滿足f(a)與f(b)符號相反的條件。二分法的第一部是選擇中點(diǎn)c=(a+b)/2，然后分析可能存在的三種情況如果f(a)和f(c)符號相反，則在區(qū)間a,c內(nèi)存在零點(diǎn)。如果

7、f(c)和f(b)符號相反則在區(qū)間c,b內(nèi)存在零點(diǎn)。如果f(c)=0，則c是零點(diǎn)。（2）迭代法 迭代是指重復(fù)執(zhí)行一個(gè)計(jì)算過程，直到找到答案。首先需要有一個(gè)用于逐項(xiàng)計(jì)算的規(guī)劃或函數(shù)g(x)，并且有一個(gè)起始po。然后通過迭代規(guī)則k 1 p =g( k p )，可得到序列值 k p 。(3)牛頓雷扶生法 如果f(x) f (x)和f (x)在根p 附近連續(xù)則可將它作為f(x)的特性,用于開發(fā)產(chǎn)生收斂到根p 的序列 k p 的算法。而且這種算法產(chǎn)生序列 k p 的速度比二分法快。牛頓雷扶生法依賴于f(x)和f (x)的連續(xù)性,是這類方法中已知的最有用和最好的方法之一。(4)迭代法的收斂階和收斂方法、割

8、線法只計(jì)算f(x)不計(jì)算f (x)而且在單根上的收斂階R 1.。割線法比牛頓法收斂速度慢一些牛頓法的收斂階為2。當(dāng)p 是一個(gè)M 階根時(shí)需要更好的求根技術(shù)以獲得比線性收斂更快的速度。最終結(jié)果顯示通過對牛頓法進(jìn)行改進(jìn)可使其在重根的情況下的收斂階為2。加速收斂方法有Aitken 加速法和Steffensen 加速法。Steffensen 算法是促使迭代加速收斂的有效算法,但該算法每算一步,需兩次迭代,其效率不夠高。(5) 解非線性方程的插值方法 Lagrange 插值公式需要進(jìn)行提高插值多項(xiàng)式次數(shù)的插值計(jì)算是不方便的。這些方法它們各有優(yōu)缺點(diǎn)二分法的優(yōu)點(diǎn)是對函數(shù)f(x)的性態(tài)要求不高,只需連續(xù)即可,且

9、計(jì)算程序簡單,能保證收斂。其缺點(diǎn)是收斂速度較慢且只能求實(shí)函數(shù)的實(shí)零點(diǎn)單重或奇數(shù)重零點(diǎn)。該方法一般用于確定方程根或函數(shù)實(shí)零點(diǎn)的粗略位置,為快速收斂的算法提供初值。Newton 法的主要優(yōu)點(diǎn)是收斂速度快,缺點(diǎn)是其收斂性是局部收斂,要求初始值0 x 選在精確解* x 附近才能保證收斂。割線法迭代一次僅需計(jì)算函數(shù)值f( k x )可保留作為下次迭代用,且避免了計(jì)算導(dǎo)數(shù)。第2 章 非線性方程的數(shù)值解法滿足非線性方程f(x)=0 的解x ,稱為方程的根或零點(diǎn)。一般用迭代法求非線性方程的根。通常,非線性方程的根不是唯一的,而任何一種方法一次只能算出一個(gè)根。因此,在求解非線性方程時(shí),要給定初始條件或求解范圍。

10、根可為實(shí)數(shù)或復(fù)數(shù),也稱為實(shí)根或復(fù)根。二分法二分法是求方程近似解的一種簡單直觀的方法。設(shè)函數(shù)f(x)在a,b上連續(xù),且f(a)f(b)計(jì)算中點(diǎn)x=(a+b)/2 以及f(x)的值;分情況處理 | f(x)| 停止計(jì)算x =x,轉(zhuǎn)向step4f(a) f(x)a,bf(x) f(b)a,bENDWHILEstep 3: x =(a+b)/2。Step 4:輸出近似根x 。二分法的算法簡單然而若f(x)在a,b上有幾個(gè)零點(diǎn)時(shí)只能算出其中一個(gè)零點(diǎn)另一方面即使f(x)在a,b上有零點(diǎn).也未必有f(a) f(b)B，BA交替出現(xiàn)。但現(xiàn)在假設(shè)軍中有一個(gè)膽小鬼，同時(shí)大家又都很照顧他，每次沖鋒都是讓他跟在后面，

11、每當(dāng)前面的人占據(jù)一個(gè)新的位置，就把位置交給他，然后其他人再往前占領(lǐng)新的位置。也就是A始終在B的前面，A向前邁進(jìn)，B跟上，A把自己的位置交給B（即執(zhí)行B = A操作），然后A 再前進(jìn)占領(lǐng)新的位置，B再跟上直到占領(lǐng)所有的陣地，前進(jìn)結(jié)束。像這種兩個(gè)數(shù)一前一后逐步向某個(gè)位置逼近的方法稱之為迭代法。 迭代法也稱輾轉(zhuǎn)法，是一種不斷用變量的舊值遞推新值的過程,跟迭代法相對應(yīng)的是直接法（或者稱為一次解法），即一次性解決問題。迭代算法是用計(jì)算機(jī)解決問題的一種基本方法。它利用計(jì)算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn)，讓計(jì)算機(jī)對一組指令（或一定步驟）進(jìn)行重復(fù)執(zhí)行，在每次執(zhí)行這組指令（或這些步驟）時(shí)，都從變量的原值推

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

13、情況，可以構(gòu)建一個(gè)固定次數(shù)的循環(huán)來實(shí)現(xiàn)對迭代過程的控制；對于后一種情況，需要進(jìn)一步分析出用來結(jié)束迭代過程的條件。 最經(jīng)典的迭代算法是歐幾里德算法，用于計(jì)算兩個(gè)整數(shù)a,b的最大公約數(shù)。其計(jì)算原理依賴于下面的定理： 定理：gcd(a, b) = gcd(b, a mod b) 證明：a可以表示成a = kb + r，則r = a mod b 。假設(shè)d是a,b的一個(gè)公約數(shù)，則有 a%d=0, b%d=0，而r = a - kb，因此r%d=0 ，因此d是(b, a mod b)的公約數(shù) 同理，假設(shè)d 是(b, a mod b)的公約數(shù)，則 b%d=0 , r%d=0 ，但是a = kb +r ，因此

14、d也是(a,b)的公約數(shù) 。 因此(a,b)和(b,a mod b)的公約數(shù)是一樣的，其最大公約數(shù)也必然相等，得證。 歐幾里德算法就是根據(jù)這個(gè)原理來做的，歐幾里德算法又叫輾轉(zhuǎn)相除法，它是一個(gè)反復(fù)迭代執(zhí)行，直到余數(shù)等于0停止的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)。其算法用C語言描述為： int Gcd_2(int a, int b)/ 歐幾里德算法求a, b的最大公約數(shù) if (a=0 | b 0) /b總是表示較小的那個(gè)數(shù)，若不是則交換a，b的值 temp = a % b; /迭代關(guān)系式 a = b; /是那個(gè)膽小鬼，始終跟在b的后面 b = temp; /向前沖鋒占領(lǐng)新的位置 return a; 從

15、上面的程序我們可以看到a，b是迭代變量，迭代關(guān)系是temp = a % b; 根據(jù)迭代關(guān)系我們可以由舊值推出新值，然后循環(huán)執(zhí)a = b; b = temp;直到迭代過程結(jié)束（余數(shù)為0）。在這里a好比那個(gè)膽小鬼，總是從b手中接過位置，而b則是那個(gè)努力向前沖的先鋒。 還有一個(gè)很典型的例子是斐波那契(Fibonacci)數(shù)列。斐波那契數(shù)列為：0、1、1、2、3、5、8、13、21、，即 fib(1)=0; fib(2)=1; fib(n)=fib(n-1)+fib(n-2) (當(dāng)n2時(shí))。 在n2時(shí)，fib(n)總可以由fib(n-1)和fib(n-2)得到，由舊值遞推出新值，這是一個(gè)典型的迭代關(guān)系，所以我們可以考慮迭代算法。 int Fib(int n)