數(shù)值計(jì)算與最優(yōu)化lecture計(jì)算方法學(xué)習(xí)教案

1、數(shù)值數(shù)值(shz)計(jì)算與最優(yōu)化計(jì)算與最優(yōu)化lecture計(jì)算方計(jì)算方法法第一頁，共49頁。第1頁/共49頁第二頁，共49頁。課程成績：課程成績：平時(shí)成績（含考勤、作業(yè)及平時(shí)平時(shí)成績（含考勤、作業(yè)及平時(shí)表現(xiàn)）表現(xiàn)）30%期末考試成績期末考試成績 70%第2頁/共49頁第三頁，共49頁。$1.1 引引 言言第一章三大科學(xué)(kxu)方法：理論研究(ynji)、科學(xué)實(shí)驗(yàn)、科學(xué)計(jì)算科學(xué)計(jì)算核心技術(shù)：數(shù)值(shz)計(jì)算技術(shù)和計(jì)算機(jī)技術(shù)計(jì)算數(shù)學(xué)、圖像處理、統(tǒng)計(jì)分析、計(jì)算機(jī)仿真?？茖W(xué)計(jì)算包含：第3頁/共49頁第四頁，共49頁。一個(gè)科學(xué)計(jì)算過程主要一個(gè)科學(xué)計(jì)算過程主要(zhyo)包括如下幾個(gè)環(huán)節(jié)：包括如下幾個(gè)環(huán)

