計(jì)算方法第一章

1、 教教 材材： 數(shù)值計(jì)算方法 曾金平 主編 湖南大學(xué)出版社，2006 參考教材：參考教材： 計(jì)算方法 鄧建中，劉之行 編 西安交通大學(xué)出版社，2004 前期課程前期課程： 數(shù)學(xué)分析、高等代數(shù)、常微分方程 引引 言言第一章 隨著科學(xué)技術(shù)的飛速發(fā)展，科學(xué)計(jì)算愈來愈顯示出其重要性?？茖W(xué)計(jì)算的應(yīng)用之廣已遍及各行各業(yè)，例如：氣象資料的分析圖像，飛機(jī)、汽車及輪船的外形設(shè)計(jì)，高科技研究等都離不開科學(xué)計(jì)算。因此，作為科學(xué)計(jì)算的數(shù)學(xué)工具數(shù)值計(jì)算方法，已成為各高等院校數(shù)學(xué)、物理和計(jì)算機(jī)應(yīng)用專業(yè)等理工科本科生的專業(yè)基礎(chǔ)課，也是工科碩士研究生的學(xué)位必修課。 計(jì)算數(shù)學(xué)：計(jì)算數(shù)學(xué)：常稱為數(shù)值分析或（數(shù)值）計(jì)算方法。 主要

2、是研究如何運(yùn)用計(jì)算工具（如計(jì)算 器、計(jì)算機(jī)等）去獲得數(shù)學(xué)問題的數(shù)值數(shù)值 解解的理論和方法。當(dāng)代實(shí)踐表明：計(jì)算方法正在日趨明顯地成為數(shù)學(xué) 與計(jì)算機(jī)科學(xué)的交叉性科學(xué)。 對(duì)那些在經(jīng)典數(shù)學(xué)中，用解析方法在理論上已作出解的存在，但要求出他的解析解又十分困難，甚至是不可能的這類數(shù)學(xué)問題，數(shù)值解法就顯得不可缺少，同時(shí)又十分有效。邊緣科學(xué)：計(jì)算物理，計(jì)算力學(xué)，計(jì)算化學(xué)， 計(jì)算生物學(xué)，計(jì)算經(jīng)濟(jì)學(xué)等。算法算法：從給定的已知量出發(fā)，經(jīng)過有限次四則運(yùn)算及規(guī)定的運(yùn)算順序，最后求出未知量的數(shù)值解，這樣構(gòu)成的完整計(jì)算步驟稱為算法。運(yùn)算量運(yùn)算量( (計(jì)算量計(jì)算量) )： 一個(gè)算法所需的乘除運(yùn)算總次數(shù)計(jì)算量是衡量一個(gè)算法好壞的

3、重要指標(biāo)計(jì)算量是衡量一個(gè)算法好壞的重要指標(biāo)! !計(jì)算數(shù)學(xué)的根本任務(wù)就是研究算法計(jì)算數(shù)學(xué)的根本任務(wù)就是研究算法 研究數(shù)值算法的任務(wù)主要有：研究數(shù)值算法的任務(wù)主要有：(1) 構(gòu)造計(jì)算機(jī)上可執(zhí)行的算法構(gòu)造計(jì)算機(jī)上可執(zhí)行的算法(2) 構(gòu)造計(jì)算復(fù)雜性好的算法構(gòu)造計(jì)算復(fù)雜性好的算法(3) 構(gòu)造可靠性好的數(shù)值方法構(gòu)造可靠性好的數(shù)值方法計(jì)算機(jī)上可執(zhí)行的運(yùn)算： 四則運(yùn)算邏輯運(yùn)算盡可能提高數(shù)值方法的計(jì)算速度和少占存貯空間。選擇或研制能達(dá)到“數(shù)值問題”要求的計(jì)算精度的數(shù)值方法，為此須研究數(shù)值問題的性態(tài)及數(shù)值方法的穩(wěn)定性。計(jì)算方法：把求解數(shù)學(xué)問題轉(zhuǎn)化為按一定次序只 進(jìn)行加、減、乘、除等基本運(yùn)算 數(shù)值方法。例例1 1.

