數(shù)值分析-ch1-緒論

1、《數(shù) 值 分 析》Numerical Analysis李慶楊 王能超易大義 編華中科技大學(xué)出版社,“數(shù)值分析” 就是研究適合用計算機解決數(shù)學(xué)問題的理論和數(shù)值方法: ? 數(shù)值方法: 計算公式和算法步驟 ? 理論分析：誤差分析、收斂性、穩(wěn)定性等,什么是數(shù)值分析?,Chapter 1 Introduction,Chapter 1 Introduction,數(shù)值分析的學(xué)科別名,? 計算方法? 科

2、學(xué)與工程計算,Chapter 1 Introduction,科學(xué)計算的重要性,? 科學(xué)計算是工程實踐的重要工具? 科學(xué)計算是繼理論與實驗后另一科學(xué) 研究手段,Chapter 1 Introduction,計算機發(fā)展的四個階段,第一代計算機：電子管數(shù)字計算機(1946-1958年)第二代計算機：晶體管數(shù)字計算機(1958-1964年)  第三代計算機：集成電路數(shù)字計算機(1964-1970年)第四代計算機：大規(guī)

3、模集成電路計算機(1970年~),科學(xué)計算的國家戰(zhàn)略與發(fā)展,? 1983 年一個由美國著名數(shù)學(xué)家向美國政府提出的報告之中， 強調(diào)“科學(xué)計算是關(guān)系到國家安全、經(jīng)濟發(fā)展和科技進步的關(guān) 鍵性環(huán)節(jié)，是事關(guān)國家命脈的大事?！? 1984 年美國政府大幅度地增加對科學(xué)計算經(jīng)費的支持,新建成 五個國家級超級計算中心,配備當(dāng)時最高性能的計算機，建立 NSF -net 新網(wǎng)絡(luò)。? 80 年代中期我國將“大規(guī)?？茖W(xué)與工程計算”列入國

4、家資助重大 項目。,Chapter 1 Introduction,? 1987年起美國NSF 把“科學(xué)與工程計算” ，“生物工程” “全局 性科學(xué)”作為三大優(yōu)先資助的領(lǐng)域。? 1990年美國國家研究委員會發(fā)表《振興美國數(shù)學(xué)：90年代的計 劃》的報告，建議對由計算引發(fā)的數(shù)學(xué)給予特殊的鼓勵和資助。? 1991年以美國總統(tǒng)倡議的形式提出了“高性能計算與通信HPCC 計劃”，這是為了保持和提高美國在計算和網(wǎng)絡(luò)的所有先進

5、領(lǐng) 域中的領(lǐng)導(dǎo)地位而制定的。? 1995年美國為了確保核庫存的性能安全性、可靠性和更新需要 而實施的“加速戰(zhàn)略計算創(chuàng)新ASCI 計劃”。,Chapter 1 Introduction,? 2010年希拉里提出的“國家寬帶戰(zhàn)略”，“大數(shù)據(jù)研究和發(fā)展計劃”也被認為是1993年時任美國副總統(tǒng)戈爾宣布的“信息高速公路”計劃后美國政府政策層面的一次“狂飆突進”，將“大數(shù)據(jù)”上升到國家意志將在下一個10年帶來深遠影響。? 在互聯(lián)網(wǎng)和

6、通信技術(shù)飛速發(fā)展20年后，一個屬于“大數(shù)據(jù)”的時代，真的來了。,Chapter 1 Introduction,? 2013年3月22日，奧巴馬宣布以2億美元投資“大數(shù)據(jù)”領(lǐng)域，在次日的電話會議上，美國政府將數(shù)據(jù)定義為“未來的新石油”，美國政府認識到了一個國家擁有數(shù)據(jù)的規(guī)模，活性及解釋運用的能力將成為綜合國力的重要組成部分，未來對數(shù)據(jù)的占有和控制甚至將成為繼陸權(quán)、海權(quán)、空權(quán)之外另一個國家核心資產(chǎn)。? 2014.6.22報道，天河一

7、號計算機第三次奪得世界最快計算機。,Chapter 1 Introduction,大數(shù)據(jù),? 大數(shù)據(jù)(bigdata)，或稱巨量資料，指的是所涉及的資料量規(guī)模巨大到無法透過目前主流軟件工具，在合理時間內(nèi)達到擷取、管理、處理、并整理成為幫助企業(yè)經(jīng)營決策更積極目的的資訊。(在維克托·邁爾-舍恩伯格及肯尼斯·庫克耶編寫的《大數(shù)據(jù)時代》中大數(shù)據(jù)指不用隨機分析法(抽樣調(diào)查)這樣的捷徑，而采用所有數(shù)據(jù)的方法)。 ? 大數(shù)據(jù)的

