數(shù)值計算方法在計算機科學(xué)中的應(yīng)用和誤差序列實驗

1、12數(shù)值方法實驗報告數(shù)值計算方法在計算機科學(xué)中的應(yīng)用和誤差序列實驗【摘要】計算數(shù)學(xué)也叫做數(shù)值計算方法或數(shù)值分析。主要內(nèi)容包括代數(shù)方程、線性代數(shù)方程組、微分方程的數(shù)值解法，函數(shù)的數(shù)值逼近問題，矩陣特征值的求法，最優(yōu)化計算問題，概率統(tǒng)計計算問題等等，還包括解的存在性、唯一性、收斂性和誤差分析等理論問題。測量值與真實值之間的差異稱為誤差，物理實驗離不開對物理量的測量，測量有直接的，也有間接的。由于儀器、實驗條件、環(huán)境等因素的限制，測量不可能無限精確，物理量的測量值與客觀存在的真實值之間總會存在著一定的差異，這種差異就是測量誤差。誤差是不可避免的，只能減小。 關(guān) 鍵 詞 數(shù)值計算方法、計算機科學(xué)、誤差

2、一、數(shù)值計算方法在計算機科學(xué)中的應(yīng)用1、 數(shù)值計算方法概述 （一）數(shù)值計算方法屬于計算數(shù)學(xué)的范疇，是研究各種數(shù)學(xué)問題的數(shù)值方法設(shè)計、分析、有關(guān)的數(shù)學(xué)理論和具體實現(xiàn)的一門學(xué)科。由于近幾十年來計算機的迅速發(fā)展，數(shù)值計算方法的應(yīng)用已經(jīng)普遍深入到各個科學(xué)領(lǐng)域，很多復(fù)雜的和大規(guī)模的計算問題都可以在計算機上進(jìn)行計算，新的、有效的數(shù)值計算方法不斷出現(xiàn)。現(xiàn)在，科學(xué)與工程中的數(shù)值計算已經(jīng)成為各門自然科學(xué)和工程技術(shù)科學(xué)的一種重要手段，成為與實驗和理論并列的一個不可缺少的環(huán)節(jié)。所以數(shù)值計算方法既是一個基礎(chǔ)性的，同時也是一個應(yīng)用性的數(shù)學(xué)學(xué)科，與其它學(xué)科的聯(lián)系十分緊密。 由于大量的問題要在計算機上求解，所以要對各種數(shù)值

3、計算方法進(jìn)行分析，其內(nèi)容包括：誤差、穩(wěn)定性、收斂性、計算工作量、存貯量和自適應(yīng)性，這些基本的概念用于刻畫數(shù)值方法的適用范圍、可靠性、準(zhǔn)確性、效率和使用的方便性等。 當(dāng)代實際的科學(xué)與工程計算中，計算問題往往是復(fù)雜的和綜合的。但是有一些最基礎(chǔ)、最常用的數(shù)值計算方法，它們成為通常大學(xué)數(shù)值計算方法課程的內(nèi)容。本書主要討論這些方法及其分析，它們包括逼近問題（函數(shù)的插值和逼近，數(shù)值積分和微分），線性代數(shù)問題（方程組和特征值問題）和非線性方程及方程組的數(shù)值解法問題，以及常微分方程的數(shù)值解法等。這些是數(shù)值計算方法最基礎(chǔ)的內(nèi)容，不僅可以直接應(yīng)用于實際計算，同時也是其它數(shù)值計算問題所用到的方法及其分析的基礎(chǔ)。 （

4、二）數(shù)值計算方法（或稱計算方法）是研究數(shù)學(xué)問題求數(shù)值解的算法和有關(guān)理論的一門學(xué)科，它的理論與方法隨計算工具的發(fā)展而發(fā)展。在古代，人類研究的數(shù)學(xué)問題幾乎總與計算有關(guān)，而計算工具的簡陋，使求解問題受到很大限制。現(xiàn)代科學(xué)技術(shù)日新月異，尤其是計算機技術(shù)飛速發(fā)展，人類可以用計算機進(jìn)行復(fù)雜的數(shù)值計算、數(shù)據(jù)處理（包括圖形，圖像，聲音，文字），計算機不僅是現(xiàn)代計算工具，而且已成了我們工作環(huán)境的一部分。計算方法所研究的內(nèi)容是用計算機解決數(shù)學(xué)問題的方法（包括算法）和理論。用計算機進(jìn)行數(shù)值計算的核心是算法設(shè)計。算法是對解題方案的準(zhǔn)確描述，是“解題的操作序列”。在研究算法時，離不開誤差分析，同時還需要考慮算法的穩(wěn)定性