4、1.1求二次方程02cbxax求根公式為：aacbbx2422,1aacbsqrtbx2)4(22,1的根。開方運(yùn)算不能在計(jì)算機(jī)上直接進(jìn)行運(yùn)算，必須化為可在計(jì)算機(jī)上執(zhí)行的等價(jià)運(yùn)算。即應(yīng)化為公式：例例1.1.2 已知 a0, a1, a2 , an, x, 計(jì)算多項(xiàng)式：1110( ).nnnnp xa xaxa xa直接計(jì)算：運(yùn)算量（乘法）1(1)21(1).2nnn n 秦九韶算法（1247年）：1210( )( ()nnnp xx xx a xaaaa10,1,2,1,0( )nnkkkbabbxa knnp xb運(yùn)算量：. n例例1.1.3 解線性方程組,Axb其中，1212(),( ,)

5、 ,( ,) .TTijn nnnAaxx xxbb bb 克蘭姆(Cramer)法則：,1,2, .iiAxinA 運(yùn)算量(乘除)：(1)! (1)(1)! (1)nnnnnn高斯消元法(Gauss)：運(yùn)算量(乘除)3211.33nnn2 0n 取Gauss: 3060次Cramer:121930.78(10/)19(20+1)! (20-1)5.1 10年次 秒理論上很理論上很“漂亮漂亮”的的CramerCramer法法則則 在計(jì)算機(jī)上并不適用！在計(jì)算機(jī)上并不適用！一個(gè)計(jì)算過程主要包括如下幾個(gè)環(huán)節(jié)：一個(gè)計(jì)算過程主要包括如下幾個(gè)環(huán)節(jié)：(1) 數(shù)學(xué)建模數(shù)學(xué)建模：將工程問題數(shù)學(xué)化工程中的數(shù)學(xué)模型

6、一般可分為三類：(2) 算法設(shè)計(jì)算法設(shè)計(jì)：將數(shù)學(xué)問題數(shù)值化連續(xù)型（確定型）離散型（統(tǒng)計(jì)型）不確定型（隨機(jī)型）本書重點(diǎn)討論例1.1.4 求解線性方程組bAx 求解二次方程02cbxax是數(shù)值問題cbabA,與系數(shù)常數(shù)項(xiàng)向量輸入的數(shù)據(jù)是系數(shù)矩陣21,xxx 和方程的解輸出的數(shù)據(jù)是解向量求解微分方程0)0(32yxy不是數(shù)值問題xxy3,2函數(shù)但輸出的不是數(shù)據(jù)而是輸入的雖是數(shù)據(jù)將其變成數(shù)值問題，即將其“離散化”xxy32即將求函數(shù)nnxxxxyxyxy2121),(,),(),(改變成求函數(shù)值“離散化”是將非數(shù)值問題的數(shù)學(xué)模型化為數(shù)值問題的主要方法，這也是計(jì)算方法的任務(wù)之一(3) 程序設(shè)計(jì)程序設(shè)計(jì)：

7、將數(shù)值問題機(jī)器化軟件開發(fā)方法：結(jié)構(gòu)化方法：面向過程，“自頂而下，逐步細(xì)化”其關(guān)鍵方面：劃分模塊設(shè)計(jì)或選擇模塊的算法充實(shí)細(xì)節(jié)組裝式開發(fā)方法： 面向?qū)ο?，“自下向上”例?.1.5求二次方程02cbxax的根。此問題本身可看成功能單一的模塊數(shù)值方法：直接方法，即用求根公式迭代方法（后面將介紹）須考慮的細(xì)節(jié)：24dbac當(dāng)大于零或小于零時(shí)，需選用不同的公式0ddb當(dāng)且時(shí)，會(huì)出現(xiàn)兩個(gè)近似數(shù)相減而影響有效數(shù)字的位數(shù)a當(dāng)| |較|b|和|c|相對(duì)小很多時(shí)，有可能出現(xiàn)舍入誤差增大(4) 上機(jī)運(yùn)行上機(jī)運(yùn)行：數(shù)值模擬物理過程(5) 計(jì)算結(jié)果再表示計(jì)算結(jié)果再表示：如圖像的可視化等(6) 可靠性分析可靠性分析：分析

8、計(jì)算結(jié)果的可靠性，必要時(shí) 重復(fù)上述過程。其中算法設(shè)計(jì)是本書的核心內(nèi)容。本書針對(duì)來源于科學(xué)與工程中的數(shù)學(xué)模型問題，介紹計(jì)算機(jī)上常用的數(shù)值方法的算法設(shè)計(jì)思想并進(jìn)行算法分析。 本書研究?jī)?nèi)容：本書研究?jī)?nèi)容：對(duì)如下五類問題探索數(shù)值求解方法 及其與算法有關(guān)的理論分析(1)(1) 非線性方程求根(2) 求解線性代數(shù)方程組的數(shù)值方法(3) 數(shù)值逼近：插值逼近和最佳逼近(4) 數(shù)值微分和數(shù)值積分(5)(5) 常微分方程數(shù)值解法 將問題可算化的手段：將問題可算化的手段：將問題可算化是設(shè)計(jì)一個(gè)算 法的第一步(1)(1) 用有限維空間代替無(wú)限維空間(2) 用有限過程代替無(wú)限過程(3) 用簡(jiǎn)單問題代替復(fù)雜問題(4) 擾

