計(jì)算方法第一章課件

1、數(shù)值計(jì)算方法12引 言第一章31.數(shù)值計(jì)算方法及其主要研究?jī)?nèi)容 隨著科學(xué)技術(shù)的飛速發(fā)展，科學(xué)計(jì)算愈來(lái)愈顯示出其重要性?？茖W(xué)計(jì)算的應(yīng)用之廣已遍及各行各業(yè)，例如：氣象資料的分析圖像，飛機(jī)、汽車(chē)及輪船的外形設(shè)計(jì)，高科技研究等都離不開(kāi)科學(xué)計(jì)算。因此，作為科學(xué)計(jì)算的數(shù)學(xué)工具數(shù)值計(jì)算方法，已成為各高等院校數(shù)學(xué)、物理和計(jì)算機(jī)應(yīng)用專業(yè)等理工科本科生的專業(yè)基礎(chǔ)課，也是工科碩士研究生的學(xué)位必修課。4計(jì)算數(shù)學(xué)：常稱為數(shù)值分析或（數(shù)值）計(jì)算方法。 主要是研究如何運(yùn)用計(jì)算工具（如計(jì)算 器、計(jì)算機(jī)等）去獲得數(shù)學(xué)問(wèn)題的數(shù)值 解的理論和方法。當(dāng)代實(shí)踐表明：計(jì)算方法正在日趨明顯地成為數(shù)學(xué) 與計(jì)算機(jī)科學(xué)的交叉性科學(xué)。 對(duì)那些在經(jīng)

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

3、運(yùn)算盡可能提高數(shù)值方法的計(jì)算速度和少占存貯空間。選擇或研制能達(dá)到“數(shù)值問(wèn)題”要求的計(jì)算精度的數(shù)值方法，為此須研究數(shù)值問(wèn)題的性態(tài)及數(shù)值方法的穩(wěn)定性。計(jì)算方法：把求解數(shù)學(xué)問(wèn)題轉(zhuǎn)化為按一定次序只 進(jìn)行加、減、乘、除等基本運(yùn)算 數(shù)值方法。7例1.1.1求二次方程求根公式為：的根。開(kāi)方運(yùn)算不能在計(jì)算機(jī)上直接進(jìn)行運(yùn)算，必須化為可在計(jì)算機(jī)上執(zhí)行的等價(jià)運(yùn)算。即應(yīng)化為公式：8例1.1.2 已知 a0, a1, a2 , an, x, 計(jì)算多項(xiàng)式：直接計(jì)算：運(yùn)算量（乘法）秦九韶算法（1247年）：運(yùn)算量：9例1.1.3 解線性方程組其中， 克蘭姆(Cramer)法則： 運(yùn)算量(乘除)：高斯消元法(Gauss)：運(yùn)

4、算量(乘除)Gauss: 3060次Cramer:理論上很“漂亮”的Cramer法則 在計(jì)算機(jī)上并不適用！10一個(gè)計(jì)算過(guò)程主要包括如下幾個(gè)環(huán)節(jié)：(1) 數(shù)學(xué)建模：將工程問(wèn)題數(shù)學(xué)化工程中的數(shù)學(xué)模型一般可分為三類：(2) 算法設(shè)計(jì)：將數(shù)學(xué)問(wèn)題數(shù)值化連續(xù)型（確定型）離散型（統(tǒng)計(jì)型）不確定型（隨機(jī)型）本書(shū)重點(diǎn)討論例1.1.4 求解線性方程組求解二次方程是數(shù)值問(wèn)題11求解微分方程不是數(shù)值問(wèn)題將其變成數(shù)值問(wèn)題，即將其“離散化”“離散化”是將非數(shù)值問(wèn)題的數(shù)學(xué)模型化為數(shù)值問(wèn)題的主要方法，這也是計(jì)算方法的任務(wù)之一?12(3) 程序設(shè)計(jì)：將數(shù)值問(wèn)題機(jī)器化軟件開(kāi)發(fā)方法：結(jié)構(gòu)化方法：面向過(guò)程，“自頂而下，逐步細(xì)化”其