5、、收斂性、計算工作量等問題。 （三）計算方法是計算數(shù)學(xué)的一個主要部分。而計算數(shù)學(xué)是數(shù)學(xué)科學(xué)的一個分支，它研究用計算機求解數(shù)學(xué)問題的數(shù)值計算方法及其軟件實現(xiàn)。計算數(shù)學(xué)幾乎與數(shù)學(xué)科學(xué)的一切分支有聯(lián)系，它利用數(shù)學(xué)領(lǐng)域的成果發(fā)展了新的更有效的算法及其理論，反過來很多數(shù)學(xué)分支都需要探討和研究適用于計算機的數(shù)值方法。因此，計算方法的內(nèi)容十分廣泛。但本書作為計算方法的基礎(chǔ)，只介紹科學(xué)與工程計算中最常用的基本數(shù)值方法，包括線性方程組與非線性方程求根、插值與最小二乘擬合、數(shù)值積分與常微分方程數(shù)值解法等。這些都是計算數(shù)學(xué)中最基礎(chǔ)的內(nèi)容。 近幾十年來由于計算機的發(fā)展及其在各技術(shù)科學(xué)領(lǐng)域的應(yīng)用推廣與深化，新的計算性學(xué)

6、科分支紛紛興起，如計算力學(xué)、計算物理、計算化學(xué)、計算經(jīng)濟學(xué)等等，不論其背景與含義如何，要用計算機進(jìn)行科學(xué)計算都必須建立相應(yīng)的數(shù)學(xué)模型，并研究其適合于計算機編程的計算方法。因此，計算數(shù)學(xué)是各種計算性科學(xué)的聯(lián)系紐帶和共性基礎(chǔ)，是一門兼有基礎(chǔ)性、應(yīng)用性和邊緣性的數(shù)學(xué)學(xué)科。 2、 數(shù)值計算方法研究的對象、任務(wù)與特點 計算數(shù)學(xué)作為數(shù)學(xué)科學(xué)的一個分支，當(dāng)然具有數(shù)學(xué)科學(xué)的抽象性與嚴(yán)密科學(xué)性的特點，但它又具有廣泛的應(yīng)用性和邊緣性特點。 現(xiàn)代科學(xué)發(fā)展依賴于理論研究、科學(xué)實驗與科學(xué)計算三種主要手段，它們相輔相成，互相獨立，可以互相補充又都不可缺少，作為三種科學(xué)研究手段之一的科學(xué)計算是一門工具性。方法性、邊緣性的新

7、學(xué)科，發(fā)展迅速，它的物質(zhì)基礎(chǔ)是計算機（包括其軟硬件系統(tǒng)），其理論基礎(chǔ)主要是計算數(shù)學(xué)。 計算數(shù)學(xué)與計算工具發(fā)展密切相關(guān)，在計算機出現(xiàn)以前，數(shù)值計算方法只能計算規(guī)模小的問題，并且也沒形成單獨的學(xué)科，只有在計算機出現(xiàn)以后，數(shù)值計算才得以迅速發(fā)展并成為數(shù)學(xué)科學(xué)中一個獨立學(xué)科計算數(shù)學(xué)。當(dāng)代計算能力的大幅度提高既來自計算機的進(jìn)步，也來自計算方法的進(jìn)步，計算機與計算方法的發(fā)展是相輔相成、互相促進(jìn)的。計算方法的發(fā)展啟發(fā)了新的計算機體系結(jié)構(gòu)，而計算機的更新?lián)Q代也對計算方法提出了新的標(biāo)準(zhǔn)和要求。例如為在計算機上求解大規(guī)模的計算問題、提高計算效率，誕生并發(fā)展了并行計算機。自計算機誕生以來，經(jīng)典的計算方法業(yè)已經(jīng)歷了一

