數(shù)值計算 第一講

1、數(shù)值分析與算法 (1)Numerical Analysis & Algorithms清華大學(xué) 計算機(jī)系 喻文健Wenjian Yu2課程簡介計算方法數(shù)值分析與算法科學(xué)計算導(dǎo)論（scientific computing）數(shù)值計算基礎(chǔ)（numerical computing）課程目標(biāo)介紹廣泛應(yīng)用于科學(xué)與工程領(lǐng)域的各種數(shù)值計算方法 鞏固連續(xù)數(shù)學(xué)基礎(chǔ)知識、增強(qiáng)實際應(yīng)用能力Wenjian Yu3授課方式與考核授課方式以講授為主，輔以作業(yè)、上機(jī)實驗考評方法作業(yè)、上機(jī)實驗：30%期末閉卷考試：70%附加分：3-5% (實驗加分、師生互動)，編程Project?作業(yè)提交紙版課代表收齊交助教處(東主樓8-404

2、)，周日晚10:30前散選同學(xué)上課時交講臺實驗在系機(jī)房檢查，具體要求第5周布置Wenjian Yu4主要教學(xué)內(nèi)容一.緒論 (數(shù)值分析與科學(xué)計算引論)誤差的基本概念(有效數(shù)字)、數(shù)值運算的誤差限、問題的敏感性與條件數(shù)、數(shù)值算法的穩(wěn)定性、“抵消”現(xiàn)象、減小舍入誤差的建議二.非線性方程解法三.線性方程組的直接解法四.線性方程組的迭代解法五.矩陣特征值計算Wenjian Yu5主要教學(xué)內(nèi)容六-1.函數(shù)逼近與線性最小二乘六-2.函數(shù)插值七.數(shù)值積分與微分八.常微分方程初值問題附加.Matlab數(shù)值計算與應(yīng)用補(bǔ)充內(nèi)容、非考試要求穿插在各章內(nèi)容之間類似數(shù)學(xué)基礎(chǔ)課：公式多、推導(dǎo)多、還有理論證明注重實際應(yīng)用：要

3、上機(jī)編程，有時還包含經(jīng)驗成份Wenjian Yu6數(shù)值計算的背景與概況Wenjian Yu7數(shù)值分析、科學(xué)計算、數(shù)值計算 數(shù)值計算作為當(dāng)今科學(xué)研究的三種基本手段之一，是數(shù)學(xué)和計算機(jī)應(yīng)用于其他學(xué)科的橋梁，因此它的發(fā)展受到廣泛關(guān)注。有些發(fā)達(dá)國家甚至將科學(xué)計算作為衡量國家綜合實力的一個重要方面，大力推動其發(fā)展。 參考書影印版序言科學(xué)計算的發(fā)展分硬件和軟件兩個方面，這里我們只考慮軟件方面，即數(shù)值計算的有關(guān)算法 (數(shù)值仿真軟件)“數(shù)值分析”、“數(shù)值計算”是研究求解連續(xù)數(shù)學(xué)問題的算法的學(xué)科（而不僅僅局限于計算誤差的研究）對象核心Wenjian Yu8Top ten algorithms of the ce

4、ntury1.1946 Los Alamos國家實驗室的J. von Neumann, S. Vlam和N. Metropolis編的Metropolis算法,即Monte Carlo方法（“隨機(jī)漫步”）2.1947 蘭德（RAND）公司的G. Dantzig創(chuàng)造的線性規(guī)劃的單純型算法（simplex method）3.1950 美國國家標(biāo)準(zhǔn)局?jǐn)?shù)值分析所的M. Hestenes, E. Stiefel和C. Lanczos開創(chuàng)的Krylov子空間迭代法4.1951 橡樹嶺（Oak Ridge）國家實驗室的A. House-holder形式化的矩陣計算的分解方法(矩陣的各種分解)“We trie

5、d to assemble the 10 algorithms with the greatest influence on the development and practice of science and engineering in the 20th century”Editors of IEEE Computational Science and Engineering, Jan. 2000 (后被SIAM轉(zhuǎn)載)Wenjian Yu9Top ten algorithms of the century5.1951 IBM由J. Backus領(lǐng)導(dǎo)的小組研制Fortran最優(yōu)編譯器6.1

6、959-61 倫敦Ferranti Ltd.的J.G.F. Francis發(fā)明QR算法，能穩(wěn)定的計算矩陣特征值7.1962 倫敦Elliot Brothers, Ltd.的Tony Hoare提出快速排序算法（Quicksort）8.1965 IBM Watson研究中心的J. Cooley與U. Princeton及AT&T Bell Lab.的J. Turkey共同提出了的FFT算法9.1977 Brigham Young大學(xué)的H. Ferguson和R. Forcede提出的整數(shù)關(guān)系偵察算法（integer relation detection）10.1987 Yale大學(xué)的L. Gre

7、engard和V. Rokhlin發(fā)明了快速多極算法(fast multipole algorithm)除了No. 5, 7, 9外，都屬于或涉及數(shù)值計算的范疇!Wenjian Yu10數(shù)值算法與非數(shù)值算法算法分為“數(shù)值算法”和“非數(shù)值算法”數(shù)值算法用途非常廣泛，發(fā)展迅速，具有跨學(xué)科的特點“非數(shù)值算法”的研究則通常歸于“計算機(jī)科學(xué)”From D. E. Knuth, The art of computer programming, Vol. 1 (計算機(jī)程序設(shè)計藝術(shù)) We might call the subject of these books “nonnumerical analysis

