數值分析與科學計算引論課件

1、第1章 數值分析與科學計算引論1.1 數值分析的對象、作用與特點什么是數值分析(Numerical Analysis)？數值分析是計算數學的一個主要部分,計算數學是數學科學的一個分支,它研究用計算機求解各種數學問題的數值計算方法及其理論與軟件實現。實際問題數學模型數值計算方法 程序設計上機計算求出結果數值分析的基本內容計算機只能進行加減乘除四則運算和一些簡單的函數計算(即使是函數也是通過數值分析方法處理，轉化為四則運算而形成了的一個小型論軟件包)。數值代數：求解線性和非線性方程的解法插值和數值逼近數值微分和數值積分常微方程數值解法和偏微方程數值解法數值分析的特點面向計算機，要根據計算機的特點提

2、供切實可行的有效算法有可靠的理論分析，能任意逼近并達到精度要求。要有良好的計算復雜性，時間復雜性和空間復雜性。要有數值實驗，即任何一個算法除從理論上要滿足上述三點外，還要通過數值試驗證明是行之有效的。例：求解一個20階線性方程組，用加減消元法需3000次乘法運算；而用克萊姆（Cramer）法則要進行9.7*1020次運算，若用每秒億次乘法運算的計算機要30萬年。 例: 一元二次方程x2-(109+1)x+109=0其精確解為X1=109, X2=1。如用求根公式和字長為8位的計算器求解,有與精確解有天壤之別。,若因此,算法的選用很重要。 1.2 數值計算的誤差(Error)誤差來源與分類模型誤

3、差觀測誤差截斷誤差(Truncation Error) 舍入誤差(Round-off Error)用數學方法解決一個具體的實際問題，首先要建立數學模型，這就要對實際問題進行抽象、簡化，因而數學模型本身總含有誤差，這種誤差叫做模型誤差數學模型是指那些利用數學語言模擬現實而建立起來的有關量的描述數學模型的準確解與實際問題的真解不同實際問題的真解數學模型的真解為減化模型忽略次要因素定理在特定條件下建立與實際條件有別模型誤差在數學模型中通常包含各種各樣的參變量，如溫度、長度、電壓等，這些參數往往是通過觀測得到的，因此也帶來了誤差，這種誤差叫觀測誤差數學模型中的參數和原始數據，是由觀測和試驗得到的由于測

4、量工具的精度、觀測方法或客觀條件的限制,使數據含有測量誤差,這類誤差叫做觀測誤差或數據誤差根據實際情況可以得到誤差上下界數值方法中需要了解觀測誤差,以便選擇合理的數值方法與之適應觀測誤差精確公式用近似公式代替時,所產生的誤差叫截斷誤差 例如, 函數f(x)用泰勒(Taylor)多項式 截斷誤差（介于0與x之間）近似代替，則數值方法的截斷誤差是 截斷誤差的大小直接影響計算結果的精度和計算 工作量，是數值計算中必須考慮的一類誤差在數值計算中只能對有限位字長的數值進行運算需要對參數、中間結果、最終結果作有限位字長的處理工作，這種處理工作稱作舍入處理用有限位數字代替精確數，這種誤差叫做舍入誤差，是數值

5、計算中必須考慮的一類誤差舍入誤差誤差與有效數字(Significant digits/figures)定義1 絕對誤差absolute error，簡稱誤差：誤差限：相對誤差relative error ：相對誤差限：定義2 例1 42.195, 0.0375551, 8.00033, 2.71828,按四舍五入寫出上述各數具有四位有效數字的近似數.例2 考察三位有效數字重力加速度g,若以m/s2為單位, g9.80m/s2, 若以km/s2為單位, g0.00980km/s2,解1：若取近似值x*=3.1415，絕對誤差是0.0000926，有，即m=0,n4，故近似值x*=3.1415只有

6、4位有效數字解2：x*3.1415的絕對誤差限0.0005，它是x的小數后第3位的半個單位，故近似值x*=3.1415準確到小數點后第3位故近似值x*=3.1415只有4位有效數字例3 設x= =3.1415926，求x*=3.1415近似值的有效數字定理 例4 解：設取n位有效數字，相對誤差限*r=，例5 指出下列各數具有幾位有效數字，及其絕對誤差限和相對誤差限：0.002 009 000.00解 因為x1*=0.002 00， m=3絕對誤差限0.000 005= 因為m=3，n=3，x1*= 0.002 00有3位有效數字. a1=2，相對誤差限r=x2*=9 000.00，絕對誤差限0

7、.005，因為m=3，n=6，x2*=9 000.00有6位有效數字，相對誤差限為r 如果認為小數點后邊的0無用，將9 000.00隨便寫作90009103，那么它的絕對誤差就是=0.5=0.51034+1，即m=3，n=4，表明這個數有4位有效數字可見，小數點之后的0，不是可有可無的，它是有實際意義的.數值運算的誤差估計誤差分析簡介 向后誤差分析法區(qū)間分析法概率分析法1.3 誤差定性分析、避免誤差危害算法的數值穩(wěn)定性考慮初始數據誤差在計算中的傳播問題. 方案（A）不穩(wěn)定，方案（B）穩(wěn)定設計算法時應遵循的原則要有數值要穩(wěn)定性,即能控制誤差的傳播.避免大數吃小數,即兩數相加時,防止較小的數加不到