8、個重新評價、篩選、改造和創(chuàng)新的過程，與此同時，涌現(xiàn)了許多新概念、新課題和能充分發(fā)揮計算機潛力、有更大解題能力的新方法，這就構(gòu)成了現(xiàn)代意義下的計算數(shù)學(xué)。這也是數(shù)值分析的研究對象與特點。 概括地說，計算方法是研究適合于在計算機上使用的實際可行、理論可靠、計算復(fù)雜性好的數(shù)值計算方法。具體說就是： 第一，面向計算機，要根據(jù)計算機特點提供實際可行的算法，即算法只能由計算機可執(zhí)行的加減乘除四則運算和各種邏輯運算組成。 第二，要有可靠的理論分析，數(shù)值分析中的算法理論主要是連續(xù)系統(tǒng)的離散化及離散型方程數(shù)值求解。有關(guān)基本概念包括誤差、穩(wěn)定性、收斂性、計算量、存儲量等，這些概念是刻畫計算方法的可靠性、準(zhǔn)確性、效率

9、以及使用的方便性。 第三，要有良好的復(fù)雜性及數(shù)值試驗，計算復(fù)雜性是算法好壞的標(biāo)志，它包括時間復(fù)雜性（指計算時間多少）和空間復(fù)雜性（指占用存儲單元多少）對很多數(shù)值問題使用不同算法，其計算復(fù)雜性將會大不一樣，例如對20階的線性方程組若用代數(shù)中的Cramer法則作為算法求解，其乘除法運算次數(shù)需要9.7×1020次，若用每秒運算1億次的計算機計算也要30萬年，這是無法實現(xiàn)的，而用計算方法中介紹的Gauss消去法求解，其乘除法運算次數(shù)只需3060次，這說明選擇算法的重要性。當(dāng)然有很多數(shù)值方法不可能事先知道其計算量，故對所有數(shù)值方法除理論分析外，還必須通過數(shù)值試驗檢驗其計算復(fù)雜性。本課程雖然只著

10、重介紹計算方法及其理論，一般不涉及具體的算法設(shè)計及編程技巧，但作為基本要求仍希望讀者能適當(dāng)做一些計算機上的數(shù)值試驗，它對加深算法的理解是很有好處的。 三、數(shù)值計算方法與計算機科學(xué) 計算機的飛速發(fā)展，正在日益影響著人們對傳統(tǒng)數(shù)值分析（即計算方法）的認(rèn)識。近幾十年來，人們越來越認(rèn)識到計算方法的學(xué)習(xí)與研究離不開計算機，僅僅只依靠數(shù)學(xué)理論的演繹和推導(dǎo)還不能解決實際中的數(shù)值問題，只有與計算機科學(xué)相結(jié)合，才能研制出實用的好算法。而且好的算法必須變成數(shù)值軟件后才有可能為社會創(chuàng)造更大的財富。當(dāng)代實踐證明，計算方法正在日趨明顯地成為數(shù)學(xué)與計算機科學(xué)的交叉性學(xué)科。 數(shù)學(xué)與計算機科學(xué)的密切關(guān)系，歷史已作了回答，可以

11、說計算機科學(xué)是吸吮著數(shù)學(xué)的乳汁而成長起來的。德國數(shù)學(xué)家Leibniz在研究組合數(shù)學(xué)時發(fā)現(xiàn)的二進(jìn)制編碼是電子計算機誕生的基礎(chǔ)；VOn Nellmsnll提出了用流程圖描述計算機運行過程后，軟件的開發(fā)研究才得以發(fā)展和遍地開花；流行一時的結(jié)構(gòu)化程序設(shè)計也是Bohm和 JacoPini證明的一條數(shù)學(xué)原理“任何單入口和單出口，且沒有“死循環(huán)”的程序，都能由三種最基本的控制結(jié)構(gòu)構(gòu)造出來”的產(chǎn)物。另一方面，計算機的誕生和發(fā)展，給數(shù)學(xué)增加了新的血液，對數(shù)學(xué)的發(fā)展產(chǎn)生了不可估量的影響。借助于計算機可以證明玄妙的數(shù)學(xué)定理、揭示某些數(shù)學(xué)規(guī)律，以及求解許多原來令人一籌莫展的數(shù)學(xué)模型問題；由于并行計算機的誕生和發(fā)展，促