5、關(guān)鍵方面：劃分模塊設(shè)計(jì)或選擇模塊的算法充實(shí)細(xì)節(jié)組裝式開(kāi)發(fā)方法：面向?qū)ο?，“自下向上?3例1.1.5求二次方程的根。此問(wèn)題本身可看成功能單一的模塊數(shù)值方法：直接方法，即用求根公式迭代方法（后面將介紹）須考慮的細(xì)節(jié)：14(4) 上機(jī)運(yùn)行：數(shù)值模擬物理過(guò)程(5) 計(jì)算結(jié)果再表示：如圖像的可視化等(6) 可靠性分析：分析計(jì)算結(jié)果的可靠性，必要時(shí) 重復(fù)上述過(guò)程。其中算法設(shè)計(jì)是本書(shū)的核心內(nèi)容。本書(shū)針對(duì)來(lái)源于科學(xué)與工程中的數(shù)學(xué)模型問(wèn)題，介紹計(jì)算機(jī)上常用的數(shù)值方法的算法設(shè)計(jì)思想并進(jìn)行算法分析。15 本書(shū)研究?jī)?nèi)容：對(duì)如下五類問(wèn)題探索數(shù)值求解方法 及其與算法有關(guān)的理論分析(1) 非線性方程求根(2) 求解線性代

6、數(shù)方程組的數(shù)值方法(3) 數(shù)值逼近：插值逼近和最佳逼近(4) 數(shù)值微分和數(shù)值積分(5) 常微分方程數(shù)值解法16 將問(wèn)題可算化的手段：將問(wèn)題可算化是設(shè)計(jì)一個(gè)算 法的第一步(1) 用有限維空間代替無(wú)限維空間(2) 用有限過(guò)程代替無(wú)限過(guò)程(3) 用簡(jiǎn)單問(wèn)題代替復(fù)雜問(wèn)題(4) 擾動(dòng)分析：估計(jì)誤差或精度17余項(xiàng)(即截?cái)嗾`差)為例1.1.6解根據(jù)微分學(xué)的Taylor公式，有將問(wèn)題可算化，即用有限過(guò)程代替無(wú)限過(guò)程僅包含有限次的四則運(yùn)算18 構(gòu)造算法的途徑：(多用于確定型連續(xù)的數(shù)學(xué)模型)(1) 迭代技術(shù)（迭代法）(2) 離散化技術(shù)(3) 離散問(wèn)題解析化技術(shù)(4) 優(yōu)化技術(shù)19例1.1.7解若已知根的粗略近似值

7、，根據(jù)Taylor公式，有取等式右邊前二項(xiàng)近似替代f(x)，就會(huì)得到容易求解的線性方程稱為迭代序列Newton迭代法對(duì)于迭代法，通常需考慮迭代序列的收斂性與收斂效率！202.誤差及誤差分析計(jì)算公式中的運(yùn)算必須是在計(jì)算機(jī)上可執(zhí)行的運(yùn)算參與運(yùn)算的數(shù)必須是有限小數(shù)或整數(shù)因此，數(shù)值方法中的取數(shù)和運(yùn)算往往會(huì)出現(xiàn)誤差，算得的結(jié)果（稱為計(jì)算值）一般也為近似值。在任何科學(xué)計(jì)算中，其解的精確性總是相對(duì)的，而誤差則是絕對(duì)的。數(shù)值方法中的計(jì)算公式及參與運(yùn)算的數(shù)，都和數(shù)學(xué)中的一般情況有所不同，即21一、誤差的種類及來(lái)源一個(gè)物理量的真實(shí)值和我們算出的值（即計(jì)算值）往往存在差異，它們之差稱為誤差。模型誤差在建立數(shù)學(xué)模型過(guò)

8、程中，要將復(fù)雜的現(xiàn)象抽象歸結(jié)為數(shù)學(xué)模型，往往要忽略一些次要因素的影響，而對(duì)問(wèn)題作一些簡(jiǎn)化，因此數(shù)學(xué)模型和實(shí)際問(wèn)題之間有一定的誤差。觀測(cè)誤差在建模和具體運(yùn)算過(guò)程中所用的數(shù)據(jù)往往是通過(guò)觀察和測(cè)量得到的，受觀測(cè)方式、儀器精度以及外部觀測(cè)條件等多種因素限制，不可能獲得精確值，由此而來(lái)產(chǎn)生的誤差。22截?cái)嗾`差由于計(jì)算機(jī)只能完成有限次算術(shù)運(yùn)算和邏輯運(yùn)算，因此要將有些需用極限或無(wú)窮過(guò)程進(jìn)行的運(yùn)算有限化，對(duì)無(wú)窮過(guò)程進(jìn)行截?cái)?，這就帶來(lái)誤差。例:若將前若干項(xiàng)的部分和作為函數(shù)值的近似公式，由于以后各項(xiàng)都舍棄了，自然產(chǎn)生了誤差Taylor展開(kāi)23舍入誤差在數(shù)值計(jì)算過(guò)程中還會(huì)遇到無(wú)窮小數(shù)，因計(jì)算機(jī)受到機(jī)器字長(zhǎng)的限制，它