8、4V特點： Volume(大量)， Variety (多樣), Value (價值)， Velocity(高速)。,Chapter 1 Introduction,? Volume(大量)：數(shù)據(jù)體量巨大。 1024GB=1TB； 1024TB=1PB； 1024PB=1EB； 1024EB=1ZB； 1024ZB=YB。 到目前為止，人類生產(chǎn)的所有印刷材料的

9、數(shù)據(jù)量是 200PB，而歷史上全人類說過的所有的話的數(shù)據(jù)量 大約是5EB。,Chapter 1 Introduction,? Variety (多樣)：數(shù)據(jù)類型繁多。 拜互聯(lián)網(wǎng)和通信技術(shù)近年來迅猛發(fā)展所賜，如今的數(shù)據(jù)類型早已不是單一的文本形式，除了網(wǎng)絡(luò)日志、音頻、視頻、圖片、地理位置信息等等多類型的數(shù)據(jù)對數(shù)據(jù)的處理能力提出了更高的要求。,Chapter 1 Introduction,? Value (價值

10、)：價值密度低。 價值密度的高低與數(shù)據(jù)總量的大小成反比。以視頻為例，一部一小時的視頻，在連續(xù)不間斷監(jiān)控過程中，可能有用的數(shù)據(jù)僅僅只有一兩秒。如何通過強大的機器算法更迅速地完成數(shù)據(jù)的價值“提純”是目前大數(shù)據(jù)洶涌背景下亟待解決的難題。,Chapter 1 Introduction,? Velocity(高速)：處理速度快。 這是大數(shù)據(jù)區(qū)分于傳統(tǒng)數(shù)據(jù)挖掘最顯著的特征。根據(jù)IDC的一份名為“數(shù)字宇宙”的報告，預(yù)計到2

11、020年全球數(shù)據(jù)使用量將會達到35.2ZB。。,Chapter 1 Introduction,§1 數(shù)值分析的對象與特點,? 插值和函數(shù)逼近? 數(shù)值微分和數(shù)值積分? 常微分方程數(shù)值解法 非線性方程的迭代法? 數(shù)值代數(shù):求解線性和非線性方程組的直接 法和間接法? 代數(shù)特征值問題的數(shù)值解法,總之，是構(gòu)造數(shù)值算法,構(gòu)造數(shù)值算法的基本思想,近似替代：如，離散化：如，遞推化：如，,§1

12、 數(shù)值分析的對象與特點,(P3-例1),秦九韶算法:,,數(shù)值分析的學(xué)科特點,實用性 理論性 實踐性1 面向計算機，根據(jù)計算機的特點提供可行的有效算法； ? 只提供加減乘除和邏輯運算 ? 串行機和并行機2 有可靠的理論分析:算法的收斂性、穩(wěn)定性和誤差分析；3 有好的計算復(fù)雜性:時間和空間復(fù)雜性；4 有充分的數(shù)值實驗證明算法的有效性。,§1 數(shù)值分析的對象與特點,學(xué)習(xí)“數(shù)值分析”需注意如下幾點

13、,1. 要掌握算法的原理和思想2. 要掌握算法的處理技巧,步驟和計算公式3. 重視誤差分析,理解收斂性,穩(wěn)定性分析的理論4. 做一定的理論分析證明與計算練習(xí)5. 上機實踐,§1 數(shù)值分析的對象與特點,§2 誤差的基本理論,用計算機進行實際問題的數(shù)值計算時，往往求得的是問題的近似解，都存在誤差；2. 誤差是不可避免的，既要允許誤差，又要控制誤差。要重視誤差分析，分析誤差的來源，誤差的傳播及對誤差作出估計。

14、,誤差的來源主要有如下幾個方面： 模型誤差 觀測誤差——不是來自于計算機 截斷誤差 舍入誤差——計算機產(chǎn)生的,例 傳播與積累 /* Spread & Accumulation */,蝴蝶效應(yīng) —— 紐約的一只蝴蝶翅膀一拍，風(fēng)和日麗的北京 就刮起臺風(fēng)來了？！,,,NY,BJ,,,,,,以上是一個病態(tài)問題 /* ill-pos

15、ed problem*/關(guān)于本身是病態(tài)的問題，我們還是留給數(shù)學(xué)家去頭痛吧！,§2 誤差的基本理論,蝴蝶效應(yīng)（Butterfly Effect）是指在一個動力系統(tǒng)中，初始條件下微小的變化能帶動整個系統(tǒng)的長期的巨大的連鎖反應(yīng)。這是一種混沌現(xiàn)象?；煦绗F(xiàn)象是指發(fā)生在確定性系統(tǒng)中的貌似隨機的不規(guī)則運動，一個確定性理論描述的系統(tǒng)，其行為卻表現(xiàn)為不確定性——不可重復(fù)、不可預(yù)測，這就是混沌現(xiàn)象。進一步研究表明，混沌是非線性動力系統(tǒng)的固有

