計算方法1_緒論與誤差等

1、Numerical Analysis能源與動力工程學院能源與動力工程學院 劉火星劉火星 82316418課程介紹課程介紹l 緒論緒論l 誤差分析誤差分析(2)(2)l 線性方程組的解法線性方程組的解法(6)(6)l 常微分方程的初值問題常微分方程的初值問題(6)(6)l 矩陣的特征值和特征向量矩陣的特征值和特征向量(2)(2)l 插值和擬合插值和擬合l 數值微分和數值積分數值微分和數值積分l 非線性方程解法非線性方程解法Course Outlinel數值分析，顏慶津，北京航空航天大學出版社，數值分析，顏慶津，北京航空航天大學出版社，2002006 6l徐翠薇、孫繩武，計算方法引論（第二版），徐

2、翠薇、孫繩武，計算方法引論（第二版），高等教育出版社，高等教育出版社，20022002lRichard L. Burden & J. Douglas Faires, Richard L. Burden & J. Douglas Faires, Numerical Analysis (Seventh Edition), Numerical Analysis (Seventh Edition), 高高等教育出版社，等教育出版社，20012001主要參考書主要參考書成績評定方法成績評定方法l平時成績：平時成績：20%l期末考試期末考試: : 80%先修課程先修課程l高等數學高等數學l

3、線性代數線性代數l程序設計語言程序設計語言C,C+,Fortran,Matlab,Mathematica1 1 緒論緒論Introduction1.1 1.1 關于計算方法關于計算方法1.2 1.2 計算方法的過去和未來計算方法的過去和未來1.3 1.3 誤差分析誤差分析1.1.4 4 在近似計算中需要注意的問題在近似計算中需要注意的問題目次目次現實中，具體的科學、工程問題的解決：現實中，具體的科學、工程問題的解決：實際問題實際問題物理模型物理模型數學模型數學模型數值方法數值方法計算機求解計算機求解計算方法是一種研究并解決計算方法是一種研究并解決數學問題的數值數學問題的數值近似解近似解方法方法

4、 隨著計算機的飛速發(fā)展，數值分析方隨著計算機的飛速發(fā)展，數值分析方法已深入到計算物理、計算力學、計算化法已深入到計算物理、計算力學、計算化學、計算生物學、計算經濟學等各個領域。學、計算生物學、計算經濟學等各個領域。本課僅限介紹最常用的數學模型的最基本本課僅限介紹最常用的數學模型的最基本的數值分析方法。的數值分析方法。1.1 1.1 關于計算方法關于計算方法 在計算機上是否根據數學公式編程在計算機上是否根據數學公式編程就能得到正確結果就能得到正確結果? ?研究例子:求解線性方程組123123123111123611113234121114734560 xxxxxxxxx1231231230 50

5、0 331 80 500 330 251 10 330 250 200 78.xxxxxxxxx如把方程組的系數舍入成兩位有效數字它的解為 x1 =-6.222 x2 =38.25 x3 =-33.65.準確解為x1=x2=x3=1lNumerical analysis is the study of algorithms for the problems of continuous mathematics -Lloyd N. Trefethenl“計算方法計算方法”就是研究在計算機上解決數學問就是研究在計算機上解決數學問題的理論和數值方法題的理論和數值方法計算方法研究的對象計算方法研究的對象

6、: 研究數值方法的研究數值方法的設計設計、分析分析和和有關理論有關理論基礎與基礎與軟件實現。軟件實現。F計算方法又稱：計算數學、數值方法、數值分析等計算方法又稱：計算數學、數值方法、數值分析等F計算方法的分枝有最優(yōu)化方法、計算幾何、計算概率統(tǒng)計算方法的分枝有最優(yōu)化方法、計算幾何、計算概率統(tǒng)計等計等計算方法的內容計算方法的內容l 連續(xù)系統(tǒng)的離散化連續(xù)系統(tǒng)的離散化l 離散性方程的數值求解離散性方程的數值求解 n計算數學的發(fā)展與科學工程計算是緊密相計算數學的發(fā)展與科學工程計算是緊密相聯(lián)的，計算數學的發(fā)展歷史也就是與其他聯(lián)的，計算數學的發(fā)展歷史也就是與其他學科結合，利用計算機不斷形成新的理論學科結合，

