數(shù)值分析第一章 緒論

1、數(shù)值分析又稱(chēng)計(jì)算方法或數(shù)值計(jì)算方法，是一門(mén)與計(jì)算機(jī)應(yīng)用密切結(jié)合的實(shí)用性很強(qiáng)的數(shù)學(xué)課程，它研究的是各種數(shù)學(xué)問(wèn)題的一類(lèi)近似解法數(shù)值方法，即從一組原始數(shù)據(jù)（如模型中的某些參數(shù)）出發(fā)，按照確定的運(yùn)算規(guī)則進(jìn)行有限步運(yùn)算，最終獲得數(shù)學(xué)問(wèn)題數(shù)值形式的滿(mǎn)足精度要求的近似解。,1.1 研究對(duì)象,1.緒論,數(shù)值分析方法課程主要討論如何構(gòu)造求數(shù)學(xué)模型近似解的算法，討論算法的數(shù)學(xué)原理、誤差和復(fù)雜性，配合程序設(shè)計(jì)進(jìn)行計(jì)算試驗(yàn)并分析試驗(yàn)結(jié)果。 與純數(shù)學(xué)的理論方法不同，用數(shù)值分析所求出的結(jié)果一般不是解的精確值或者準(zhǔn)確的解析表達(dá)式，而是所求真解的某些近似值或近似曲線。,1、數(shù)值逼近 插值與擬合、數(shù)值積分與微分 2、數(shù)值代數(shù)

2、線性代數(shù)方程組的解法、非線性代數(shù)方程（組）的解法 3、微分方程數(shù)值解 ODE PDE,現(xiàn)代計(jì)算方法：融進(jìn)了機(jī)器學(xué)習(xí)計(jì)算、仿生計(jì)算、網(wǎng)絡(luò)計(jì)算、以數(shù)據(jù)為核心的計(jì)算和各種普適計(jì)算、非線性科學(xué)計(jì)算等內(nèi)容。,1.2 研究?jī)?nèi)容,數(shù)值計(jì)算方法的主要特點(diǎn),借助計(jì)算機(jī)提供切實(shí)可行的數(shù)學(xué)算法.,通過(guò)數(shù)值實(shí)驗(yàn)證明算法行之有效.,采用“近似替代”方法逼近 采用“構(gòu)造性”方法 采用“離散化”方法 把求連續(xù)變量的問(wèn)題轉(zhuǎn)化為求離散變量的問(wèn)題 采用“遞推化”方法 復(fù)雜的計(jì)算歸結(jié)為簡(jiǎn)單過(guò)程的多次重復(fù)，易于用循環(huán)結(jié)構(gòu)來(lái)實(shí)現(xiàn)（迭代法）。 采用各種搜索方法,構(gòu)造數(shù)值算法主要手段,隨著科學(xué)技術(shù)的飛速發(fā)展，科學(xué)計(jì)算愈來(lái)愈顯示出其重要性。

3、科學(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)用專(zhuān)業(yè)等理工科本科生的專(zhuān)業(yè)基礎(chǔ)課，也是工科碩士研究生的學(xué)位必修課。,為什么要開(kāi)設(shè)這個(gè)課呢？,根據(jù)數(shù)學(xué)模型提出求解的數(shù)值計(jì)算方法直到編出程序上機(jī)算出結(jié)果，這一過(guò)程便是數(shù)值分析研究的對(duì)象,數(shù)值計(jì)算方法的任務(wù) （解題過(guò)程）,1. 認(rèn)識(shí)建立算法和對(duì)每個(gè)算法進(jìn)行理論分析是基本 任務(wù)，主動(dòng)適應(yīng)“公式多”的特點(diǎn)；2. 注重各章建立算法的問(wèn)題的提法，搞清問(wèn)題的基 本提法，逐步深入；3. 理解每個(gè)算法建立的數(shù)學(xué)背景，數(shù)學(xué)

4、原理和基本 線索，對(duì)最基本的算法要非常熟悉；4. 認(rèn)真進(jìn)行數(shù)值計(jì)算的訓(xùn)練，學(xué)習(xí)各章算法完全是,如何進(jìn)行學(xué)習(xí)？,為用于實(shí)際計(jì)算，必須真會(huì)算。,1.3.1 誤差的來(lái)源與分類(lèi),從實(shí)際問(wèn)題中抽象出數(shù)學(xué)模型 模型誤差,例:質(zhì)量為m的物體，在重力作用下,自由下落， 其下落距離s 與時(shí)間t 的關(guān)系是：,其中 g 為重力加速度。,1.3 誤 差,通過(guò)測(cè)量得到模型中參數(shù)的值 觀測(cè)誤差,求近似解 方法誤差 （截?cái)嗾`差）,例如，當(dāng)函數(shù),用 maclaurin 多項(xiàng)式,近似代替時(shí)，數(shù)值方法的截?cái)嗾`差是,機(jī)器字長(zhǎng)有限 舍入誤差,用計(jì)算機(jī)、計(jì)算器和筆算，都只能用有限位, = 3.1415926,小數(shù)來(lái)代替無(wú)窮小數(shù)或用位數(shù)