16、特性，是非線性系統(tǒng)普遍存在的現(xiàn)象。,§3 誤差的基本概念,定義1 設(shè) 為準(zhǔn)確值 的近似值，記,誤差限 ： 的一個上界,即,相對誤差： 或 .(后者方便使用),相對誤差限 ： 的一個上界,即,例如，軸的設(shè)計尺寸,中0.01即是誤差限,(絕對)誤差 ：為正(負)時稱 為強(弱)近似值,例如，測得某人身高1.78m,尺子的誤差為1%,則實際身高 ：,3-1~2 誤

17、差與誤差限,§3 誤差的基本概念,§3 誤差的基本概念,3-3 有效數(shù)字,定義2 若近似值 的誤差限是某一位數(shù)字的半個單位，該位,到 的第一位非零數(shù)字共有n位，就說 有n位有效數(shù)字. 即,且,例如：對,——科學(xué)記數(shù)法, m+1位整數(shù),——e*的小數(shù)點后有n-(m+1)個零,注：稱為精確到,——保留n-(m+1)位小數(shù),最后一位經(jīng)四舍五入得到,§3 誤差的基本概念,有(m=0),例

18、1 設(shè)四個數(shù)：42.195, 0.0375551, 8.00033, 2.71828. 按四舍五入寫出上述各數(shù)具有4位有效數(shù)字的近似數(shù).,解 42.195的4位有效數(shù)字近似數(shù)為42.20, |e*|=0.005 0.0375551的4位有效數(shù)字近似數(shù)為0.03756,|e*|<0.000005 8.00033的4位有效數(shù)字近似數(shù)為8.000, |e*|<0.0005 2.7

19、1828的4位有效數(shù)字近似數(shù)為2.718, |e*|<0.0005,§3 誤差的基本概念,注意：8.00033的4位有效數(shù)字近似數(shù)是8.000, 而不是8. 又如：0.2300有4位有效數(shù)字，而00023只有2位有效. 12300如果寫成0.123?105，則表示只有3位有效數(shù)字. 數(shù)字末尾的0不可隨意省去！,§3 誤差的基本概念

20、,例2 重力加速度g=9.80m/s²,g=0.00980km/s².它們都具有3位 有效數(shù)字，其絕對誤差不同(限:0.5e-2,0.5e-5)， 但相對誤差(限)相同：,注: (1)相對誤差(限)沒有量綱，而絕對誤差有量綱. (2) 對于同一量的兩個不同近似值，可以通過其絕對誤差來判斷哪個更精確；對于兩個不同量的近似值，只有通過其相對誤差來比較其精確程度。,Def 1,2,例11

21、,例12,§3 誤差的基本概念,?有效數(shù)字與相對誤差的關(guān)系,? 有效數(shù)字 ? 相對誤差限,§3 誤差的基本概念,定理2？？？？,? 相對誤差限 ? 有效數(shù)字,§3 誤差的基本概念,例13,例14,§3 誤差的基本概念,3-4 數(shù)值運算的誤差估計,問題：設(shè)x的近似值為x* ，y的近似值為y* ，如下關(guān)系對嗎？,分析：,(x+y)*=x*+y* (xy)*=x*y*

22、 (x/y)*=x*/y*,§3 誤差的基本概念,1. 算術(shù)運算的誤差和絕對誤差限分析——特例,§3 誤差的基本概念,§3 誤差的基本概念,2 一般情況,問題：對于 y = f (x)，若用 x* 取代 x，將對y 產(chǎn)生什么影響？,分析：e (y*) = f (x*) ? f (x) e (x*) = x* ? x,Mean Value

