非線性方程的數值解法

1、精選優(yōu)質文檔-傾情為你奉上非線性方程的數值解法摘要：數值計算方法，是一種研究解決數學問題的數值近似解方法，它的計算對象是那些在理論上有解而又無法用手工計算的數學問題。在科學研究和工程技術中都要用到各種計算方法。例如，在地質勘探、汽車制造、橋梁設計、天氣預報和漢字設計中都有計算方法的蹤影。本文討論了非線性方程的數值解法：非線性方程的二分法、迭代法原理、牛頓迭代法，迭代法的收斂性條件及適合非線性方程的插值法等等，基于C語言及MATLAB程序設計，通過實例驗證了非線性方程數值解法的有效性。關鍵字：迭代法 收斂 精度 插值節(jié)點 差商 基函數Abstract：Computing technology o

2、f number value is used to solve the problems of approximate solution of number value in mathematics, its calculated target is that those who have solutions in theory but cant be calculated by hand.Some kinds of computing technologies are used in the scientific research and engineering technologies.

3、For example, there are traces of the computing technology everywhere in geological exploration, car manufacturing, bridge design, weather forecast and Chinese character design.This thesis introduces the value number solution of the non-linear equation and lists the important point of contents and co

4、re calculating formula，Combining the calculating description that discusses some parts of calculating formula. This calculating method can concisely express the operations such as circulation and iteration, which shortens the distance from the method to the computer. The basic contents are composed

5、by the convergence conditions, including the dichotomy of non-linear equation, the iterative method principle, the Newton method, the astringency of the iterative method and interpolation method etc., giving the solid example and procedure in which a calculator tool C language and mathematics softwa

6、re MATLAB are used.Keywords: Iterative Method, Astringency, Precious dimension Interpolation, Primary Function目 錄摘要1第1章 緒論31 1 問題的提出和研究目的和意義312 國內外相關研究綜述313 論文的結構與研究方法3第2章 非線性方程的數值解法421 二分法522迭代法623 迭代法的局部收斂性及收斂的階724 牛頓迭代法725 牛頓法的改進826 插值11第3章 程序設計13基于C語言：牛頓迭代法，弦截法，拉格朗日插值13第4章 程序設計仿真計算結果15基于MATLAB：多

7、元插值15第5章 尚待深入研究的問題17第6章 參考文獻18第7章 致謝18第1章 緒論1 1 問題的提出和研究目的和意義非線性方程的問題在工程實踐中有很多用途，研究其數值解法是當前一個研究方向，目前已有相當一部分算法在廣泛使用于工程實踐中。非線性方程組和無約束最優(yōu)化的數值解法，一直是數值優(yōu)化領域中熱門的研究課題。本文對傳統(tǒng)的方法進行改進和提出新的算法，該算法不僅有重要的理論價值，而且有很高的實用價值。例如：在天體力學中，有如下Kepler（開普勒）方程：x-t-sin x=0,0<<1,其中t表示時間，x表示弧度，行星運動的軌道x是t的函數。也就是說，對每個時刻，上述方程有唯一解

8、（運動軌道位置）。12 國內外相關研究綜述隨著科學技術的高速發(fā)展和計算機的廣泛應用，求解形如F(x)=0的非線性方程組問題越來越多的被提出來了，其中F是的連續(xù)可微函數。例如非線性有限元問題、非線性斷裂問題、彈塑性問題、電路問題、電子系統(tǒng)計算以及經濟與非線性規(guī)劃問題等都可轉化為非線性方程組的求解問題。只要包含有未知函數及其導函數的非線性項的微分方程，無論是用差分方法或有限元方法，離散化后得到的方程組都是非線性方程組。與線性方程組相比,非線性方程組的求解問題無論在理論上還是在解法上都不如線性方程組成熟和有效.例如,非線性方程組是否有解,有多少解,理論上都沒有很好的解法,而對于非線性方程組,除了形式

