1、數值計算方法數值計算方法The Method of Numerical ComputationNumerical Analysis教教 材材林成森 編著數值計算方法 上下冊科學出版社 1998什么是科學計算 科學計算就是研究如何在計算機上解決工程中數學問題。 科學計算包含數值方法研究和應用研究兩部分。 數值方法研究包含理論和算法兩部分， 這是科學計算的核心部分，即計算數學。 應用部分：計算物理，計算流體，計算生物學，計算大氣物理，數值預報，CAD/CAM, 大規模社會計算等等。 在科學研究中，科學計算已成為與理論研究和實驗研究相并列的三大重要手段之一。科學計算回顧 從人類結繩記事起，就開始了計

2、算，就孕育了計算數學。 現代科學計算的主要發展階段是從電子計算機誕生開始。 計算數學與其他學科的結合，開拓出更為廣闊的新天體。象計算物理，計算流體，計算生物學，計算大體物理，數值預報，CAD/CAM等等。科學計算回顧“科學計算”一詞首次出現在1983年，由美國國防部、能源部、國家科學基金會及國家航天局等單位主持下，一個由美國著名數學家拉克斯（P.Lax）為首的不同學科的專家委員會向美國政府提出的報告之中，強調“科學計算是關系到國家安全、經濟發展和科技進步的關鍵性環節，是事關國家命脈的大事。” 1984年美國政府大幅度地增加對科學計算經費的支持, 新建成五個國家級超級計算中心（分別在普林斯頓大學

3、、圣地亞哥、伊里諾大學、康奈爾大學、匹茲堡），配備當時最高性能的計算機，建立NSF-net新網絡。科學計算回顧 1987年起美國NSF把“科學與工程計算”、“生物工程”、“全局性科學”作為三大優先資助的領域。 1990年美國國家研究委員會發表振興美國數學：90年代的計劃的報告，建議對由計算引發的數學給予特殊的鼓勵和資助。報告指出由于大存儲的高速計算機的使用已導致了科學和技術方面的兩大突出進展：一是大量用于設計工作的實驗被數學模型的研究逐步取代，如航天飛機設計、反應堆設計、人工心瓣膜設計等；二是能獲取和存儲大量的數據，并能提取隱秘的信息，如計算機層析X射線攝影，核磁共振等。科學計算回顧1991年

4、以美國總統倡議的形式提出了“高性能計算與通信（HPCC）計劃”。這是為了保持和提高美國在計算和網絡的所有先進領域中的領導地位而制定的。該計劃為期五年（19921996），由美國8個重要部門負責實施。投資的重點（43）是發展先進的軟件技術與并行算法，關鍵技術是可擴展的大規模并行計算。 要求到1996年高性能計算能力提高14倍，達到每秒萬億次浮點運算速度（1012 Teraops/S）。計算機網絡通迅能力提高1百倍，達到每秒109位（Gigabits/S）。 該計劃中列舉的“挑戰”項目有：磁記錄技術、藥物設計、催化、燃燒、海洋模擬、臭氧洞、空氣污染、高速民用運輸機、數字解剖、蛋白質結構設計、金星成

5、像等。科學計算回顧 80年代中期我國將“大規模科學與工程計算”列入國家資助重大項目。 1985-1990 現代數學研究NSFC 200萬程民德，其中計算數學50萬馮康 1991-1995 攀登一期，大規模科學與工程計算的方法和理論，500萬馮康石鐘慈 1996-1999 攀登二期500萬石鐘慈 2000-2004 973一期，大規模科學計算研究，3000萬杜強 2006-2010 973二期，高性能科學計算研究，2500萬陳志明科學計算回顧 大規模科學計算研究 復雜流動的高精度數值模擬 物質性質機理的多尺度計算研究 油藏模擬與波動問題及其反問題計算 基礎計算方法的創新與發展 大規模計算工程軟件

6、系統的基礎理論和實施科學計算回顧高性能科學計算研究 創新計算方法的基礎理論研究 大規模并行計算研究 復雜流動問題的高性能算法研究 材料物性的多物理多尺度計算研究科學計算與其他學科的關系 數學學科始終是科學計算發展的依托；科學計算反過來又給數學各分支提出了新問題、新方法、新思想。 計算機科學的發展強烈影響著科學計算的內容、方法、地位和層次。由于計算機的發展，許多數學軟件的生成、開拓、豐富和發展，給數學，特別是科學計算以更大的便利。 科學計算對其他學科的滲透，吸收以及相互結合，提出了豐富的研究內容，開拓著新的方向，提出了新的理論課題。 科學計算發展的生命力是由于計算機科學和數學學科的發展，它的源動

7、力來自于各自然科學和工程技術，以及人類改造自然，建設家園的需求和任務。科學計算與其他學科的關系 科學計算的許多方法、方向，乃至理論課題，常常起源于或者萌芽于其他相關的自然學科，其中包括數學學科。有限元的發展非常突出的表現了這一點，它起源于結構分析，后來由許多數學家與力學家共同豐富和發展了它。 偏微分方程數值方法作為科學計算的另一典型方向，它的發展，豐富，同樣展現了數學家與物理，力學家共同智慧的結晶。古老的差分方法在當代取得了迅速而深刻的發展，最具代表性的是高分辨方法的興起。 Courant，Von Neumann奠基的差分方法理論，在后來的弱解問題研究中，首先從熱力學理論受到啟發，Lax 等許