2、節(jié)：(1) 數(shù)學(xué)建模：將工程數(shù)學(xué)建模：將工程(gngchng)問題數(shù)學(xué)化問題數(shù)學(xué)化工程中的數(shù)學(xué)模型一般(ybn)可分為三類：(2) 算法設(shè)計(jì)算法設(shè)計(jì)：將數(shù)學(xué)問題數(shù)值化(指標(biāo)：速度和精度)連續(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ù)是解向量第4頁/共49頁第五頁，共49頁。求解(qi ji)微分方程0)0(32yxy不是(b shi)數(shù)值問題xxy3,2函數(shù)但輸出的不是數(shù)據(jù)而是輸入的雖是數(shù)據(jù)將其變成數(shù)值問題(wnt)，即將其“

3、離散化”xxy32即將求函數(shù)nnxxxxyxyxy2121),(,),(),(改變成求函數(shù)值“離散化”是將非數(shù)值問題的數(shù)學(xué)模型化為數(shù)值問題的主要方法，這也是計(jì)算方法的任務(wù)之一第5頁/共49頁第六頁，共49頁。(3) 程序設(shè)計(jì)：將數(shù)值程序設(shè)計(jì)：將數(shù)值(shz)問題機(jī)問題機(jī)器化器化實(shí)現(xiàn)(shxin)要求：最簡練(jinlin)的計(jì)算機(jī)語言最快的速度最少的存儲空間第6頁/共49頁第七頁，共49頁。(4) 上機(jī)計(jì)算并分析結(jié)果上機(jī)計(jì)算并分析結(jié)果(ji gu)：數(shù)值模擬物：數(shù)值模擬物理過程，分析計(jì)算結(jié)果理過程，分析計(jì)算結(jié)果(ji gu)的可靠性，必要的可靠性，必要時(shí)重復(fù)上述過程。時(shí)重復(fù)上述過程。其中(qz

4、hng)算法設(shè)計(jì)是數(shù)值計(jì)算的核心內(nèi)容。數(shù)值計(jì)算方法針對來源于科學(xué)與工程中的數(shù)學(xué)模型問題，介紹計(jì)算機(jī)上常用的數(shù)值方法的算法設(shè)計(jì)思想并進(jìn)行算法分析。第7頁/共49頁第八頁，共49頁。數(shù)值計(jì)算：常稱為數(shù)值分析或計(jì)算數(shù)學(xué)數(shù)值計(jì)算：常稱為數(shù)值分析或計(jì)算數(shù)學(xué)(shxu)或或計(jì)算方法。計(jì)算方法。 主要是研究如何運(yùn)用計(jì)算工具（如計(jì)算主要是研究如何運(yùn)用計(jì)算工具（如計(jì)算 器、計(jì)算機(jī)等）去獲得數(shù)學(xué)器、計(jì)算機(jī)等）去獲得數(shù)學(xué)(shxu)問題問題的數(shù)值的數(shù)值 解的理論和方法。解的理論和方法。實(shí)踐表明：計(jì)算方法正在(zhngzi)日趨明顯地成為數(shù)學(xué) 與計(jì)算機(jī)科學(xué)的交叉科學(xué)。 對那些在經(jīng)典數(shù)學(xué)中，用解析方法在理論上已作出解的

5、存在，但要求出他的解析解又十分困難，甚至(shnzh)是不可能的這類數(shù)學(xué)問題，數(shù)值解法就顯得不可缺少，同時(shí)又十分有效。第8頁/共49頁第九頁，共49頁。邊緣科學(xué)(binyunkxu)：計(jì)算物理，計(jì)算力學(xué)，計(jì)算化學(xué)， 計(jì)算生物學(xué)，計(jì)算經(jīng)濟(jì)學(xué)等。算法：從給定的已知量出發(fā)，經(jīng)過算法：從給定的已知量出發(fā)，經(jīng)過(jnggu)(jnggu)有限次四則運(yùn)算及有限次四則運(yùn)算及規(guī)定的運(yùn)算順序，最后求出未知量的數(shù)值解，這樣構(gòu)規(guī)定的運(yùn)算順序，最后求出未知量的數(shù)值解，這樣構(gòu)成的完整計(jì)算步驟稱為算法。成的完整計(jì)算步驟稱為算法。運(yùn)算量運(yùn)算量( (計(jì)算計(jì)算(j (j sun)sun)量量) )： 一個(gè)算法所需的乘除運(yùn)算總次

6、數(shù)計(jì)算量是衡量一個(gè)算法好壞的重要指標(biāo)計(jì)算量是衡量一個(gè)算法好壞的重要指標(biāo)! !數(shù)值計(jì)算的根本任務(wù)就是研究算法數(shù)值計(jì)算的根本任務(wù)就是研究算法第9頁/共49頁第十頁，共49頁。 研究數(shù)值算法的任務(wù)研究數(shù)值算法的任務(wù)(rn wu)主要有：主要有：(1) 構(gòu)造計(jì)算機(jī)上可執(zhí)行構(gòu)造計(jì)算機(jī)上可執(zhí)行(zhxng)的算法的算法(2) 構(gòu)造構(gòu)造(guzo)計(jì)算復(fù)雜性好的計(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)定

7、性。計(jì)算方法：把求解數(shù)學(xué)問題轉(zhuǎn)化為按一定次序只 進(jìn)行加、減、乘、除等基本運(yùn)算 數(shù)值方法。第10頁/共49頁第十一頁，共49頁。例例1.1.1 1.1.1 已知已知 a0, a1, a2 , an, x, a0, a1, a2 , an, x, 計(jì)算計(jì)算(j sun)(j sun)多項(xiàng)式：多項(xiàng)式：1110( ).nnnnp xa xaxa xa直接(zhji)計(jì)算：運(yùn)算量（乘法）1(1)2 1(1).2nnn n 秦九韶算法(sun f)（1247年）：1210( )( ()nnnp xx xx a xaaaa10,1,2,1,0( )nnkkkbabbxa knnp xb運(yùn)算量：. n第11頁

8、/共49頁第十二頁，共49頁。例例1.1.2 解線性方程組,Axb其中(qzhng)，1212(),( ,) ,( ,) .TTijn nnnAaxx xxbb bb 克蘭姆(Cramer)法則(fz)：,1,2, .iiAxinA 運(yùn)算量(乘除(chngch)：(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ī)上并不

9、適用！第12頁/共49頁第十三頁，共49頁。 數(shù)值計(jì)算研究內(nèi)容：對如下五類問題探索數(shù)值求解數(shù)值計(jì)算研究內(nèi)容：對如下五類問題探索數(shù)值求解 方法及其與算法有關(guān)的理論方法及其與算法有關(guān)的理論(lln)(lln)分析分析(2) 數(shù)值數(shù)值(shz)逼近（各種函數(shù)逼近問題的數(shù)值逼近（各種函數(shù)逼近問題的數(shù)值(shz)解、數(shù)值解、數(shù)值(shz)積分和微分）積分和微分）(5) 最優(yōu)化理論最優(yōu)化理論(lln)和方法和方法(4) 偏微分方程數(shù)值解(3)(3) 常微分方程數(shù)值解法(1) 數(shù)值代數(shù)（線性方程組、非線性方程及方程組的數(shù)值解法）第13頁/共49頁第十四頁，共49頁。 將問題可算化的手段將問題可算化的手段(s

10、hudun)(shudun)：將問題可算化是：將問題可算化是設(shè)計(jì)一個(gè)算設(shè)計(jì)一個(gè)算 法的第一步法的第一步(1) (1) 用有限維空間代替用有限維空間代替(dit)(dit)無限維無限維空間空間(2) 用有限過程用有限過程(guchng)代代替無限過程替無限過程(guchng)(3) 用簡單問題代替復(fù)雜問題(4) 擾動分析：估計(jì)誤差或精度第14頁/共49頁第十五頁，共49頁。計(jì)算公式中的運(yùn)算(yn sun)必須是在計(jì)算機(jī)上可執(zhí)行的運(yùn)算(yn sun)參與運(yùn)算(yn sun)的數(shù)必須是有限小數(shù)或整數(shù)因此，數(shù)值方法中的取數(shù)和運(yùn)算往往會出現(xiàn)誤差，算得的結(jié)果（稱為計(jì)算值）一般也為近似值。在任何科學(xué)計(jì)算中，

11、其解的精確性在任何科學(xué)計(jì)算中，其解的精確性總是相對的，而誤差則是絕對的。總是相對的，而誤差則是絕對的。數(shù)值方法中的計(jì)算公式及參與運(yùn)算的數(shù)，都和數(shù)學(xué)中的一般情況有所不同，即第15頁/共49頁第十六頁，共49頁。一、誤差的種類(zhngli)及來源一個(gè)物理量的真實(shí)值和我們算出的值（即計(jì)算值）往往(wngwng)存在差異，它們之差稱為誤差。模型(mxng)誤差在建立數(shù)學(xué)模型過程中，要將復(fù)雜的現(xiàn)象抽象歸結(jié)為數(shù)學(xué)模型，往往要忽略一些次要因素的影響，而對問題作一些簡化，因此數(shù)學(xué)模型和實(shí)際問題之間有一定的誤差。觀測誤差在建模和具體運(yùn)算過程中所用的數(shù)據(jù)往往是通過觀察和測量得到的，受觀測方式、儀器精度以及外部觀

12、測條件等多種因素限制，不可能獲得精確值，由此而來產(chǎn)生的誤差。第16頁/共49頁第十七頁，共49頁。截?cái)嗾`差由于計(jì)算機(jī)只能完成(wn chng)有限次算術(shù)運(yùn)算和邏輯運(yùn)算，因此要將有些需用極限或無窮過程進(jìn)行的運(yùn)算有限化，對無窮過程進(jìn)行截?cái)?，這就帶來誤差。! 3! 2132xxxex! 7! 5! 3sin753xxxxx! 4! 3! 2)1ln(432xxxxx例:若將前若干項(xiàng)的部分和作為函數(shù)值的近似公式，由于以后各項(xiàng)都舍棄了，自然產(chǎn)生(chnshng)了誤差Taylor展開(zhn ki)第17頁/共49頁第十八頁，共49頁。舍入誤差(wch)在數(shù)值計(jì)算過程中還會遇到無窮小數(shù)，因計(jì)算機(jī)受到機(jī)器

13、字長(z chn)的限制，它所能表示的數(shù)據(jù)其位數(shù)只能是有限的，如按四舍五入規(guī)則取有限位數(shù)，由此引起的誤差14159265. 3414213562. 12 166666666. 061! 311415927. 34142136. 12 16666667. 0! 31另外還有過失誤差(wch)，這類誤差(wch)是由于模型錯(cuò)誤或方法錯(cuò)誤所引起的，一般可以避免。第18頁/共49頁第十九頁，共49頁。結(jié)論：誤差(wch)是不可避免的經(jīng)過大量的運(yùn)算之后，積累的總誤差有時(shí)會大得驚人，因此如何控制誤差的傳播(chunb)也是數(shù)值方法的研究對象。在種誤差中，前種是客觀存在的，后種是計(jì)算方法引起的。數(shù)學(xué)模型一旦

14、建立，進(jìn)入具體計(jì)算時(shí)所考慮和分析(fnx)的就是截?cái)嗾`差和舍入誤差。因此本課程只涉及這種誤差。在實(shí)際問題中求精確解是沒有意義的，求近似解是正常的。問題是如何盡量減少誤差，提高精度。第19頁/共49頁第二十頁，共49頁。二、誤差(wch)和誤差(wch)限定義定義(dngy)1.2.1 (dngy)1.2.1 *xxx設(shè) 為準(zhǔn)確值，為 的一個(gè)近似值。稱*( )xxx*.x為近似值 的絕對誤差，簡稱誤差x因?yàn)闇?zhǔn)確值往往是未知甚至是無法知道的，*( )xxx因此往往也無法求出。*( )xxx而只能知道絕對值的某個(gè)上界，即*|( ) | |().xxxx*()xx數(shù)值稱為近似值 的一個(gè)絕對誤差(ju

15、du w ch)限或誤差限,簡記為第20頁/共49頁第二十一頁，共49頁。顯然(xinrn)*xxx有時(shí)(yush)也表示為*xx0且152x 例：對于51000 y15*x1000*y2)(*x5)(*y哪個(gè)(n ge)更精確呢?嗎？15*x*( )xxxxyxy對于同一個(gè)準(zhǔn)確值 而言，或 越小，近似值也就越精確。但是對不同的數(shù) 和 而言，誤差 和誤差限 的大小就不完全能反映出近似值和誰的近似程度好。第21頁/共49頁第二十二頁，共49頁。定義定義(dngy)1.2.2 *0 xxx設(shè)為準(zhǔn)確值，為 的一個(gè)近似值。稱*()()xxxxxx*x為近似值 的相對誤差。*()()rrxxxxx*xr

16、則稱為近似值 的一個(gè)相對誤差限。絕對誤差和絕對誤差限僅考慮(kol)了誤差值本身的大小，沒有考慮(kol)準(zhǔn)確值的大小。為了能較好地反映近似值的精確程度，還應(yīng)考慮(kol)準(zhǔn)確值的大小。r若存在正數(shù)滿足第22頁/共49頁第二十三頁，共49頁。| xr絕對誤差(ju du w ch)限相對誤差(xin du w ch)限*()()xxxxxx|*xr代替(dit)相對誤差代替相對誤差限15*x1000*y2)(*x5)(*y因此%33.13152)(*xr%5 . 010005)(*yr*x絕對誤差用來衡量 的精度高低比較直觀，但無法衡量精度的好壞；而相對誤差用來衡量精度的好壞更合理。往往未知第

17、23頁/共49頁第二十四頁，共49頁。例例1.2.1*2.718 281822.718 28.reee已知，其近似值為，求 的絕對誤差限 和相對誤差限解解*ee 絕對誤差82001000. 0|0.000 00182 002000. 061026102|*er28718. 2102628718. 2102661071. 0是唯一的并不和*r第24頁/共49頁第二十五頁，共49頁。三、有效數(shù)字(yu xio sh z)定點(diǎn)數(shù)：小數(shù)點(diǎn)的位置(wi zhi)固定在個(gè)位數(shù)后。機(jī)器(j q)數(shù)：計(jì)算機(jī)中可表示的數(shù)。為了提高精度，機(jī)器數(shù)通常是用浮點(diǎn)數(shù)表示的。x在計(jì)算機(jī)中，一般實(shí)數(shù) 均按舍入原則表示成：12

18、( )0.,mtfl xa aa 稱為 進(jìn)制浮點(diǎn)數(shù)稱為基數(shù)稱為尾數(shù)或數(shù)碼稱為階碼第25頁/共49頁第二十六頁，共49頁。12,011ta aa而只能是 ， ， ，中的數(shù)字。10( )afl x 時(shí)稱為規(guī)格化浮點(diǎn)數(shù)。其中基數(shù)是正整數(shù)，一般(ybn)取為，但為照顧習(xí)慣和書寫方便，通?；癁槭M(jìn)制數(shù)輸入或輸出。階碼是整數(shù)。一定型號的計(jì)算機(jī)，尾數(shù)的位數(shù)t是固定的，稱為(chn wi)計(jì)算機(jī)的位數(shù)；階碼m也有一定的取值范圍：12mmm( )0 xxxfl x因此，計(jì)算機(jī)存儲或運(yùn)算的數(shù) 其絕對值| |不能過大，否則計(jì)算機(jī)因“溢出”而停止計(jì)算；| |也不能過小，否則計(jì)算機(jī)自動令 ，得出難以預(yù)料的結(jié)果。第26頁

19、/共49頁第二十七頁，共49頁。有4位有效數(shù)字(yu xio sh z)有6位有效數(shù)字(yu xio sh z)定義定義(dngy)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ù)，故通常利用某種舍入規(guī)則舍入規(guī)則(如四舍五入，截?cái)嗾`差等)，將數(shù)進(jìn)行浮點(diǎn)化。因而勢必產(chǎn)生舍入誤差。第27頁/共49頁第二十八

20、頁，共49頁。定理定理(dngl)1.2.1 的近似值的表達(dá)式為作為若xx*1210.10 ,0kmxa aaa *(1)xn若 具有 位有效數(shù)字，則其相對誤差 滿足*xn則 至少有 位有效數(shù)字。11| (1/(2) 10na *(2)x反之，若 的相對誤差 滿足| 0.5 10n，證明證明(zhngmng)kmaaax10. 021*有位有效數(shù)字時(shí)有當(dāng),)1(*nx*| |xx nk105 . 0*10.10| 10kkax下面的結(jié)果論述了相對誤差與有效數(shù)字(yu xio sh z)的關(guān)系第28頁/共49頁第二十九頁，共49頁。 xx* xx*10.5 10|0.10knkxxxa11110

21、2na 111|102na 即*(2)x若 的相對誤差 滿足| 0.5 10n*|xxxk10n105 . 0k10n105 . 0nk105 . 0則有*xn至少有 位有效數(shù)字。第29頁/共49頁第三十頁，共49頁。例例1.2.7少取幾位有效數(shù)字？，應(yīng)至的相對誤差不超過要使%1 . 020解解. 4201a的首位數(shù)是.*20位有效數(shù)字有的近似值設(shè)nx*1|*|0.5 10| *|0.nxxxa則相對誤差(xin du w ch)滿足001. 0104211n%1 . 0097. 3n即應(yīng)取4位有效數(shù)字，近似值的誤差(wch)不超過0.1%.第30頁/共49頁第三十一頁，共49頁。四、誤差(w

22、ch)的傳播1、數(shù)據(jù)誤差的傳播、數(shù)據(jù)誤差的傳播(chunb)121212( ,),*,*,*nnnyf x xxx xxxxx設(shè)，的近似值為，12*( *,*,*)nyf xxx121( )*(,)()innixiyyyfxxxx12112( ,)( )( )( )( ,)innxiiinfx xxyyxxyf x xx由多元函數(shù)的Taylor展開(zhn ki)公式可得，的絕對誤差絕對誤差為：相對誤差相對誤差為：稱為 f 的條件數(shù)，其絕對值的大小可反映函數(shù)值對數(shù)據(jù)的敏感程度第31頁/共49頁第三十二頁，共49頁。利用(lyng)上面的誤差估計(jì)公式，可以得到兩個(gè)數(shù)的和、差、積、商的誤差估計(jì)12

23、1212211221212212121212121212121212()()(/)/()()(/)xxx xxxxxxxxxxxxxxxxx xxx 第32頁/共49頁第三十三頁，共49頁。2、舍入誤差、舍入誤差(wch)的傳播的傳播( )( )txfl xfl x在字長為 的十進(jìn)制計(jì)算機(jī)中，設(shè) 經(jīng)四舍五入得到機(jī)器數(shù)，即浮點(diǎn)數(shù)，且的浮點(diǎn)表示形式為1( )0.5 105,|0.tfl x - xxxat| ( )|=10( )fl x為的一個(gè)相對誤差限。121( )0.10(0),mtfl xa aaa 12( )( )ta aafl xtfl x則為的 位有效數(shù)字，且的相對誤差滿足因舍入導(dǎo)致(

24、dozh)的相對誤差限僅與計(jì)算機(jī)的字長有關(guān)，通常稱相對誤差限 為計(jì)算機(jī)的相對精度。5t10即5t10第33頁/共49頁第三十四頁，共49頁。( )(1),|5 10 .tfl xx在計(jì)算機(jī)中，數(shù)需首先(shuxin)轉(zhuǎn)化為機(jī)器數(shù)，比如浮點(diǎn)數(shù)，在運(yùn)算器中參與運(yùn)算后仍需將運(yùn)算結(jié)果轉(zhuǎn)化成浮點(diǎn)數(shù)的形式進(jìn)行存儲。( )( )fl xxxx令，則有12xx設(shè) ， 為浮點(diǎn)數(shù)，則12121121221212312124()()(1),()()(1),()()(1),(/)(/)(1),fl xxxxfl xxxxfl x xx xfl xxxx|5 101,2,3,4.tii其中第34頁/共49頁第三十五頁，

25、共49頁。由上面的討論可以看出，為了求得滿意的計(jì)算(j sun)解，在選用計(jì)算(j sun)公式和設(shè)計(jì)算(j sun)法時(shí)，都應(yīng)注意如下普遍原則：(1) 防止大數(shù)(d sh)吃小數(shù)主要(zhyo)由計(jì)算機(jī)的位數(shù)引起選用算法應(yīng)遵循的原則選用算法應(yīng)遵循的原則計(jì)算機(jī)中數(shù)的計(jì)算特點(diǎn)：計(jì)算機(jī)中數(shù)的計(jì)算特點(diǎn)：加法先對階，后運(yùn)算，再舍入。乘法先運(yùn)算，再舍入。不在計(jì)算機(jī)數(shù)系中的數(shù)做四舍五入處理。第35頁/共49頁第三十六頁，共49頁。作一個(gè)(y )有效數(shù)字為4位的連加運(yùn)算4697. 0 ,4896. 0 ,4987. 01234. 0104吃了將小數(shù)大數(shù)而如果將小數(shù)放在前面(qin mian)計(jì)算4012.

26、04697. 04896. 04987. 01234. 01041234. 01041234. 0104012. 04697. 04896. 04987. 041236. 0104在作連加時(shí)，為防止大數(shù)吃小數(shù)，應(yīng)從小到大進(jìn)行相加，如此，精度將得到適當(dāng)(shdng)改善。當(dāng)然也可采取別的方法。 例例第36頁/共49頁第三十七頁，共49頁。(2) 作減法時(shí)應(yīng)避免兩個(gè)(lin )相近數(shù)相減兩個(gè)(lin )相近的數(shù)相減，會使有效數(shù)字的位數(shù)嚴(yán)重?fù)p失！例例1.2.10用四位(s wi)浮點(diǎn)數(shù)計(jì)算 76017591解解522102 .0101316.0101318.076017591只有一位有效數(shù)字,有效數(shù)

27、字大量損失，造成相對誤差擴(kuò)大。56101734.0105768.01760759176017591結(jié)果仍然有四位有效數(shù)字。這說明了算法設(shè)計(jì)的重要性。在算法設(shè)計(jì)中，若可能出現(xiàn)兩個(gè)相近數(shù)相減，則改變計(jì)算公式，如使用三角變換、有理化等等。第37頁/共49頁第三十八頁，共49頁。(3) 避免(bmin)小數(shù)作除數(shù)和大數(shù)作乘數(shù)( )y2112xx21xxy對于21xxy 對于( )y2221121xxx|21xx或( )y|2x( )y小數(shù)作除數(shù)或大數(shù)作乘數(shù)(chn sh)會產(chǎn)生溢出錯(cuò)誤，因而產(chǎn)生大的誤差。在算法設(shè)計(jì)時(shí)，要避免這類情況在計(jì)算公式中出現(xiàn)。此時(shí)可以根據(jù)一些具體情況, 把某些算式改寫成另一種等

28、價(jià)的形式，如分母有理化等。根據(jù)誤差(wch)傳播的估計(jì)式第38頁/共49頁第三十九頁，共49頁。如前所述，由于各種誤差的存在(cnzi)，計(jì)算機(jī)往往只能近似地求解實(shí)際問題，因而計(jì)算時(shí)會冒風(fēng)險(xiǎn)。一、問題(wnt)的性態(tài)第39頁/共49頁第四十頁，共49頁。123123123111123611113234121114734560 xxxxxxxxx1231231230.500.331.80.500.330.251.10.330.250.200.78xxxxxxxxx如把方程組的系數(shù)(xsh)舍入成兩位有效數(shù)字它的精確(jngqu)解為x1 = -6.222. x2= 38.25 x3= -33.6

29、5.例例求解(qi ji)線性方程組其精確解為 x1=x2=x3=1.第40頁/共49頁第四十一頁，共49頁。若對方程組的系數(shù)和中間結(jié)果均取3位10進(jìn)制有效數(shù)字，然后(rnhu)用Gauss消元法求解，得到計(jì)算解為：1231.090.4880.491.xxx，123123132314254226xxxxxxxx顯然(xinrn)，該計(jì)算解的精度較差。同樣(tngyng)用Gauss消元法求解方程組：也取3位10進(jìn)制有效數(shù)字，得到計(jì)算解為：1239.001.006.00.xxx ，容易驗(yàn)證，它是方程組的精確解。第41頁/共49頁第四十二頁，共49頁。上述例子(l zi)表明，數(shù)值問題計(jì)算解的精度

30、，與數(shù)值問題本身的性態(tài)有關(guān)。定義定義1.3.1 在數(shù)值問題中，如果輸出數(shù)據(jù)對輸入數(shù)據(jù)的在數(shù)值問題中，如果輸出數(shù)據(jù)對輸入數(shù)據(jù)的擾動（如誤差）很敏感，即若輸入數(shù)據(jù)（如原始數(shù)據(jù)）擾動（如誤差）很敏感，即若輸入數(shù)據(jù)（如原始數(shù)據(jù)）有較小的變化，會引起輸出數(shù)據(jù)（如計(jì)算解）的較大變有較小的變化，會引起輸出數(shù)據(jù)（如計(jì)算解）的較大變化，稱這類數(shù)值問題為病態(tài)化，稱這類數(shù)值問題為病態(tài)(bngti)問題或壞條件問題。非病態(tài)問題或壞條件問題。非病態(tài)(bngti)問題又稱為良態(tài)問題。問題輸出變量的相對誤差與輸入問題又稱為良態(tài)問題。問題輸出變量的相對誤差與輸入變量的相對誤差的商稱為問題的條件數(shù)變量的相對誤差的商稱為問題的條件數(shù)第42頁/共49頁第四十三頁，共49頁。二、算法的穩(wěn)定性與設(shè)計(jì)(shj)原則例例1.3.3101dxexeIxnn計(jì)算(j sun)定積分7 , 2 , 1 , 0n解解nI101xndexe101xnexe101dxexenxn11nnI0,I(1) 先計(jì)算721,III然后再計(jì)算一個(gè)程序往往要進(jìn)行大量的四則運(yùn)算才能