9、極為特殊的小型方程組以外,直接解法幾乎是不可能的.因而,我們主要考慮迭代解法.一般都是采用線性化的方法去構造各種形式的迭代系列.通常都要討論以下幾個基本問題:第一個問題是,迭代點列的適定性問題,即要求迭代點列是有意義的.例如對于牛頓法,Jacobi矩陣必須是非奇異的.第二個問題,也是最基本的問題,生成的迭代點列的收斂性以及極限點是否為方程組的解.最后一個問題是,迭代點列的收斂速度問題.早在七十年代以前,許多學者在理論上和數值解法上都對非線性方程組做了大量的研究.Ortega Rheinboldt系統(tǒng)的介紹了n階非線性方程組的基本理論成果,并對牛頓法,延拓法等幾種主要迭代法作了詳盡的分析.另外,

10、也有一些學者把非線性方程組的求解問題轉化為極小化問題,得到一類稱為極小化方法的迭代法,如下降法,共軛方向法,Gauss-Newton法等,李,莫&祁詳細介紹了一些適合在計算機上求解的有效算法,如Broyden算法,以及近十幾年來發(fā)展的新方法,如區(qū)間迭代法,單調迭代法和單純形法等.13 論文的結構與研究方法欲解決的主要問題是：1 綜合當前各類非線性方程的數值解法，通過比較分析（1）二分法；（2）迭代法；（3）牛頓雷扶生方法；（4）迭代法的收斂階和加速收斂方法；（5）解非線性方程的插值方法，這以上五種的算法應用，對某個具體實際問題選擇相應的數值解法。2 比較各類數值算法，分析其優(yōu)缺點，并應

11、用到具體的實際問題中。3 利用計算機MATLAB語言對非線性方程的數值解法進行程序設計。研究的基本思路是結合目標所提出的問題針對各種方法來具體分析比較：(1) 二分法 起始區(qū)間a,b必須滿足f(a)與f(b)符號相反的條件。二分法的第一部是選擇中點c=(a+b)/2，然后分析可能存在的三種情況：如果f(a)和f(c)符號相反，則在區(qū)間a,c內存在零點。如果f(c)和f(b)符號相反，則在區(qū)間c,b內存在零點。如果f(c)=0，則c是零點。迭代法 迭代是指重復執(zhí)行一個計算過程，直到找到答案。首先需要有一個用于逐項計算的規(guī)劃或函數g(x)，并且有一個起始。然后通過迭代規(guī)則=g()，可得到序列值。(

12、3)牛頓雷扶生法 如果f(x)，和在根p附近連續(xù)，則可將它作為f(x)的特性，用于開發(fā)產生收斂到根p的序列的算法。而且這種算法產生序列的速度比二分法快。牛頓雷扶生法依賴于和的連續(xù)性，是這類方法中已知的最有用和最好的方法之一。（4）迭代法的收斂階和收斂方法、割線法只計算f(x)，不計算，而且在單根上的收斂階R1.。割線法比牛頓法收斂速度慢一些，牛頓法的收斂階為2。當p是一個M階根時，需要更好的求根技術以獲得比線性收斂更快的速度。最終結果顯示，通過對牛頓法進行改進，可使其在重根的情況下的收斂階為2。加速收斂方法有Aitken加速法和Steffensen加速法。Steffensen算法是促使迭代加速

13、收斂的有效算法，但該算法每算一步，需兩次迭代，其效率不夠高。(5) 解非線性方程的插值方法 Lagrange插值公式需要進行提高插值多項式次數的插值計算是不方便的。這些方法它們各有優(yōu)缺點：二分法的優(yōu)點是對函數f(x)的性態(tài)要求不高，只需連續(xù)即可，且計算程序簡單，能保證收斂。其缺點是收斂速度較慢，且只能求實函數的實零點（單重或奇數重零點）。該方法一般用于確定方程根（或函數實零點）的粗略位置，為快速收斂的算法提供初值。Newton法的主要優(yōu)點是收斂速度快，缺點是其收斂性是局部收斂，要求初始值選在精確解附近才能保證收斂。割線法迭代一次僅需計算函數值f()，可保留作為下次迭代用，且避免了計算導數。第2