7、利用計算機不斷形成新的理論及數值方法并不斷形成新的學科的歷史，及數值方法并不斷形成新的學科的歷史，例如：例如：“計算物理計算物理” “計算流體力學計算流體力學”1.2 1.2 計算方法的過去和未來計算方法的過去和未來nH. Aiken (1900-1973)n哈佛大學博士，因做博士論文涉及到空間哈佛大學博士，因做博士論文涉及到空間電荷傳導問題的計算，電荷傳導問題的計算，1937年提出方案，年提出方案，1939年得到年得到IBM資助，資助，1944年建成投入使年建成投入使用。這是繼電式計算機用。這是繼電式計算機Mark I三位計算機設計大師的貢獻三位計算機設計大師的貢獻nJ. W. Mauchl

8、y (1907-1980)n賓夕法尼亞物理博士，因從事天氣預報需賓夕法尼亞物理博士，因從事天氣預報需要想設計計算機，要想設計計算機，1942年提出計算機方案，年提出計算機方案，1945年底竣工，這就是世界上第一臺電子年底竣工，這就是世界上第一臺電子計算機計算機ENIAC機機三位計算機設計大師的貢獻三位計算機設計大師的貢獻nJ. Von Neumann (1903-1957)n普林斯頓高級研究所，普林斯頓高級研究所，1945年在普林斯頓年在普林斯頓研制成研制成MANIAC機，有力地支持美國氫機，有力地支持美國氫彈研制，稱為計算機之父彈研制，稱為計算機之父三位計算機設計大師的貢獻三位計算機設計大師

9、的貢獻n在研制原子彈和氫彈過程中，許多物在研制原子彈和氫彈過程中，許多物理規(guī)律必須通過計算機上的計算摸清理規(guī)律必須通過計算機上的計算摸清楚。計算物理、理論物理與實驗物理楚。計算物理、理論物理與實驗物理相輔相成相互促進共同發(fā)展，形成現相輔相成相互促進共同發(fā)展，形成現代物理學的三大分支代物理學的三大分支n由于核武器研制需要，由于核武器研制需要，1950年全球只有年全球只有15臺，到了臺，到了1962年年9月僅美國就有月僅美國就有16187臺計臺計算機算機計算數學發(fā)展的歷史回顧計算數學發(fā)展的歷史回顧l1983年一個由美國著名數學家拉克斯年一個由美國著名數學家拉克斯(P. Lax)為為首的不同學科的專

10、家委員會向美國政府提出的首的不同學科的專家委員會向美國政府提出的報告之中，強調報告之中，強調“科學計算是關系到國家安全、科學計算是關系到國家安全、經濟發(fā)展和科技進步的關鍵性環(huán)節(jié)，是事關國經濟發(fā)展和科技進步的關鍵性環(huán)節(jié)，是事關國家命脈的大事。家命脈的大事。” l1984年美國政府大幅度地增加對科學計算經費年美國政府大幅度地增加對科學計算經費的支持的支持, 新建成五個國家級超級計算中心（分別新建成五個國家級超級計算中心（分別在普林斯頓大學、圣地亞哥、伊里諾大學、康在普林斯頓大學、圣地亞哥、伊里諾大學、康奈爾大學、匹茲堡），配備當時最高性能的計奈爾大學、匹茲堡），配備當時最高性能的計算機，建立算機，

11、建立NSF-net新網絡新網絡l 80年代中期我國將年代中期我國將“大規(guī)模科學與工程計算大規(guī)?？茖W與工程計算”列入國家資助重大項目列入國家資助重大項目l1987年起美國年起美國NSF把把“科學與工程計算科學與工程計算”、“生物工程生物工程”“”“全局性科學全局性科學”作為三大優(yōu)先資作為三大優(yōu)先資助的領域助的領域l由于大存儲的高速計算機的使用已導致了科學由于大存儲的高速計算機的使用已導致了科學和技術方面的兩大突出進展：和技術方面的兩大突出進展：大量用于設計工作的實驗被數學模型的研大量用于設計工作的實驗被數學模型的研究逐步取代，如航天飛機設計、反應堆設究逐步取代，如航天飛機設計、反應堆設計、人工心

12、瓣膜設計等計、人工心瓣膜設計等能獲取和存儲大量的數據，并能提取隱秘能獲取和存儲大量的數據，并能提取隱秘的信息，如計算機層析的信息，如計算機層析X射線攝影，核磁射線攝影，核磁共振等共振等l1991年以美國總統(tǒng)倡議的形式提出了年以美國總統(tǒng)倡議的形式提出了“高性能高性能計算與計算與通信計劃通信計劃”。這是為了保持和提高美國。這是為了保持和提高美國在計算和網絡的所有先進領域中的領導地位而在計算和網絡的所有先進領域中的領導地位而制定的。計劃為期五年（制定的。計劃為期五年（19921996），投資），投資的重點是發(fā)展先進的軟件技術與并行算法，關的重點是發(fā)展先進的軟件技術與并行算法，關鍵技術是可擴展的大規(guī)模

