數值分析(1)NumericalAnalysisWenjianYu2課程簡介計算方法數值分析與算法科學計算導論（scientificcomputing）數值計算基礎（numericalcomputing）課程目標介紹廣泛應用于科學與工程領域的各種數值計算方法

鞏固連續數學基礎知識、增強實際應用能力WenjianYu3教材數值分析與算法(第2版)清華大學出版社,2015年課件參考書喻文健譯,“Matlab數值計算”,

機械工業出版社，2006年李慶揚等,數值分析(第5版)，

清華大學出版社,2009年

/moler/index_ncm.htmlWenjianYu4授課方式與考核授課方式以講授為主，輔以作業、上機實驗考評方法作業、上機實驗：35%期末閉卷考試：65%附加分：1~2%(實驗加分、師生互動)作業提交紙版課代表收齊、或自行上交,周二上課交講臺批改后作業也在課上取東主樓機房檢查，提交報告

具體要求第5周布置WenjianYu5主要教學內容一.數值計算導論概述、誤差分析基礎(近似、有效數字、誤差分類、問題的敏感性、算法的穩定性)、浮點算術系統與舍入誤差(“抵消”現象、減小舍入誤差的建議等)二.非線性方程解法三.線性方程組的直接解法四.線性方程組的迭代解法五.矩陣特征值計算WenjianYu6主要教學內容六-1.函數逼近與線性最小二乘六-2.函數插值七.數值積分與微分八.常微分方程初值問題附加.Matlab數值計算與應用補充內容、非考試要求穿插在各章內容中類似數學基礎課：公式多、推導多、還有理論證明注重實際應用：要上機編程、實驗，有時還需要點經驗WenjianYu7學習本課程的建議往屆學生的主要問題到了大三、大四，已不適應本課程考試形式思想上不重視、投入精力不夠措施和建議教師要改進教學，調整考核機制學生要嚴格要求自己，把握聽課、作業、實驗環節重點理解問題背景、算法思路和具體步驟(會算)適當進行公式推導、算法復雜度分析與比較，提高解決具體問題的能力借助教學演示網站、Matlab軟件,提升學習興趣!多人不及格，甚至影響畢業WenjianYu8數值計算的背景與概況WenjianYu9數值分析、科學計算、數值計算

數值計算，也稱為科學計算，已成為當今科學研究的三種基本手段之一。它是計算數學、計算機科學和其他工程學科相結合的產物，并隨著計算機的普及和各門類科學技術的迅速發展日益受到人們的重視。

參考書譯者序科學計算的發展分硬件和軟件兩個方面，這里我們只考慮軟件方面，即數值計算的有關算法(數值仿真軟件)“數值分析”、“數值計算”是研究求解連續數學問題的算法的學科（而不僅僅局限于計算誤差的研究）對象核心WenjianYu10Toptenalgorithmsofthecentury1.1946美國LosAlamos國家實驗室的J.vonNeumann,S.Ulam和N.Metropolis提出的Metropolis算法（MonteCarlo方法最成功、最有影響的一個）2.1947美國蘭德（RAND）公司的G.Dantzig提出的解線性規劃的單純形算法（simplexmethod）3.1950

美國UCLA大學與美國國家標準局數值分析所的M.Hestenes,E.Stiefel和C.

Lanczos開創的Krylov子空間迭代法(Lanczos過程、CG算法)4.1950’s美國橡樹嶺（OakRidge）國家實驗室的A.Householder形式化的矩陣分解方法(表示為矩陣分解)“Wetriedtoassemblethe10algorithmswiththegreatestinfluenceonthedevelopmentandpracticeofscienceandengineeringinthe20thcentury”EditorsofIEEEComputationalScienceandEngineering,Jan.2000(后被SIAM轉載)WenjianYu11Toptenalgorithmsofthecentury5.1957

美國IBM的J.

Backus領導開發的Fortran最優編譯器6.1959-61

英國FerrantiLtd.的J.G.F.Francis發明QR算法，能穩定的計算矩陣特征值7.1962英國ElliotBrothers,

Ltd.的TonyHoare提出快速排序算法（Quicksort）8.1965

美國IBMWatson研究中心的J.Cooley與普林斯頓大學及AT&TBellLab.的J.Turkey共同提出了的FFT算法9.1977

美國BrighamYoung大學的H.

Ferguson和R.Forcede提出的整數關系偵察算法(integerrelationdetection)10.1987

美國Yale大學的L.Greengard和V.

Rokhlin發明的快速多極算法(fastmultipolealgorithm)除了No.5,7,9外，都屬于或涉及數值計算的范疇!WenjianYu12數值算法與非數值算法算法分為“數值算法”和“非數值算法”數值算法用途非常廣泛，發展迅速，具有跨學科的特點“非數值算法”的研究則通常歸于“計算機科學”FromD.E.Knuth,Theartofcomputerprogramming,Vol.1

(《計算機程序設計藝術》)……

Wemightcallthesubjectofthesebooks“nonnumericalanalysis.”Computershavetraditionallybeenassociatedwiththesolutionofnumericalproblemssuchas……Numericalcomputerprogrammingisanextremelyinterestingandrapidlyexpandingfield,andmanybookshavebeenwrittenaboutit.