5、較少的小數(shù)來(lái),代替位數(shù)較多的有限小數(shù)，如：,四舍五入后,在數(shù)值計(jì)算方法中，主要研究截?cái)嗾`差和舍入誤差 （包括初始數(shù)據(jù)的誤差）對(duì)計(jì)算結(jié)果的影響！,1.3.2 誤差與有效數(shù)字,1、絕對(duì)誤差與絕對(duì)誤差限,例 :若用以厘米為最小刻度的尺去量桌子的長(zhǎng)，大約為1.45米，求1.45米的絕對(duì)誤差。,1.45米的 絕對(duì)誤差=？,不知道！,定義：設(shè) 是準(zhǔn)確值，為 的一個(gè)近似值，稱(chēng),是近似值 的絕對(duì)誤差,簡(jiǎn)稱(chēng)為誤差。,但實(shí)際問(wèn)題往往可以估計(jì)出 不超過(guò)某個(gè)正數(shù) ，,即 則稱(chēng) 為絕對(duì)誤差限，有了絕對(duì)誤差限,就可以知道 的范圍為,即 落在 內(nèi)。,在應(yīng)用上，常常采用下列寫(xiě)法來(lái)刻劃 的精度。,例1 設(shè)x =3.141592

6、6 近似值x* =3.14,它的絕 對(duì)誤差是 0.0015926，有, x-x*=0.0015926 0.002=0.210-2 例2 又近似值x* =3.1416，它的絕對(duì)誤差是 0.0000074，有 x-x*=0.0000074 0.000008=0.810-5 例3 而近似值x* =3.1415，它的絕對(duì)誤差是 0.0000926，有 x-x*=0.0000926 0.0001=0.110-3 可見(jiàn)，絕對(duì)誤差限*不是唯一的，但*越小越好,2、相對(duì)誤差與相對(duì)誤差限,定義：設(shè) 是準(zhǔn)確值， 是近似值，是近似值的誤差，,通常取,為近似值 的相對(duì)誤差，記作 ，,稱(chēng),一般情況下是不知道 的，怎么辦

7、？,事實(shí)上，當(dāng) 較小時(shí),是 的二次方項(xiàng)級(jí),故可忽略不計(jì).,相應(yīng)地，若正數(shù),滿(mǎn)足,則稱(chēng) 為 的相對(duì)誤差限。,例4. 甲打字每100個(gè)錯(cuò)一個(gè)，乙打字每1000個(gè) 錯(cuò)一個(gè)，求其相對(duì)誤差 解： 根椐定義:甲打字時(shí)的相對(duì)誤差 乙打字時(shí)的相對(duì)誤差,3 、有效數(shù)字,定義：如果,則說(shuō) 近似表示 準(zhǔn)確到小數(shù)后第 位，并從這,由上述定義,第 位起直到最左邊的非零數(shù)字之間的一切數(shù)字都,稱(chēng)為有效數(shù)字，并把有效數(shù)字的位數(shù)稱(chēng)為有效位數(shù)。,定義 :,若近似值 的誤差限是某一位的半個(gè)單位,也即，若,其中， 是1到9中的一個(gè)數(shù)字； 是 0到9中一個(gè)數(shù)字； 為整數(shù)，且,該位到 的左邊第一位非零數(shù)字共有 位,就說(shuō) 有 位有效數(shù)字。

8、,取 作 的近似值， 就有三位有效數(shù)字；,取 作 的近似值， 就有五位有效數(shù)字。,例如：,x-x*=0.0015926 0.002=0.210-20.510-2,前面例1,前面例2,x-x*=0.0000074 0.000008=0.810-5 0.510-4,關(guān)于有效數(shù)字說(shuō)明 用四舍五入取準(zhǔn)確值的前n位x*作為近似值,則 x*必有n位有效數(shù)字。如3.142作為 的近似值 有4位有效數(shù)字，而3.141為3位有效數(shù)字 有效數(shù)字相同的兩個(gè)近似數(shù)，絕對(duì)誤差不一定 相同。例如，設(shè)x1*=12345,設(shè)x2*=12.345,兩者 均有5位有效數(shù)字但絕對(duì)誤差不一樣 x- x1* =x- 12345 0.5

9、= 1/2 100 x- x2* =x- 12.3450.0005=1/210-3 把任何數(shù)乘以10p(p=0,1,)不影響有效位數(shù) 準(zhǔn)確值具有無(wú)窮多位有效數(shù)字,如三角形面積 S=1/2ah=0.5ah 因?yàn)?.5是真值,沒(méi)有誤差 *=0,因此n,準(zhǔn)確值具有無(wú)窮位有效數(shù)字,4 、誤差限與有效數(shù)字的關(guān)系,則 至少具有 位有效數(shù)字。,Th1：,對(duì)于用 式表示的近似數(shù) ，若 具有 位有效,數(shù)字，則其相對(duì)誤差限為,反之，若 的相對(duì)誤差限為,例5 已知近似數(shù)x*有兩位有效數(shù)字，試求其相 對(duì)誤差限 解：已知 n=2 代入公式 r*=1/2x1 10-(n-1)得 r*=1/2x1 10-1 x*的第一位有

10、效數(shù)字x1沒(méi)有給出，可進(jìn)行如下討論：當(dāng) x1=1 r*=1/2x1 10-1=1/2*1 10-1=5% x1=9 r*=1/2x1 10-1=1/2*9 10-1=0.56% 取 x1=1 時(shí)相對(duì)誤差為最大，即 5%,例6 已知近似數(shù)x*的相對(duì)誤差限為0.3%，問(wèn)x* 有幾位有效數(shù)字？ 解：由,得,當(dāng)x1=1時(shí),310-3=1/410-(n-1)1210-3=10-(n-1) 上式兩邊取以10為底的對(duì)數(shù)得 lg22+lg3+(-3)=-n+1 lg2=0.3010 lg3=0.4771 20.3010+0.4771-4=-n n=2.9209 當(dāng)x1=9時(shí),310-3=1/2010-(n-1

11、) 610-3=10-n 上式兩邊取以10為底的對(duì)數(shù)得 lg2+lg3+(-3)=-n n=2.2219 x*至少有3位有效數(shù)字,例7 為使 的近似數(shù)的相對(duì)誤差小于0.1%， 問(wèn)查開(kāi)方表時(shí)，要取幾位有效數(shù)字？ 解： 8 9 x1=8, -(n-1)2.7448 取 n =3即查平方表時(shí) 8.37取三位有效數(shù)字,1.3.3 數(shù)值運(yùn)算的誤差估計(jì),一、四則運(yùn)算的誤差估計(jì),兩個(gè)近似數(shù) 與 ,其誤差限分別為 及 , 它們進(jìn)行加減乘除運(yùn)算得到的誤差限分別為,從而有,的相對(duì)誤差,對(duì)于近似值,，函數(shù),在,舍去右邊第二項(xiàng)得到,即,的絕對(duì)誤差,可以得到,附近按泰勒展式展開(kāi)得到,二、函數(shù)誤差估計(jì),當(dāng)自變量有誤差時(shí)，

12、計(jì)算函數(shù)值也會(huì)產(chǎn)生誤差，其誤差限可利用函數(shù)的Taylor展開(kāi)式進(jìn)行估計(jì)。,對(duì)絕對(duì)誤差式兩邊取絕對(duì)值得,故,的相對(duì)誤差限,的誤差限,而,解釋?zhuān)?當(dāng) 為多元函數(shù)時(shí)計(jì)算 ,如果,的近似值為 ,則 的近似為,于是函數(shù)值 的誤差 由Taylor展開(kāi),得：,多元函數(shù)的情況,于是誤差限為,而 的相對(duì)誤差限為,式(1),例8:已測(cè)得某場(chǎng)地長(zhǎng) 的值為 ,寬 的值為 ,已知 , .試求 面積 的絕對(duì)誤差限與相對(duì)誤差限.,解: 因,其中,由式(1)得,而,于是絕對(duì)誤差限為,相對(duì)誤差限為,三、 算法的數(shù)值穩(wěn)定性,數(shù)值計(jì)算在設(shè)計(jì)算法時(shí)首先關(guān)心的是由它產(chǎn)生的計(jì)算結(jié)果的穩(wěn)定性，而算法的穩(wěn)定性與舍入誤差是否增長(zhǎng)密切相關(guān)。一個(gè)

13、算法如果輸入數(shù)據(jù)有微小擾動(dòng)（即誤差），而在計(jì)算過(guò)程中舍入誤差不增長(zhǎng)，則稱(chēng)此算法是數(shù)值穩(wěn)定的，否則稱(chēng)其為數(shù)值不穩(wěn)定。,例9：求定積分,的值.,解：直接積分可產(chǎn)生遞推公式,若取初值,可得遞推公式,按公式就可以逐步算出,What happened?!,不穩(wěn)定的算法 ！,這就是誤差傳播所引起的危害 !,注意此公式精確成立，且,由題設(shè)中的遞推公式（1）可看出， 的誤差擴(kuò)大了,5倍后傳給 ，因而初值 的誤差對(duì)以后各步,這就造成 的計(jì)算結(jié)果嚴(yán)重失真。,計(jì)算結(jié)果的影響，隨著 的增大愈來(lái)愈嚴(yán)重。,要怎么做才能解決這個(gè)問(wèn)題呢?,可求得I9 0.017，按改寫(xiě)后的公式可逐次求得,不妨設(shè)I9 I10，于是由,(2),

14、I8 0.019 I7 0.021 I6 0.024 I5 0.028 I4 0.034 I3 0.043 I2 0.058 I1 0.088 I0 0.182,穩(wěn)定的算法 ！,在我們今后的討論中，誤差將不可回避， 算法的穩(wěn)定性會(huì)是一個(gè)非常重要的話(huà)題。,注：遞推公式(1)的舍入誤差以5的冪次增長(zhǎng)進(jìn)行傳播，因此是數(shù)值不穩(wěn)定的，而遞推公式(2)的舍入誤差在一定范圍內(nèi)以0.2的冪次進(jìn)行傳播，隨著n的增大，誤差逐步減少，因此該算法是數(shù)值穩(wěn)定的。,因此，可以看出數(shù)值不穩(wěn)定的算法是不能使用的，實(shí)際計(jì)算中對(duì)任何輸入數(shù)據(jù)都是數(shù)值穩(wěn)定的算法，稱(chēng)為無(wú)條件穩(wěn)定。而對(duì)某些數(shù)據(jù)數(shù)值穩(wěn)定，對(duì)其它數(shù)據(jù)數(shù)值不穩(wěn)定的算法，稱(chēng)為

15、條件穩(wěn)定。,病態(tài)問(wèn)題和條件數(shù),如果問(wèn)題的輸入數(shù)據(jù)有微小擾動(dòng)，就會(huì)引起輸出結(jié)果數(shù)據(jù) （即解）的很大擾動(dòng)，稱(chēng)這樣的問(wèn)題為病態(tài)問(wèn)題。相反的情形 稱(chēng)為良態(tài)問(wèn)題。對(duì)于病態(tài)的數(shù)學(xué)問(wèn)題，用通常的算法求數(shù)值解 都是不穩(wěn)定的。,病態(tài)和良態(tài)是相對(duì)的，沒(méi)有嚴(yán)格的界限，通常用條件數(shù)大小 來(lái)衡量問(wèn)題的病態(tài)程度，條件數(shù)越大病態(tài)可能越嚴(yán)重。,條件數(shù)c(x)越大，f(x)的相對(duì)誤差越大，通常認(rèn)為,時(shí)，問(wèn)題是病態(tài)的。,1.3.4 數(shù)值計(jì)算中應(yīng)該注意的一些原則,1.要選擇數(shù)值穩(wěn)定的計(jì)算公式,定義 一種數(shù)值方法，若原始數(shù)據(jù)有誤差，而在計(jì)算的過(guò)程中，由于舍入誤差的傳播，使得近似計(jì)算結(jié)果與準(zhǔn)確值相差很大，則稱(chēng)這種數(shù)值方法是不穩(wěn)定的。否

16、則，在計(jì)算的過(guò)程中，若舍入誤差得到控制，近似計(jì)算結(jié)果能逼近準(zhǔn)確值，則稱(chēng)這種數(shù)值方法是穩(wěn)定的。,從而有,對(duì)上式兩邊求絕對(duì)值得,2.要避免兩個(gè)相近的數(shù)相減,在數(shù)值計(jì)算中，兩個(gè)相近的數(shù)作減法時(shí) 有效數(shù)字會(huì)損失。,例11: 求,當(dāng)x = 1000，y 的準(zhǔn)確值為0.01580,類(lèi)似地,(2) 若將原式改寫(xiě)為,則 y = 0.01581,(1)直接相減,有3位有效數(shù)字！,只有1位有效數(shù)字,3.盡量避免絕對(duì)值太小的數(shù)作分母,例12：,如分母變?yōu)?.0011，也即分母只有0.0001的變化時(shí),結(jié)果相差這么大!,4. 避免大數(shù)吃小數(shù),精確解為, 算法1：利用求根公式,例13：用單精度計(jì)算 的根。,在計(jì)算機(jī)內(nèi)，109存為0.11010，1存為0.1101。做加法時(shí)，兩加數(shù)的指數(shù)先向大指數(shù)對(duì)齊，再將浮點(diǎn)部分相加。即1 的指數(shù)部分須變?yōu)?010，則：1 = 0.0000000001 1010，取單精度時(shí)就成為： 109+1=0.100000001010+0.00000000 1010=0.10000000 1010,算法2：先解出,再利用,注：求和時(shí)從小到大相加，可使和的誤差減小。,例14：試按從小到大、以及從大到小的順序分別計(jì)算,1 + 2 + 3 + + 4