14、章 非線性方程的數值解法滿足非線性方程f(x)=0的解x,稱為方程的根或零點。一般用迭代法求非線性方程的根。通常，非線性方程的根不是唯一的，而任何一種方法一次只能算出一個根。因此，在求解非線性方程時，要給定初始條件或求解范圍。根可為實數或復數，也稱為實根或復根。2 1 二分法：二分法是求方程近似解的一種簡單直觀的方法。設函數f(x)在a,b上連續(xù)，且f(a) f(b)<0，則f(x)在a,b上至少有一零點，這是微積分中的介值定理1，也是使用二分法的前提條件。計算中通過對分區(qū)間，縮小區(qū)間范圍的步驟搜索零點的位置。二分法是對逐步搜索法的一種改進。對于有根區(qū)間 a, b , 如果取x0= (a

15、+ b)2, 則 將其分為兩半; 然后通過檢查f () 與f (a)是否同號來判斷根的位置(見圖1)。如此反復二分, 即可得出一系列的有根區(qū)間; 其中,每個區(qū)間都是前一個區(qū)間的一半。當K時, 該區(qū)間的大小趨近于零, 其值便為所求方程f (x) = 0 的根。由此可見, 二分法算法簡單, 在允許的誤差范圍內通過有限次的計算,總能求得方程在該有根區(qū)間的根。圖2-1二分法求根算法：計算f(x)=0的一般計算步驟如下：step1：輸入求根區(qū)間a,b和誤差控制量，定義函數f(x)。 IF（f(a) f(b)0 THEN 做step2 ELSE 退出選用其他求根方法step 2：WHILE（ |a-b|&

16、gt;）計算中點x=(a+b)/2以及f(x)的值；分情況處理| f(x)| ：停止計算x=x,轉向step4f(a) f(x)<0：修正區(qū)間a,x->a,bf(x) f(b)<0: 修正區(qū)間x,b->a,bENDWHILEstep 3: x=(a+b)/2。Step 4:輸出近似根x。二分法的算法簡單，然而，若f(x)在a,b上有幾個零點時，只能算出其中一個零點；另一方面，即使f(x)在a,b上有零點，也未必有f(a) f(b)<0。這就限制了二分法的使用范圍。二分法只能計算方程f(x)=0的實根。22迭代法：對給定的非線性方程f(x)=0，將它轉換成等價形式x

17、=(x)。選取初始值x，構造迭代序列x=(x),k=0,1,；如果序列x x，則f(x)=0。圖2-2定理 若(x)定義在a,b上，如果(x)滿足（1） 當xa,b有a(x)b （2） (x)在a,b上可導，并且存在正數L<1，使對任意的xa,b，有|(x)| L；則在a,b上有唯一的點x滿足x=( x)，稱x為(x)的不動點2。而且迭代格式x=(x)對任意的初值xa,b均收斂于(x)的不動點x，并有誤差估計式| x- x|x-x|事實上，如果x為f(x)的根，只要在（x-，x+），則迭代收斂。2 3 迭代法的局部收斂性及收斂的階：一種迭代過程，只有具備了收斂性，才能表明其迭代的有效性，

18、同時還需要考察其迭代過程的收斂速度3，即其在接近收斂的過程中迭代誤差的下降速度。迭代計算過程不收斂，可能是因為迭代格式本身構造不成功，那么算法必須重新構造；也可能是初值選擇不當，這時往往可通過調整初值解決。下述局部收斂定理可用于將這兩種情況分開。 定理：（局部收斂性）設在x=的根x附近有連續(xù)的一階導數，且，則存在充分靠近x的初值，使收斂于x。設迭代公式x=(x)（k=1,2,）收斂，=（），則是f(x)=0的根。若=M，則成迭代公式是k階方法。24 牛頓迭代法：牛頓法就是將非線性方程線性化的一種方法。給定f(x)=0和初始值x，以(x)為斜率做過點（x，f(x)）的直線，即做f(x)在x點的切