9、動(dòng)分析：估計(jì)誤差或精度余項(xiàng)(即截?cái)嗾`差)為246221( 1)cos1R( ).24!6!(2 )!nnnxxxxxxn cosxx計(jì)算的值，其中已知角 的弧度在0和 之間。例例1.1.6解解246221( 1)cos( )1.24!6!(2 )!nnnxxxxxpxn 2121( )cos( ).nnRxxpx根據(jù)微分學(xué)的Taylor公式，有將問題可算化，即用有限過程代替無(wú)限過程僅包含有限次的四則運(yùn)算 構(gòu)造算法的途徑：構(gòu)造算法的途徑：(多用于確定型連續(xù)的數(shù)學(xué)模型)(1)(1) 迭代技術(shù)（迭代法）(2) 離散化技術(shù)(3) 離散問題解析化技術(shù)(4) 優(yōu)化技術(shù)000( )()()(),f xf x

10、fxxx( )0 , f xa b求非線性方程在上的實(shí)根。例例1.1.7解解000( )()()().f xf xfxxx111000()().xxxxfxf x從此式解出 ，記為 ，即若已知根的粗略近似值，根據(jù)Taylor公式，有取等式右邊前二項(xiàng)近似替代f(x)，就會(huì)得到容易求解的線性方程10201kxxxxxx用 代替上面的 ，進(jìn)行類似計(jì)算， 即可得 。如此繼續(xù)下去，可得一系列根的近似值, , ,稱為迭代序列11().)()kkkkxxfxf x其中Newton迭代法對(duì)于迭代法，通常需考慮迭代對(duì)于迭代法，通常需考慮迭代序列的收斂性與收斂效率！序列的收斂性與收斂效率！計(jì)算公式中的運(yùn)算必須是在

11、計(jì)算機(jī)上可執(zhí)行的運(yùn)算參與運(yùn)算的數(shù)必須是有限小數(shù)或整數(shù)因此，數(shù)值方法中的取數(shù)和運(yùn)算往往會(huì)出現(xiàn)誤差，算得的結(jié)果（稱為計(jì)算值）一般也為近似值。在任何科學(xué)計(jì)算中，其解的精確性在任何科學(xué)計(jì)算中，其解的精確性總是相對(duì)的，而誤差則是絕對(duì)的?？偸窍鄬?duì)的，而誤差則是絕對(duì)的。數(shù)值方法中的計(jì)算公式及參與運(yùn)算的數(shù)，都和數(shù)學(xué)中的一般情況有所不同，即一、誤差的種類及來源一個(gè)物理量的真實(shí)值和我們算出的值（即計(jì)算值）往往存在差異，它們之差稱為誤差誤差。模型誤差在建立數(shù)學(xué)模型過程中，要將復(fù)雜的現(xiàn)象抽象歸結(jié)為數(shù)學(xué)模型，往往要忽略一些次要因素的影響，而對(duì)問題作一些簡(jiǎn)化，因此數(shù)學(xué)模型和實(shí)際問題之間有一定的誤差。觀測(cè)誤差在建模和具體運(yùn)

12、算過程中所用的數(shù)據(jù)往往是通過觀察和測(cè)量得到的，受觀測(cè)方式、儀器精度以及外部觀測(cè)條件等多種因素限制，不可能獲得精確值，由此而來產(chǎn)生的誤差。截?cái)嗾`差由于計(jì)算機(jī)只能完成有限次算術(shù)運(yùn)算和邏輯運(yùn)算，因此要將有些需用極限或無(wú)窮過程進(jìn)行的運(yùn)算有限化，對(duì)無(wú)窮過程進(jìn)行截?cái)?，這就帶來誤差。! 3! 2132xxxex! 7! 5! 3sin753xxxxx! 4! 3! 2)1ln(432xxxxx例:若將前若干項(xiàng)的部分和作為函數(shù)值的近似公式，由于以后各項(xiàng)都舍棄了，自然產(chǎn)生了誤差Taylor展開舍入誤差在數(shù)值計(jì)算過程中還會(huì)遇到無(wú)窮小數(shù)，因計(jì)算機(jī)受到機(jī)器字長(zhǎng)的限制，它所能表示的數(shù)據(jù)其位數(shù)只能是有限的，如按四舍五入規(guī)

13、則取有限位數(shù)，由此引起的誤差14159265. 3414213562. 12 166666666. 061! 311415927. 34142136. 12 16666667. 0! 31另外還有過失誤差，這類誤差是由于模型錯(cuò)誤或方法錯(cuò)誤所引起的，一般可以避免。結(jié)論：誤差是不可避免的誤差是不可避免的經(jīng)過大量的運(yùn)算之后，積累的總誤差有時(shí)會(huì)大得驚人，因此如何控制誤差的傳播也是數(shù)值方法的研究對(duì)象。在種誤差中，前種是客觀存在的，后種是計(jì)算方法引起的。數(shù)學(xué)模型一旦建立，進(jìn)入具體計(jì)算時(shí)所考慮和分析的就是截?cái)嗾`差和舍入誤差。因此本課程只涉及這種誤差。在實(shí)際問題中求精確解是沒有意義的，求近似解是正常的。問題是

14、如何盡量減少誤差，提高精度。二、誤差和誤差限定義定義1.2.1 *xxx設(shè) 為準(zhǔn)確值，為 的一個(gè)近似值。稱*()xxx*.x為近似值 的絕對(duì)誤差，簡(jiǎn)稱誤差x因?yàn)闇?zhǔn)確值往往是未知甚至是無(wú)法知道的，*()xxx因此往往也無(wú)法求出。*()xxx而只能知道絕對(duì)值的某個(gè)上界，即*|() | |().xxxx*()xx數(shù)值稱為近似值 的一個(gè)絕對(duì)誤差限或誤差限,簡(jiǎn)記為顯然*xxx有時(shí)也表示為*xx0且152x 例：對(duì)于51000 y15*x1000*y2)(*x5)(*y哪個(gè)更精確呢?嗎？15*xx準(zhǔn)確值的范圍*( )xxxxyxy對(duì)于同一個(gè)準(zhǔn)確值 而言，或 越小，近似值也就越精確。但是對(duì)不同的數(shù) 和 而言

15、，誤差 和誤差限 的大小就不完全能反映出近似值和誰(shuí)的近似程度好。定義定義1.2.2 *0 xxx設(shè)為準(zhǔn)確值， 為 的一個(gè)近似值。稱*()()xxxxxx*x為近似值 的相對(duì)誤差。*()()rrxxxxx*xr則稱為近似值 的一個(gè)相對(duì)誤差限。絕對(duì)誤差和絕對(duì)誤差限僅考慮了誤差值本身的大小，沒有考慮準(zhǔn)確值的大小。為了能較好地反映近似值的精確程度，還應(yīng)考慮準(zhǔn)確值的大小。r若存在正數(shù)滿足| xr絕對(duì)誤差限相對(duì)誤差限*()()xxxxxx|*xr代替相對(duì)誤差代替相對(duì)誤差限15*x1000*y2)(*x5)(*y因此%33.13152)(*xr%5 . 010005)(*yr*x絕對(duì)誤差用來衡量 的精度高低

16、比較直觀，但無(wú)法衡量精度的好壞；而相對(duì)誤差用來衡量精度的好壞更合理。往往未知例例1.2.1*2.718 281822.718 28.reee已知，其近似值為，求 的絕對(duì)誤差限 和相對(duì)誤差限解解*ee 絕對(duì)誤差82001000. 0| 0.000 00182 002000. 061026102|*er28718. 2102628718. 2102661071. 0是唯一的并不和*r例例1.2.2.,7 ,5 ,3求絕對(duì)誤差限位數(shù)的近似值經(jīng)四舍五入取小數(shù)點(diǎn)后若解解65592141. 359141. 3*142. 3*7592141. 3*|407000. 065002000. 004000000.

17、 03105 . 05105 . 07105 . 0可見，經(jīng)四舍五入取近似值，其絕對(duì)誤差限將不超過其末位數(shù)字的半個(gè)單位。三、浮點(diǎn)數(shù)與有效數(shù)字定點(diǎn)數(shù)：小數(shù)點(diǎn)的位置固定在個(gè)位數(shù)后。機(jī)器數(shù)：計(jì)算機(jī)中可表示的數(shù)。為了提高精度，機(jī)器數(shù)通常是用浮點(diǎn)數(shù)表示的。x在計(jì)算機(jī)中，一般實(shí)數(shù) 均按舍入原則表示成：12( )0.,mtfl xa aa 稱為 進(jìn)制浮點(diǎn)數(shù)稱為基數(shù)稱為尾數(shù)或數(shù)碼稱為階碼12,011ta aa而只能是 ， ， ，中的數(shù)字。10( )afl x 時(shí)稱為規(guī)格化浮點(diǎn)數(shù)。其中基數(shù)是正整數(shù)，一般取為，但為照顧習(xí)慣和書寫方便，通?；癁槭M(jìn)制數(shù)輸入或輸出。階碼是整數(shù)。一定型號(hào)的計(jì)算機(jī)，尾數(shù)的位數(shù)t是固定的，

18、稱為計(jì)算機(jī)的位數(shù)；階碼m也有一定的取值范圍：12mmm( )0 xxxfl x因此，計(jì)算機(jī)存儲(chǔ)或運(yùn)算的數(shù) 其絕對(duì)值| |不能過大，否則計(jì)算機(jī)因“溢出”而停止計(jì)算；| |也不能過小，否則計(jì)算機(jī)自動(dòng)令 ，得出難以預(yù)料的結(jié)果。有4位有效數(shù)字有6位有效數(shù)字定義定義1.2.3 *|xxxxxxxxnn1設(shè) 為準(zhǔn)確值，如果近似值 的誤差限是10，即21| ( )|=|10，2則稱，并稱的第一個(gè)非零數(shù)字位到小數(shù)點(diǎn)后n位的全部數(shù)字準(zhǔn)確到小數(shù)點(diǎn)后n位的為有效數(shù)字。65592141. 359141. 3*142. 3*7592141. 3*有8位有效數(shù)字1415. 3*只有4位有效數(shù)字！由于計(jì)算機(jī)只能表示有限個(gè)數(shù)

19、，故通常利用某種舍入規(guī)則舍入規(guī)則(如四舍五入，截?cái)嗾`差等)，將數(shù)進(jìn)行浮點(diǎn)化。因而勢(shì)必產(chǎn)生舍入誤差。*12121.(0)mnxa aa b bba 若*1|0.51050.10nn+mmxxxxa（)| ( )|=10| |*1210.000(0)mmnmxbbbb 若10.51050.10nnmmmxb（)| ( )|10*1210.10(0)knxa aaa 若規(guī)格化形式10.5 100.50.10knnkxa| ( )|10n+m位有效數(shù)字n-m位有效數(shù)字n位有效數(shù)字*xn對(duì)于一般情形，設(shè)準(zhǔn)確到小數(shù)點(diǎn)后 位。如何確定有效數(shù)字、絕對(duì)誤差限、相對(duì)誤差限？說明有效數(shù)字位數(shù)與小數(shù)點(diǎn)的位置無(wú)關(guān)。只有