12、使數(shù)學(xué)工作者去研究適應(yīng)新一代計算機發(fā)展需要的算法并行算法?？傊?，由于計算機科學(xué)的發(fā)展，可以使數(shù)學(xué)上靈活的推演和運算改變成遵循某種規(guī)律的算法設(shè)計，從而為發(fā)展數(shù)值軟件奠定了基礎(chǔ)。因此，計算方法也得到更快發(fā)展，大量適合計算機求解的現(xiàn)代數(shù)值方法隨之產(chǎn)生，并被廣泛使用，成為當(dāng)代科學(xué)計算的主要方法。 使用傳統(tǒng)的計算方法解決實際問題，不但要求使用者具有一定的數(shù)學(xué)修養(yǎng)，而且還應(yīng)具有相當(dāng)?shù)木幊棠芰?，因而使計算方法的廣泛應(yīng)用受到了影響。為解決這些問題，科學(xué)計算工作者經(jīng)過長時間努力，將數(shù)值方法設(shè)計成算法，進(jìn)而編制成數(shù)值軟件，并逐步形成數(shù)值軟件產(chǎn)業(yè)，為廣大用戶打開了方便之門。當(dāng)今，已有不少集各種數(shù)值算法于一體的綜合數(shù)

13、學(xué)軟件庫（包括數(shù)值軟件）。在國內(nèi)外具有代表性的部分綜合數(shù)學(xué)軟件庫（包）分別為： IMSL（International Mathematics and Statistics Library）是美國IMSL公司研制的大型數(shù)學(xué)和統(tǒng)計軟件庫，自研制至今已更新了十多個版本，是目前國內(nèi)外流傳最廣，影響最大的數(shù)值軟件庫之一。 NAGmumerical Algorithm GrOUP）是英國政府研究機構(gòu)聯(lián)合幾所大學(xué)共同研制成功的大型綜合性數(shù)值軟件庫，它用多種語言寫成，可移植性非常好，普遍流行于歐洲，在我國也有用戶。 “Mathematica”是1988年美國IllilloiS大學(xué)開發(fā)成功的綜合數(shù)學(xué)軟件包，它把

14、符號演算、數(shù)值計算、圖形演示以及人機交互接口有機地結(jié)合在一起，幾乎包括大學(xué)本科的所有數(shù)學(xué)演算和數(shù)值計算，為研究和應(yīng)用數(shù)學(xué)理論和方法提供了先進(jìn)的環(huán)境，目前是國內(nèi)外廣泛流行的數(shù)學(xué)軟件包。STYR（是“數(shù)學(xué)、統(tǒng)計、應(yīng)用、軟件”的漢語拼音的首字母人是中國科學(xué)院計算中心等單位在“七五”期間聯(lián)合開發(fā)的綜合性數(shù)值軟件庫，是我國開發(fā)的第一個大型綜合數(shù)值軟件庫，在國內(nèi)有一定影響。 CUMSS（China University Mathematics and Statistics Software的縮寫）是1987年由原國家教委的六所高校聯(lián)合開發(fā)成功的綜合性數(shù)學(xué)與統(tǒng)計軟件庫，是我國迄今第一個正式出版的大型綜合數(shù)值

15、軟件庫。 數(shù)學(xué)軟件庫（包）的引進(jìn)與開發(fā)，給工程技術(shù)人員使用數(shù)值方法求解各種數(shù)值問題帶來了極大的方便。但是，如果工程技術(shù)人員僅知道如何使用這些數(shù)值軟件，一旦出現(xiàn)問題就難于解決；再者，有不少工程技術(shù)人員需要結(jié)合各自的具體需求靈活使用軟件庫，或者自己設(shè)計專用算法。因此，雖然有了各種軟件庫， 工程技術(shù)人員掌握數(shù)值方法和算法設(shè)計基礎(chǔ)還是很有必要的，這可以使他們真正成為使用數(shù)學(xué)軟件庫的“主人”。為此，本教程不追求完美的數(shù)學(xué)演繹、論證以及詳盡的公式推導(dǎo)，也不以數(shù)學(xué)課程的類別為序來講述數(shù)值計算方法，而盡量以數(shù)值計算方法間的內(nèi)在聯(lián)系為主線，著重介紹數(shù)值計算方法及它們之間的關(guān)系與結(jié)構(gòu)，力求少而精，使讀者用較少的學(xué)

16、時能對一般常用數(shù)值計算方法有較多的了解與掌握，并為進(jìn)一步研究新算法奠定基礎(chǔ)；內(nèi)容以研究計算機上常用數(shù)值計算方法為主要對象，盡可能縮小數(shù)值計算方法與程序設(shè)計之間的距離，通過對一些有代表性的算法設(shè)計介紹，使讀者了解數(shù)值計算方法與算法之間的關(guān)系與差別，初步掌握算法設(shè)計技術(shù)，為使用計算機求解數(shù)學(xué)模型問題架好橋梁；通過課堂教學(xué)與計算實習(xí)，使讀者盡可能多地了解算法設(shè)計與程序設(shè)計之間的關(guān)系，進(jìn)而培養(yǎng)用計算機解決實際問題的技能。 以計算機為工具來求解各種數(shù)學(xué)模型，無論使用何種方法，均需要經(jīng)歷三個中間過程：總體設(shè)計（模型的細(xì)化等），詳細(xì)設(shè)計（主要為算法設(shè)計）和程序設(shè)計等。計算機數(shù)值計算方法主要是研究將數(shù)學(xué)模型變

