本科生畢業(yè)論文題 目: 拉格朗日插值和牛頓插值多項式的C程序算法專業(yè)代碼: 070101 作者姓名: 學 號: 單 位: 08級1班 指導教師: 2012年 5月 20 日原創(chuàng)性聲明本人鄭重聲明: 所提交的學位論文是本人在導師指導下, 獨立進行研究取得的成果. 除文中已經(jīng)注明引用的內(nèi)容外, 論文中不含其他人已經(jīng)發(fā)表或撰寫過的研究成果, 也不包含為獲得*大學或其他教育機構的學位證書而使用過的材料. 對本文的研究做出重要貢獻的個人和集體, 均已在文中以明確方式標明. 本人承擔本聲明的相應責任. 學位論文作者簽名 : 日期 指 導 教 師 簽 名: 日期 目 錄拉格朗日插值多項式的C程序算法11引言11.1插值問題的提出11.2插值法21.3插值法思想22拉格朗日插值法32.1拉格朗日插值法的由來32.2n次插值基函數(shù)42.3拉格朗日插值多項式43牛頓插值法53.1均差：53.2牛頓插值多項式：54C程序設計64.1算法設計：74.2程序源碼編寫75程序檢測125.1對拉格朗日插值的檢測125.2對牛頓插值的檢測13總結15參考文獻16致謝17摘 要本論文著重研究了用C語言編寫程序計算拉格朗日插值和牛頓插值的方法。在前人已有的研究成果的基礎上，首先介紹了拉格朗日插值和牛頓插值的思想和方法，通過添加可以循環(huán)計算功能和輸入非法數(shù)值時的糾錯功能，改進了已有文獻的方法，對其進行了推廣，使之更加的合理和完美，并且通過實際的例子進行了具體的驗證。最后，總結了一下本論文的主要研究成果和應用前景。關鍵詞：拉格朗日插值，牛頓插值，C算法，精確解AbstractThis article discuss the method to calculate Lagrange interpolation and Newton interpolation with C program. Base on the results of predecessors research, firstly, this article introduces the thoughts and methods of Lagrange interpolation and Newton interpolation. Improving the old method by adding functions which can repeatedly computing interpolation and correct illegal data. Then spreading it and making it more reasonable and perfect, checking it with some examples. Finally, summing up the main results of this article and application prospect.Key words：Lagrange interpolation; Newton interpolation ; C program;拉格朗日插值多項式的C程序算法1引言插值法是一種古老的數(shù)學研究方法，他的產(chǎn)生來自與社會的生產(chǎn)實踐活動。在我國，早在一千多年前的隋唐時期，制定歷法時，就應用了二次插值的方法。隋朝劉焯將等距節(jié)點二次插值應用于天文計算。但是，終究沒有形成系統(tǒng)的理論。插值理論都是10世紀微積分產(chǎn)生以后漸漸發(fā)展起來的。拉格朗日插值和牛頓插值都是優(yōu)秀的重要研究成果。數(shù)值分析1對此作了詳細介紹，最近50多年來計算機技術的飛速發(fā)展和廣泛應用，以及輕重工業(yè)等各方面實際問題的需要，促使插值法得到了更進一步的發(fā)展。之前也有不少關于拉格朗日插值和牛頓插值的C程序算法，但是，經(jīng)過實際運用發(fā)現(xiàn)都有各種各樣的缺點，主要分為以下兩種：1、每次只能執(zhí)行一次，算完一次之后，就會出現(xiàn)“press anykey to continue”，從而沒法在進行下一次的計算；2、沒有糾錯功能，通常情況下，為了計算的精確，我們這一個程序一般只用于計算20組以內(nèi)的（即不超過20個節(jié)點的），當超過之后，會產(chǎn)生較大誤差，甚至用戶輸入負組數(shù)之后，程序崩潰，即程序的健壯性沒有設計好；本算法在盡量彌補這兩個不足的同時，也注意盡量優(yōu)化程序，使占用的資源和運算的時間不會明顯增加。1.1插值問題的提出在實際生活中，我們常用來表示某種內(nèi)在的數(shù)量關系，其中很多數(shù)據(jù)可以通過實驗或觀測得到。這樣雖然在給定的區(qū)間上是存在的，但是也僅僅能夠得到上的一系列點的函數(shù)值。但這也只能刻畫有限的情形。為了研究函數(shù)整體的變化規(guī)律，以及實際的需要，我們往往要求出不再上的情形。因此我們常常會試著找出一個既能方便運算，又能和比較接近的函數(shù)。為了計算的方便，我們一般選一類比較簡單的函數(shù)作為，使得滿足=。這樣確定的函數(shù)就是我們想要得到的插值函數(shù)。1.2插值法拉格朗日平均插值法2介紹，當一些實際問題用數(shù)學函數(shù)關系來描述時,往往沒有明顯的解析表達式,只能根據(jù)實驗觀測或其他途徑提供一些離散點處的函數(shù)值和導數(shù),有時盡管有表達式,卻比較復雜,不便于研究和使用。對此,人們希望構造一個簡單的連續(xù)函數(shù)p(x)來近似替代所考察的函數(shù)f(x),使問題得到簡化。用代數(shù)多項式作為研究插值的工具，進而得出較為精確結果的方法，就是代數(shù)插值。當給定一張具有+1個點的函數(shù)表以后，我們要構造一個函數(shù)，這樣的滿足兩個條件：第一，是一個不超過次的多項式；第二，在給定的點（）上的值必須與給定的值相同。 設函數(shù)在區(qū)間上有定義，且已知在點上的值，。如果有一個簡單的函數(shù)，使得=，成立，就稱是的插值函數(shù)，點稱為插值節(jié)點，包含插值節(jié)點節(jié)點的區(qū)間稱為插值區(qū)間，求得函數(shù)的方法稱為插值法。幾何意義：從幾何上看，插值法就是求曲線=,使其通過給定的個點，并用它近似已知曲線=。1.3插值法思想已知在區(qū)間上有個點，以及他們對應的函數(shù)值，下面我們求次數(shù)不超過的多項式，使得=。根據(jù)已知的條件，我們可以得到關于系數(shù),，的元線性方程組其系數(shù)矩陣為=稱為范德蒙德矩陣，由于互異，所以=因此，線性方程組的解，存在且唯一，從而滿足條件的是存在且唯一的。直接求解上面的方程組就可以得到插值多項式，但這是球插值多項式最繁雜的方法。從范德蒙行列式到拉格朗日插值公式3中描述的則更為貼切，范得蒙行列式與拉格朗日插值公式看來沒什么關系，但仔細思索可得結論：應用范得蒙行列式可推得拉格朗日插值公式。2拉格朗日插值法2.1拉格朗日插值法的由來在數(shù)值分析中，拉格朗日插值法是一種多項式差值方法，它的命名來源于法國十八世紀大數(shù)學家約瑟夫路易斯拉格朗日。在很多實際問題中都傾向于函數(shù)來表示某種內(nèi)在聯(lián)系或規(guī)律，但是呢，有相當?shù)囊徊糠趾瘮?shù)都只能通過實驗和觀測來了解。如對實踐中的某個物理量進行觀測，在若干個不同的地方得到相應的觀測值，拉格朗日插值法可以找到一個這樣的一個多項式，這個多項式恰好在各個觀測的點取到觀測到的值。這樣的多項式稱為拉格朗日插值多項式。從代數(shù)的角度來說，拉格朗日插值法可以給出一個恰好穿過二維平面上若干個已知點的多項式函數(shù)。拉格朗日插值法最早被英國數(shù)學家愛德華華林于1779年發(fā)現(xiàn)，不久后（1783年）由萊昂哈德歐拉再次發(fā)現(xiàn)。1795年，拉格朗日在他的著作師范學校數(shù)學基礎教程中發(fā)表了這個插值方法，從此他的名字就和這個方法產(chǎn)生了不解之緣。插值是一種逼近的方法。拉格朗日插值法是一種較為簡單的多項式插值構造性方法，其計算復雜度并不高，得到拉格朗日插值法的途徑不止一種。通用教材北大版高等代數(shù)4以習題的形式從多項整式整除的角度得到拉格朗日插值公式。2.2n次插值基函數(shù)插值基函數(shù)的描述在拉格朗日插值基函數(shù)的相關性質(zhì)5中十分詳細。拉格朗日插值是代數(shù)多項式插值中較為簡單的一種，它具有格式整齊、對稱和規(guī)范的特點，是便于程序設計的一種形式。拉格朗日插值函數(shù)是拉格朗日插值基函數(shù)的線性組合，因此探究拉格朗日插值基函數(shù)的性質(zhì)就十分重要了。利用拉格朗日插值求余式的探討6中，對代數(shù)插值做了概括。用代數(shù)多項式作為研究插值的工具,就是所謂的代數(shù)插值。當給定一張有個點的函數(shù)表以后,要構造一個函數(shù)滿足兩個條件,即(1)：是一個不超過次的多項式；(2)：在給定點上與取相同值，即= 。我們稱為的拉格朗日插值函數(shù)。通常，若次多項式在個節(jié)點上滿足條件= 這是稱這個次多項式上的次插值基函數(shù)。2.3拉格朗日插值多項式通過推倒，我們已經(jīng)得到次插值基函數(shù)可表示為，為節(jié)點=，故插值多項式可表示為=.令,所以拉格朗日插值多項式可以寫為：.3牛頓插值法利用插值基函數(shù)很容易得到拉格朗日插值多項式，它的公式結構緊湊，整齊，很方便我們的記憶與使用，這在理論分析中非常重要。但是，當插值節(jié)點刪減時，計算就要全部重新開始，這一點非常不方便。為了能方便的進行節(jié)點刪減后的運算，我們可以重新設計一種逐次生成插值多項式的方法。這就是牛頓插值多項式。在牛頓插值公式的拓展使用7中可以看出，通過對牛頓插值公式與泰勒公式的比較，把牛頓插值公式拓展到埃爾米特插值公式和樣條函效插值的使用領域，從而可以把插值問題都歸結到牛頓插值公式上，而且在解決插值問題上很簡單、高效、方便。3.1均差：稱為函數(shù)關于點,的一階均差。稱為的二階均差。一般地，我們稱下面的函數(shù)為階均差。階均差可以表示成函數(shù)值，的線性組合，如下：=3.2牛頓插值多項式：借助均差的定義，一次插值多項式可以表示為而二次插值多項式可以表示為根據(jù)均差定義，將x看成是上的一點，可以得到,將上面的式子，后一式帶入前一式，得到,其中以上(x)我們稱為牛頓插值多項式。為插值余項。4 C程序設計基于靜態(tài)分析的C語言緩沖區(qū)溢出漏洞檢測研究8中明確指出：C語言是一種廣泛流行的高級計算機語言，即使現(xiàn)在已經(jīng)有像java這樣可以檢查數(shù)組越界的語言，C語言還被使用于很多的系統(tǒng)開發(fā)中。 “學以致用”是每一門學科都致力追求的境界,數(shù)學自然也不例外?？扇藗兺蜎]于一堆高深的數(shù)學理論及煩瑣的分析、論證之中,早已失去了數(shù)學的樂趣!特別是用數(shù)學來解決實際的問題更是感到無所適從。拉格朗日插值法在工程應用中的算法實現(xiàn)9介紹拉格朗日插值法在現(xiàn)實分析中的應用,并通過C語言程序來實現(xiàn)這一數(shù)學分析法的自動化,為復雜的工程分析研究提供了一條數(shù)學算法的捷徑。4.1算法設計：S1：選擇兩個變量控制選擇項的實現(xiàn)，分別命名為Flag和flag；S2：為了計算的精確，定義2個不超過20祖的數(shù)組x20和y20;S3：定義3個控制循環(huán)的變量，i、f、k；S4：定義幾個過程變量，a，b1，b2，c，d，e，j，w1，w2，l，L，newx，newy，P；S5：輸入已知的數(shù)組的組數(shù)，用j表示，當j在0,20之間時，繼續(xù)，當輸入的數(shù)不在此范圍時，提示錯誤，并重新輸入，知道正確為止。并通過循環(huán)語句輸入所有的數(shù)組；S6：選擇要計算的插值類型，或退出；S7：如果選擇1，計算拉格朗日插值時，先輸入要插入的新數(shù)值newx，通過循環(huán)語句，分別用w1表示,用w2表示，d=newx-b1表示對應每一個k值的，用L表示對應每一個k值的，所以所有的L相加，就得到了拉格朗日插值；S8：如果選擇2，計算牛頓插值的時候，同樣先輸入要計算插值的數(shù)值newx，通過循環(huán)語句，分別用w1表示，用w2表示，l=,L=L+l,另d=（因為牛頓插值法中，每一項只乘到，而不是所以要把多余的除掉）,通過累加，p=p+d,最終用P表示newx的牛頓插值。S9：執(zhí)行完S7和S8之后，由用戶選擇繼續(xù)重新運算還是退出；S10：如果用戶在S6中選擇的是0，則直接退出程序；4.2程序源碼編寫#include stdio.hint main()int Flag = 1;float x20,y20;int k,j,i,flag;float a,b1,b2,c,d,e,f,w1,w2,l,L,newx,P;w1=1;w2=1;L=0;P=0;while(Flag = 1)printf(請輸入0,20之間的數(shù)據(jù)。n);printf(輸入的數(shù)據(jù)為幾組:n);scanf(%d,&j);if(j20|j=0)printf(請輸入0,20之間的數(shù)據(jù)。n);printf(輸入的數(shù)據(jù)為幾組:n);scanf(%d,&j);elsefor(i=0;i=j-1;i+)printf(第%d組為:n,i+1);printf(x=);scanf(%f,&xi);printf(y=);scanf(%f,&yi);printf(請選擇:1,拉格朗日插值。2,牛頓插值。0,退出。n);scanf(%d,&flag);if(flag=1)printf(請輸入插入的數(shù)值：);scanf(%f,&newx);for(k=0;k=j-1;k+)b1=xk;b2=yk;for(i=0;i=j-1;i+)a=xi;c=newx-a;w1=w1*c;e=b1-a;if(e!=0)w2=w2*e;if(e=0)e=e+1;w2=w2*e;d=newx-b1;f=d*w2;/*printf(f=%fn,f);*/l=b2*w1/f;/*printf(l=%fn,l);*/L=L+l;w1=1;w2=1;printf(newy=%f,L);if(flag=2)printf(請輸入插入的數(shù)值：);scanf(%f,&newx);for(f=0;f=j-1;f+)for(k=0;k=f;k+)b1=xk;b2=yk;for(i=0;i=f;i+)a=xi;e=b1-a;if(e!=0)w1=w1*e;else if(e=0)e=e+1;w1=w1*e;l=b2/w1;L=L+l;w1=1;c=newx-b1;w2=w2*c;d=L*w2/c;w2=1;P=P+d;L=0;printf(newy=%f,P);printf(n);printf(請選擇 ：1 繼續(xù) 。2 退出 。n);scanf(%d,&Flag);printf(n);if(Flag = 2)return 0;if(flag=0)return 0;5程序檢測C語言程序設計教程10高度概括了程序檢測的重要性。寫完一個程序只能說完成任務的一半（甚至不到一半）。調(diào)試程序往往比寫程序更難，更需要精力、時間和經(jīng)驗。常常有這樣的情況：程序花一天就寫完了，而調(diào)試程序兩三天也未能完成。有事一個小小的程序會出錯五六處，而發(fā)現(xiàn)和排除一個錯誤，有時竟需要半天，甚至更多。C語言是應用較廣泛的一種程序設計語言,其程序格式靈活、簡潔、代碼執(zhí)行效率高。正如C程序調(diào)試中常見錯誤分析11中介紹的，由于其語法限制不嚴,且采用了一些用以提高執(zhí)行效率的措施,因而在調(diào)試時經(jīng)常會出現(xiàn)莫明其妙的錯誤,這種錯誤需要仔細檢查和分析才能發(fā)現(xiàn)。在本論文中，主要對程序計算結果的精確性進行檢驗。5.1對拉格朗日插值的檢測在對拉格朗日插值的精確性進行檢測時，我們用下面的一個例子：例1：已知sin0.32=0.314 567 ,sin0.34=0.333 487 ,sin0.36=0.352 274,2用線性插值及拋物線插值計算sin0.3367的值。我們依次鍵入， ，；經(jīng)過運算，我們可以得到如下的結果：我們可以看到，計算的結果為0.330 374，這個結果和6位有效數(shù)字的正弦函數(shù)表完全一樣。說明這個算法的精度很高。5.2對牛頓插值的檢測我們同樣引用一個例子對牛頓插值的精確性進行檢驗：例2：給出的函數(shù)和均差表如下：0.400.410750.550.578151.116000.650.696750.186000.280000.800.888111.275730.358930.197330.901.026521.384100.433480.213000.031341.051.253821.515330.524930.228630.03126-0.00012計算出的近似值。解答：我們依次輸入，。運行結果如下：這個結果極近似于例題的答案：0.63192。從結果我們不難看出：通過這個算法所得到的結果與它的真是值之間的誤差很小，即通過算法算出的牛頓插值是法的近似值。這樣這個算法的可行性得證。總結通過以上兩個例題，可以看出，這樣一個C程序可以使復雜難算的拉格朗日插值和牛頓插值很方便的計算出。既不需要熟練的操作技巧，又不需要花費大量的時間和精力。同時，我們可以看到，至少在數(shù)組的數(shù)量小于20組的時候，計算的精確度是很高的。雖然用其他的大型計算工具，也會快速的計算出插值，例如MATLAB程序，但操作起來比較復雜，而且對設備有一定的要求。一般電腦上沒有裝MATLAB環(huán)境，沒法運行。但是這樣的一個小程序，攜帶方便，運算和操作都很簡單。在工程技術中，經(jīng)常會遇到插值之類的計算問題，例如在半 導體技術中，設計晶體管和分析其性能時，常常涉及到與半導體 的雜質(zhì)濃度有關的參盤;在溫度自動控制系統(tǒng)中的熱電偶和溫 度的對應關系，當采用計算機輔助分析和控制時，必須將這些關系曲線離散化，然后運用插值法進行數(shù)學分析，最終得到我們需要的結果。參考文獻1李慶揚，易大義，王能超.現(xiàn)代數(shù)值分析.北京：高等教育出版社,1995.2符錫成，郭學品，拉格朗日平均插值法，海南大學學報（自然科學版），2007年02期。3王洪玉，從范德蒙行列式到拉格朗日插值公式，滄州師范學院學報，1990年第04期。4 徐章韜，從矩陣的角度解讀拉格朗日插值法，中國數(shù)學雜志（高中版），2011年第三期。5車明剛，拉格朗日插值基函數(shù)的相關性質(zhì)，保山學院學報，2010年第2期。6黃濤，利用拉格朗日插值求余式的探討，河南財政稅務高等專科學校學報，2009年02期。7王森，牛頓插值公式的拓展使用，阜陽師范學院學報（自然科學版），2005年03期。8 沙月林，基于靜態(tài)分析的C語言緩沖區(qū)溢出漏洞檢測研究，TP311.52。9徐小麗，拉格朗日插值法在工程應用中的算法實現(xiàn)，林區(qū)教學，2010年01期。10譚浩強，張基溫，唐永炎編著. C語言程序設計教程.北京：高等教育出版社，1992.11陳鑫，C程序調(diào)試中常見錯誤分析，長治學院學報，2009年02期。12戴聚嶺，多項式差值在工程計算中的應用，福建電腦，2006年04期。13Golub G H,OLeary D P. Some history of the conjugate gradient and Lanczos methods .SIAM Review,1989,31:50-10214李岳生,齊東旭.樣條函數(shù)方法.北京：科學出版社,197915關治,陸金甫.數(shù)值分析基礎.北京：高等教育出版社,2000致謝我是*大學數(shù)學科學學院的一名學生，在此我非常感謝我的導師，*大學數(shù)學科學學院的*老師。正是在*老師的辛苦指導下,我的論文終于定稿.在整個論文撰寫的過程中,*老師秉著嚴謹求實的治學態(tài)度,大膽創(chuàng)新的進取精神,高度負責的敬業(yè)精神,不僅對我的論文撰寫提供了巨大的幫助甚至在對我以后的學習工作，都產(chǎn)生了巨大的影響，她教會我怎么去學習，而這正是我們要學習的精髓.她不僅知識淵博,而且視野開闊,思維敏銳,讓我真正感覺到了一個導師的專業(yè)水平,在此我向*老師表示深深的感謝.同時,我要也感謝那些曾經(jīng)給予過我?guī)椭睦蠋?、同學和朋友們,是他們讓我不僅圓滿完成了學習任務，而且學到了課堂上沒有學到的東西。17