13、并行計算鍵技術是可擴展的大規(guī)模并行計算l要求到要求到1996年高性能計算能力提高年高性能計算能力提高14倍，達倍，達到每秒萬億次浮點運算速度（到每秒萬億次浮點運算速度（1012 Teraops/S）。計算機網絡通迅能力提高）。計算機網絡通迅能力提高1百倍，達到每百倍，達到每秒秒109位（位（Gigabits/S）l該計劃中列舉的該計劃中列舉的“挑戰(zhàn)挑戰(zhàn)”項目有：磁記錄技術項目有：磁記錄技術、藥物設計、催化、燃燒、海洋模擬、臭氧洞、藥物設計、催化、燃燒、海洋模擬、臭氧洞、空氣污染、高速民用運輸機、數字解剖、蛋、空氣污染、高速民用運輸機、數字解剖、蛋白質結構設計、金星成像等白質結構設計、金星成像等

14、l1993年初美國總統(tǒng)發(fā)布年初美國總統(tǒng)發(fā)布“發(fā)展信息高速公路發(fā)展信息高速公路”（NII）的總統(tǒng)令）的總統(tǒng)令l1994年年4月美國總統(tǒng)發(fā)布月美國總統(tǒng)發(fā)布“建立國家（地球）建立國家（地球）空間數據基礎實施空間數據基礎實施”（NSDI）的總統(tǒng)令）的總統(tǒng)令數值方法和數值軟件過去數值方法和數值軟件過去50年的主要進展年的主要進展Before 1940Newtons method; Gaussian elimination; Gauss quadrature; least squares fitting; Adams and Runge-Kutta formulas;Richardson extrapol

15、ation1940-1970floating point arithmetic; Fortran ; finite differences; finite elements; FFT; simplex algorithm; Monte Carlo; orthogonal linear algebra; spline function1970-2000quasi-Newton iterations; adaptivity; stiff ODE solvers; software libraries; Matlab; multigrid; sparse and iterative linear a

16、lgebra; spectral methods; interior point methods計算數學未來計算數學未來50年的展望年的展望l將更多的通過聲音，而不是鍵盤向計算機傳遞信將更多的通過聲音，而不是鍵盤向計算機傳遞信息，而計算機將更多地以圖象而不是數字反映結息，而計算機將更多地以圖象而不是數字反映結果果l數值計算將更具有適應性、迭代性、靈活性。計數值計算將更具有適應性、迭代性、靈活性。計算能力大得驚人算能力大得驚人l數值計算中更具智能性數值計算中更具智能性數學軟件數學軟件lMATLABMATLABnMATLABMATLAB是建立在向量、數組和矩陣基礎上是建立在向量、數組和矩陣基礎上的

17、一種分析和仿真工具軟件包，包含各種的一種分析和仿真工具軟件包，包含各種能夠進行常規(guī)運算的能夠進行常規(guī)運算的“工具箱工具箱”，如常用，如常用的矩陣代數運算、數組運算、方程求根、的矩陣代數運算、數組運算、方程求根、優(yōu)化計算及函數求導積分符號運算等；同優(yōu)化計算及函數求導積分符號運算等；同時還提供了編程計算的編程特性，通過編時還提供了編程計算的編程特性，通過編程可以解決一些復雜的工程問題；也可繪程可以解決一些復雜的工程問題；也可繪制二維、三維圖形，輸出結果可視化。目制二維、三維圖形，輸出結果可視化。目前，已成為工程領域中較常用的軟件工具前，已成為工程領域中較常用的軟件工具包之一。包之一。 lMATLA

18、BMATLABlMAPLEMAPLElMATLABMATLABlMAPLEMAPLElMATHEMATICMATHEMATICMapleMaple是加拿大滑鐵盧大學是加拿大滑鐵盧大學(University of (University of Waterloo)Waterloo)和和Waterloo Maple SoftwareWaterloo Maple Software公司注冊公司注冊的一套為微積分、線性代數和微分方程等高等數的一套為微積分、線性代數和微分方程等高等數學使用的軟件包。它是當今世界上最優(yōu)秀的幾個學使用的軟件包。它是當今世界上最優(yōu)秀的幾個數學軟件之一，它以良好的使用環(huán)境、強有力的

