數(shù)值與計算方法緒論P(yáng)PT課件

1、1 先修課程 高等代數(shù)、線性代數(shù)、一門編程語言 開課情況 48學(xué)時，3學(xué)分。第1頁/共74頁2教學(xué)安排 1. 緒論 2. 非線性方程的數(shù)值解法 3. 線性方程組的數(shù)值解法 4. 函數(shù)逼近的插值法與曲線擬合法 5. 數(shù)值積分 6. 常微分方程數(shù)值解法 7. 矩陣特征值和特征向量的數(shù)值解法第2頁/共74頁3第1章 緒論利用計算機(jī)解決實(shí)際問題有三大步驟：I.建立模型II.計算問題的解( 1.選擇數(shù)值方法；2 .編寫程序)III.實(shí)驗驗證本課程的任務(wù)： 討論第步，即介紹計算機(jī)上的常用的數(shù)值方法第3頁/共74頁4實(shí)際問題數(shù)學(xué)模型(數(shù)值)算法編程計算結(jié)果抽象：“去偽存真，去粗取精”()()()第4頁/共7

2、4頁5I.總體設(shè)計(含模型的細(xì)化等)II. 詳細(xì)設(shè)計(主要是算法設(shè)計)III. 實(shí)驗驗證其中包括：連續(xù)系統(tǒng)的離散化離散型方程的數(shù)值求解以計算機(jī)為工具 求解各種數(shù)學(xué)模型需經(jīng)歷三個過程第5頁/共74頁6計算方法 主要研究將數(shù)學(xué)模型變成數(shù)值問題,并研究求解數(shù)值問題的數(shù)值方法，進(jìn)而設(shè)計數(shù)值算法。內(nèi)容包括: 基本概念介紹；誤差及分析；收斂性、穩(wěn)定性；算法復(fù)雜性等第6頁/共74頁7計算數(shù)學(xué)的對象 計算數(shù)學(xué)是一門古老的數(shù)學(xué) 如計算圓周率、九章計算等； 牛頓、萊布尼茲等提出的微分、積分計算； 計算數(shù)學(xué)是一門年輕的數(shù)學(xué) 近代計算機(jī)的誕生，產(chǎn)生了數(shù)學(xué)的計算機(jī)計算. 計算機(jī)與數(shù)學(xué)的關(guān)系非常密切 計算數(shù)學(xué)：計算機(jī)上的

3、數(shù)學(xué)方法。 或定義為：研究數(shù)值計算方法的設(shè)計、分析和有關(guān)理論基礎(chǔ)與軟件實(shí)現(xiàn)的一個數(shù)學(xué)分支。計算數(shù)學(xué)：計算方法或數(shù)值分析第7頁/共74頁8 科學(xué)理論、科學(xué)試驗和科學(xué)計算(計算的方法)是現(xiàn)代科學(xué)的三個組成部分 計算機(jī)下的科學(xué)計算大大地提高了計算速度和計算精度，是使原來不能實(shí)現(xiàn)的海量復(fù)雜計算成為現(xiàn)實(shí) 科學(xué)計算是以計算機(jī)為基礎(chǔ)的科學(xué)計算，其計算理論是計算數(shù)學(xué) 計算數(shù)學(xué)的應(yīng)用：天體物理、大氣研究、分子生物、集成電路、天氣預(yù)報、模式識別、網(wǎng)絡(luò)信息搜索等 計算數(shù)學(xué)的發(fā)展：進(jìn)行高效率、高精度的并行計算計算數(shù)學(xué)的應(yīng)用與發(fā)展第8頁/共74頁9為什么要學(xué)習(xí)計算方法這門課？ 利用計算機(jī)求解實(shí)際問題的核心過程，非常重要

