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

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

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

4、ntury1.1946 Los Alamos國家實驗室的J. von Neumann, S. Vlam和N. Metropolis編的Metropolis算法,即Monte Carlo方法（“隨機漫步”）2.1947 蘭德（RAND）公司的G. Dantzig創造的線性規劃的單純型算法（simplex method）3.1950 美國國家標準局數值分析所的M. Hestenes, E. Stiefel和C. Lanczos開創的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轉載)Wenjian Yu9Top ten algorithms of the century5.1951 IBM由J. Backus領導的小組研制Fortran最優編譯器6.1

6、959-61 倫敦Ferranti Ltd.的J.G.F. Francis發明QR算法，能穩定的計算矩陣特征值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大學的H. Ferguson和R. Forcede提出的整數關系偵察算法（integer relation detection）10.1987 Yale大學的L. Gre

7、engard和V. Rokhlin發明了快速多極算法(fast multipole algorithm)除了No. 5, 7, 9外，都屬于或涉及數值計算的范疇!Wenjian Yu10數值算法與非數值算法算法分為“數值算法”和“非數值算法”數值算法用途非常廣泛，發展迅速，具有跨學科的特點“非數值算法”的研究則通常歸于“計算機科學”From D. E. Knuth, The art of computer programming, Vol. 1 (計算機程序設計藝術) 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好數值算法的特點計算效率高、計算復雜度低可靠性好：在考慮

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

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

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

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

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