19、線方程：y- f(x)=(x)(x- x)令y=0，則得此切線與x軸的交點x，即x= x- f(x)/(x)。再做f(x)在x處的切線，得交點。繼續(xù)做下去，逐步逼近方程的根。X= x-，k=0,1當是f(x)=0的單根時，牛頓迭代法是2階方法。牛頓迭代法是對f(x)=0做等價形式x=x-,再構造迭代格式：x= x-，k=0,1圖2-3牛頓迭代法的收斂速度明顯快于二分法。牛頓迭代法也有局限性。在牛頓迭代法中，選取適當迭代初始值x是求解的前提，當迭代的初始值x在某根的附近時迭代才能收斂到這個根，有時會發(fā)生從一個根附近跳向另一個根附近的情況，尤其在導數(x)數值很小時。牛頓迭代算法：step1：定義

20、函數f(x)，輸入或定義迭代初始值x_k0和控制精度epsilon。Step2：FOR i=0,1,MAXREPTx_k1:=f(x_k0) /迭代IF (|x_k1-x_k0|<epsilon)THEN輸出滿足給定精度的近似解x_k1，結束x_k0:= x_k1ENDFORstep3:輸出：在x_k0附近f(x)無根。2 5 迭代法的改進：為了說明牛頓法的應用，針對牛頓法的某些特點，我們下面介紹牛頓法的改進和推廣。弦截法：牛頓法的每一步迭代中，都要計算一次導數值，而在計算機上，計算一次導數的近似值比計算函數的近似值要麻煩得多。為了避免求導數，將牛頓迭代公式中的用差商f，x代替，得x=

21、x-，k=1，2這種迭代需要前兩次的迭代結果，初值要取，兩個值。圖2-4弦截法算法：step1:定義函數f(x)，輸入或定義控制精度和迭代初始值，。計算:= ! ，表示，step2: FOR i =0 TO MAXREPT 2.1 := 2.2 newx:=- ! newx表示 2.3 IF （| newx -|<）OR（|f(newx)|< ） THEN輸出滿足給定精度的近似解，結束 2.4 := !為下一次迭代準備數值:=:= newxENDFORStep3:輸出：在初始值，附近f(x)無根。注：！為注釋。下同。與牛頓法的計算量相比，弦截法每迭代一次僅需要計算一次的值，而牛頓法

22、不僅要計算一次的值，還需要計算的值；另一方面，弦截法收斂的階為1.618，牛頓法收斂的階為2。牛頓下山法：牛頓法收斂速度快，但初值不容易確定，往往由于初值取得不當而使迭代不收斂，但若能保證|（稱為下山條件），則有可能收斂。把新的近似值看作初值的話，會比原來取的好，有可能落入局部收斂的鄰域4。設下山因子為，是以與的加權平均作為新的近似解的。先取1，若已滿足，實質上是原來的牛頓法，若不滿足下山條件，取下山因子=/2，判斷是否滿足下山條件，若滿足，就可把作為第K+1次近似值，若還不滿足條件，則使再分半，直到滿足為止。此方法的本質，可以看成是初值的不斷調正，當然，若一開始的初值取得太差了，也還是可能不