4、。 雖然已有大量數(shù)值算法的軟件包，但需要我們了解算法設(shè)計的原理，以便更好地應(yīng)用。 隨著計算機(jī)的應(yīng)用越來越廣泛，計算問題越來越復(fù)雜，規(guī)模越來越大，現(xiàn)成的數(shù)值方法軟件包不能滿足特定需要，如數(shù)字圖像處理、天氣預(yù)報、Web搜索。第9頁/共74頁10 用計算機(jī)求解，需要首先將數(shù)學(xué)模型轉(zhuǎn)換為數(shù)值問題，然后研究求解數(shù)值問題的數(shù)值算法。第10頁/共74頁11（1）數(shù)值問題數(shù)值問題：輸入數(shù)據(jù)與輸出數(shù)據(jù)之間函數(shù)關(guān)系的一個確定而無歧義的描述。即： 輸入與輸出的都是數(shù)值的數(shù)學(xué)問題如求解線性方程組bAx 求解二次方程02cbxaxcbabA,與系數(shù)常數(shù)項向量輸入的數(shù)據(jù)是系數(shù)矩陣都是數(shù)值問題21,xxx 和方程的解輸出的

5、數(shù)據(jù)是解向量第11頁/共74頁12求解微分方程0)0(32yxy是不是數(shù)值問題？xxy3,2函數(shù)但輸出的不是數(shù)據(jù)而是輸入的雖是數(shù)據(jù)將其變成數(shù)值問題，即將其“離散化”xxy32即將求函數(shù)nnxxxxyxyxy2121),(,),(),(改變成求函數(shù)值“離散化”是將非數(shù)值問題的數(shù)學(xué)模型化為數(shù)值問題的主要方法，這也是計算方法的任務(wù)之一第12頁/共74頁13（2）數(shù)值方法數(shù)值方法：是指解數(shù)值問題的 在計算機(jī)上可執(zhí)行的系列計算公式。在計算機(jī)上可執(zhí)行的公式是指只含有加減乘除的公式。現(xiàn)在的計算機(jī)中幾乎都含有關(guān)于開方的標(biāo)準(zhǔn)函數(shù)sqrt()常見的在計算機(jī)上不能直接運(yùn)行的計算有: 開方、極限、超越函數(shù)、微分、積分

6、等等。要在計算機(jī)上實(shí)行上述運(yùn)算需將其化為可執(zhí)行的等價或近似等價運(yùn)算。第13頁/共74頁14，應(yīng)化為超越函數(shù)xe. 3! 212nxxxenx的計算應(yīng)化為的導(dǎo)數(shù)函數(shù))()(. 4xyxyhxyhxyxy)()()(1. 如求根公式aacbbx2422,12. 應(yīng)化為公式aacbsqrtbx2)4(22,1第14頁/共74頁151.1數(shù)學(xué)問題的數(shù)值解法例示 例1.1.1試求函數(shù)方程x=cosx在區(qū)間 內(nèi)的一個根。解 )2, 0(.)2, 0(, 0sin1)(.)2, 0(0)(,02*) 1()2()0(,2, 0)(,cos)(知上述零點(diǎn)唯一又由內(nèi)至少有一個零點(diǎn)在方程由零點(diǎn)定理知且上是連續(xù)函數(shù)

7、在易知令xxxfxfffxfxxxf第15頁/共74頁16 注：【零點(diǎn)定理】設(shè)函數(shù)f(x)在閉區(qū)間a,b上連續(xù)，且f(a)與 f(b)異號（即f(a) f(b)0），那么在開區(qū)間（a,b）內(nèi)至少有函數(shù)f(x)的一個零點(diǎn)，即至少有一點(diǎn)（ab）使f()=0。 第16頁/共74頁171.1數(shù)學(xué)問題的數(shù)值解法例示.4.,cos.,.*附近大致位于看出從圖中可以為所求方程的解的橫坐標(biāo)取兩曲線交點(diǎn)作圖像可大致判定此零點(diǎn)位置法若用圖解困難本題用解析法求解較為xxpxyxy第17頁/共74頁18 簡單迭代法： 取初值：x0=0.75迭代得：x1=0.731688868，x2=0.744047084 x42=0

8、.739085133，x43=0.739085133 牛頓迭代法： 取初值：x0=0.75迭代得：x1=0.739111138，x2=0.739085133 x3=0.739085133nnxxcos1nnnnnnnnxxxxxfxfxxsin1cos)()(1比較：兩種方法同樣獲得9位數(shù)字的近似解， 簡單迭代法需要迭代43次，牛頓迭代法迭代3次。第18頁/共74頁1910102212)2(14I 12.1.1dxeIdxxx）（計算定積分例公式有的復(fù)化被積函數(shù)擇數(shù)值方法有多種，如選Simpsonxxfhn214)(,21,20arctan41arctan4|arctan41101xI萊布尼茲

9、公式）由牛頓解：（第19頁/共74頁20141568627.3)1()43(4)21(2)41(4)0(61fffffhI。行數(shù)值求解有公式進(jìn)的復(fù)化法求解。仍選擇數(shù)值方公式無法求解，僅可用由無原函數(shù)，因此，由于）（746855379. 0,21, 2LeibnizNewtone)(,e2210222IsimpsonhnxxfdxI-x第20頁/共74頁21注釋1. 1. 牛頓- -萊布尼茲公式2. 2. 數(shù)值解：在特定條件下通過近似計算, ,（如有限元的方法, 數(shù)值逼近, ,插值的方法）得出來的一個數(shù)值。 解析解：解析解為該函數(shù)的解析式。第21頁/共74頁22例1.2.3 求 Ax=b， De

10、t(A)0，A=(aij)20 20解：1. 用Cramar法則求解，總計算量 N = ( ( n+1)(n-1)n!+n) flop當(dāng)n=20, N9.7 1020 flop. 以一臺10億/秒的計算機(jī)需約3萬年.結(jié)論：分析算法的效率，選擇算法非常重要解：2.使用Gauss消去法， n=20， N3060 flop = O(n3 /3) flop.第22頁/共74頁23注釋：Cramer法則 設(shè)線性方程組 簡記 AX=bnnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111第23頁/共74頁24 其中TnTnnnijnnnbbbxxxaaaa

11、aaaaaabx2121n2n1n2222112111,)(A第24頁/共74頁25代替所得。列用的第是，其中法則：biAAADniDDxGrameriiiii)det(0A)det(D,.,2 , 1第25頁/共74頁26:121)0(23 .1 .12方法我們選擇經(jīng)典的四階如。本題數(shù)值方法很多，解析解解得方程，令該方程是解求解初值問題例KRxyyuBernoulliyyxydxdy第26頁/共74頁27 為步長。；這里hyxyyxfkyhthfkkyhthfkkyhthfkythfkkkkkyynnnnnnnnnn2),(,),()2,2()2,2(),()22(6134231214321

12、1第27頁/共74頁28現(xiàn)取h=0.05,其結(jié)果見下表:xnynY=xnynY=01.000001.000001.21.849311.849310.21.183221.183221.41.943961.943960.41.341641.341641.62.049392.049390.61.483241.483241.82.144762.144760.81.612451.612452.02.236072.236071.01.732051.7320512x12x第28頁/共74頁291.2 誤差概念和有效數(shù) 在任何科學(xué)計算中其解的精確性總是相對的,而誤差則是絕對的. 我們從下面這個例子就可以了解誤

13、差產(chǎn)生的原因.例1.2.1 試求擺長為L的單擺運(yùn)動周期. 第29頁/共74頁3022sing:gl2Tdtdmlmamgfml牛頓定律的質(zhì)量。如圖所示：由是質(zhì)點(diǎn)為自由落體加速度；為擺長；其中擺周期在物理學(xué)中我們知道單第30頁/共74頁310,sin,0sinsin22222222dtdlglgdtdmgdtdml則有令很小時當(dāng)即所以第31頁/共74頁32：期求解過程的誤差情況現(xiàn)在我們來分析單擺周因此，故有解微分方程得，glTtcctctc22)sin(.sincos22212121第32頁/共74頁33開方：舍入誤差長度秒米觀察誤差：展式：由截斷誤差：點(diǎn)處的摩擦力忽略忽略空氣阻力模型誤差/,*

14、,.4,/8 . 93.! 5! 3sinTaglorsin2o10205300lg第33頁/共74頁34實(shí)際問題數(shù)學(xué)模型(數(shù)值)算法編程計算結(jié)果抽象模型誤差模型誤差,觀測誤差觀測誤差第34頁/共74頁35誤差的分類 模型誤差：從實(shí)際問題建立的數(shù)學(xué)模型往往都忽略了許多次要的因素,因此產(chǎn)生的誤差稱為模型誤差. 觀測誤差：一般數(shù)學(xué)問題包含若干參數(shù),他們是通過觀測得到的,受觀測方式、儀器精度以及外部觀測條件等多種因素，不可能獲得精確值，由此而來產(chǎn)生的誤差稱為觀測誤差。第35頁/共74頁36 截斷誤差： 在求解過程中，往往以近似替代，化繁為簡，這樣產(chǎn)生的誤差稱為截斷誤差。 舍入誤差： 在計算機(jī)上運(yùn)算時

15、受機(jī)器字長的限制，一般必須進(jìn)行舍入，此時產(chǎn)生的誤差稱為舍入誤差。第36頁/共74頁37誤差和有效數(shù)字稱為近似數(shù)為準(zhǔn)確數(shù)，設(shè)定義,2 . 2 . 1*xxxxxex*)(絕對誤差：的）（近似數(shù))0()()(*xxxexexr相對誤差：的）（近似數(shù)第37頁/共74頁38絕對誤差 是為了衡量x*的精度高低，比較直觀，但無法衡量精度的好壞。而相對誤差（也成百分比誤差），衡量好壞更合理。第38頁/共74頁39誤差估計 由于準(zhǔn)確值在一般情況下是未知的，因此絕對誤差和相對誤差常常是無法計算的，但有可能給出估計。 誤差界就是用于誤差估計的。第39頁/共74頁40誤差估計差界。的絕對誤差界和相對誤為近似數(shù)和則稱

16、滿足和若有正數(shù)為近似數(shù)為精確數(shù)，設(shè)定義*r*r*| )(| )(|:,2 . 2 . 1xxxxxexxxexxrr第40頁/共74頁41第41頁/共74頁42有效數(shù)字 在工程上，誤差的概念就轉(zhuǎn)化為有效數(shù)字。似數(shù)。具有五位有效數(shù)字的近稱則的近似數(shù)例如：3.14161021.00000734. 0.14159265. 31416. 3)(1416. 3.14159265. 3*4*e第42頁/共74頁43位有效數(shù)的近似數(shù)。的具有為則稱的絕對誤差滿足。如果是整數(shù)且和其中有規(guī)格化形式設(shè)近似數(shù)定義nxxxxxexaaniamaaaaxxnmiinm*1321*1021| )(|90 , 0,.),.,