8、多數學家對熵條件從不同側面進行了研究，并在數值實現中得到了具體的貫徹。科學計算與其他學科的關系 在八、九十年代的間斷解方法設計中，以各種豐富的形式，如Up-winding（迎風），TVD，ENO/WENO ，MUSCL，PPM，Roe方法，GRP（廣義Riemann問題方法），Godunov方法以及間斷有限元方法得以實現，從不同途徑保證了通過間斷（激波等）時的熵增原理，真正得到了合乎物理實際的解，在數值解過程中實現了解的唯一性，這許多方法的提出，有的正是著名的流體力學專家和工程技術專家。 許多其它學科的專家學者，還在不斷通過他們的實踐和研究，豐富和創新著偏微分數值解的方法、方案、理論。核武器的

9、研制只靠實驗和理論不能完全解決問題,何況做一次實驗要付出巨大的代價,必須采用計算的方法。計算工作者為我國成功地獨立自主發展核武器做出了歷史性的貢獻.我國獨立于西方創始了有限元方法。這一方法特別適用于大型工程計算,在水壩、橋梁、飛機、船舶的設計以及油田開發和核武器研制等方面得到了廣泛的應用.在我國導彈與航天技術研究方面,也正是計算數學工作者針對飛行器頭部氣動力以及燒蝕、飛行控制和結構分析等問題發展了一系列有效算法,較好地解決了計算問題,從技術上滿足了航天事業發展的需要.計算數學專業簡介 1955年由于國民經濟發展需要， 曾遠榮（南京大學函數論教研室主任） 堅持要發展計算數學，并得到領導的支持。于

10、是他集中人才，收集資料，有計劃有步驟地帶領一批中青年開展學術討論班，對分析中數值方法、微分方程數值解、線代數計算、函數逼近論及計算數學的理論與應用，大力開展學習研究。 南京大學作為一個基點，是國內最早開展計算數學研究的單位之一，由此逐步發展到開課、招生，于1958年正式建立計算數學專業，主要人員何旭初、徐家福、蘇煜城等。 1980 年何旭初創辦高校計算數學學報， 1992年英文版（蘇煜城）。 高校計算數學會議。計算數學專業簡介 主要研究方向 優化及其在管理科學中的應用 微分方程數值解法 計算流體力學 非線性方程數值解法 師資力量共24人，教授10人， 副教授9人，講師5 人。 在研項目：國家自

11、然科學基金重點項目1項，面上項目5項，教育部新世紀人才基金1項，參與973項目1項。課程設置 本科：數值計算I、數值計算II、偏微分方程數值解法。 研究生：根據不同研究方向設置各種類型的課程。 數值計算I、II的主要內容： 函數插值、數值積分、數值微分、曲線擬合；線性方程組的數值解法、非線性方程及方程組的數值解法、特征值和特征向量的數值解法；常微分方程的數值解法。 偏微分方程數值解法：雙曲、橢圓、拋物型方程的差分方法。 數值計算方法是一門專門研究如何從給定問題的已知數據得到所需計算結果的學科，它被廣泛應用于各個自然科學領域，也被用于多個社會科學領域. 數值計算方法包括數值代數，數值逼近，微分方

12、程的數值解法，最優化，概率統計. 數值代數： 線性方程組的數值計算方法；數據擬合；矩陣特征值問題. 數值逼近：數值插值；數值積分；數值微分. 微分方程的數值解法：常微分方程的數值解法；偏微分方程的數值解法. 最優化：無約束最優化；約束最優化；各種規劃問題. 概率統計先行課程先行課程 數學分析 ( Mathematical Analysis ) 線性代數 ( Linear Algebra ) 常微分方程 ( Original Differential Equation 簡寫為 ODE ) 計算機基礎及計算機語言第一章第一章 算術運算中的誤差分析初步算術運算中的誤差分析初步 數值方法、算法 誤差來

13、源 誤差大小的衡量方法 舍入誤差與有效數字 數據誤差在算術運算中的傳播 機器誤差數值方法數值方法( (Numerical Method)Numerical Method)： 數值方法是對給定問題的輸入數據和所需計算結果之間的關系的一種明確的描述。例： 用 Newton 法 ( 將在 Ch2 4 中討論) 計算 3 。給定3的一個初始近似值 )0(,00 xx由迭代公式： ,2, 1,)3(2111nxxxnnn產生一個序列 ,10nxxx算法：算法：( (Algorithm)Algorithm) 它是算術和邏輯運算的完整描述，按一定順序執行這些運算，經有限步把輸入數據的每一個容許集轉換成輸出數

14、據。建立數值方法的基本原則：建立數值方法的基本原則： 便于在計算機上實現 計算工作量盡量小 存儲量盡量小 問題的解與近似解的誤差小誤差的來源誤差的來源( (Error Resource)Error Resource)：模型誤差 ( Model Error )數據誤差 ( Data Error )截斷誤差 (Truncation Error )離散誤差 ( Discrete Error )數據計算過程中的誤差誤差大小的衡量：誤差大小的衡量：絕對誤差 （ absolute error ) 相對誤差 （ relative error )誤差界 （ bound of error ) 舍入誤差與有效數字

