計算方法-1-緒論

1、2021-7-71 第一章 引論 2021-7-72 第一章 引論 1.3 誤差 1.1 數(shù)值計算的研究對象與特點 1.2 數(shù)值問題與數(shù)值方法 2021-7-73 本章要點:絕對誤差(限)和相對誤差(限) 有效數(shù)字位數(shù)及其與誤差的關系 數(shù)值問題的性態(tài)與誤差的關系 數(shù)值算法設計原則 2021-7-74 數(shù)值分析數(shù)值分析 能夠做什么？ Introduction 2021-7-75 研究使用計算機求解各種科學與工研究使用計算機求解各種科學與工 程計算問題的數(shù)值方法（近似方法），程計算問題的數(shù)值方法（近似方法）， 對求得的解的精度進行評估，以及如何對求得的解的精度進行評估，以及如何 在計算機上實現(xiàn)求解

2、等。在計算機上實現(xiàn)求解等。 數(shù)值分析課程中所講述的各種數(shù)值方數(shù)值分析課程中所講述的各種數(shù)值方 法在科學與工程計算、信息科學、管理法在科學與工程計算、信息科學、管理 科學、生命科學等交叉學科中有著廣泛科學、生命科學等交叉學科中有著廣泛 的應用。的應用。 2021-7-76 應用問題舉例 今有上禾三秉，中禾二秉，下禾一秉，實三今有上禾三秉，中禾二秉，下禾一秉，實三 十九斗；十九斗； 上禾二秉，中禾三秉，下禾一秉，實三上禾二秉，中禾三秉，下禾一秉，實三 十四斗；十四斗； 上禾一秉，中禾二秉，下禾三秉，實二上禾一秉，中禾二秉，下禾三秉，實二 十六斗。十六斗。 問上、中、下禾實一秉各幾何？問上、中、下禾

3、實一秉各幾何？ 答曰：上禾一秉九斗四分斗之一。中禾一秉答曰：上禾一秉九斗四分斗之一。中禾一秉 四斗四分斗之一。下禾一秉二斗四分斗之三。四斗四分斗之一。下禾一秉二斗四分斗之三。 -九章算術九章算術 2021-7-77 2632 3432 3923 zyx zyx zyx 1、一個兩千年前的例子 2021-7-78 nnnn n n aaa aaa aaa 21 22221 11211 bxA nn b b b x x x 2 1 2 1 本課程第六章的內容：本課程第六章的內容： 線性代數(shù)方程組的數(shù)值解法！線性代數(shù)方程組的數(shù)值解法！ 2021-7-79 2、天體力學中的Kepler方程 x是行星運

4、動的軌道，它是時間t 的函數(shù) sin0,01xxt 本課程第七章的內容： 非線性代數(shù)方程的求根 2021-7-710 全球定位系統(tǒng)： 在地球的任何 一個位置，至 少可以同時收 到4顆以上衛(wèi)星 發(fā)射的信號 3、全球定位系統(tǒng)（Global Positioning System, GPS) 2021-7-711 0 2 4 6 8 0 5 10 0 2 4 6 8 圖 7.8 Height S6 S3 S4 S2 S1 R S5 N-S positions 表示地球上 一個接收點R的當前位 置，衛(wèi)星Si的位置為 ，則得 到下列非線性方程組： ( , , , )x y z t (, ) iiii xy

5、 z t 222 1111 222 2222 222 3333 222 4444 222 5555 222 6666 ()()()(t -t)0 ()()()(t -t)0 ()()()(t -t)0 ()()()(t -t)0 ()()()(t -t)0 ()()()(t -t) xxyyzzc xxyyzzc xxyyzzc xxyyzzc xxyyzzc xxyyzz 0c 2021-7-712 非線性方程組的數(shù)值方法（不講）非線性方程組的數(shù)值方法（不講） 112 212 12 (,)0 (,)0 (,)0 n n nn fxxx fxxx fxxx ( )0F x 記為記為 其中其中