9、所能表示的數(shù)據(jù)其位數(shù)只能是有限的，如按四舍五入規(guī)則取有限位數(shù)，由此引起的誤差另外還有過(guò)失誤差，這類誤差是由于模型錯(cuò)誤或方法錯(cuò)誤所引起的，一般可以避免。24結(jié)論：誤差是不可避免的經(jīng)過(guò)大量的運(yùn)算之后，積累的總誤差有時(shí)會(huì)大得驚人，因此如何控制誤差的傳播也是數(shù)值方法的研究對(duì)象。在種誤差中，前種是客觀存在的，后種是計(jì)算方法引起的。數(shù)學(xué)模型一旦建立，進(jìn)入具體計(jì)算時(shí)所考慮和分析的就是截?cái)嗾`差和舍入誤差。因此本課程只涉及這種誤差。在實(shí)際問(wèn)題中求精確解是沒(méi)有意義的，求近似解是正常的。問(wèn)題是如何盡量減少誤差，提高精度。25二、誤差和誤差限定義1.2.1 絕對(duì)誤差限或誤差限,26顯然有時(shí)也表示為且哪個(gè)更精確呢?27

10、定義1.2.2 絕對(duì)誤差和絕對(duì)誤差限僅考慮了誤差值本身的大小，沒(méi)有考慮準(zhǔn)確值的大小。為了能較好地反映近似值的精確程度，還應(yīng)考慮準(zhǔn)確值的大小。28絕對(duì)誤差限相對(duì)誤差限代替相對(duì)誤差代替相對(duì)誤差限因此往往未知29例1.2.1解30例1.2.2解可見(jiàn)，經(jīng)四舍五入取近似值，其絕對(duì)誤差限將不超過(guò)其末位數(shù)字的半個(gè)單位。31三、浮點(diǎn)數(shù)與有效數(shù)字定點(diǎn)數(shù)：小數(shù)點(diǎn)的位置固定在個(gè)位數(shù)后。機(jī)器數(shù)：計(jì)算機(jī)中可表示的數(shù)。為了提高精度，機(jī)器數(shù)通常是用浮點(diǎn)數(shù)表示的。稱為基數(shù)稱為尾數(shù)或數(shù)碼稱為階碼32其中基數(shù)是正整數(shù)，一般取為，但為照顧習(xí)慣和書(shū)寫(xiě)方便，通常化為十進(jìn)制數(shù)輸入或輸出。階碼是整數(shù)。一定型號(hào)的計(jì)算機(jī)，尾數(shù)的位數(shù)t是固定的

11、，稱為計(jì)算機(jī)的位數(shù)；階碼m也有一定的取值范圍：33有4位有效數(shù)字有6位有效數(shù)字定義1.2.3 有8位有效數(shù)字只有4位有效數(shù)字！由于計(jì)算機(jī)只能表示有限個(gè)數(shù)，故通常利用某種舍入規(guī)則(如四舍五入，截?cái)嗾`差等)，將數(shù)進(jìn)行浮點(diǎn)化。因而勢(shì)必產(chǎn)生舍入誤差。34n+m位有效數(shù)字n-m位有效數(shù)字n位有效數(shù)字如何確定有效數(shù)字、絕對(duì)誤差限、相對(duì)誤差限？說(shuō)明有效數(shù)字位數(shù)與小數(shù)點(diǎn)的位置無(wú)關(guān)。只有寫(xiě)成規(guī)格化形式后，小數(shù)點(diǎn)后的位數(shù)才能反映出其有效位數(shù)的多少。35因此，根據(jù)上述分析，對(duì)有效數(shù)字有如下結(jié)果：定理1.2.1 例1.2.3求下列四舍五入近似值的有效數(shù)字位數(shù).3位3位4位4位3位5位補(bǔ)充36例1.2.4實(shí)際上只有1位