15、舍入誤差與有效數字 舍入誤差 （rounding error )（四舍五入表示近似數產生的誤差 ） 有效數字 第一位非零數字到最右邊的數字為止的所有的數字被稱為有效數字有效數字。數據誤差在算術運算中的傳播數據誤差在算術運算中的傳播 初始數據誤差和計算結果中產生的誤差之間的關系 要注意避免相減相消要注意避免相減相消。設yx,分別是初始數據yx,的近似值，即yxeyyexx,yxee ,分別是yx,的絕對誤差。考察用yx,分別代替yx,計算函數值 ),(yxfz 產生的誤差。即),(yxfz 的誤差。 假設絕對誤差yxee ,的絕對值都很小，且),(yxf可微，則z的誤差 ),(),(yxfyxf

16、zzez可以近似地表示成 yxzeyxyfeyxxfe),)(),)( （5. 1）而且， yeyxyfzyxeyxxfzxzeryxzz),)(),)( yxryxyfzyryxxfzx),)(),)( (5. 2)進行算術運算時初始數據誤差和計算結果中產生的誤差之間有下列關系（1）:),(yxyxf絕對誤差： yxyxeee；相對誤差： yxyxryxyryxxr從上式可見，接近相等的同號數相減時，會使計算結果的誤差變得很大。 故應避免相減相消故應避免相減相消。（2）:),(xyyxf 絕對誤差： yxyxexeye； 相對誤差： yxyxrrr （3）:/),(yxyxf 絕對誤差： 2

17、/yexeyeyxyx； 從上式可見， 應避免絕對值很小的數作分母。 相對誤差： yxyxrrr/例 1 求方程 0,02acbxax 的兩個根分別為 aacbbx2421和 aacbbx2422若,0b且042 acb，則1x需改為 acbbcx4221例例 2 計算表達式 xcos1。 當 0 x時 為避免相減相消，應利用 恒等式 2sin2cos12xx 機器誤差機器誤差 計算機中數的表示 浮點運算和舍入誤差設計算機中的數x為有限位小數，表示為 tkkkJdx11010 (6.1)其中UJL（L 和 U 是正整數或零）t 為計算機的字長字長，tidi, 1,都是9 , 2 , 1 , 0

18、中的一個數字若記 ttkkkdddda211. 010 (6.2)則 Jax10 (6.3) 令 xxxR 則對十進制系統有tRxx105),1 ( (6.11)對二進制系統有 t2 (6.16)若用只“舍”不“入”的斷位法，則界為 t 110 或 t 12 例 3 在5, 3,10ULtp的斷位機上 對數 0.0438 , 0.0693 , 13.2 進行加法運算那么 先加前兩個數后再加第三個數為 0.13310 若先加后兩個數再加第一個數為 0.13210 由此可見，對于浮點運算，通常的運算規律通常的運算規律 不再成立。不再成立。 作乘法運算時，不必對階。下面考察計算機中浮點數的算術運算的

19、舍入誤差：下面考察計算機中浮點數的算術運算的舍入誤差： 設 Fyx,，均為規格化的浮點數。 用)/(),(),(yxflyxflyxfl分別表示得到準確的yxyxyx/,后按相關舍入規則進行舍入的結果，即 Ryxyxfl)()( RRyxyxflyxyxfl)/()/(,)()(就上述例 2， 3101255562. 0 yx因此31012556. 0)(,yxflFyx而據(6.11)和(6.16)式，立得下述定理：定理定理 1 )1)()(1yxyxfl (6.17) )1)()(2yxyxfl (6.18) )1)()(3yxyxfl (6.19) )1)(/()/(4yxyxfl (6

20、.20)其中 , 4 , 3 , 2 , 1, iepsi （二進制系統）（十進制系統）tteps2105下面討論更復雜的浮點運算的誤差界：下面討論更復雜的浮點運算的誤差界： 通過例子可見，在做三個以上的數的加法運算時，做三個以上的數的加法運算時，需要考慮相加的兩個同號數的階數應盡量接近。需要考慮相加的兩個同號數的階數應盡量接近。 定義 )()(zyxflflzyxfl據(6.17)式，)1 ()1)(1)()1)()1)()1)()(221211zyxzyxzyxflzyxfl (6.21)其中 . 2 , 1, iepsi為估計)1 (i，先證明下面的引理引理引理（Lemma） 若), 2 , 1(niepsi， 且01. 0epsn，則 niiepsnepsn101. 11)1 (1， (6.23)其中 二進制系統）十進制系統）；(2(105tteps(6.23)式還可改寫成 1,01. 11)1 (1niiepsn (6.24)證明證明 ( Proof ) 由假設epsi，有 nininepsep