17、2 , 1(.0103 .2 .1第43頁/共74頁44 例：求1.3824具有幾位有效數(shù)字?第44頁/共74頁45 絕對誤差，相對誤差，有效數(shù)是度量近似數(shù)精度的常用三種。實(shí)際計算時最終結(jié)果均以有效數(shù)給出。同時也就隱含了絕對誤差和相對誤差界。界。絕對誤差界和相對誤差的有效數(shù)字位數(shù)、請分析例：若取*,4142. 1,2*xxx4*1021, 5, 1的絕對誤差界解：xnm第45頁/共74頁46554*1041044142.11021|)(|rrxxe即而相對誤差界估計為第46頁/共74頁47函數(shù)值的誤差估計 引入微分符號*ln)()(xdxdxxxxxedxxxxer第47頁/共74頁48，則：

18、的近似數(shù)設(shè)*2*121,xxxx)()()()(. 1*2*1*2*1*2*1*2*1xexedxdxxxdxxe)()(lnln)ln(ln)ln()(. 2*2*1*2*1*2*1*2*1*2*1xexexdxdxxdxxdxxerrr第48頁/共74頁49)()()()()()(. 3*2*1*1*2*2*1*2*1*2*1*2*1*2*1xexxexxexexxxxexxxxerrr)()()(. 4*2*1*2*1xexexxerrr2*2*2*1*1*2*2*1)()()()(. 5xxexxexxxe第49頁/共74頁501.2.3 函數(shù)值的誤差估計)()()()()()()()