8、較大的數上.避免兩相近的數相減,以免有效數字的大量丟失.避免分母很小(或乘法因子很大),以免產生溢出.避免誤差危害的若干原則除了分清問題是否病態(tài)和算法是否數值穩(wěn)定外,還要考慮避免誤差危害和防止有效數字損失的如下原則：1.避免大數除以小數例 仿計算機，采用3位十進制，用消元法求解方程組 解：錯.為什么,怎么辦？減少運算誤差源2、兩個相近的數相減，會嚴重損失有效數字 例如x =1958.75，y =1958.32都具有五位 有效數字，但x-y=0.43只有兩位有效數字 通常采用的方法是改變計算公式,例如當與 很接近時,由于用右端代替左端公式計算,有效數字就不會損失 當x很大時可作相應的變換 則用右

9、端來代替左端。 減少運算誤差源減少運算誤差若干原則當x接近0時 一般情況，當f(x)f(x*)時，可用泰勒展開 取右端的有限項近似左端。 如果計算公式不能改變，則可采用增加有效位數的方法保證精度 例 仿計算機在3位十進制下，、防止大數吃小數例 求二次方程x2-105x+1=0的根 解：按二次方程求根公式 x1=(105+(1010-4)1/2)/2 x2=(105-(1010-4)1/2)/2 在8位浮點數計算得 x1=(105+105 )/2=105 (正確）, x2=(105-105 )/2=0 (錯誤）產生錯誤的原因 出現大數1010吃掉小數4的情況 分子部分出現兩個相近數相減而喪失有

10、效數位常稱為災難性的抵消4、絕對值太小的數不宜做除數當分母為兩個相近數相減時,會喪失有效數字這里分子的誤差被擴大104倍,再如若將分母變?yōu)?.0011,即分母只有0.0001的變化時,計算結果卻有了很大變化 例 計算 解: 分子分母分別計算后相除(取9位小數)A=0.0005*0.0143*0.0012=0.00000715*0.0012 =0.000000009(有舍入)B=0.0003*0.0125*0.0135=0.00000375*0.0135 =0.000000051(有舍入)D=A/B=0.17647真值為0.16948148，所以D只準確到小數后一位 算法2：分成三組因子。每組只

11、取六位小數計算 a=0.0005/0.0003=1.666667(有舍入) b=0.0143/0.0125=1.144000 c=0.0012/0.0135=0.088889 (有舍入) D=a*b*c=1. 666667* 1.144000* 0.088889 =0.169482,準確到小數后5位。bca5、簡化計算步驟，減少運算次數減少運算次數可以不但節(jié)省時間，而且減少舍入誤差 例x255=xx2x4x8x16x32x64x128 原先要做254次乘法現只需14次即可 例 如計算多項式 p(x)=anxn an-1xn-1 a1x a0 的值 若直接計算akxk,再逐項相加，一共要做 n+

12、(n-1)+2+1=n(n+1)/2次乘法和n次加法 如果將前n項提出x，則有 p(x)=（anxn-1 an-1xn-2 a1 ）x a0 =(anxn-2an-1xn-3 a2)xa1）x a0 =(anx an-1)xa2)x a1)x a0寫成遞推公式 于是 ,這種多項式求值的算法稱為秦九韶算法,只做n次乘法和n次加法,程序實現簡單 1.5 數學軟件針對高級語言(FORTRAN,C,C+)的通用軟件包LAPACKIMSL (International Mathematical and Statistical Libraries)NAG (Numerical Algorithms Gro

13、up)Maple和Mathematic符號計算、數值計算和工作表的特性MATLAB針對矩陣計算的數值計算系統(tǒng)Python開源多用途解釋語言，MIT教學用語言，與多種系統(tǒng)嵌入式使用第1次軟件危機(The first Software Crisis)60s-70s，匯編語言Assembly Language Programing為主，計算機需要處理更復雜問題，誕生了FORTRAN和C高級語言，用共同的機器語言來處理不同的處理器第2次軟件危機(The Second Software Crisis)80s-90s，無法處理和維護復雜和魯棒的應用，需要大量程序員和大量程序去處理更復雜問題，誕生了面向對象的程序設計OOP（C+,C# and Java）第3次軟件危機？(The Origins of a Third Crisis)2005-20?，摩爾定律，并行計算、多核處理、云計算？面向對象編程(Object Oriented Programming，OOP)封裝（Encapsulation）繼承（Inheritance）多態(tài)（Polymorphism）摩爾定律：當價格不變時，集成電路上可容納的晶體管數目，約每隔18個月便會增加一倍，性能也將提升一倍。換言之，每一美元所能買到的電腦性能，將每隔18個月翻兩倍