20、寫成規(guī)格化形式后，小數(shù)點(diǎn)后的位數(shù)才能反映出其有效位數(shù)的多少。因此，根據(jù)上述分析，對(duì)有效數(shù)字有如下結(jié)果：定理定理1.2.1 的近似值滿足作為若xx*| |xx 0.5 10.kn*1210.100,kmxa aaa ，*xn至少有 位有效數(shù)字；例例1.2.3求下列四舍五入近似值的有效數(shù)字位數(shù).218.0*1x18002.0*2x180.2*3x0.218*4x2*51018.2x*660.218 0010 x3位3位4位4位3位5位,mn而時(shí),時(shí)則nm *xm恰好有 位有效數(shù)字。補(bǔ)充例例1.2.4個(gè)近似值有設(shè)395. 3x0 . 4*1x9 . 3*2x4*3x|*1xx |95. 30 . 4

21、|05. 021105 . 0|*2xx |95. 39 . 3|05. 021105 . 0|*3xx |95. 34| 05. 021105 . 0*121.2.1xx根據(jù)定理，知 ，都至少有兩位有效數(shù)字*12,xx即都具有兩位有效數(shù)字*3?x 也至少具有兩位有效數(shù)字嗎實(shí)際上只有1位！試求它們的有效數(shù)字位數(shù)。解解k=1, n=2, m=2例例1.2.5:1000效數(shù)字位數(shù)的下面兩個(gè)近似值的有判斷 x9 .999*1x1 .1000*2x3109999. 041010001. 0*111| |0.1xx33105 . 0*222| |0.1xx44105 . 0位有效數(shù)字有所以3*1x位有效