Theartofcomputerprogramming系列WenjianYu13好數值算法的特點計算效率高、計算復雜度低可靠性好：在考慮實際計算的各種誤差情況下，結果盡可能地準確數值計算與數值算法數值計算的特點（區別于其他計算機方向）處理連續數學的量(實數量)，問題中常涉及微分、積分和非線性。被求解的問題一般沒有解析解、或理論上無法通過有限步計算求解無解析解：有解析解，但需無限步計算：sin(x)更多的實際應用問題通過數值模擬來解決目標：尋找迅速完成的(迭代)算法，評估結果的準確度WenjianYu14數值計算的步驟建立數學模型（需要相關學科背景）研究數值求解方程的算法通過計算機軟件實現算法在計算機上運行軟件進行數值模擬將計算結果用較直觀的方式輸出，如圖形可視化方法解釋和驗證計算結果，如果需要重復上面的某些步驟上述各步驟相互間緊密地關聯，影響著最終的計算結果和效率（問題的實際背景和要求也左右著方法的選擇）本課程學習重點設計數值方法(算法)的關鍵：將問題簡化(估計帶來的誤差)，然后求解簡化后的問題WenjianYu15數值軟件/程序包數值計算的軟件與程序包解決常見問題，促進各個科學和工程領域的科研了解基本原理，學習算法設計和實現技巧成為聰明的軟件/程序包使用者存在形式和資源商業軟件/免費軟件，互聯網上共享的程序包Fortran,C,C++,Matlab源代碼使用，或API調用交互式集成環境的軟件WenjianYu16Internet網絡資源越來越豐富，使用越來越方便！[3][4][5]WenjianYu17廣泛應用的數值計算軟件：Matlab集成環境：交互式計算系統，高級編程語言數值計算、矩陣計算功能強(包含很多先進算法)，方便的計算可視化功能大量專題工具箱(Toolbox)，為專業應用提供便利建議大家學習、使用MatlabWenjianYu18數值計算知識應用廣泛(以計算機相關方向為例)人工智能、機器人控制：矩陣特征值、奇異值分解、常微分方程數值解、最小二乘擬合計算機圖形學CAD：函數插值、逼近、微分方程數值解集成電路CAD（EDA）：大規模線性方程組求解、常微分方程、偏微分方程系統軟件、編譯、網絡等方向：線性方程組求解、非線性方程組求解高性能計算：用數值算法來評測機器性能電力系統仿真、大氣仿真，。。。。。。是數學規劃/最優化算法的基礎，部分內容也是大數據分析、機器學習中一些復雜算法的基礎WenjianYu19誤差分析基礎WenjianYu20誤差分析基礎§1.2.1誤差的來源§1.2.2誤差及其分類誤差與有效數字數據傳遞誤差與計算誤差截斷誤差與舍入誤差§1.2.3問題的敏感性與數據傳遞誤差§1.2.4算法的穩定性WenjianYu21誤差的來源模型誤差(忽略摩擦、空氣阻力)數據誤差

常數或測量值、前一步計算

的結果截斷誤差方法誤差

例:sin(x)=…舍入誤差計算時表示數的位數有限需“四舍五入”計算前計算中例1.1用球表面積公式計算地球表面積

模型誤差數據誤差數據誤差舍入誤差WenjianYu22誤差及其分類

便于絕對誤差限

相對誤差限WenjianYu23誤差及其分類

WenjianYu24誤差及其分類

以上是根據正確的有效數字位數判斷相對誤差限反過來呢？WenjianYu25誤差及其分類

WenjianYu26誤差及其分類

WenjianYu27誤差及其分類

WenjianYu28誤差及其分類

f(x)=sinx,x=1

WenjianYu29問題的敏感性(數據傳遞誤差)

范數(近似公式)WenjianYu30問題的敏感性(數據傳遞誤差)

WenjianYu31算法的穩定性與問題的敏感性相對應的一個概念；也叫數值穩定性1結果對計算過程中的擾動不敏感的算法是穩定的算法例1.7

對長度100的數組求和,每個數只有2位數字精度算法1:按存儲順序對這100個數直接累加若實際數據為1.0,0.01,…,0.01(99個),則結果？算法2:先按元素絕對值遞增的順序排序,再依次求和對上述數據取值,sum=0.99+1.0=2.0,更準確!2對包含一系列計算的過程,若計算中的小擾動不放大或放大不嚴重,則該過程對應的算法是穩定的算法sum=1.0算法2比算法1更穩定！WenjianYu32算法的穩定性

每步僅做

一次減法

n20.38196630.236068……180.000144190.00015420-0.000010

…,

WenjianYu33算法的穩定性

每步僅做

一次減法思考:從條件數角度分析算法2為何不穩定

n20.38196630.236068……180.000144190.00015420-0.000010

WenjianYu34算法的穩定性

WenjianYu35計算機浮點數系統WenjianYu36計算機浮點數系統與舍入誤差

(課本1.3節的部分內容)WenjianYu37計算機中的浮點數

WenjianYu38計算機中的浮點數

浮點數系統IEEE單精度224-1261275.960

10-8IEEE雙精度253-102210231.110

10-16例:一個簡單浮點數系統,(5位二進制)~2.2

10-308WenjianYu39計算機中的浮點數

(證明留做課后思考)應用定理1.2可證明!，2進制應用定理1.3證明!WenjianYu40