數(shù)值計算與最優(yōu)化lecture計算方法PPT課件

1、第1頁/共49頁要求:1. 課前預習和課后復習,并及時完成課后作業(yè).（掌握構造方法的原理和思想）2. 課余將書本上的程序進行上機計算, 掌握并熟練運用Matlab進行數(shù)值計算。（掌握運用數(shù)值計算方法在計算機上解決各類工程問題）課程成績：平時成績（含考勤、作業(yè)及平時表現(xiàn)）30%期末考試成績 70%第2頁/共49頁$1.1 引引 言言第一章三大科學方法：理論研究、科學實驗、科學計算科學計算核心技術：數(shù)值計算技術和計算機技術計算數(shù)學、圖像處理、統(tǒng)計分析、計算機仿真?？茖W計算包含：第3頁/共49頁一個科學計算過程主要包括如下幾個環(huán)節(jié)：(1) 數(shù)學建模：將工程問題數(shù)學化工程中的數(shù)學模型一般可分為三類：(

2、2) 算法設計：將數(shù)學問題數(shù)值化(指標：速度和精度)連續(xù)型（確定型）離散型（統(tǒng)計型）不確定型（隨機型）本書重點討論例1.1.4 求解線性方程組bAx 求解二次方程02cbxax是數(shù)值問題cbabA,與系數(shù)常數(shù)項向量輸入的數(shù)據(jù)是系數(shù)矩陣21,xxx 和方程的解輸出的數(shù)據(jù)是解向量第4頁/共49頁求解微分方程0)0(32yxy不是數(shù)值問題xxy3,2函數(shù)但輸出的不是數(shù)據(jù)而是輸入的雖是數(shù)據(jù)將其變成數(shù)值問題，即將其“離散化”xxy32即將求函數(shù)nnxxxxyxyxy2121),(,),(),(改變成求函數(shù)值“離散化”是將非數(shù)值問題的數(shù)學模型化為數(shù)值問題的主要方法，這也是計算方法的任務之一第5頁/共49頁

3、(3) 程序設計：將數(shù)值問題機器化實現(xiàn)要求：最簡練的計算機語言最快的速度最少的存儲空間第6頁/共49頁(4) 上機計算并分析結果：數(shù)值模擬物理過程，分析計算結果的可靠性，必要時重復上述過程。其中算法設計是數(shù)值計算的核心內容。數(shù)值計算方法針對來源于科學與工程中的數(shù)學模型問題，介紹計算機上常用的數(shù)值方法的算法設計思想并進行算法分析。第7頁/共49頁 數(shù)值計算：常稱為數(shù)值分析或計算數(shù)學或計算方法。 主要是研究如何運用計算工具（如計算 器、計算機等）去獲得數(shù)學問題的數(shù)值 解的理論和方法。實踐表明：計算方法正在日趨明顯地成為數(shù)學 與計算機科學的交叉科學。 對那些在經(jīng)典數(shù)學中，用解析方法在理論上已作出解的

4、存在，但要求出他的解析解又十分困難，甚至是不可能的這類數(shù)學問題，數(shù)值解法就顯得不可缺少，同時又十分有效。第8頁/共49頁邊緣科學：計算物理，計算力學，計算化學， 計算生物學，計算經(jīng)濟學等。算法：從給定的已知量出發(fā)，經(jīng)過有限次四則運算及規(guī)定的運算順序，最后求出未知量的數(shù)值解，這樣構成的完整計算步驟稱為算法。運算量( (計算量) )： 一個算法所需的乘除運算總次數(shù)計算量是衡量一個算法好壞的重要指標! !數(shù)值計算的根本任務就是研究算法第9頁/共49頁 研究數(shù)值算法的任務主要有：(1) 構造計算機上可執(zhí)行的算法(2) 構造計算復雜性好的算法(3) 構造可靠性好的數(shù)值方法計算機上可執(zhí)行的運算： 四則運算

5、邏輯運算盡可能提高數(shù)值方法的計算速度和少占存貯空間。選擇或研制能達到“數(shù)值問題”要求的計算精度的數(shù)值方法，為此須研究數(shù)值問題的性態(tài)及數(shù)值方法的穩(wěn)定性。計算方法：把求解數(shù)學問題轉化為按一定次序只 進行加、減、乘、除等基本運算 數(shù)值方法。第10頁/共49頁例1.1.1 已知 a0, a1, a2 , an, x, 計算多項式：1110( ).nnnnp xa xaxa xa直接計算：運算量（乘法）1(1)2 1(1).2nnn n 秦九韶算法（1247年）：1210( )( ()nnnp xx xx a xaaaa10,1,2,1,0( )nnkkkbabbxa knnp xb運算量：. n第11

6、頁/共49頁例1.1.2 解線性方程組,Axb其中，1212(),( ,) ,( ,) .TTijn nnnAaxx xxbb bb 克蘭姆(Cramer)法則：,1,2, .iiAxinA 運算量(乘除)：(1)! (1)(1)! (1)nnnnnn 高斯消元法(Gauss)：運算量(乘除)3211.33nnn2 0n 取Gauss: 3060次Cramer:121930.78(10/)19(20+1)! (20-1)5.1 10年次 秒理論上很“漂亮”的CramerCramer法則 在計算機上并不適用！第12頁/共49頁 數(shù)值計算研究內容：對如下五類問題探索數(shù)值求解 方法及其與算法有關的理

7、論分析(2) 數(shù)值逼近（各種函數(shù)逼近問題的數(shù)值解、數(shù)值積分和微分）(5) 最優(yōu)化理論和方法(4) 偏微分方程數(shù)值解(3)(3) 常微分方程數(shù)值解法(1) 數(shù)值代數(shù)（線性方程組、非線性方程及方程組的數(shù)值解法）第13頁/共49頁 將問題可算化的手段：將問題可算化是設計一個算 法的第一步(1)(1) 用有限維空間代替無限維空間(2) 用有限過程代替無限過程(3) 用簡單問題代替復雜問題(4) 擾動分析：估計誤差或精度第14頁/共49頁計算公式中的運算必須是在計算機上可執(zhí)行的運算參與運算的數(shù)必須是有限小數(shù)或整數(shù)因此，數(shù)值方法中的取數(shù)和運算往往會出現(xiàn)誤差，算得的結果（稱為計算值）一般也為近似值。在任何科

8、學計算中，其解的精確性總是相對的，而誤差則是絕對的。數(shù)值方法中的計算公式及參與運算的數(shù)，都和數(shù)學中的一般情況有所不同，即第15頁/共49頁一、誤差的種類及來源一個物理量的真實值和我們算出的值（即計算值）往往存在差異，它們之差稱為誤差。模型誤差在建立數(shù)學模型過程中，要將復雜的現(xiàn)象抽象歸結為數(shù)學模型，往往要忽略一些次要因素的影響，而對問題作一些簡化，因此數(shù)學模型和實際問題之間有一定的誤差。觀測誤差在建模和具體運算過程中所用的數(shù)據(jù)往往是通過觀察和測量得到的，受觀測方式、儀器精度以及外部觀測條件等多種因素限制，不可能獲得精確值，由此而來產(chǎn)生的誤差。第16頁/共49頁截斷誤差由于計算機只能完成有限次算術

9、運算和邏輯運算，因此要將有些需用極限或無窮過程進行的運算有限化，對無窮過程進行截斷，這就帶來誤差。! 3! 2132xxxex! 7! 5! 3sin753xxxxx! 4! 3! 2)1ln(432xxxxx例:若將前若干項的部分和作為函數(shù)值的近似公式，由于以后各項都舍棄了，自然產(chǎn)生了誤差Taylor展開第17頁/共49頁舍入誤差在數(shù)值計算過程中還會遇到無窮小數(shù)，因計算機受到機器字長的限制，它所能表示的數(shù)據(jù)其位數(shù)只能是有限的，如按四舍五入規(guī)則取有限位數(shù)，由此引起的誤差14159265. 3414213562. 12 166666666. 061! 311415927. 34142136. 1

10、2 16666667. 0! 31另外還有過失誤差，這類誤差是由于模型錯誤或方法錯誤所引起的，一般可以避免。第18頁/共49頁結論：誤差是不可避免的經(jīng)過大量的運算之后，積累的總誤差有時會大得驚人，因此如何控制誤差的傳播也是數(shù)值方法的研究對象。在種誤差中，前種是客觀存在的，后種是計算方法引起的。數(shù)學模型一旦建立，進入具體計算時所考慮和分析的就是截斷誤差和舍入誤差。因此本課程只涉及這種誤差。在實際問題中求精確解是沒有意義的，求近似解是正常的。問題是如何盡量減少誤差，提高精度。第19頁/共49頁二、誤差和誤差限定義1.2.1 *xxx設 為準確值，為 的一個近似值。稱*( )xxx*.x為近似值 的

11、絕對誤差，簡稱誤差x因為準確值往往是未知甚至是無法知道的，*( )xxx因此往往也無法求出。*( )xxx而只能知道絕對值的某個上界，即*|( ) | |().xxxx*()xx數(shù)值稱為近似值 的一個絕對誤差限或誤差限,簡記為第20頁/共49頁顯然*xxx有時也表示為*xx0且152x 例：對于51000 y15*x1000*y2)(*x5)(*y哪個更精確呢?嗎？15*xx準確值的范圍*( )xxxxyxy對于同一個準確值 而言，或 越小，近似值也就越精確。但是對不同的數(shù) 和 而言，誤差 和誤差限 的大小就不完全能反映出近似值和誰的近似程度好。第21頁/共49頁定義1.2.2 *0 xxx設

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

13、頁/共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頁三、有效數(shù)字定點數(shù)：小數(shù)點的位置固定在個位數(shù)后。機器數(shù)：計算機中可表示的數(shù)。為了提高精度，機器數(shù)通常是用浮點數(shù)表示的。x在計算機中，一般實數(shù) 均按舍入原則表示成：12( )0.,mtfl xa aa 稱為 進制浮點數(shù)稱為基數(shù)稱為尾數(shù)或數(shù)碼稱為階碼第25頁/共49頁12,

14、011ta aa而只能是 ， ， ，中的數(shù)字。10( )afl x 時稱為規(guī)格化浮點數(shù)。其中基數(shù)是正整數(shù)，一般取為，但為照顧習慣和書寫方便，通?；癁槭M制數(shù)輸入或輸出。階碼是整數(shù)。一定型號的計算機，尾數(shù)的位數(shù)t是固定的，稱為計算機的位數(shù)；階碼m也有一定的取值范圍：12mmm( )0 xxxfl x因此，計算機存儲或運算的數(shù) 其絕對值| |不能過大，否則計算機因“溢出”而停止計算；| |也不能過小，否則計算機自動令 ，得出難以預料的結果。第26頁/共49頁有4位有效數(shù)字有6位有效數(shù)字定義1.2.3 *|xxxxxxxxnn1設 為準確值，如果近似值 的誤差限是10，即21| ( )|=|10，2

15、則稱，并稱的第一個非零數(shù)字位到小數(shù)點后n位的全部數(shù)字準確到小數(shù)點后n位的為有效數(shù)字。65592141. 359141. 3*142. 3*7592141. 3*有8位有效數(shù)字1415. 3*只有4位有效數(shù)字！由于計算機只能表示有限個數(shù)，故通常利用某種舍入規(guī)則(如四舍五入，截斷誤差等)，將數(shù)進行浮點化。因而勢必產(chǎn)生舍入誤差。第27頁/共49頁定理1.2.1 的近似值的表達式為作為若xx*1210.10 ,0kmxa aaa *(1)xn若 具有 位有效數(shù)字，則其相對誤差 滿足*xn則 至少有 位有效數(shù)字。11| (1/(2) 10na *(2)x反之，若 的相對誤差 滿足| 0.5 10n，證明

16、kmaaax10. 021*有位有效數(shù)字時有當,)1(*nx*| |xx nk105 . 0*10.10| 10kkax下面的結果論述了相對誤差與有效數(shù)字的關系第28頁/共49頁 xx* xx*10.5 10|0.10knkxxxa111102na 111|102na 即*(2)x若 的相對誤差 滿足| 0.5 10n*|xxxk10n105 . 0k10n105 . 0nk105 . 0則有*xn至少有 位有效數(shù)字。第29頁/共49頁例1.2.7少取幾位有效數(shù)字？，應至的相對誤差不超過要使%1 . 020解. 4201a的首位數(shù)是.*20位有效數(shù)字有的近似值設nx*1|*|0.5 10| *

17、|0.nxxxa則相對誤差滿足001. 0104211n%1 . 0097. 3n即應取4位有效數(shù)字，近似值的誤差不超過0.1%.第30頁/共49頁四、誤差的傳播1、數(shù)據(jù)誤差的傳播121212( ,),*,*,*nnnyf x xxx xxxxx設，的近似值為，12*( *,*,*)nyf xxx121( )*(,)()innixiyyyfxxxx12112( ,)( )( )( )( ,)innxiiinfx xxyyxxyf x xx由多元函數(shù)的Taylor展開公式可得，的絕對誤差為：相對誤差為：稱為 f 的條件數(shù)，其絕對值的大小可反映函數(shù)值對數(shù)據(jù)的敏感程度第31頁/共49頁利用上面的誤差

18、估計公式，可以得到兩個數(shù)的和、差、積、商的誤差估計121212211221212212121212121212121212()()(/)/()()(/)xxx xxxxxxxxxxxxxxxxx xxx 第32頁/共49頁2、舍入誤差的傳播( )( )txfl xfl x在字長為 的十進制計算機中，設 經(jīng)四舍五入得到機器數(shù)，即浮點數(shù)，且的浮點表示形式為1( )0.5 105,|0.tfl x - xxxat| ( )|=10( )fl x為的一個相對誤差限。121( )0.10(0),mtfl xa aaa 12( )( )ta aafl xtfl x則為的 位有效數(shù)字，且的相對誤差滿足因舍入

19、導致的相對誤差限僅與計算機的字長有關，通常稱相對誤差限 為計算機的相對精度。5t10即5t10第33頁/共49頁( )(1),|5 10 .tfl xx在計算機中，數(shù)需首先轉化為機器數(shù)，比如浮點數(shù)，在運算器中參與運算后仍需將運算結果轉化成浮點數(shù)的形式進行存儲。( )( )fl xxxx令，則有12xx設 ，為浮點數(shù)，則12121121221212312124()()(1),()()(1),()()(1),(/)(/)(1),fl xxxxfl xxxxfl x xx xfl xxxx|5 101,2,3,4.tii其中第34頁/共49頁由上面的討論可以看出，為了求得滿意的計算解，在選用計算公式

20、和設計算法時，都應注意如下普遍原則：(1) 防止大數(shù)吃小數(shù)主要由計算機的位數(shù)引起選用算法應遵循的原則計算機中數(shù)的計算特點：加法先對階，后運算，再舍入。乘法先運算，再舍入。不在計算機數(shù)系中的數(shù)做四舍五入處理。第35頁/共49頁作一個有效數(shù)字為4位的連加運算4697. 0 ,4896. 0 ,4987. 01234. 0104吃了將小數(shù)大數(shù)而如果將小數(shù)放在前面計算4012. 04697. 04896. 04987. 01234. 01041234. 01041234. 0104012. 04697. 04896. 04987. 041236. 0104在作連加時，為防止大數(shù)吃小數(shù)，應從小到大進行相

21、加，如此，精度將得到適當改善。當然也可采取別的方法。 例第36頁/共49頁(2) 作減法時應避免兩個相近數(shù)相減兩個相近的數(shù)相減，會使有效數(shù)字的位數(shù)嚴重損失！例1.2.10用四位浮點數(shù)計算 76017591解522102 .0101316.0101318.076017591只有一位有效數(shù)字,有效數(shù)字大量損失，造成相對誤差擴大。56101734.0105768.01760759176017591結果仍然有四位有效數(shù)字。這說明了算法設計的重要性。在算法設計中，若可能出現(xiàn)兩個相近數(shù)相減，則改變計算公式，如使用三角變換、有理化等等。第37頁/共49頁(3) 避免小數(shù)作除數(shù)和大數(shù)作乘數(shù)( )y2112xx

22、21xxy對于21xxy 對于( )y2221121xxx|21xx或( )y|2x( )y小數(shù)作除數(shù)或大數(shù)作乘數(shù)會產(chǎn)生溢出錯誤，因而產(chǎn)生大的誤差。在算法設計時，要避免這類情況在計算公式中出現(xiàn)。此時可以根據(jù)一些具體情況, 把某些算式改寫成另一種等價的形式，如分母有理化等。根據(jù)誤差傳播的估計式第38頁/共49頁算法的穩(wěn)定性如前所述，由于各種誤差的存在，計算機往往只能近似地求解實際問題，因而計算時會冒風險。一、問題的性態(tài)第39頁/共49頁123123123111123611113234121114734560 xxxxxxxxx1231231230.500.331.80.500.330.251.1

23、0.330.250.200.78xxxxxxxxx如把方程組的系數(shù)舍入成兩位有效數(shù)字它的精確解為x1 = -6.222. x2= 38.25 x3= -33.65.例求解線性方程組其精確解為 x1=x2=x3=1.第40頁/共49頁若對方程組的系數(shù)和中間結果均取3位10進制有效數(shù)字，然后用Gauss消元法求解，得到計算解為：1231.090.4880.491.xxx，123123132314254226xxxxxxxx顯然，該計算解的精度較差。同樣用Gauss消元法求解方程組：也取3位10進制有效數(shù)字，得到計算解為：1239.001.006.00.xxx ，容易驗證，它是方程組的精確解。第41

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