23、收斂的。牛頓下山法算法：step1.置初始狀態(tài)：n=0,input ,N,t=1step2.計算step3.IF|,then output ,STOPstep4. IF then ， t=1step5.t=t/2step6.IF (t>) GOTO step 2step7.step8.IF (n<N) t=1step9.output “Method failed after N iterations”,STOP其中,是精度要求，是為了防止無休止地細分t而設的，是為了處理取得太差的情況而設置的，因此可適當取的大一些。N不可取得太大，以防初值跳躍次數太多。26 插值：插值定義：設f(x

24、)是定義在區(qū)間a,b上的連續(xù)函數，是a,b上n+1個互不相同的點，是給定的某一函數類。若上有函數（x），滿足，i =0,1,n則稱（x）為f(x)關于節(jié)點，在上的插值函數，稱，為插值節(jié)點；稱（，f()）(i =0,1,n)為插值型值點，簡稱型值點或插值點5；f(x)稱為被插值函數。拉格朗日（Lagrange）插值多項式：給定（，f()）（i =0,1,n；互不相同），構造次數至多為n的插值多項式： =稱為f(x)關于，的n次拉格朗日插值多項式，它滿足可以證明插值多項式存在并唯一。拉格朗日插值多項式的算法：step1.輸入：插值節(jié)點控制數n，插值點序列（），i =0,1,n，要計算的函數點x。s

25、tep2. FOR i =0,1,n ！i控制拉格朗日基函數序列tmp:=1;2.1 FOR j:=0,1,n! 對于給定x，計算拉格朗日基函數if(j<>i)thentmp:=tmp*; ! tmp表示控制拉格朗日基函數2.2f(x):=fx+tmp* ! 計算=fxstep3.輸出的計算結果fx。插值多項式的截斷誤差： 設是在a,b上關于（，f()）（i =0,1,n；互不相同）的n次插值多項式，f(x)在a,b上有n階連續(xù)導數，在a,b上存在，則插值多項式的截斷誤差為拉格朗日插值多項式的優(yōu)點是格式整齊和規(guī)范，它的缺點是沒有承襲6性質，當需要增加插值節(jié)點時，不得不重新計算所有插

26、值基函數。差商的定義：（1） 設，稱 是f(x)關于的一階差商。F(x)在的零階差商為f=f()。（2） 設點，互不相同，f(x)關于，的k階差商為 f，= 牛頓插值多項式：關于型值點（，f()）（i =0,1,n；互不相同），次數至多為n的牛頓插值多項式為 插值誤差為Hermite插值：拉格朗日（Lagrange）插值僅考慮節(jié)點的函數約束，而一些插值問題還需要在某些節(jié)點具有插值函數與被插值函數導函數值（包括高階導函數值）的一致性。具有節(jié)點的導函數值約束的插值為Hermite插值。第3章 程序設計計算實例：1已知f(x)=-3x-1,取=，x=1.5,用牛頓迭代法計算f(x)的根。#inclu

27、de <stdio.h>#include <math.h>#define iterate(x) (x-(x*x-3)*x-1)/(3*x*x-3)#define x0 1.5 /迭代初值x0#define MAXREPT 1000 /最大迭代次數 #define epsilon 0.0001 /精度void main() int i; double x_k=x0,x_k1=x0; for(i=0;i<MAXREPT;i+) printf(“Got%fn”,x_k1); /滿足精度，輸出 x_k1=iterate(x_k); if(x_k1-x_k<epsil

28、on&&x_k1-x_k>-epsilon) printf(“! Root:%fn”,x_k1);return; x_k=x_k1;printf(“After %d repeat,no solved.n”,MAXREPT);程序輸入輸出： 由本程序預設的f(x)及x=1.5，得到輸出：！Root：1.2用弦截法求方程f(x)=-7.7+19.2x-15.3的根，取=1.5,=4.0。#include <stdio.h>#include <math.h>#define f(x) (x*x*x-7.7*x*x+19.2*x-15.3) /f函數#def

