信息與計算科學-求解非線性方程組的幾種迭代方法的理論及應用案例論文

[8]，一般而言，牛頓迭代法的收斂性依賴于初值x0的選取，如果x0的選取偏離精確解，則牛頓迭代法可能會發(fā)散。為了防止發(fā)散，常常對迭代過程額外加上一項要求，用來保證函數(shù)數(shù)值的單調下降：f滿足這項要求的算法被稱作下山法。牛頓下山法的迭代公式如下：xk+1=xk將λ稱為下山因子，且0<λ≤1。λ值的選取滿足λ=1有關牛頓下山法的基本算法實現(xiàn)流程：首先給定x的初值x0，精度要求ε，最大迭代次數(shù)N與下山因子λ=1，設一個迭代次數(shù)初值；然后用牛頓迭代公式x1=x0-fx0f'x0，得到x12.5不動點迭代法假設存在n個未知數(shù)與n個方程的某個非線性方程組化簡后為Fx=0，再將方程組更改為方便迭代的一種等價形式x=φx，有φ：D?Rn→Rn。若x*∈D滿足x*=φx*，則稱x*為函數(shù)φx的不動點。所以，φx的不動點就是非線性方程組再選取合適的初始向量x0∈D，將之構成迭代公式xk+1=φxk，k=0，1不動點迭代法的基礎定理采用的是壓縮映射原理，假設φ：D?Rn→φ把D0映入它自身，即φφ在D0上是壓縮映射，即存在常數(shù)L∈0，φ所以可得出以下的相關結論：對任意取得的x0∈D0，通過迭代公式xk+1=φxk，創(chuàng)建誤差估計式x*-xkx*-xk關于不動點迭代法的局部收斂定理，設φ：D?Rn→Rn，x*∈intD是方程組Fx=0的解，在x*可微。若φ'x對于不動點迭代法xk+1=φxk+1-x*xk+1-xk由于φ'x≤Lx=L≤Lxx≤??≤由于L<1，limk→∞xk-x*=0xk-x*不動點迭代法需要注意等價形式的選擇，如果選擇不當，迭代結果會越來越大，不能趨近于某個極限，這樣一個發(fā)散的迭代過程是沒有價值的。不動點迭代法原理見圖3所示：圖3不動點迭代法簡略理解圖有關不動點迭代法的基本算法實現(xiàn)流程：首先將方程fx等價的轉化稱方程x=φx，由此建立不動點迭代公式x1=φx0，將給定的初值x0代入其中得到x3.幾種常用的求解非線性方程組的迭代方法數(shù)值實例3.1牛頓迭代法對于牛頓迭代法解非線性方程組的數(shù)值應用實例，列舉了如下一個二元二階非線性方程組：2求解這個非線性方程組，給定它的初值x0=-1，y0=1，設定它的誤差精度為10-10，用C語言編程模擬它的迭代過程，最終給出該非線性方程組的近似解。誤差精度值不變，更改所給定的初值，使之更貼近方程組的解，設x0=0，y0=1。改變后的編譯的結果顯示，它經(jīng)歷了若不更改初值，將它的誤差精度值改為10-5，改變后的編譯的結果顯示，它經(jīng)歷了15次迭代，歷時不到一毫秒得到方程組的解為：x=-0.26528046490022428,y=0.802002181053570573.2簡化牛頓法用簡化牛頓迭代法計算非線性方程組，用C語言編程模擬它的迭代過程，最終給出該非線性方程組的近似解。編譯的結果顯示，它經(jīng)歷了54次迭代，歷時10毫秒得到方程組的解為：x=-0.26527251509605621,y=0.80200384302780292。同樣保持誤差精度值不變，更改所給定的初值，使之更貼近方程組的解，設x0=0，y0=1。改變后的編譯的結果顯示，它經(jīng)歷了同樣若不更改初值，將它的誤差精度值改為10-5，改變后的編譯的結果顯示，它經(jīng)歷了24次迭代，歷時不到一毫秒得到方程組的解為：x=-0.26528979753965148,3.3牛頓弦截法用牛頓弦截法計算非線性方程組，用C語言編程模擬它的迭代過程，最終給出該非線性方程組的近似解。編譯的結果顯示，它經(jīng)歷了72次迭代，歷時14毫秒得到方程組的解為：x=-0.26527251508431543,y同樣保持誤差精度值不變，更改所給定的初值，使之更貼近方程組的解，設x0=0，y0=1。改變后的編譯的結果顯示，它經(jīng)歷了同樣若不更改初值，將它的誤差精度值改為10-5，改變后的編譯的結果顯示，它經(jīng)歷了36次迭代，歷時3毫秒得到方程組的解為：x=-0.26538823618029506,3.4不動點迭代法對于不動點迭代法解非線性方程組的數(shù)值應用實例，列舉了如下一個三角函數(shù)非線性方程組：3x求解這個非線性方程組，給定它的初值x0=1，y0=1，設定它的誤差精度為10-12，用C語言編程模擬它的迭代過程，最終給出該非線性方程組的近似解。編譯的結果顯示，它經(jīng)歷了27對這個三角函數(shù)非線性方程組，用牛頓迭代法對它也進行編譯，使之與不動點迭代法所產(chǎn)生的結果進行對比，C語言牛頓迭代法編譯的結果顯示，它經(jīng)歷了58次迭代，歷時9毫秒得到方程組的解為：x=0.41516942713962368,y保持精度不變，改變初值大小，將初值設為x0=0，y0=0，改變后的編譯的結果顯示，它經(jīng)歷了繼續(xù)保持精度不變，改變初值為x0=100，y0=100，改變后的編譯的結果顯示，它經(jīng)歷了26次迭代，歷時保持初值不變，將精度改為10-5，改變后的編譯的結果顯示，它經(jīng)歷了11次迭代，歷時不到一毫秒得到方程組的解為：x=0.41516897278745452,保持初值不變，將精度改為10-20，改變后的編譯的結果顯示，它經(jīng)歷了37次迭代，歷時4毫秒得到方程組的解為：x=0.41516942713927385,3.5結果對比分析關于二元二階非線性方程組2x表1三種迭代方法結果對比表近似解x近似解y迭代次數(shù)牛頓迭代法-0.265272514922748950.8020038430510502131簡化牛頓迭代法-0.265272515096056210.8020038430278029254牛頓弦截法-0.265272515084315430.8020038431811372772保持精度不變，改變初值后三種迭代方法對比表如下所示：表2改變初值后三種迭代方法結果對比表近似解x近似解y迭代次數(shù)牛頓迭代法-0.265272514943998010.802003843046608126簡化牛頓迭代法-0.265272514897307960.8020038430782816523牛頓弦截法-0.265272515021787170.8020038431599900722保持初值不變，改變精度后三種迭代方法對比表如下所示：表3改變精度后三種迭代方法結果對比表近似解x近似解y迭代次數(shù)牛頓迭代法-0.265280464900224280.8020021810535705715簡化牛頓迭代法-0.265289797539651480.8020012656908955824牛頓弦截法-0.265388236180295060.801990258664471636關于三角函數(shù)非線性方程組3x-表4關于三角函數(shù)非線性方程組相關結果對比表近似解x近似解y迭代次數(shù)不動點迭代法0.415169427139194750.336791217025349227牛頓迭代法0.415169427139623680.3367912170250437258不動點迭代法初值更改接近解0.415169427139335080.3367912170252405626不動點迭代法初值更改遠離解0.415169427139161220.3367912170253751226不動點迭代法誤差精度調大0.415168972787454520.3367915689078352411不動點迭代法誤差精度調小0.415169427139273850.3367912170252879737關于二元二階非線性方程組2x2-x牛頓迭代法的迭代次數(shù)最少，牛頓弦截法的迭代次數(shù)最多。但當保持誤差精度不變，改變它的初值，使之更加接近方程組的近似解時，牛頓弦截法的迭代次數(shù)最少，牛頓迭代法的迭代次數(shù)最多，而且三種迭代算法的迭代次數(shù)都有明顯減少。當保持初值不變，調大對它的誤差精度要求，三種迭代算法的迭代次數(shù)也有明顯減少。關于三角函數(shù)非線性方程組3x-cosx將不動點迭代法與牛頓迭代法結果進行比較，不動點迭代法的迭代次數(shù)遠小于牛頓迭代法的迭代次數(shù)。保持不動點迭代法的誤差精度不變，改變其初值，發(fā)現(xiàn)無論怎樣改變初值大小，不動點迭代法的迭代次數(shù)基本維持不變。保持不動點迭代法的初值不變，將誤差精度調大，迭代次數(shù)減少，將誤差精度調小，迭代次數(shù)變大。通過以上的這些比較發(fā)現(xiàn)初值與精度的選取對求解非線性方程組有很大的影響，沒一點的小改動都可能使你的結果相差甚遠。降低對其精度的要求都能使得迭代次數(shù)的減少，提高精度要求也使得迭代次數(shù)的增加。當你的初值選取越靠近精確解時，你所需的迭代次數(shù)也在減少，但初值的選取對不動點迭代法迭代次數(shù)的增減沒有明顯的改變。本次論文主要分成了兩個非線性方程組進行迭代算法的研究和比較。第一組實驗（見表1，2，3）比較了牛頓迭代法和它的兩個改進后的迭代方法，首先假定一個初值進行帶入編程計算，將所得結果比較后，得到結論第一次比較牛頓迭代法的迭代次數(shù)最少，計算效率最高，牛頓弦截法的迭代次數(shù)最多，計算效率最差。本次實驗不動點迭代法的迭代效率比牛頓迭代法的迭代效率更高，但是當將它的初值結果改成最接近精確解后再計算結果，結果發(fā)生巨大轉變，牛頓弦截法迭代次數(shù)最少，計算效率最高，牛頓迭代法所用迭代次數(shù)最多，計算效率最差。之后又進行了精度改變的實驗，當誤差精度的要求放低后，實驗的三個迭代算法所用迭代次數(shù)都普遍減少了，但依舊牛頓迭代法計算效率最高，簡化牛頓迭代法次之，牛頓弦截法最低。第二組實驗（見表4）先比較了牛頓迭代法和不動點迭代法的差別，然后對不動點迭代法自身變量的改變進行了比較。在第一次比較中，不動點迭代法的迭代次數(shù)遠小于牛頓迭代法的跌打次數(shù)，效率更高。在初值與誤差精度的調整實驗中，我發(fā)現(xiàn)在同一精度條件下，無論初值調整為多少時，它的非線性方程組的解都沒有太大差別。但是，當誤差精度調大時，所用迭代次數(shù)變少，提高了計算效率，當誤差精度調小時，所用迭代次數(shù)變多，計算效率也下降了。4.總結與思考4.1內容總結本文主要介紹的是求解非線性方程組的幾種迭代方法的理論及數(shù)值應用案例。求解非線性方程組的迭代方法，它的基本思想就是通過一次又一次的求解，不斷逼近精確解。迭代方法例如牛頓迭代法，簡化牛頓迭代法，牛頓弦截法，牛頓下山法和另一種不動點迭代法。本文簡單介紹了它們的算法流程并選取了其中幾個算法進行C語言編程求解，再對它們的結果進行比較分析。如今，社會在不斷進步，科技在不斷發(fā)展，很多領域都需要求解非線性方程組，其中牛頓迭代法是最常用的求解方式，根據(jù)不同的情況，對牛頓迭代法進行修飾，改進。由上文的一些數(shù)值實例可以看出這些迭代法的一些優(yōu)勢與缺點。在同一初值，同一誤差精度的條件下，若是初值非常接近精確解，牛頓弦截法的迭代次數(shù)最少，計算效率最高，簡化牛頓法情況次之，牛頓迭代法計算效率最低。若是初值遠離精確解，情況就會倒過來，牛頓弦截法的計算效率最低，牛頓迭代法的計算效率最高。不動點迭代法與牛頓迭代法的比較過程中，不動點迭代法的迭代效率要高于牛頓迭代法。在同一精度下，初值的改變不會影響不動點迭代法的計算結果，然而在同一初值下，誤差精度要求變低時，所用的迭代次數(shù)也會減少，相反就會增多。4.2思考除卻一些常用的求解非線性方程組的迭代方法，還有對迭代法加速，多步迭代法等。在日常生活中，不只有普通的非線性方程組，還有其他的特殊的非線性方程組，如非線性代數(shù)方程組，非線性復數(shù)方程組等。對這些求解問題的研究，無論是在理論還是在實際應用中都是十分重要的。當在生活中遇到這種數(shù)值問題時，首先要選取適當?shù)那蠼夥绞?，然后再不斷地運算驗證它的可行性，必要時還需要改變它的參數(shù)來比較結果。每一個問題的解決都需要經(jīng)過成千上萬次的計算。本次論文的編寫，讓我更加深入的了解了數(shù)學的世界，懂得了計算機與數(shù)學相輔相成的關系。同一個非線性方程組，所使用的求解方式不同，所設定的變量不同，得到的結果也是天差地別，使用C語言來編程，能很方便調試每個不一樣之處。現(xiàn)如今，科技在飛速發(fā)展，人們對數(shù)學的研究也越來越深，世界因為數(shù)學而精彩。參考文獻李慶揚，莫孜中，祁力群等著.非線性方程組的數(shù)值解法[M].北京：科學出版社，1987.J.M.奧加特，W.C.萊因博爾特著.多元非線性方程組迭代解法[M].北京：科學出版社，1983.馮果忱.非線性方程組迭代解法[M].上海：上?？茖W技術出版社，1989.黃象鼎，曾鐘剛，馬亞南.非線性數(shù)值分析的理論與方法[M].武漢：武漢大學出版社，2004.代璐璐，檀結慶.兩種解非線性方程組的四階迭代方法[J].數(shù)值計算與計算機應用，2012.陳小惠，唐爍.解非線性方程的一類多參數(shù)迭代格式[J].合肥工業(yè)大學學報：自然科學版，2011.劉惠牲，張立杰.關于非線性方程組一種Newton型解法的一個注記[J].新疆工學院學報，1998.吳淦洲.求解非線性方程組的改進牛頓法[J].茂名學院學報，2009.趙建興，李耀堂.解非線性方程組的Newton-Simpson方法的收斂性定理的修正[J].昆明學院學報，2009.致謝因為疫情原因，大學四年的最后一學期沒能在學校度過就要畫上一個句號了，我即將正式畢業(yè)，告別我的學校生活，踏入社會?；厥走@幾個月寫論文的過程，在這里，我要感謝那些對我學習和生活上進行巨大幫助的人。首先，我要感謝我的指導老師蔣濤蔣老師，蔣老師在一開始分組的時候就依次耐心地講解每個人畢業(yè)論文題目的一些注意點和要求，并在這幾個月論文編寫的過程中能能不辭辛勞地及時解答我們的困惑與難題。當我在編寫材料懈怠懶惰時，也是蔣老師指正批評我，讓我能及時地改正悔悟。在這里我要對老師說一聲抱歉和感謝。最后，我要感謝我的家人和朋友，是他們給予了我許多精神和物質上的支持，促使我能更好的完成我的論文，面對我的一些煩人的要求，能心平氣和地對我提供幫助。感謝你們的幫助，我會一直記得你們的支持，理解與幫助，再次感謝你們所有人。附錄牛頓迭代法代碼：#include<stdio.h>#include<math.h>#include<time.h>#definetol-10//精度/*方程組及一階導數(shù)*/doublefunc1(doublex,doubley){ return2*x*x-x-3*y+2;}doublefunc2(doublex,doubley){ returnx*x+3*y*y-2;}doublefunc11(doublex,doubley){ return4*x-4;}doublefunc21(doublex,doubley){ return2*x+6*y;}intmain(void){ intbegintime,endtime;//定義開始，結束時間 unsignedintc_times=0;//定義迭代次數(shù)初值 doubler_x,r_y,p_x,p_y;//定義變量 doublen_tol=1; p_x=-1;//給定方程組初值 p_y=1; n_tol=pow((double)10,tol);//誤差界限 printf("%s\t%s\t%s\n","迭代次數(shù)","X","Y");//輸出列號 /*牛頓迭代法*/ begintime=clock();//開始計時 for(c_times=1;c_times<1000;c_times++){//進行for循環(huán)，每執(zhí)行一次以下程序迭代次數(shù)加一 r_x=p_x-func1(p_x,p_y)/func11(p_x,p_y);//牛頓迭代法迭代公式 r_y=p_y-func2(p_x,p_y)/func21(p_x,p_y); printf("%d\t%-.20lg\t%-.20lg\n",c_times,r_x,r_y);//輸出每次迭代后的x，y值和迭代次數(shù) if(((p_x-r_x)>0?p_x-r_x:r_x-p_x)<n_tol)//與誤差精度比較，若小于則退出循環(huán) break; p_x=r_x;//將新的x值賦予舊的x值，進行數(shù)值替換 p_y=r_y;//將新的y值賦予舊的y值，進行數(shù)值替換 } printf("迭代次數(shù):%d\n",c_times-1);//輸出該算法所需的迭代次數(shù) printf("方程組的解:\n");//輸出“方程組的解：” printf("%.20lg\t%.20lg\n",r_x,r_y);//輸出x，y具體數(shù)值 endtime=clock();//結束計時printf("\n\nRunningTime：%dms\n",endtime-begintime);//輸出程序運行時間 getchar();//讓程序暫停 return0;}簡化牛頓迭代法代碼：#include<stdio.h>#include<math.h>#include<time.h>#definetol-10//精度/*方程組及一階導數(shù)*/doublefunc1(doublex,doubley){ return2*x*x-x-3*y+2;}doublefunc2(doublex,doubley){ returnx*x+3*y*y-2;}doublefunc11(doublex,doubley){ return4*x-4;}doublefunc21(doublex,doubley){ return2*x+6*y;}intmain(void){ intbegintime,endtime;//定義開始，結束時間 unsignedintc_times=0;//定義迭代次數(shù)初值 doubler_x,r_y,p_x,p_y;//定義變量 doublen_tol=1; p_x=-1;//給定方程組初值 p_y=1; n_tol=pow((double)10,tol);//誤差界限 printf("%s\t%s\t%s\n","迭代次數(shù)","X","Y");//輸出列號 /*簡化牛頓迭代法*/ begintime=clock();//開始計時 for(c_times=1;c_times<1000;c_times++){//進行for循環(huán)，每執(zhí)行一次迭代次數(shù)加一 r_x=p_x-func1(p_x,p_y)/func11(-1,1);//簡化牛頓迭代法迭代公式保持導數(shù)初值不變 r_y=p_y-func2(p_x,p_y)/func21(-1,1); printf("%d\t%-.20lg\t%-.20lg\n",c_times,r_x,r_y);//輸出每次迭代后的x，y值和迭代次數(shù) if(((p_x-r_x)>0?p_x-r_x:r_x-p_x)<n_tol)//與誤差精度比較，若小于則退出循環(huán) break; p_x=r_x;//將新的x值賦予舊的x值，進行數(shù)值替換 p_y=r_y;//將新的y值賦予舊的y值，進行數(shù)值替換 } printf("迭代次數(shù):%d\n",c_times-1);//輸出該算法所需的迭代次數(shù) printf("方程組的解:\n");//輸出“方程組的解：” printf("%.20lg\t%.20lg\n",r_x,r_y);//輸出x，y具體數(shù)值 endtime=clock();//結束計時printf("\n\nRunningTime：%dms\n",endtime-begintime);//輸出程序運行時間 getchar();//讓程序暫停 return0;} 牛頓弦截法代碼：#include<stdio.h>#include<math.h>#include<time.h>#definetol-10//精度/*方程組及一階導數(shù)*/doublefunc1(doublex,doubley){ return2*x*x-x-3*y+2;}doublefunc2(doublex,doubley){ returnx*x+3*y*y-2;}doublefunc11(doublex,doubley){ return4*x-4;}doublefunc21(doublex,doubley){ return2*x+6*y;}intmain(void){intbegintime,endtime;//定義開始，結束時間 unsignedintc_times=0;//定義迭代次數(shù)初值 doubler_x,r_y,p_x,p_y,a_x,a_y;//定義變量 doublen_tol=1; p_x=-1;//給定方程組初值 p_y=1; n_tol=pow((double)10,tol);//誤差界限 printf("%s\t%s\t%s\n","迭代次數(shù)","X","Y");//輸出列號/*牛頓弦截法*/ begintime=clock();//開始計時 r_x=p_x-func1(p_x,p_y)/func11(p_x,p_y);//牛頓迭代法迭代公式進行一次迭代r_y=p_y-func2(p_x,p_y)/func21(p_x,p_y); c_times++;//迭代次數(shù)加一 printf("%d\t%-.20lg\t%-.20lg\n",c_times,r_x,r_y);//輸出迭代后的x，y值和迭代次數(shù) for(c_times=2;c_times<1000;c_times++){//進行for循環(huán)，每執(zhí)行一次以下程序迭代次數(shù)加一 a_x=r_x-(func1(r_x,r_y))*(r_x-p_x)/(func1(r_x,r_y)-func1(p_x,p_y));//牛頓弦截法迭代公式 a_y=r_y-(func2(r_x,r_y))*(r_y-p_y)/(func2(r_x,r_y)-func2(p_x,p_y)); printf("%d\t%-.20lg\t%-.20lg\n",c_times,r_x,r_y);//輸出每次迭代后的x，y值和迭代次數(shù) if(((a_x-r_x)>0?a_x-r_x:r_x-a_x)<n_tol)//與誤差精度比較，若小于則退出循環(huán) break; p_x=r_x;//進行數(shù)值替換 p_y=r_y; r_x=a_x; r_y=a_y; } printf("迭代次數(shù):%d\n",c_times-1);//輸出該算法所需的迭代次數(shù) printf("方程組的解:\n");//輸出“方程組的解：” printf("%.20lg\t%.20lg\n",r_x,r_y);//輸出x，y具體數(shù)值 endtime=clock();//結束計時printf("\n\nRunningTime：%dms\n",endtime-begintime);//輸