19、()()()()(),(*xexfxfxfexexfxxxfxdfxfxffexfxxxfyrr或時，則誤差為計算函數(shù)值則代替用近似數(shù)當(dāng)設(shè)函數(shù)第50頁/共74頁51定的。是可以控制的，或是穩(wěn)過自變量的誤差，時，函數(shù)值的誤差不超這表明當(dāng)時有當(dāng)若記1, 1)()()()(1, 1|,)()(|,)(|*rrrrrCCxefexefeCCxfxfxCxfC第51頁/共74頁52義下的條件數(shù)。在絕對意義下和相對意為一般分別稱)(,xfCCr為良態(tài)；稱當(dāng))(1xfC 為病態(tài)。稱當(dāng))(1xfC 第52頁/共74頁53在正根附近的性態(tài)。討論函數(shù)例10100)(2 . 2 . 12xxxf100:100,10

20、10)(:21xxxxf即正根為解得由解在正根附近是病態(tài)的)(1201|12| )100(|100 xfxfx第53頁/共74頁54。變化，函數(shù)值變化極大也就是自變量發(fā)生微小則取則如：取09.20)9 .99()(, 9 .99200)99()(,99*1*1*1*1fxfxfxfx第54頁/共74頁55多元函數(shù)誤差估計TnTnnxxxxxxxxxxxfy),.,(),.,(),.,(21*2*1*21代替用對于多元函數(shù)niiiniiiinnxexfxxxfxxxfxxxffe1*1*21*2*1)()(),.,(),.,()(:其絕對誤差為)()(*1*iniixexffe因此絕對誤差界為第

21、55頁/共74頁56niiriirxexfxxxffe1*)()()(（同理相對誤差為| )(|)()(| )(|1*niiriirxexfxxxffe相對誤差界第56頁/共74頁57例題。的絕對誤差和相對誤差面積試估計觀測數(shù)據(jù)為設(shè)例SABC,)02.060(,)10.0120(,)10.0100(ABC3 .1.2oAmcmb第57頁/共74頁58，則解：由AbcSsin21)()()()(*AeAScecSbebSSe1 . 0sin211 . 0sin21*AbAc2*57.1018002. 0cos21mAcb第58頁/共74頁593*10035. 2sin2157.10|)(| )(

22、|Acbsseser對誤差界。如：出，則知道絕若數(shù)據(jù)以規(guī)格化形式給注意:10010. 01010.1003b253*10211021| )(|be則：第59頁/共74頁601.3算法的優(yōu)化 算法優(yōu)劣的標(biāo)準(zhǔn) 從截斷誤差觀點(diǎn)看,算法必須是截斷誤差小,收斂斂速要快。即運(yùn)算量小,機(jī)器用時少. 從舍入誤差觀點(diǎn)看,舍入誤差在計算過程中要能控制,即算法的數(shù)值要穩(wěn)定. 從實(shí)現(xiàn)算法的觀點(diǎn)看,算法的邏輯結(jié)構(gòu)不宜太復(fù)雜，便于程序編制和上機(jī)實(shí)現(xiàn).第60頁/共74頁61 設(shè)計算法時應(yīng)遵循的原則 要有數(shù)值要穩(wěn)定性,即能控制誤差的傳播. 避免大數(shù)吃小數(shù),即兩數(shù)相加時,防止較小的數(shù)加不到較大的數(shù)上. 避免兩相近的數(shù)相減,以免

23、有效數(shù)字的大量丟失. 避免分母很小(或乘法因子很大),以免產(chǎn)生溢出.第61頁/共74頁62例題。并評價算法收斂的快慢的值計算,2ln1.3.1例.) 1(.32)1ln(:解132nxxxxxTaylornn展式有算法一：由有：令1x.1) 1(.312112ln1nn第62頁/共74頁63收斂。所以且由級數(shù)判別，交錯級數(shù)2ln0limnna時，若要求510|度慢。，顯然項數(shù)大，收斂速則5102n第63頁/共74頁64得：并取則令則由于算法二1031211.)12.531(2)1ln()1ln(11ln:.)1(.32)1ln(.32)1ln(:24213232nxxxnxxxxxxxxnxxxxxnxxxxxnnnn第64頁/共74頁65)31(211.3151311 (322ln20421210111211109123112191119123132.)9125191231(32T其截斷誤差為很大。，計算精度及速度差距兩種算法，同樣計算2ln第65頁/共74頁66的值。計算圓周率例2 . 3 . 1.121) 1(.51311114:1102ndxxn算法一：由定積分解。則時同理若要5510,10|n第66頁/共74頁67141568627. 34785392156