12、！試求它們的有效數(shù)字位數(shù)。解k=1, n=2, m=237例1.2.5從以上分析可見(jiàn)，四舍五入的近似值的數(shù)字都是有效數(shù)字而不是四舍五入得到的近似值的數(shù)字不一定是有效數(shù)字。k=3, m=4n=3k=4, m=5n=438定理1.2.2 證明下面的結(jié)果論述了相對(duì)誤差與有效數(shù)字的關(guān)系補(bǔ)充39即則有由定理1.2.1可知，40例1.2.6解4142定理1.2.3 該結(jié)論可以參照定理1.2.2的證明，請(qǐng)同學(xué)們自證補(bǔ)充定理說(shuō)明:有效數(shù)字位數(shù)越多相對(duì) 誤差限就越小，反之亦然。 43例1.2.7解則根據(jù)定理1.2.3，相對(duì)誤差滿足即應(yīng)取4位有效數(shù)字，近似值的誤差不超過(guò)0.1%.44四、誤差的傳播1、數(shù)據(jù)誤差的傳

13、播由多元函數(shù)的Taylor展開(kāi)公式可得，的絕對(duì)誤差為：相對(duì)誤差為：稱為 f 的條件數(shù)，其絕對(duì)值的大小可反映函數(shù)值對(duì)數(shù)據(jù)的敏感程度45利用上面的誤差估計(jì)公式，可以得到兩個(gè)數(shù)的和、差、積、商的誤差估計(jì)462、舍入誤差的傳播因舍入導(dǎo)致的相對(duì)誤差限僅與計(jì)算機(jī)的字長(zhǎng)有關(guān)，通常稱相對(duì)誤差限 為計(jì)算機(jī)的相對(duì)精度。即47在計(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ǔ)。48由上面的討論可以看出，為了求得滿意的計(jì)算解，在選用計(jì)算公式和設(shè)計(jì)算法時(shí)，都應(yīng)注意如下普遍原則：(1) 防止大數(shù)吃小數(shù)主要由計(jì)算機(jī)的位數(shù)引起選用算法應(yīng)遵循的原則計(jì)算機(jī)中數(shù)的計(jì)算特點(diǎn)：加

14、法先對(duì)階，后運(yùn)算，再舍入。乘法先運(yùn)算，再舍入。不在計(jì)算機(jī)數(shù)系中的數(shù)做四舍五入處理。49計(jì)算機(jī)在進(jìn)行運(yùn)算時(shí)，首先要把參加運(yùn)算的數(shù)對(duì)階，即把兩數(shù)都寫(xiě)成絕對(duì)值小于1而階碼相同的數(shù)。例1.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 = 10450作一個(gè)有效數(shù)字為4位的連加運(yùn)算而如果將小數(shù)放在前面計(jì)算在作連加時(shí)，為防止大數(shù)吃小數(shù)，應(yīng)從小到大進(jìn)行相加，如此，精度將得到適當(dāng)改善。當(dāng)然也可采取別的方法。例1.2.951(

15、2) 作減法時(shí)應(yīng)避免兩個(gè)相近數(shù)相減兩個(gè)相近的數(shù)相減，會(huì)使有效數(shù)字的位數(shù)嚴(yán)重?fù)p失！例1.2.10用四位浮點(diǎn)數(shù)計(jì)算 解只有一位有效數(shù)字,有效數(shù)字大量損失，造成相對(duì)誤差擴(kuò)大。結(jié)果仍然有四位有效數(shù)字。這說(shuō)明了算法設(shè)計(jì)的重要性。在算法設(shè)計(jì)中，若可能出現(xiàn)兩個(gè)相近數(shù)相減，則改變計(jì)算公式，如使用三角變換、有理化等等。52例1.2.11解方程解方程的精確解為而如果在字長(zhǎng)為8，基底為10的計(jì)算機(jī)上利用求根公式機(jī)器吃了因此在計(jì)算機(jī)上53上式是解二次方程的數(shù)值公式的值與精確解差別很大！54(3) 避免小數(shù)作除數(shù)和大數(shù)作乘數(shù)小數(shù)作除數(shù)或大數(shù)作乘數(shù)會(huì)產(chǎn)生溢出錯(cuò)誤，因而產(chǎn)生大的誤差。在算法設(shè)計(jì)時(shí)，要避免這類情況在計(jì)算公式中