22、數(shù)字卻有而5*2x從以上分析可見，四舍五入的近似值的數(shù)字都是有效數(shù)字而不是四舍五入得到的近似值的數(shù)字不一定是有效數(shù)字。k=3, m=4n=3k=4, m=5n=4*3 411| 0.1 0.5 10 xx定理定理1.2.2 的近似值的表達(dá)式為作為若xx*1210.10 ,0kmxa aaa *(1)xn若 具有 位有效數(shù)字，則其相對(duì)誤差 滿足*xn則 至少有 位有效數(shù)字。1| 0.5 10n *(2)x反之，若 的相對(duì)誤差 滿足| 0.5 10n，證明證明kmaaax10. 021*有位有效數(shù)字時(shí)有當(dāng),)1(*nx*| |xx nk105 . 0kkx10|101 . 0*下面的結(jié)果論述了相對(duì)

23、誤差與有效數(shù)字的關(guān)系補(bǔ)充 xx* xx*0.5 10|0.1 10knkxxx1105 . 0n1| 0.5 10n 即*(2)x若 的相對(duì)誤差 滿足| 0.5 10n*|xxxk10n105 . 0k10n105 . 0nk105 . 0則有由定理1.2.1可知，*xn至少有 位有效數(shù)字。例例1.2.6986. 11x設(shè)014. 12x98. 1*1x01. 1*2x.*2*1誤差限的有效數(shù)字位數(shù)與相對(duì)與分別求xx31105 . 0解解*111*1|xxx0.0061.982105 . 0*111| |0.006xx *12x根據(jù)定理1.2.2(2)，至少有 位有效數(shù)字。*12x因此，根據(jù)定

24、義，只有 位有效數(shù)字，不會(huì)有3位有效數(shù)字。31105 . 0*222*2|xxx0.0041.012105 . 0*222| |0.004xx位有效數(shù)字必然有經(jīng)四舍五入得到事實(shí)上3,*2x*22x根據(jù)定理1.2.2， 至少有 位有效數(shù)字。*2x因此，有3位有效數(shù)字。定理定理1.2.3 的近似值的表達(dá)式為作為若xx*1210.100kmxa aaa ，*(1)xn若 有 位有效數(shù)字，則其相對(duì)誤差滿足*xn則 至少有 位有效數(shù)字。*111|102na*(2)x反之，若 的相對(duì)誤差滿足*111|102(1)na該結(jié)論可以參照定理1.2.2的證明，請(qǐng)同學(xué)們自證補(bǔ)充定理定理說明說明: :有效有效數(shù)字?jǐn)?shù)字

