計算方法第一章

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、舍入誤差：下面考察計算機(jī)中浮點(diǎn)數(shù)的算術(shù)運(yùn)算的舍入誤差： 設(shè) Fyx,，均為規(guī)格化的浮點(diǎn)數(shù)。 用)/(),(),(yxflyxflyxfl分別表示得到準(zhǔn)確的yxyxyx/,后按相關(guān)舍入規(guī)則進(jìn)行舍入的結(jié)果，即 Ryxyxfl)()( RRyxyxflyxyxfl)/()/(,)()(就上述例 2， 3101255562. 0 yx因此31012556. 0)(,yxflFyx而據(jù)(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 （二進(jìn)制系統(tǒng)）（十進(jìn)制系統(tǒng)）tteps2105下面討論更復(fù)雜的浮點(diǎn)運(yùn)算的誤差界：下面討論更復(fù)雜的浮點(diǎn)運(yùn)算的誤差界： 通過例子可見，在做三個以上的數(shù)的加法運(yùn)算時，做三個以上的數(shù)的加法運(yùn)算時，需要考慮相加的兩個同號數(shù)的階數(shù)應(yīng)盡量接近。需要考慮相加的兩個同號數(shù)的階數(shù)應(yīng)盡量接近。 定義 )()(zyxflflzyxfl據(jù)(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)其中 二進(jìn)制系統(tǒng)）十進(jìn)制系統(tǒng)）；(2(105tteps(6.23)式還可改寫成 1,01. 11)1 (1niiepsn (6.24)證明證明 ( Proof ) 由假設(shè)epsi，有 nininepsep