8、.” Computers have traditionally been associated with the solution of numerical problems such as Numerical computer programming is an extremely interesting and rapidly expanding field, and many books have been written about it. The art of computer programming系列Wenjian Yu11好數(shù)值算法的特點計算效率高、計算復(fù)雜度低可靠性好：在考慮

9、實際計算的各種誤差情況下，結(jié)果盡可能地準(zhǔn)確數(shù)值計算與數(shù)值算法數(shù)值計算的特點（區(qū)別于其他計算機(jī)方向）處理連續(xù)數(shù)學(xué)的量(實數(shù)量)，問題中常涉及微分、積分和非線性。被求解的問題一般沒有解析解、或理論上無法通過有限步計算求解無解析解：有解析解，但需無限步計算：sinx更多的實際應(yīng)用問題通過數(shù)值模擬來解決目標(biāo)：尋找快速結(jié)束(收斂)的算法，評估結(jié)果的準(zhǔn)確度Wenjian Yu12數(shù)值計算的步驟建立數(shù)學(xué)模型（需要相關(guān)學(xué)科背景）研究數(shù)值求解方程的算法通過計算機(jī)軟件實現(xiàn)算法在計算機(jī)上運行軟件進(jìn)行數(shù)值模擬將計算結(jié)果用較直觀的方式輸出，如圖形可視化方法解釋和驗證計算結(jié)果，如果需要重復(fù)上面的某些步驟上述各步驟相互間緊

10、密地關(guān)聯(lián)，影響著最終的計算結(jié)果和效率（問題的實際背景和要求也左右著方法的選擇）本課程學(xué)習(xí)重點設(shè)計數(shù)值方法(算法)的關(guān)鍵：將問題簡化(估計帶來的誤差)，然后求解簡化后的問題Wenjian Yu13數(shù)值軟件/程序包數(shù)值計算的軟件與程序包解決常見問題，促進(jìn)各個科學(xué)和工程領(lǐng)域的科研了解基本原理，學(xué)習(xí)算法設(shè)計和實現(xiàn)技巧成為聰明的軟件/程序包使用者存在形式和資源互聯(lián)網(wǎng)，免費/商業(yè)代碼Fortran, C, C+, Matlab源代碼使用，或API調(diào)用交互式集成環(huán)境的軟件Wenjian Yu14Internet網(wǎng)絡(luò)資源越來越豐富，使用越來越方便！Wenjian Yu15廣泛應(yīng)用的數(shù)值計算軟件：Matlab集

11、成環(huán)境：交互式計算系統(tǒng)，高級編程語言數(shù)值計算、矩陣計算功能強(qiáng)(包含很多先進(jìn)算法)，方便的計算可視化功能大量專題工具箱(Toolbox)，為專業(yè)應(yīng)用提供便利建議大家學(xué)習(xí)、使用MatlabWenjian Yu16數(shù)值計算知識應(yīng)用廣泛 (以計算機(jī)系方向為例)人工智能、機(jī)器人控制：矩陣特征值、奇異值分解、常微分方程數(shù)值解、最小二乘擬合計算機(jī)圖形學(xué)CAD：函數(shù)插值、逼近、微分方程數(shù)值解集成電路CAD（EDA）：大規(guī)模線性方程組求解、常微分方程、偏微分方程系統(tǒng)軟件、編譯、網(wǎng)絡(luò)等方向：線性方程組求解、非線性方程組求解高性能計算：用數(shù)值算法來評測機(jī)器性能更廣泛的應(yīng)用電力系統(tǒng)仿真、大氣仿真 更多科學(xué)與工程領(lǐng)域W

12、enjian Yu17誤差分析基礎(chǔ)Wenjian Yu18誤差分析基礎(chǔ)1.2.1誤差的來源1.2.2誤差及其分類誤差與有效數(shù)字截斷誤差與舍入誤差數(shù)據(jù)傳遞誤差與計算誤差1.2.3問題的敏感性與數(shù)據(jù)傳遞誤差1.2.4算法的穩(wěn)定性(通過板書講解)Wenjian Yu19計算機(jī)浮點數(shù)系統(tǒng)Wenjian Yu20計算機(jī)浮點數(shù)系統(tǒng)與舍入誤差(課本1.3節(jié)的部分內(nèi)容)Wenjian Yu21計算機(jī)中的浮點數(shù)Wenjian Yu22計算機(jī)中的浮點數(shù)浮點數(shù)系統(tǒng)IEEE單精度224-1261275.96010-8IEEE雙精度253-102210231.11010-16例: 一個簡單浮點數(shù)系統(tǒng),Wenjian Y

13、u23計算機(jī)中的浮點數(shù)(了解即可, 不要求證明)Wenjian Yu24抵消現(xiàn)象Wenjian Yu25抵消現(xiàn)象一元二次方程求根公式的例子解為：解決辦法：計算x2可能出現(xiàn)的問題也類似地解決Wenjian Yu26建議與總結(jié)Wenjian Yu27減小舍入誤差的幾條建議采用雙精度浮點數(shù)，一般舍入誤差不大對包含大量計算的算法，分析舍入誤差很難應(yīng)遵循如下幾條建議避免中間計算結(jié)果出現(xiàn)上(下)溢出避免“大數(shù)吃掉小數(shù)”(加、減法)避免符號相同的兩相近數(shù)相減注意簡化步驟，減少運算次數(shù)例：計算Wenjian Yu28總結(jié)總誤差計算誤差數(shù)據(jù)傳遞誤差截斷誤差舍入誤差如何評估大??？根據(jù)不同問題和方法進(jìn)行討論向后誤差分析；區(qū)間分析法；很難定量分析問題敏感性(條件數(shù)