23、Theorem,= f ?(? )(x* ? x),x* 與 x 非常接近時，可認為 f ?(? ) ? f ?(x*) ，則有|e (y*)| ? | f ?(x*)|·|e(x*)|.,即：x*產(chǎn)生的誤差經(jīng)過 f 作用后被放大/縮小了| f ?(x*)|倍。故稱| f ?(x*)|為放大因子 /* amplification factor */ 或 絕對條件數(shù) /* absolute condition numbe

24、r */.,§3 誤差的基本概念,,相對誤差條件數(shù) /* relative condition number*/,f 的條件數(shù)在某一點是小\大，則稱 f 在該點是好條件的 /* well-conditioned */ \壞條件的 /* ill-conditioned */。,Mean Value Theorem,§3 誤差的基本概念,例15 : 計算 y = ln x。若 x ? 20，則取 x 的幾

25、位有效數(shù)字可保證 y 的相對誤差 < 0.1% ?,解：設(shè)截取 n 位有效數(shù)字后得 x* ? x，則,估計 x 和 y 的相對誤差上限滿足近似關(guān)系,? n ? 4,例：計算 ，取 4 位有效，即 , 則相對誤差,§3 誤差的基本概念,§3 誤差的基本概念,例16,§3 誤差的基本概念,特例----算術(shù)運算的相對誤差和相對誤差限分析:,&#

26、167;3 誤差的基本概念,§3 誤差的基本概念,§3 誤差的基本概念,§3 誤差的基本概念,§4 誤差分析的方法與原則,1. 避免相近二數(shù)相減,例：a1 = 0.12345，a2 = 0.12346，各有5位有效數(shù)字。 而 a2 ? a1 = 0.00001，只剩下1位有效數(shù)字。,? 幾種經(jīng)驗性避免方法：,當(dāng) | x | << 1 時：,§

27、;4 誤差分析的方法與原則,3. 避免大數(shù)吃小數(shù),例：用單精度計算 的根。,精確解為,? 算法1：利用求根公式,在計算機內(nèi)，109存為0.1?1010，1存為0.1?101。做加法時，兩加數(shù)的指數(shù)先向大指數(shù)對齊，再將浮點部分相加。即1 的指數(shù)部分須變?yōu)?010，則：1 = 0.0000000001 ? 1010，取單精度時就成為： 109+1=0.10000

28、000?1010+0.00000000 ?1010=0.10000000 ?1010,大數(shù)吃小數(shù),,§4 誤差分析的方法與原則,算法2：先解出 再利用,注：求和時從小到大相加，可使和的誤差減小。,例：按從小到大、以及從大到小的順序分別計算1 + 2 + 3 + … + 40 + 109,4. 先化簡再計算，減少步驟，避免誤差積累。,一般來說，計算機處理下列運算的速度為,5. 選用穩(wěn)定的算法。,,評價算法

29、的準(zhǔn)則：復(fù)雜度、精度、穩(wěn)定性,§4 誤差分析的方法與原則,,“天河一號”是中國自主研制的超級計算機，坐落在位于天津的國家超級計算中心，由140個計算機柜組成，用來執(zhí)行大規(guī)模科學(xué)計算。自身沒有鍵盤和鼠標(biāo)，是通過網(wǎng)絡(luò)的方式讓用戶來登陸它使用它。所以，當(dāng)用戶通過個人的計算機登錄到“天河一號”上后，他的PC機已經(jīng)成為“天河一號”的末梢神經(jīng)，成為一臺終端設(shè)備?！疤旌右惶枴背売嬎銠C提供的計算方式是現(xiàn)在業(yè)界叫作“云計算”的計算方式。

30、 12年美國總統(tǒng)奧巴馬在一次講話中說：現(xiàn)在，不僅世界上速度最快的火車在中國？而且中國還制造出了世界上速度最快的超級計算機。,,戰(zhàn)略計算,?這是因為美國克林頓總統(tǒng)在1995 年8月11 日宣布：“美國決定謀求真正的“零當(dāng)量”全面禁止試驗核武器條約”。?這并不意味著核競賽的結(jié)束，恰恰相反是核武器計劃新時代的開始，要求通過逼真的建模和模擬計算來取代傳統(tǒng)的反復(fù)試驗的工程處理方法，這主要依賴于先進的數(shù)值計算和模擬能力。? 1995年8

31、月22日（即美國總統(tǒng)宣布決定后的11天），能源部DOE就采購世界上最快的一臺計算機（速度超過萬億次運算）交付圣地亞哥實驗室（96年12月安裝）。? 1998年7月30-31日，美國DOE/FNS 共同聯(lián)合組織召開了關(guān)于“先進科學(xué)計算”的全國會議，會議強調(diào)科學(xué)模擬的重要性，希望應(yīng)用科學(xué)模擬來攻克復(fù)雜的科學(xué)與工程難題。,Chapter 1 Introduction,,計算機發(fā)展的四個階段 1.第一代計算機：電子管數(shù)字計算機

