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

1、數(shù)值分析又稱計算方法或數(shù)值計算方法，是一門與計算機(jī)應(yīng)用密切結(jié)合的實(shí)用性很強(qiáng)的數(shù)學(xué)課程，它研究的是各種數(shù)學(xué)問題的一類近似解法數(shù)值方法，即從一組原始數(shù)據(jù)（如模型中的某些參數(shù)）出發(fā)，按照確定的運(yùn)算規(guī)則進(jìn)行有限步運(yùn)算，最終獲得數(shù)學(xué)問題數(shù)值形式的滿足精度要求的近似解。,1.1 研究對象,1.緒論,數(shù)值分析方法課程主要討論如何構(gòu)造求數(shù)學(xué)模型近似解的算法，討論算法的數(shù)學(xué)原理、誤差和復(fù)雜性，配合程序設(shè)計進(jìn)行計算試驗(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ìn)了機(jī)器學(xué)習(xí)計算、仿生計算、網(wǎng)絡(luò)計算、以數(shù)據(jù)為核心的計算和各種普適計算、非線性科學(xué)計算等內(nèi)容。,1.2 研究內(nèi)容,數(shù)值計算方法的主要特點(diǎn),借助計算機(jī)提供切實(shí)可行的數(shù)學(xué)算法.,通過數(shù)值實(shí)驗(yàn)證明算法行之有效.,采用“近似替代”方法逼近 采用“構(gòu)造性”方法 采用“離散化”方法 把求連續(xù)變量的問題轉(zhuǎn)化為求離散變量的問題 采用“遞推化”方法 復(fù)雜的計算歸結(jié)為簡單過程的多次重復(fù)，易于用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)（迭代法）。 采用各種搜索方法,構(gòu)造數(shù)值算法主要手段,隨著科學(xué)技術(shù)的飛速發(fā)展，科學(xué)計算愈來愈顯示出其重要性。

3、科學(xué)計算的應(yīng)用之廣已遍及各行各業(yè)；例如：氣象資料的分析圖像，飛機(jī)、汽車及輪船的外形設(shè)計，高科技研究等都離不開科學(xué)計算。因此，作為科學(xué)計算的數(shù)學(xué)工具數(shù)值計算方法已成為各高等院校數(shù)學(xué)、物理和計算機(jī)應(yīng)用專業(yè)等理工科本科生的專業(yè)基礎(chǔ)課，也是工科碩士研究生的學(xué)位必修課。,為什么要開設(shè)這個課呢？,根據(jù)數(shù)學(xué)模型提出求解的數(shù)值計算方法直到編出程序上機(jī)算出結(jié)果，這一過程便是數(shù)值分析研究的對象,數(shù)值計算方法的任務(wù) （解題過程）,1. 認(rèn)識建立算法和對每個算法進(jìn)行理論分析是基本 任務(wù)，主動適應(yīng)“公式多”的特點(diǎn)；2. 注重各章建立算法的問題的提法，搞清問題的基 本提法，逐步深入；3. 理解每個算法建立的數(shù)學(xué)背景，數(shù)學(xué)

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

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

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

7、？,事實(shí)上，當(dāng) 較小時,是 的二次方項級,故可忽略不計.,相應(yīng)地，若正數(shù),滿足,則稱 為 的相對誤差限。,例4. 甲打字每100個錯一個，乙打字每1000個 錯一個，求其相對誤差 解： 根椐定義:甲打字時的相對誤差 乙打字時的相對誤差,3 、有效數(shù)字,定義：如果,則說 近似表示 準(zhǔn)確到小數(shù)后第 位，并從這,由上述定義,第 位起直到最左邊的非零數(shù)字之間的一切數(shù)字都,稱為有效數(shù)字，并把有效數(shù)字的位數(shù)稱為有效位數(shù)。,定義 :,若近似值 的誤差限是某一位的半個單位,也即，若,其中， 是1到9中的一個數(shù)字； 是 0到9中一個數(shù)字； 為整數(shù)，且,該位到 的左邊第一位非零數(shù)字共有 位,就說 有 位有效數(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ù)字說明 用四舍五入取準(zhǔn)確值的前n位x*作為近似值,則 x*必有n位有效數(shù)字。如3.142作為 的近似值 有4位有效數(shù)字，而3.141為3位有效數(shù)字 有效數(shù)字相同的兩個近似數(shù)，絕對誤差不一定 相同。例如，設(shè)x1*=12345,設(shè)x2*=12.345,兩者 均有5位有效數(shù)字但絕對誤差不一樣 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)確值具有無窮多位有效數(shù)字,如三角形面積 S=1/2ah=0.5ah 因?yàn)?.5是真值,沒有誤差 *=0,因此n,準(zhǔn)確值具有無窮位有效數(shù)字,4 、誤差限與有效數(shù)字的關(guān)系,則 至少具有 位有效數(shù)字。,Th1：,對于用 式表示的近似數(shù) ，若 具有 位有效,數(shù)字，則其相對誤差限為,反之，若 的相對誤差限為,例5 已知近似數(shù)x*有兩位有效數(shù)字，試求其相 對誤差限 解：已知 n=2 代入公式 r*=1/2x1 10-(n-1)得 r*=1/2x1 10-1 x*的第一位有

10、效數(shù)字x1沒有給出，可進(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 時相對誤差為最大，即 5%,例6 已知近似數(shù)x*的相對誤差限為0.3%，問x* 有幾位有效數(shù)字？ 解：由,得,當(dāng)x1=1時,310-3=1/410-(n-1)1210-3=10-(n-1) 上式兩邊取以10為底的對數(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時,310-3=1/2010-(n-1

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

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

13、算法如果輸入數(shù)據(jù)有微小擾動（即誤差），而在計算過程中舍入誤差不增長，則稱此算法是數(shù)值穩(wěn)定的，否則稱其為數(shù)值不穩(wěn)定。,例9：求定積分,的值.,解：直接積分可產(chǎn)生遞推公式,若取初值,可得遞推公式,按公式就可以逐步算出,What happened?!,不穩(wěn)定的算法 ！,這就是誤差傳播所引起的危害 !,注意此公式精確成立，且,由題設(shè)中的遞推公式（1）可看出， 的誤差擴(kuò)大了,5倍后傳給 ，因而初值 的誤差對以后各步,這就造成 的計算結(jié)果嚴(yán)重失真。,計算結(jié)果的影響，隨著 的增大愈來愈嚴(yán)重。,要怎么做才能解決這個問題呢?,可求得I9 0.017，按改寫后的公式可逐次求得,不妨設(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)定性會是一個非常重要的話題。,注：遞推公式(1)的舍入誤差以5的冪次增長進(jìn)行傳播，因此是數(shù)值不穩(wěn)定的，而遞推公式(2)的舍入誤差在一定范圍內(nèi)以0.2的冪次進(jìn)行傳播，隨著n的增大，誤差逐步減少，因此該算法是數(shù)值穩(wěn)定的。,因此，可以看出數(shù)值不穩(wěn)定的算法是不能使用的，實(shí)際計算中對任何輸入數(shù)據(jù)都是數(shù)值穩(wěn)定的算法，稱為無條件穩(wěn)定。而對某些數(shù)據(jù)數(shù)值穩(wěn)定，對其它數(shù)據(jù)數(shù)值不穩(wěn)定的算法，稱為

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

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