25、位數(shù)越多相對(duì)位數(shù)越多相對(duì) 誤差限誤差限就就越小越小，反之亦然。，反之亦然。 例例1.2.7少取幾位有效數(shù)字？，應(yīng)至的相對(duì)誤差不超過要使%1 . 020解解. 4201a的首位數(shù)是.*20位有效數(shù)字有的近似值設(shè)nx*11|*|1|10| *|2nxxxa則根據(jù)定理1.2.3，相對(duì)誤差滿足001. 0104211n%1 . 0097. 3n即應(yīng)取4位有效數(shù)字，近似值的誤差不超過0.1%.四、誤差的傳播1、數(shù)據(jù)誤差的傳播、數(shù)據(jù)誤差的傳播121212( ,),*,*,*nnnyf x xxx xxxxx設(shè)，的近似值為，12*( *,*,*)nyf xxx121( )*(,)()innixiyyyfxx

26、xx12112( ,)( )( )( )( ,)innxiiinfx xxyyxxyf x xx由多元函數(shù)的Taylor展開公式可得，的絕對(duì)誤差絕對(duì)誤差為：相對(duì)誤差相對(duì)誤差為：稱為 f 的條件數(shù)，其絕對(duì)值的大小可反映函數(shù)值對(duì)數(shù)據(jù)的敏感程度利用上面的誤差估計(jì)公式，可以得到兩個(gè)數(shù)的和、差、積、商的誤差估計(jì)和、差、積、商的誤差估計(jì)121212211221212212121212121212121212()()(/)/()()(/)xxx xxxxxxxxxxxxxxxxx xxx 2、舍入誤差的傳播、舍入誤差的傳播( )( )txfl xfl x在字長(zhǎng)為 的十進(jìn)制計(jì)算機(jī)中，設(shè) 經(jīng)四舍五入得到機(jī)器數(shù)，