32、（1946-1958年）    硬件方面，邏輯元件采用電子管，主存儲器采用汞延遲線、磁鼓、磁芯；外存儲器采用磁帶。軟件方面采用機器語言、匯編語言。應(yīng)用領(lǐng)域以軍事和科學(xué)計算為主。特點是體積大、功耗高、可靠性差、速度慢（一般為每秒數(shù)千次至數(shù)萬次）、價格昂貴，但為以后的計算機發(fā)展奠定了基礎(chǔ)。,,2.第二代計算機：晶體管數(shù)字計算機（1958-1964年） 

33、60;  硬件方面，邏輯元件采用晶體管，主存儲器采用磁芯，外存儲器采用磁盤。軟件方面出現(xiàn)了以批處理為主的操作系統(tǒng)、高級語言及其編譯程序。應(yīng)用領(lǐng)域以科學(xué)計算和事務(wù)處理為主。并開始進入工業(yè)控制領(lǐng)域。特點是體積縮小、能耗降低、可靠性提高、運算速度提高（一般為每秒數(shù)十萬次，可高達300萬次）、性能比第一代計算機有很大的提高。,,3.第三代計算機：集成電路數(shù)字計算機（1964-1970年）

34、0;   硬件方面，邏輯元件采用中、小規(guī)模集成電路，主存儲器仍采用磁芯。軟件方面出現(xiàn)了分時操作系統(tǒng)以及結(jié)構(gòu)化、規(guī)?；绦蛟O(shè)計方法。特點是速度更快（一般為每秒數(shù)百萬至數(shù)千萬次）。而且可靠性有了顯著提高，價格進一步下降，產(chǎn)品走向通用話、系列化和標(biāo)準(zhǔn)化。應(yīng)用領(lǐng)域開始進入文字處理和圖形圖像處理領(lǐng)域。,,4.第四代計算機：大規(guī)模集成電路計算機（1970年至今） 硬件方面，邏輯元

35、件采用大規(guī)模和超大規(guī)模集成電路，軟件方面出現(xiàn)了數(shù)據(jù)庫管理系統(tǒng)、網(wǎng)絡(luò)管理系統(tǒng)和面向?qū)ο笳Z言等。特點是1971年世界上第一臺微處理器在美國硅谷誕生，開始了微型計算機的新時代。應(yīng)用領(lǐng)域從科學(xué)計算、事務(wù)管理、過程控制伜步走向家庭。,Chapter 1 Introduction,,蝴蝶效應(yīng)（Butterfly Effect）是指在一個動力系統(tǒng)中，初始條件下微小的變化能帶動整個系統(tǒng)的長期的巨大的連鎖反應(yīng)。這是一種混沌現(xiàn)象?；煦绗F(xiàn)象 混沌

36、現(xiàn)象是指發(fā)生在確定性系統(tǒng)中的貌似隨機的不規(guī)則運動，一個確定性理論描述的系統(tǒng)，其行為卻表現(xiàn)為不確定性一不可重復(fù)、不可預(yù)測，這就是混沌現(xiàn)象。進一步研究表明，混沌是非線性動力系統(tǒng)的固有特性，是非線性系統(tǒng)普遍存在的現(xiàn)象。,,這句話的來源，是由于這位氣象學(xué)家制作了一個電腦程序，可以模擬氣候的變化，并用圖像來表示。最后他發(fā)現(xiàn)，圖像是混沌的，而且十分像一只蝴蝶張開的雙翅，因而他形象的將這一圖形以“蝴蝶扇動翅膀”的方式進行闡釋，于是便有了上述的說法。,

37、,蝴蝶效應(yīng)通常用于天氣，股票市場等在一定時段難于預(yù)測的比較復(fù)雜的系統(tǒng)中。此效應(yīng)說明，事物發(fā)展的結(jié)果，對初始條件具有極為敏感的依賴性，初始條件的極小偏差，將會引起結(jié)果的極大差異。,,蝴蝶效應(yīng)在社會學(xué)界用來說明：一個壞的微小的機制，如果不加以及時地引導(dǎo)、調(diào)節(jié)，會給社會帶來非常大的危害，戲稱為“龍卷風(fēng)”或“風(fēng)暴”；一個好的微小的機制，只要正確指引，經(jīng)過一段時間的努力，將會產(chǎn)生轟動效應(yīng)，或稱為“革命”。　　蝴蝶效應(yīng)在混沌學(xué)中也常出現(xiàn)。又被稱