29、ine x0 0.0 /初值x0,x1#define x1 1.0#define MAXREPT 1000 /最大迭代次數#define epsilon 0.00001 /求解精度void main() int i; double x_k=x0,x_k1=x1,x_k2=x1; for(i=0;i<MAXREPT;i+) printf(“Got%fn”,x_k2); x_k2=x_k1-(f(x_k1)*(x_k1-x_k)/(f(x_k1)-f(x_k); /弦截求新x_n if(x_k2-x_k1<epsilon&&x_k2-x_k1>-epsilon)

30、printf(“! Root:%fn”,x_k2); /滿足精度，輸出 return; x_k=x_k1;x_k1=x_k2; /反復 printf(“After %d repeat,no solved.n”,MAXREPT);程序輸入輸出：由本程序的f(x)及，得到輸出：！Root:1.3給定sin=0.,sin=0.,sin13=0.,構造拉格朗日插值函數，計算sin11。#include <stdio.h>#define MAX_N 20 /定義(x_i,y_i)的最大維數typedef struct POINT /點的結構 double x; double y;POINT;

31、void main() int n; int i,j; POINT pointsMAX_N+1;double lMAX_N+1; double x,tmp,lagrange=0; printf(“nInput n value:”); /輸入被插值點的數目 scanf(“%d”,&n); if(n>MAX_N) printf(“The input n is larger then MAX_N,please redefine the MAX_N.n”); return 1; if(n<=0) printf(“Please input a number between 1 and

32、 %d.n”,MAX_N); return 1; printf(“Now input the (x_i,y_i),i=0,%d:n”,n); /輸入被插值點(x_i,y_i)for(i=0;i<=n;i+) scanf(“%lf%lf”,&pointsi.x,&pointsi.y); printf(“Now input the x value:”); /輸入計算拉格朗日插值多項式的x值 scanf(“%lf”,&x); for(i=0;i<=n;i+) for(j=0,tmp=1;j<=n;j+) if(j=i) continue;tmp=tmp*(x

33、-pointsj.x)/(pointsi.x-pointsj.x); lagrange=lagrange+tmp*pointsi.y; /tmp是拉格朗日基函數 printf(“l(fā)agrange(%f)=%fn”,x,lagrange); /輸出 return 0;程序輸入輸出：Input n value:2Now input the (x_i,y_i) ,i=0,2；11 0. 12 0. 13 0.Now input the x value:11.5lagrange(11.)=0.第4章 程序設計仿真計算結果多元插值4：與一元函數類似，可以建立多元函數插值方法。在MATLAB中實現多元插值

34、：定義函數：ZI=interp2(x,y,xi,yi) x,xi為行向量，y,yi為列向量，z為矩陣。使用雙線性插值ZI=interp2(,spline) 使用二元三次樣條插值ZI=interp2(,cubic) 使用二元三次插值WI=interp3(x,y,z,w,xi,yi,zi,) 三元插值在命令窗口中：>> clear;close;x=0:4;y=2:4;>> z=82 81 80 82 84;79 63 61 65 81;84 84 82 85 86;>> subplot(2,2,1);>> mesh(x,y,z);title(RAW

35、DATA);>> xi=0:0.1:4;yi=2:0.1:4;>> zspline=interp2(x,y,z,xi,yi,spline);>> subplot(2,2,2);>> mesh(xi,yi,zspline);>> title(SPLINE);結果見以下圖：圖4-1圖4-1若數據是不規(guī)則的，即 z的數據不完全，不能構成一個矩陣，從而不能直接用interp2插值。第5章 尚待深入研究的問題雖然上述的幾種方法在一定條件下均能求出方程f (x) = 0 在有根區(qū)間的根。但由于方法和原理不同, 計算效果也不相同。而實際的問題特點往往是: 計算過程并不復雜, 但對計算、迭代次數即收斂性有較高要求, 因此需要對以上各方法的收斂性進行比較。對于方程f (x) = 0, 一般引入收斂階數來衡量相應迭代法的收斂速度。如果迭代法收斂, 即有l(wèi)im (當k時) , 其中是方程f (x) = 0 的根。令， 如存在實數和非零常數C, 使得