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

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

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

4、ntury1.1946 Los Alamos國家實(shí)驗(yàn)室的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）國家實(shí)驗(yàn)室的A. House-holder形式化的矩陣計(jì)算的分解方法(矩陣的各種分解)“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)定的計(jì)算矩陣特征值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ù)值計(jì)算的范疇!Wenjian Yu10數(shù)值算法與非數(shù)值算法算法分為“數(shù)值算法”和“非數(shù)值算法”數(shù)值算法用途非常廣泛，發(fā)展迅速，具有跨學(xué)科的特點(diǎn)“非數(shù)值算法”的研究則通常歸于“計(jì)算機(jī)科學(xué)”From D. E. Knuth, The art of computer programming, Vol. 1 (計(jì)算機(jī)程序設(shè)計(jì)藝術(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ù)值算法的特點(diǎn)計(jì)算效率高、計(jì)算復(fù)雜度低可靠性好：在考慮

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

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

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

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

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