19、數學軟件之一，它以良好的使用環(huán)境、強有力的符號計算、高精度的數值計算、靈活的圖形顯示符號計算、高精度的數值計算、靈活的圖形顯示和高效的編程功能，為越來越多的教師、學生和和高效的編程功能，為越來越多的教師、學生和科研人員所喜愛，并成為他們進行數學處理的工科研人員所喜愛，并成為他們進行數學處理的工具。具。MapleMaple軟件適用于解決微積分、解析幾何、線軟件適用于解決微積分、解析幾何、線性代數、微分方程、計算方法、概率統(tǒng)計等數學性代數、微分方程、計算方法、概率統(tǒng)計等數學分支中的常見計算問題。分支中的常見計算問題。 MathematicaMathematica是目前比較流行的符號運算是目前比較流

20、行的符號運算軟件之一，它不僅可以完成微積分、線性軟件之一，它不僅可以完成微積分、線性代數及數學各個分支公式推演中的符號演代數及數學各個分支公式推演中的符號演算，而且可以數值求解非線性方程、優(yōu)化算，而且可以數值求解非線性方程、優(yōu)化等問題。它不僅是數學建模的得力助手，等問題。它不僅是數學建模的得力助手，也是大學數學教育和科學研究不可或缺的也是大學數學教育和科學研究不可或缺的工具。工具。n原始誤差原始誤差模型誤差模型誤差（忽略（忽略次要因素次要因素，物理模型，物理模型，數學模型）數學模型）n計算誤差計算誤差舍入誤差舍入誤差（計算機數據表示方法（計算機數據表示方法造成）造成）n方法誤差方法誤差截斷誤差

21、截斷誤差（算法（算法本身造成）本身造成）1.3 1.3 誤差分析誤差分析 計算機字長有限導致實數不能精確存儲，于是產生計算機字長有限導致實數不能精確存儲，于是產生舍入誤差舍入誤差。例如：在例如：在10位十進制數限制下：位十進制數限制下： 130.3333333333 本應本應130.3333333333 1.0000022-1.000004=0 本應本應1.0000022-1.000004 =1.0000040000 04-1.000004 =0.0000000000 04 舍入誤差舍入誤差(Round-off Errors)0000333.0313333.000001356.024142.1

22、0000074.01416.34,33333.031,41421356.12,1415926.31.1121 位小數，則位小數，則若在計算機上只能取若在計算機上只能取例例舍入誤差很小，本課程將研究它在運算過程中是否舍入誤差很小，本課程將研究它在運算過程中是否能有效控制。能有效控制。用近似的值去代替數學上的準確值帶來的誤差。用近似的值去代替數學上的準確值帶來的誤差。例如：例如： 泰勒級數泰勒級數 零階近似零階近似 : : 一階近似一階近似 : : 二階近似二階近似 : : 截斷誤差截斷誤差(Truncation Error )完全的泰勒級數完全的泰勒級數: : 余項余項 (n(n階近似階近似)

23、:) : : 介于介于 xi and xi+1 x = xi+1- xi余項：余項：Taylor Taylor 級數表示為級數表示為: : 截去的部分截去的部分 零階近似零階近似 : : 截斷誤差截斷誤差 : : 一階近似一階近似 Rn :零階近似零階近似 R Rn n : :斜率斜率 : :誤差誤差 誤差限誤差限 有效數字有效數字Def若用若用x*表示表示x準確值的一個近似值。則此近準確值的一個近似值。則此近似值似值x*和準確值和準確值x的差稱為誤差，用的差稱為誤差，用e*來表示來表示e*x*xDef若若|e*|x*x|*稱為近似值稱為近似值x*的誤差限。的誤差限。例例1.2已知已知x*=3

24、.14159，求近似值，求近似值x1=3.14，x2=3.142，x3=3.1416的誤差限。的誤差限。解解 000008.0000007.01416.3x0005.000041.0142.3x002.000159.014.3x321 所以誤差限所以誤差限1=0.002，2=0.0005，3=0.000008 有效數字有效數字Def若若x的近似值的近似值x*的誤差限是某一位上的半個單的誤差限是某一位上的半個單位，該位到位，該位到x*的第一位非零數字共有的第一位非零數字共有n位，則稱位，則稱x*有有n位有效數字位有效數字若用若用x*表示表示x的近似值，并將的近似值，并將x*表示成表示成x*0.a