27、即浮點(diǎn)數(shù)，且的浮點(diǎn)表示形式為1( )0.5 105,|0.tfl x - xxxat| ( )|=10( )fl x為的一個(gè)相對(duì)誤差限。121( )0.10(0),mtfl xa aaa 12( )( )ta aafl xtfl x則為的 位有效數(shù)字，且的相對(duì)誤差滿足因舍入導(dǎo)致的相對(duì)誤差限僅與計(jì)算機(jī)的字長(zhǎng)有關(guān)，通常稱相對(duì)誤差限 為計(jì)算機(jī)的相對(duì)精度計(jì)算機(jī)的相對(duì)精度。5t10即5t10( )(1),|5 10 .tfl xx在計(jì)算機(jī)中，數(shù)需首先轉(zhuǎn)化為機(jī)器數(shù)，比如浮點(diǎn)數(shù)，在運(yùn)算器中參與運(yùn)算后仍需將運(yùn)算結(jié)果轉(zhuǎn)化成浮點(diǎn)數(shù)的形式進(jìn)行存儲(chǔ)。( )( )fl xxxx令，則有12xx設(shè) ， 為浮點(diǎn)數(shù)，則121

28、21121221212312124()()(1),()()(1),()()(1),(/)(/)(1),fl xxxxfl xxxxfl x xx xfl xxxx|5 101,2,3,4.tii其中由上面的討論可以看出，為了求得滿意的計(jì)算解，在選用計(jì)算公式和設(shè)計(jì)算法時(shí)，都應(yīng)注意如下普遍原則：(1) 防止大數(shù)吃小數(shù)主要由計(jì)算機(jī)的位數(shù)引起選用算法應(yīng)遵循的原則選用算法應(yīng)遵循的原則計(jì)算機(jī)中數(shù)的計(jì)算特點(diǎn)：計(jì)算機(jī)中數(shù)的計(jì)算特點(diǎn)：加法先對(duì)階，后運(yùn)算，再舍入。乘法先運(yùn)算，再舍入。不在計(jì)算機(jī)數(shù)系中的數(shù)做四舍五入處理。計(jì)算機(jī)在進(jìn)行運(yùn)算時(shí)，首先要把參加運(yùn)算的數(shù)對(duì)階，即把兩數(shù)都寫成絕對(duì)值小于1而階碼相同的數(shù)。例例1.

29、2.8在四位浮點(diǎn)十進(jìn)制數(shù)的計(jì)算機(jī)上計(jì)算1+ 104 解解1+ 104 =0.1000 101+ 0.1000 105 = 0.00001 105 + 0.1000 105(對(duì)階計(jì)算) = 0.10001 105 = 0.1000 105 = 104作一個(gè)有效數(shù)字為4位的連加運(yùn)算4697. 0 ,4896. 0 ,4987. 01234. 0104吃了將小數(shù)大數(shù)而如果將小數(shù)放在前面計(jì)算4012. 04697. 04896. 04987. 01234. 01041234. 01041234. 0104012. 04697. 04896. 04987. 041236. 0104在作連加時(shí)，為防止大數(shù)