17、成數(shù)值問題，并研究求解數(shù)值問題的數(shù)值計算方法，進(jìn)而設(shè)計數(shù)值計算算法。2、 誤差序列實驗 （一）、實驗描述 參照1.25對3個差分方程計算出前十個數(shù)值的近似值，構(gòu)造列表和圖 形。誤差算法分別為,. （二）、實驗內(nèi)容 對下列三個差分方程計算出前10個數(shù)值近似值。在每種情況下引入一個小的初始誤差。如果沒有初始誤差，則每個差分方程將生成序列。用MATLAB構(gòu)造生成圖表。 (a),其中n=1,2, (b) ，其中n=2,3, (c), 其中n=2,3, （三）、實驗結(jié)果及分析按附件的代碼得到下面的圖表。 表 1 序列=以及近似值，和n01.0000000000000000.994000000000000

18、 1.000000000000000 1.000000000000000 10.500000000000000 0.497000000000000 0.4970000000000000.49700000000000020.2500000000000000.2485000000000000.2455000000000000.24250000000000030.1250000000000000.1242500000000000.119750000000000 0.11525000000000040.0625000000000000.0621250000000000.056875000000000

19、0.05162500000000050.0312500000000000.0310625000000000.025437500000000 0.01981250000000060.0156250000000000.0155312500000000.0097187500000000.00390625000000070.007812500000000 0.0077656250000000.001859375000000-0.00404687500000080.0039062500000000.003882812500000-0.002070312500000-0.00802343750000090

20、.001953125000000 0.001941406250000-0.004035156250000-0.010011718750000100.0009765625000000.000970703125000-0.005017578125000-0.011005859375000 表 2 誤差序列,和 00.006000000000000 0.000000000000000 0.000000000000000 10.0030000000000000.0030000000000000.00300000000000020.0015000000000000.004500000000000 0.0

21、0750000000000030.0007500000000000.0052500000000000.01575000000000040.0003750000000000.0056250000000000.03187500000000050.0001875000000000.0058125000000000.06393750000000160.0000937500000000.0059062500000000.12796875000000170.0000468750000000.0059531250000000.25598437500000380.0000234375000000.005976

22、5625000000.51199218750000590.0000117187500000.0059882812500001.023996093750010100.0000058593750000.0059941406250002.047998046875021 是誤差穩(wěn)定的，且按指數(shù)級遞減，相差不大較為穩(wěn)定，說明該序列和等比序列較為接近。的誤差不大較為穩(wěn)定，但誤差呈遞增狀態(tài)，所以其逼近效果不如。的誤差是不穩(wěn)定的，變化幅度較大，即n越大，誤差越大，說明當(dāng)時，誤差可能比數(shù)值更大。以下就是差分方程的的圖形圖 1 穩(wěn)定遞減的誤差序列 圖 2 穩(wěn)定的誤差序列圖 3 不穩(wěn)定的誤差序列 （四）、結(jié)論通過對

23、于差分方程的求解可知，不同的差分方程的初始誤差傳播會隨著其表達(dá)式的不同有很大差異性。因此，對于不同差分方程的選取問題和計算問題應(yīng)慎重選擇，選擇穩(wěn)定算法。附件（代碼）：n=0:10;xn=1./(2.n) %-n is the input-sequence%-xn is the value of the sequence(a)r0=0.994;r(1)=r0/2for n=2:10r(n)=r(n-1)/2;%-r(n) is the general term of xnendr0,r(b)p0=1;p(1)=0.497;p(2)=3*p(1)/2-p0/2;for n=3:10p(n)=3*p(n-1)/2-p(n-2)/2;%-p(n) is the general term of pnendp0,p%- show all the items of pn(c)q0=1;q(1)=0.497;q(2)=5*q(1)/2-q0;for n=3:10q(n)=3*q(n-1)/2-q(n-2)/2;%-r(n) is the general term of pnendq0,q %- show all the items of qn(3.1) r0=0.994;r(1)=r0/2