25、1a2an10m若若|x*x|0.510mn則近似值則近似值x*有有n位有效數字位有效數字(1.1) 例例1.3 設設x*=0.0270是某數是某數x經經“四舍五入四舍五入”所得所得，則誤差，則誤差|e(x*)|不超過不超過x*末位的半個單位，即：末位的半個單位，即：|x*x|0.510 -4 又又 x*= =0.2710-1 , ,故該不等式又可寫為故該不等式又可寫為|x*x|0.510 -1-3由有效數字定義可知由有效數字定義可知, , x*有有3 3位有效數字位有效數字, ,分別是分別是2,72,7，0 0。 例例1.4 設設x32.93,x*32.89, ,則則|x*x|0.040.0

26、50.510-1即即|x*x|0.5102-3由有效數字定義可知由有效數字定義可知, , x*有有3 3位有效數字位有效數字, ,分別是分別是3,2,83,2,8。由于由于x*中的數字中的數字9 9不是有效數字，故不是有效數字，故x*不是有效數。不是有效數。1.3 相對誤差和絕對誤差相對誤差和絕對誤差xx*xx*e*er 設設 x準確值準確值 x* 近似值近似值稱稱為近似值為近似值x* 的相對誤差的相對誤差實用中，常用實用中，常用*xx*x*x*e*er 表示近似值表示近似值x* 的相對誤差，稱的相對誤差，稱*x*r 為相對誤差限為相對誤差限相應的，相應的，e*稱稱為絕對誤差，為絕對誤差，稱為

27、絕對誤差稱為絕對誤差限限有效數位與誤差的關系有效數位與誤差的關系位位有有效效數數字字至至少少具具有有則則反反之之，若若n*x10)1a(21*en11r n11r10a21*e 有效數位有效數位n n越多，則絕對誤差越多，則絕對誤差| |e*| |越小越小形如形如(1.1)式的式的近似數近似數x*具有具有n位有效數字，則位有效數字，則其相對誤差限可取為其相對誤差限可取為基本算術運算基本算術運算設設x*和和y*分別是分別是x和和y的近似值，把它們的誤差近似地的近似值，把它們的誤差近似地看做是相應地微分，即看做是相應地微分，即dx x*x， dy y*y則則d（xy）dx dyd（xy）xdy y

28、dxd（x/y）（xdyydx ）/y2 誤差傳播誤差傳播(1.3)和和(1.4)給出了由自變量的誤差引起的函數值給出了由自變量的誤差引起的函數值的誤差的近似式（誤差傳播）。的誤差的近似式（誤差傳播）。*)x(e*)x(f)x*x)(! 2/)(f ()x*x*)(x(f)x( f*)x( fy*y*)y(e2 一元函數一元函數設設yf(x)，若若x的近似值是的近似值是x*，用用f(x*) 去近似去近似f(x)的誤的誤差可用差可用Taylor公式估計公式估計*)x(e*x*)x( f*)x(f*)e(x*)x( f*)x(f*y*)y(e*)y(e*)x( f*yrr 得得兩兩邊邊除除以以(1

29、.3)(1.4)多元函數情形多元函數情形*)x,*,x*,x( f*y)x,x,x( fyn21n21 則則*)x(e*)x,*,x*,x(f*)y(ein21n1ii *)x(e*x*)x,*,x*,x( f*)x,*,x*,x(f*)y(eirin21n21in1ir 可可得得中中，分分別別取取在在式式2/1,21,2121xxxxxx)x,x( f)6 . 1 ( )7.1()x,x(xemaxxxe21)i(r2i1)21(r*同同號號 )2(r)1(r)21(r*xexexxe )x(exexexexxe*2r)1(r)2(r)1(r)*2*1(r* 由多元函數的由多元函數的Tayl

30、orTaylor展開公式類似可得展開公式類似可得 (1.5) (1.6) (1.8) (1.9) 例例1.5 測得某桌面的長測得某桌面的長a的近似值的近似值a*=120cm, ,寬寬b的近的近似值似值b*=60cm。若已知。若已知|e(a*)|0.2cm, , |e(b*)|0.1cm。 試求近似面積試求近似面積s*=a*b* 的絕對誤差限與相對誤差限的絕對誤差限與相對誤差限。2cm241.01202.060|*)b(e|*a|*)a(e|*b|*)s(e|*)b(e*a*)a(e*b*)b(eb*)b*,a(s*)a(ea*)b*,a(s*)s(e 解解: 面積面積s=ab,在公式在公式（1.5）中中,將將y=f(x1,x2) 換為換為 s=ab, 則則相對誤差限為相對誤差限為%33.06012024*s*)s(e|*)s(e|r 1.4 在近似計算中需要注意的問題在近似計算中需要注意的問題（1 1）盡量簡化計算步驟，減少乘除運算的次數盡量簡化計算步驟，減少乘除運算的次數 例