6、:, nn F DRR 12 ( ,)T n xx xx 2021-7-713 4、已經(jīng)測得在某處海洋不同深度處的水溫如下： 深度（M） 466 741 950 1422 1634 水溫（） 7.04 4.28 3.40 2.54 2.13 根據(jù)這些數(shù)據(jù)，希望合理地估計出其它深度（如500米， 600米，1000米）處的水溫 本課程第二章的內容：插值法 2021-7-714 5、用比較簡單的函數(shù)代替復雜的函數(shù) 誤差為最小，即距離為最小 （在不同的度量意義下） 本課程第三章的內容：函數(shù)逼近 2021-7-715 6、人口預測 下 面 給 出 的 是 中 國 1950年到2000年的人 口數(shù)，我們

7、的目標是 預測未來的人口數(shù) （數(shù)據(jù)量較大時） 195055196 196066207 197082992 198098705 1990114333 2000126743 43 2 2 3 1 ttty 30/ )1979( ts 43 2 2 3 1 sssy 2021-7-716 本課程第三章的內容：曲線擬合 2021-7-717 7、鋁制波紋瓦的長度問題、鋁制波紋瓦的長度問題 建筑上用的一種鋁制波紋瓦是用一種機器將一建筑上用的一種鋁制波紋瓦是用一種機器將一 塊平整的鋁板壓制而成的塊平整的鋁板壓制而成的. 假若要求波紋瓦長假若要求波紋瓦長4848英尺英尺, ,每個波紋的高度每個波紋的高度(

8、(從中心從中心 線線) )為為1 1英寸英寸, ,且每個波紋以近似且每個波紋以近似2 2英寸為一個周期英寸為一個周期. . 求制做一塊波紋瓦所需鋁板的長度求制做一塊波紋瓦所需鋁板的長度L.L. 2021-7-718 這個問題就是要求由函數(shù)這個問題就是要求由函數(shù) dxxdxxfL 48 0 2 48 0 2 )(cos1)(1 上述積分稱為第二類橢圓積分上述積分稱為第二類橢圓積分, ,它不能用普它不能用普 通方法來計算通方法來計算. 本課程第四章的內容：數(shù)值積分 2021-7-719 8、生物化學反應的例子 A，B，C是三種蛋白質，其反應如下： 1 2 3 a a a AB BBCB BCAC

9、2021-7-720 我們通過建?？梢缘玫饺缦路匠探M 111323 ya ya y y 1(0) 1y 2 21132322 ya ya y ya y2(0) 0y 3 y 2 22 a y3(0) 0y A： B： C： 本課程第九章的內容： 常微分方程初值問題的數(shù)值解法 2021-7-721 xxG T 1ex T G: Google Matrix, “the worlds largest matrix computation”. 4,300,000,000 x: PageRank vector “The $25,000,000,000 Eigenvector” 9、Google搜索引擎

10、2021-7-722 本課程第六章的內容： 矩陣代數(shù) xAx 2021-7-723 1.1 計算機數(shù)值方法的研究對象與特點 以計算機為工具,求解各種數(shù)學模型,都要經(jīng)歷三個過程: 總體設計模型的細化 詳細設計主要為算法設計 程序設計 計算機數(shù)值方法研究的是將數(shù)學模型化為數(shù)值問題， 并研究求解數(shù)值問題的數(shù)值方法進而設計數(shù)值算法 2021-7-724 數(shù)值問題： 輸入數(shù)據(jù)與輸出數(shù)據(jù)之間函數(shù)關系的 一個確定而無歧義的描述 即：輸入與輸出的都是數(shù)值的數(shù)學問題 如求解線性方程組 BAy 求解二次方程0 2 cbxax cbaBA,與系數(shù)常數(shù)項向量輸入的數(shù)據(jù)是系數(shù)矩陣 是數(shù)值問題 一、數(shù)值問題 1.2 數(shù)值

11、問題與數(shù)值算法 2021-7-725 求解微分方程 0)0( 32 y xy 不是數(shù)值問題 xxy3, 2 函數(shù)但輸出的不是數(shù)據(jù)而是輸入的雖是數(shù)據(jù) 將其變成數(shù)值問題，即將其“離散化” xxy3 2 即將求函數(shù) nn xxxxyxyxy 2121 ),(,),(),(改變成求函數(shù)值 “離散化”是將非數(shù)值問題的數(shù)學模型化為數(shù)值問題 的主要方法，這也是計算方法的任務之一 21, ,xxy 和方程的解輸出的數(shù)據(jù)是解向量 2021-7-726 二、數(shù)值方法 數(shù)值方法: 是指解數(shù)值問題的在計算機上 可執(zhí)行的系列計算公式 在計算機上可執(zhí)行的公式 是指只含有加減乘除的公式 現(xiàn)在的計算機中幾乎都含有關于開方的標

12、準函數(shù)sqrt() 常見的在計算機上不能直接運行的計算有: 開方、極限、超越函數(shù)、微分、積分等等 要在計算機上實行上述運算需將其化為可執(zhí)行的等價 或近似等價運算 2021-7-727 x e超越函數(shù)應化為 ! 2 1 2 n xx xe n x 的計算應化為的導數(shù)函數(shù))()(xyxy h xyhxy xy )()( )( 如求根公式 a acbb x 2 4 2 2,1 應化為公式 a acbsqrtb x 2 )4( 2 2,1 2021-7-728 研究數(shù)值方法的主要任務: 1.將計算機上不能執(zhí)行的運算化為在計算機上可 執(zhí)行的運算 2.針對所求解的數(shù)值問題研究在計算機上可執(zhí)行 的且有效的計

13、算公式 3.因為可能采用了近似等價運算,故要進行誤差分析, 即數(shù)值問題的性態(tài)及數(shù)值方法的穩(wěn)定性 2021-7-729 三、數(shù)值算法 數(shù)值算法是指有步驟地完成解數(shù)值問題的過程. 數(shù)值算法有四個特點: 1.目的明確 算法必須有明確的目的,其條件和結論 均應有清楚的規(guī)定 2.定義精確對算法的每一步都必須有精確的定義 3.可執(zhí)行算法中的每一步操作都是可執(zhí)行的 4.步驟有限算法必須在有限步內能夠完成解題過程 2021-7-730 四、氣象問題與數(shù)值方法 物理模型 流體力學Eqs 熱力學Eqs 計算機數(shù)值預報 計算機數(shù)值模擬 計算機資料分析 定性描述定性描述定量結果定量結果 計算機 工具工具 數(shù)值計算方法

14、 編程 手段手段 手段和橋梁作用手段和橋梁作用 2021-7-731 1.3 數(shù)值計算的誤差 一、誤差的種類及來源 模型誤差 在建立數(shù)學模型過程中在建立數(shù)學模型過程中,要將復雜的現(xiàn)象抽象歸結為要將復雜的現(xiàn)象抽象歸結為 數(shù)學模型數(shù)學模型,往往要忽略一些次要因素的影響往往要忽略一些次要因素的影響,而對問題而對問題 作一些簡化作一些簡化,因此和實際問題有一定的區(qū)別因此和實際問題有一定的區(qū)別. 觀測誤差 在建模和具體運算過程中所用的數(shù)據(jù)往往是通過觀察在建模和具體運算過程中所用的數(shù)據(jù)往往是通過觀察 和測量得到的和測量得到的,由于精度的限制由于精度的限制,這些數(shù)據(jù)一般是近似這些數(shù)據(jù)一般是近似 的的,即有誤

15、差即有誤差. 截斷誤差截斷誤差 由于計算機只能完成有限次算術運算和邏輯運算由于計算機只能完成有限次算術運算和邏輯運算,因此要因此要 將有些需用極限或無窮過程進行的運算有限化將有些需用極限或無窮過程進行的運算有限化,對無窮過對無窮過 程進行截斷程進行截斷,這就帶來誤差這就帶來誤差 2021-7-732 ! 3! 2 1 32 xx xe x ! 7! 5! 3 sin 753 xxx xx ! 4! 3! 2 )1ln( 432 xxx xx 如: 若將前若干項的部分和作為函數(shù)值的近似公式, 由于以后各項都舍棄了,自然產生了誤差 Taylor展開 2021-7-733 舍入誤差 在數(shù)值計算過程中

16、還會遇到無窮小數(shù)在數(shù)值計算過程中還會遇到無窮小數(shù),因計算機受到因計算機受到 機器字長的限制機器字長的限制,它所能表示的數(shù)據(jù)只能有一定的有它所能表示的數(shù)據(jù)只能有一定的有 限位數(shù)限位數(shù),如按四舍五入規(guī)則取有限位數(shù)如按四舍五入規(guī)則取有限位數(shù),由此引起的誤由此引起的誤 差差 14159265. 3 414213562. 12 166666666. 0 6 1 ! 3 1 1415927. 3 4142136. 12 16666667. 0 ! 3 1 過失誤差 由于模型錯誤或方法錯誤引起的誤差由于模型錯誤或方法錯誤引起的誤差. 這類誤差一般可以避免這類誤差一般可以避免 2021-7-734 數(shù)值計算中

17、除了過失誤差可以避免外數(shù)值計算中除了過失誤差可以避免外,其余誤差都是其余誤差都是 難以避免的難以避免的.數(shù)學模型一旦建立數(shù)學模型一旦建立,進入具體計算時所考進入具體計算時所考 慮和分析的就是慮和分析的就是截斷誤差和舍入誤差截斷誤差和舍入誤差 經(jīng)過大量的運算之后經(jīng)過大量的運算之后,積累的總誤差有時會大得驚人積累的總誤差有時會大得驚人, 因此如何控制誤差的傳播也是數(shù)值方法的研究對象因此如何控制誤差的傳播也是數(shù)值方法的研究對象. 二、誤差和誤差限二、誤差和誤差限 定義1. 稱的一個近似值為為準確值設, * xxx xxe * ., * 簡稱誤差的絕對誤差為近似值 x 2021-7-735 知道的往往

18、是未知甚至是無法因為準確值 x 往往也無法求出因此xxe * 即絕對值的某個上界而只能知道, * xxe * |xxe 的稱為數(shù)值 * x絕對誤差限絕對誤差限或誤差限誤差限. 顯然 * xxx的范圍準確值 x 或 * xx 0 * 且 2021-7-736 215 x若對于 51000 y 15 * x 1000 * y 2 * 5 * 哪個更精確呢?嗎？15 * x 定義2. 稱的一個近似值為為準確值設, * xxx x xx x e er * * 對誤差的相為近似值 * x * * r x xx 的相對誤差限為近似值 * x 2021-7-737 | * * x r 絕對誤差限 相對誤差限

19、 往往未知 * * * * * x xx x er | * * * x r 代替相對誤差 代替相對誤差限 15 * x 1000 * y 2 * 5 * 因此 %33.13 15 2 * r %5 . 0 1000 5 * r 2021-7-738 例1. . ,28718. 2,82281718. 2 * * r x xx 和相對誤差限的絕對誤差限求 其近似值為已知 解:xxe * 絕對誤差 82001000. 0 82001000. 0 * e002000. 0 6 102 | * * * x r 28718. 2 102 6 28718. 2 102 6 6 1071. 0 2021-7

20、-739 例2. . ,7 , 5 , 3 * 求絕對誤差限 位數(shù)的近似值經(jīng)四舍五入取小數(shù)點后若 解: 65592141. 3 59141. 3 * 142. 3 * 7592141. 3 * * | 407000. 0 * 65002000. 0 * 04000000. 0 * 3 105 . 0 5 105 . 0 7 105 . 0 可見,經(jīng)四舍五入取近似值,其絕對誤差限將 不超過其末位數(shù)字的半個單位 2021-7-740 有4位有效數(shù)字 有6位有效數(shù)字 三、有效數(shù)字和可靠數(shù)字 定義3. 若近似值x*的誤差限是某一位的半個單位，該 位到x*的第一位非零數(shù)字共有n位，就說x*有n 位有效數(shù)

21、字有效數(shù)字. 65592141. 3 59141. 3 * 142. 3 * 7592141. 3 * 有8位有效數(shù)字 1415. 3 * 只有4位有效數(shù)字 2021-7-741 形式的下列形式稱為規(guī)格化的近似值 * xx )1010(10 )1(1 21 * n n m aaax 具有n位有效數(shù)字 * x 且 )1(* 105 . 0| nm xx 為整數(shù), 0 1 ma 其中 從以上分析可見,四舍五入四舍五入的近似值的數(shù)字都是有效數(shù)字 而不是四舍五入得到的近似值的數(shù)字不一定是有效數(shù)字 2021-7-742 例3. 個近似值有設395. 3x 0 . 4 * 1 x9 . 3 * 2 x4

22、* 3 x | * 1 xx |95. 30 . 4|05. 0 1 105 . 0 | * 2 xx |95. 39 . 3| 05. 0 1 105 . 0 | * 3 xx |95. 34| 05. 0 1 105 . 0 效數(shù)字兩個有都具有,知3,根據(jù)定 義 * 2 * 1 xx ?效數(shù)字 嗎兩個有也具有 * 3 x實際上只有1個 2021-7-743 定理1. 的近似值的表達式為作為若xx * 則其相對誤差限滿足位有效數(shù)字,有若(1)nx* 位有效數(shù)字至少有則nx * )1( 1 * 10 2 1 n r a 滿足誤差限的相 對若,反之(2) * x )1( 1 * 10 ) 1(2

23、 1 n r a )1010(10 )1(1 21 * l l m aaax 2021-7-744 例4. 解: . 420 1 a的首位數(shù)是 .*20位有效數(shù)字有的近似值設nx n r ax xx 1 1 * * * 10 2 1 | | 則由定理1,相對誤差限滿足 001. 010 42 1 1 n %1 . 0 097. 3n 即應取4位有效數(shù)字,近似值的誤差限不超過0.1% 要使 20的相對誤差不超過0.1%，應至少取 幾位有效數(shù)字？ 定義4. 若近似值x*的誤差限是它保留的最后位上的 一個單位，x*的第一位非零數(shù)字到保留的最 后一位共有n位，就說x*有n位可靠數(shù)字可靠數(shù)字. 2021

24、-7-746 四、數(shù)值運算的誤差估計 )0( )()( )( )()()( )()()( 2 2 2 1221 2 1 122121 2121 * * * * * * * x x xxxx x x xxxxxx xxxx ； ； * x2兩個近似數(shù) 與 ，其誤差限分別為 及 ，它們進行加、減、乘、除運算 得到的絕對誤差限分別為： )( 1 * x )( 2 * x * x1 )0()()()( )()()( )()()( 221 2 1 2121 2121 * r * r* * r * r * r * r * r * r * r xxx x x xxxx xxxx ； ； 相對誤差限的四則運算

25、 2021-7-748 五、數(shù)值方法的穩(wěn)定性與算法設計原則 例5. 1 0 1 dxex e I xn n 計算定積分 7 , 2 , 1 , 0n 解: n I 1 0 1 xnde x e 1 0 1 xne x e 1 0 1 dxex e n xn 1 1 n nI , 0 I如果先計算 721 ,III然后再計算 2021-7-749 , * 00 II 的近似值為假設計算出)( * 0 IE誤差為 )( * 1 * 11 IEII的誤差為的近似值則 2)( * 2 * 22 IEII的誤差為的近似值 ! 3)( * 3 * 33 IEII的誤差為的近似值 ! 7)( * 7 * 7

26、7 IEII的誤差為的近似值5040 誤差放大 5千倍! n I I n n 1 1 但如果利用遞推公式 , 7 I先計算!5 70 千分之一誤差的的誤差只有II 2021-7-750 因此在計算公式選用及算法設計時,應注意以下原則 1. 四則運算中的穩(wěn)定性問題 (1) 防止大數(shù)吃小數(shù) 這一類問題主要由計算機的位數(shù)引起 假如做一個有效數(shù)字為4位的連加運算 1 1 nn nII公式 n I I n n 1 1 公式 誤差會放大 誤差不會放大 2021-7-751 4012. 04697. 04896. 04987. 01234. 010 4 1234. 010 4 4697. 0 ,4896.

27、0 ,4987. 01234. 010 4 吃了將小數(shù)大數(shù) 而如果將小數(shù)放在前面計算 1234. 0104012. 04697. 04896. 04987. 0 4 1236. 010 4 在作連加時,為防止大數(shù)吃小數(shù),應從小到大進行相加, 如此,精度將得到適當改善.當然也可采取別的方法. 2021-7-752 (2) 作減法時應避免相近數(shù)相減 兩個相近的數(shù)相減,會使有效數(shù)字的位數(shù)嚴重損失 01. 0cos1 5 10999958. 4 xcos1 2 sin2 2 x 2 01. 0 sin2 2 5 10999958333. 4 由于 在算法設計中,若可能出現(xiàn)兩個相近數(shù)相減,則改變 計算公式,如使用三角變換、有理化等等 2021-7-753 例9.解方程010)110( 992 xx 解: 由中學知識韋達定理可知,方程的精確解為 9 1 10 x 1 2 x a acbsqrtb x 2 )4( 2 2,1