30、吃小數(shù)，應(yīng)從小到大進(jìn)行相加從小到大進(jìn)行相加，如此，精度將得到適當(dāng)改善。當(dāng)然也可采取別的方法。例例1.2.9(2) 作減法時(shí)應(yīng)避免兩個(gè)相近數(shù)相減兩個(gè)相近的數(shù)相減，會(huì)使有效數(shù)字的位數(shù)嚴(yán)重?fù)p失！例例1.2.10用四位浮點(diǎn)數(shù)計(jì)算 76017591解解522102 .0101316.0101318.076017591只有一位有效數(shù)字,有效數(shù)字大量損失，造成相對(duì)誤差擴(kuò)大。56101734.0105768.01760759176017591結(jié)果仍然有四位有效數(shù)字。這說明了算法設(shè)計(jì)的重要性。在算法設(shè)計(jì)中，若可能出現(xiàn)兩個(gè)相近數(shù)相減，則改變計(jì)算公式，如使用三角變換、有理化等等。例例1.2.11解方程010)110

31、(992xx解解方程的精確解為9110 x12xaacbsqrtbx2)4(22,1而如果在字長(zhǎng)為8，基底為10的計(jì)算機(jī)上利用求根公式1109b10101 . 0100.000000000110機(jī)器吃了因此在計(jì)算機(jī)上10101 . 0b101000000000. 010101 . 0910aacbsqrtbx2)4(21)4(2acbsqrt92101014)101 . 0(910 aacbsqrtbx2)4(22可得利用根的關(guān)系acxx21999102101002101099,1x若已算出121xacx110111099上式是解二次方程的數(shù)值公式2x的值與精確解差別很大！(3) 避免小數(shù)作除

32、數(shù)和大數(shù)作乘數(shù)( )y2112xx21xxy對(duì)于21xxy 對(duì)于( )y2221121xxx|21xx或( )y|2x( )y小數(shù)作除數(shù)或大數(shù)作乘數(shù)會(huì)產(chǎn)生溢出錯(cuò)誤，因而產(chǎn)生大的誤差。在算法設(shè)計(jì)時(shí)，要避免這類情況在計(jì)算公式中出現(xiàn)。此時(shí)可以根據(jù)一些具體情況, 把某些算式改寫成另一種等價(jià)的形式，如分母有理化等。根據(jù)誤差傳播的估計(jì)式算法的穩(wěn)定性算法的穩(wěn)定性如前所述，由于各種誤差的存在，計(jì)算機(jī)往往只能近似地求解實(shí)際問題，因而計(jì)算時(shí)會(huì)冒風(fēng)險(xiǎn)。例例1.3.1分析Wilkinson多項(xiàng)式的根對(duì)系數(shù)的敏感程度。見書P15例1.3.2可以看出： Wilkinson（威爾金森）多項(xiàng)式系數(shù)的微小變化，引起多項(xiàng)式根的劇

33、烈波動(dòng)。因此， Wilkinson多項(xiàng)式的根對(duì)系數(shù)相當(dāng)敏感。一、問題的性態(tài)123123123111123611113234121114734560 xxxxxxxxx1231231230.500.331.80.500.330.251.10.330.250.200.78xxxxxxxxx如把方程組的系數(shù)舍入成兩位有效數(shù)字它的精確解為x1 = -6.222. x2= 38.25 x3= -33.65.例例1.3.2求解線性方程組其精確解為 x1=x2=x3=1.若對(duì)方程組的系數(shù)和中間結(jié)果均取3位10進(jìn)制有效數(shù)字，然后用Gauss消元法求解，得到計(jì)算解為：1231.090.4880.491.xxx，123123132314254226xxxxxxxx顯然，該計(jì)算解的精度較差。同樣用Gauss消元法求解方程組：也取3位10進(jìn)制有效數(shù)字，得到計(jì)算解為：1239.001.006.00.xxx ，容易驗(yàn)證，它是方程組的精確解。上述例子表明