16、出現(xiàn)。此時(shí)可以根據(jù)一些具體情況, 把某些算式改寫(xiě)成另一種等價(jià)的形式，如分母有理化等。根據(jù)誤差傳播的估計(jì)式553.算法的穩(wěn)定性如前所述，由于各種誤差的存在，計(jì)算機(jī)往往只能近似地求解實(shí)際問(wèn)題，因而計(jì)算時(shí)會(huì)冒風(fēng)險(xiǎn)。例1.3.1分析Wilkinson多項(xiàng)式的根對(duì)系數(shù)的敏感程度。見(jiàn)書(shū)P15例1.3.2可以看出： Wilkinson（威爾金森）多項(xiàng)式系數(shù)的微小變化，引起多項(xiàng)式根的劇烈波動(dòng)。因此， Wilkinson多項(xiàng)式的根對(duì)系數(shù)相當(dāng)敏感。一、問(wèn)題的性態(tài)56如把方程組的系數(shù)舍入成兩位有效數(shù)字它的精確解為x1 = -6.222. x2= 38.25 x3= -33.65.例1.3.2求解線性方程組其精確解為

17、 x1=x2=x3=1.57若對(duì)方程組的系數(shù)和中間結(jié)果均取3位10進(jìn)制有效數(shù)字，然后用Gauss消元法求解，得到計(jì)算解為：顯然，該計(jì)算解的精度較差。同樣用Gauss消元法求解方程組：也取3位10進(jìn)制有效數(shù)字，得到計(jì)算解為：容易驗(yàn)證，它是方程組的精確解。58上述例子表明，數(shù)值問(wèn)題計(jì)算解的精度，與數(shù)值問(wèn)題本身的性態(tài)有關(guān)。定義1.3.1 在數(shù)值問(wèn)題中，如果輸出數(shù)據(jù)對(duì)輸入數(shù)據(jù)的擾動(dòng)（如誤差）很敏感，即若輸入數(shù)據(jù)（如原始數(shù)據(jù)）有較小的變化，會(huì)引起輸出數(shù)據(jù)（如計(jì)算解）的較大變化，稱這類數(shù)值問(wèn)題為病態(tài)問(wèn)題或壞條件問(wèn)題。非病態(tài)問(wèn)題又稱為良態(tài)問(wèn)題。當(dāng)計(jì)算機(jī)用近似計(jì)算求解病態(tài)問(wèn)題時(shí)，是相當(dāng)冒險(xiǎn)的，得到的結(jié)果可能根

18、本不可靠。因此，處理病態(tài)問(wèn)題必須非常小心，一般應(yīng)采用高精度算法。對(duì)于良態(tài)問(wèn)題，由于舍入誤差的影響，不恰當(dāng)?shù)乃惴ㄍ瑯涌梢鹩?jì)算結(jié)果的不可信。59二、算法的穩(wěn)定性與設(shè)計(jì)原則例1.3.3計(jì)算定積分解一個(gè)程序往往要進(jìn)行大量的四則運(yùn)算才能得出結(jié)果，每一步的運(yùn)算均可能會(huì)產(chǎn)生舍入誤差。在大量計(jì)算中,舍入誤差是積累還是能控制,這與算法有關(guān)。60誤差放大 5千倍!并假設(shè)計(jì)算過(guò)程中不產(chǎn)生新的舍入誤差 。誤差會(huì)放大由公式可推出：61顯然算法不穩(wěn)定。理論上成立的算法，在計(jì)算機(jī)上計(jì)算時(shí)，由于初值的誤差在計(jì)算過(guò)程中的傳播，而導(dǎo)致結(jié)果的失真，這是我們數(shù)值計(jì)算方法所要研究的。(2) 利用遞推公式誤差不會(huì)放大數(shù)值穩(wěn)定，在運(yùn)算過(guò)程中，舍入誤差不增大。 62定義1.3.2 如果對(duì)于良態(tài)問(wèn)題，在運(yùn)算過(guò)程中,舍入誤差能控制在某個(gè)范圍內(nèi)的算法稱之為數(shù)值穩(wěn)定的算法,否則就稱之為不