數(shù)值分析1.1講義.課件

1、 數(shù)值分析 Numerical Analysis 數(shù)值分析(第2版) 朱曉臨 主編中國科學(xué)技術(shù)大學(xué)出版社教 材數(shù)值分析（第5版） 李慶陽，王能超，易大義編著 清華大學(xué)大學(xué)出版社數(shù)值分析（第3版） 顏慶津著， 北京航空航天大學(xué) 出版社 Numerical Analysis(Ninth ed.) Richard Burden, Dougla Faires, Brooks/Cole, Cengage Learning, 2011參考書目 微積分 線性代數(shù) 常微分方程 算法語言預(yù)備知識一、為什么要學(xué)習(xí)數(shù)值分析？課程簡介現(xiàn)實世界的問題可以歸結(jié)為各種各樣的數(shù)學(xué)問題 方程求根問題 解線性方程組的問題 定積分

2、問題 常微分方程初值問題 .方程求根問題在科學(xué)計算中常要遇到求解各種方程，例如：高次代數(shù)方程 x53x70超越方程 高次線性方程和超越方程看似簡單，但難于求其精確解。對于高次代數(shù)方程，由代數(shù)基本定理知多項式根的數(shù)目和方程的階相同，但對超越方程就復(fù)雜的多，如果有解，其解可能是一個或幾個，也可能是無窮多個。解線性方程組的問題線性方程組的一般形式(1)當(dāng)b0時稱為非齊次線性方程組，其可能有唯一解、無解或者無窮多個解。當(dāng)b=0時稱為線性齊次方程組，必有零解。 (2)由線性代數(shù)知識可知：當(dāng)系數(shù)矩陣A非奇異(即detA0)時，方程組有唯一解，可用克萊姆法則求解，但它只適合于n很小的情況。克萊姆法則其中例如

3、 用克萊姆法則求解一個n階方程組，要算n+1個n階行列式的值，總共需要 n!(n-1)(n+1)次乘法。當(dāng)n充分大時，計算量是相當(dāng)驚人的。比如一個20階不算太大的方程組，大約要做1021次乘法，這項計算即使每秒1億次浮點數(shù)乘法計算的計算機(jī)去做，也要連續(xù)工作30萬年才能完成。當(dāng)然這是完全沒有實際意義的，故需要尋找有效算法!定積分問題對于積分由微積分知識可知：只要找到被積函數(shù)f(x)的原函數(shù)F(x)，便有下列牛頓萊布尼茲公式為何要進(jìn)行數(shù)值積分？原因之一：許多形式上很簡單的函數(shù)，例如已證明它們的原函數(shù)不能用初等函數(shù)表示成有限形式。原因之二：有些被積函數(shù)的原函數(shù)過于復(fù)雜，例如的一個原函數(shù)是要計算f(x

4、)定積分的近似值，上式就不見得方便。原因之三：f (x)以離散數(shù)據(jù)點形式給出xix0 x1xnyi = f(xi)y0y1yn常微分方程初值問題一階常微分方程的初值問題，即 例常微分方程的一般解(解析解) 對一些典型的微分方程(可分離變量方程，一階線性方程等等)，有可能找出它們的一般解表達(dá)式，然后用初始條件確定表達(dá)式中的任意常數(shù)，這樣解即能確定。 例如 求解解：分離變量得 dy=2xdx 積分得y=x2+c 由初值得c=0 故解為y=x2 但是對于求解無法求出一般解！二、 如何學(xué)習(xí)數(shù)值分析？課程簡介1.注意掌握各種方法的基本原理2.注意各種方法的構(gòu)造手法3.重視各種方法的誤差分析4.做一定量的

5、習(xí)題5.注意與實際問題相聯(lián)系第一章緒 論數(shù)值分析1數(shù)值分析研究的對象與特點一、數(shù)值分析研究的對象二、數(shù)值分析研究的特點1.數(shù)值分析研究的對象數(shù)值分析是計算數(shù)學(xué)的一個主要部分，計算數(shù)學(xué)是數(shù)學(xué)科學(xué)的一個分支，它研究用計算機(jī)求解各種數(shù)學(xué)問題的數(shù)值計算方法及其理論與軟件實現(xiàn).用計算機(jī)解決科學(xué)計算問題通常經(jīng)歷以下過程實際問題數(shù)學(xué)模型數(shù)值計算方法程序設(shè)計上機(jī)計算結(jié)果應(yīng)用數(shù)學(xué)計算數(shù)學(xué)2.數(shù)值分析研究的內(nèi)容 函數(shù)的數(shù)值逼近(插值與擬合) 數(shù)值積分與數(shù)值微分 非線性方程數(shù)值解 數(shù)值線性代數(shù) 常微和偏微數(shù)值解，數(shù)值分析實質(zhì)上是以數(shù)學(xué)問題為研究對象，不像純數(shù)學(xué)那樣只研究數(shù)學(xué)本身的理論，而是把理論與計算緊密結(jié)合，著重

6、研究數(shù)學(xué)問題的數(shù)值方法及理論。3. 數(shù)值分析的特點面向計算機(jī)，要根據(jù)計算機(jī)特點設(shè)計切實可行的有效算法. 有可靠的理論分析，能任意逼近并達(dá)到精度要求，對近似計算要保證收斂性和數(shù)值穩(wěn)定性.(3) 要有好的計算復(fù)雜性，時間復(fù)雜性好是指節(jié)省時間，空間復(fù)雜性好是指節(jié)省存貯量，這也是建立算法要研究的問題.(4) 要有數(shù)值試驗，即任何一個算法除了從理論上要滿足上述三點外，還要通過數(shù)值試驗證明是行之有效的.2數(shù)值計算的誤差一、誤差來源的分類二、誤差分析的重要性三、絕對誤差和絕對誤差限四、相對誤差和相對誤差限五、有效數(shù)字一、誤差來源的類型 1.模型誤差 從實際問題中抽象出數(shù)學(xué)模型 模型誤差 /* Modelin

7、g Error */2.觀測誤差 通過測量得到模型中參數(shù)的值 觀測誤差 /* Measurement Error */注：通常根據(jù)測量工具的精度，可以知道這類誤差的上限值。 當(dāng)數(shù)學(xué)模型得不到精確解時，要用數(shù)值計算方法求它的近似解，由此產(chǎn)生的誤差稱為截斷誤差或方法誤差3. 截斷誤差 求近似解 方法誤差 (截斷誤差) /* Truncation Error */ 例如：在微積分中sinx可展開成 但在計算機(jī)中計算時，常用前幾項來代替，即拋棄了無窮級數(shù)的后段，這樣就產(chǎn)生了截斷誤差。 當(dāng)|x|很小時，常用x代替sinx，其截斷誤差大約為 x 3/6。 由于計算機(jī)字長有限，原始數(shù)據(jù)的輸入及浮點數(shù)運算過程

8、中都有可能產(chǎn)生誤差，這樣產(chǎn)生的誤差稱為舍入誤差4.舍入誤差 機(jī)器字長有限 舍入誤差 /* Roundoff Error */在數(shù)值分析課程中，主要研究 截斷誤差 舍入誤差 二、誤差分析的重要性 考察如下兩個方程組試思考這兩個方程組的解的關(guān)系？容易看出系數(shù)矩陣完全相同，而常數(shù)項矩陣有微小差別，右端系數(shù)1.9999變成2.0001，其誤差為2.0001-1.9999=0.0002 =0.02%但對應(yīng)的解為由此看出系數(shù)矩陣完全相同，而常數(shù)項矩陣有微小差別的方程組，其解竟然相差得很大！解的最大誤差= 2 = 200%據(jù)說，美軍 1910 年的一次部隊的命令傳遞是這樣的: 營長對值班軍官: 明晚大約 8

9、點鐘左右，哈雷彗星將可能在這個地區(qū)看到，這種彗星每隔 76年才能看見一次。命令所有士兵著野戰(zhàn)服在操場上集合，我將向他們解釋這一罕見的現(xiàn)象。如果下雨的話，就在禮堂集合，我為他們放一部有關(guān)彗星的影片。值班軍官對連長: 根據(jù)營長的命令，明晚8點哈雷彗星將在操場上空出現(xiàn)。如果下雨的話，就讓士兵穿著野戰(zhàn)服列隊前往禮堂，這一罕見的現(xiàn)象將在那里出現(xiàn)。連長對排長: 根據(jù)營長的命令，明晚8點，非凡的哈雷彗星將身穿野戰(zhàn)服在禮堂中出現(xiàn)。如果操場上下雨，營長將下達(dá)另一個命令，這種命令每隔76年才會出現(xiàn)一次。排長對班長: 明晚8點，營長將帶著哈雷彗星在禮堂中出現(xiàn)，這是每隔 76年才有的事。如果下雨的話，營長將命令彗星穿

10、上野戰(zhàn)服到操場上去。班長對士兵: 在明晚8點下雨的時候，著名的76歲哈雷將軍將在營長的陪同下身著野戰(zhàn)服，開著他那“彗星”牌汽車，經(jīng)過操場前往禮堂。三、絕對誤差和絕對誤差限 定義 設(shè)某一量的準(zhǔn)確值為x，近似值為x*，則x*與x之差叫做近似值x*的絕對誤差(簡稱誤差)，記為？判斷題：絕對誤差是誤差的絕對值絕對誤差的性質(zhì)(1)絕對誤差e(x*) 可正可負(fù)(2) |e(x*) |的大小標(biāo)志著x*的精確度(3) 絕對誤差e(x*) 未知定義 若指定一個適當(dāng)小的正數(shù) ，使 有時用 表示近似值x*的精度或準(zhǔn)確值的所在范圍。則 稱為近似值 x* 的絕對誤差限。絕對誤差限的性質(zhì)(1)在實際問題中，絕對誤差一般是

11、有量綱的，絕對誤差限也是有量綱的。 例如，測得某物體的長度為5m，其誤差限為0.01m(2)絕對誤差限是正的，有無窮多個。若已知 是絕對誤差限，由于則比 大的任意正數(shù)均是絕對誤差限。 思考題：設(shè)有兩個溫度計，其一測量1000時的絕對誤差限為5，而另一個測量100時的絕對誤差限為1。 問：哪一個溫度計更精確？四、相對誤差和相對誤差限答：雖然后者絕對誤差限的數(shù)值較小，但第一種溫度計更為精確。 決定一個量的近似值的精確度除了要看絕對誤差的大小外，還要考慮到該量本身的大小。定義: 絕對誤差與準(zhǔn)確值之比稱為x*的相對誤差.(2)由于準(zhǔn)確值x未知，故實際問題中，當(dāng)| |較小時，常取注(1)相對誤差是個無量

12、綱量,值小者精度高。當(dāng)| |較小時，可用下式計算定義 若指定一個適當(dāng)小的正數(shù) ，使則稱 為近似值 x*的相對誤差限 當(dāng)x有很多位數(shù)字時，常按照“四舍五入”原則取前幾位數(shù)字作為x的近似值例：設(shè) x = = 3.1415926取x1*= 3作為的近似值，則五、有效數(shù)字取 x2* = 3.14 作為的近似值，則取 x3* = 3.1416作為的近似值，則它們的誤差都不超過某一數(shù)位的半個單位。若近似值x*的絕對誤差限是某一位的半個單位，該位到x*的第一位非零數(shù)字一共有n位，則稱近似值x*有n位有效數(shù)字，或說x*精確到該位。定義：有效數(shù)字若將準(zhǔn)確值x 的近似值x*表示成標(biāo)準(zhǔn)形式而其誤差限則說近似值x*具

13、有n 位有效數(shù)字。這里n 為正整數(shù)，m 為整數(shù)，每個均為0,1，9中的一個數(shù)字， 注：有效數(shù)字的等價定義定理1.1 若 x* 具有n位有效數(shù)字，則其相對誤差限滿足反之，若x*的相對誤差限 滿足則近似值x* 至少具有n位有效數(shù)字。例：為使 的相對誤差小于0.001%,至少應(yīng)取幾位有效數(shù)字？解：假設(shè) * 取到 n 位有效數(shù)字，則其相對誤差上限為要保證其相對誤差小于0.001%，只要保證其上限滿足已知 a1 = 3，則從以上不等式可解得 n 6 log6，即 n 6，應(yīng)取 * = 3.14159。3避免誤差危害的若干原則(一) 要避免相近兩數(shù)相減(二) 要防止大數(shù)“吃掉”小數(shù)(三) 注意簡化計算步驟

14、，減少運算次數(shù)(四) 要避免絕對值小的數(shù) 作除數(shù)(五) 設(shè)法控制誤差的傳播(一) 要避免相近兩數(shù)相減的值。例: 求當(dāng)x = 1000，y 的準(zhǔn)確值為0.01580. (1)直接相減(2) 若將原式改寫為則 y = 0.01581 幾種經(jīng)驗性避免方法：很小，(二) 要防止大數(shù)“吃掉”小數(shù)例：用單精度計算 的根。精確解為 算法1：利用求根公式在計算機(jī)內(nèi)，109存為0.11010，1存為0.1101。做加法時，兩加數(shù)的指數(shù)先向大指數(shù)對齊，再將浮點部分相加。即1 的指數(shù)部分須變?yōu)?010，則：1 = 0.0000000001 1010，取單精度時就成為： 109+1=0.100000001010+0.

15、00000000 1010=0.10000000 1010算法2：先解出 再利用注：求和時從小到大相加，可使和的誤差減小。例：在5位浮點十進(jìn)制計算機(jī)上，計算 y = 54 321 + 0.4 + 0.3 + 0.4解：若按從左到右的順序進(jìn)行計算，后三位在對階過程變?yōu)?后三個數(shù)都在對階過程中變?yōu)榱悖贸龊休^大誤差的結(jié)果 y = 54321。 但若按從右到左的順序進(jìn)行計算，后三位在對階過程變?yōu)?這種算法避免了大數(shù)“吃掉”小數(shù)！一般地，有如下原則 若干數(shù)相加，采用絕對值較小者先加的算法，結(jié)果的相對誤差限較小(三) 注意簡化計算步驟，減少運算次數(shù)，避免誤差積累例：計算多項式的值解：如果先計算各項然后

16、相加，則乘法次數(shù)=4+3+2+1=10，加法次數(shù)=4但如改用下式計算 則只需做4次乘法和4次加法。計算量大大減少！注：第二種方法稱為“秦九韶算法”（ Horner算法）通常，計算如下n次多項式的值如果先計算各項然后相加，則 乘法次數(shù) =n+(n-1)+2+1 = n(n+1)/2 加法次數(shù)= n若采用“秦九韶算法”，則 乘法次數(shù)= n 加法次數(shù)= n兩種算法的乘法運算次數(shù)隨n的變化見下表：n=2n=3n=4n=5方法1361015方法22345例：當(dāng)x接近于0時，的分子、分母都接近0，為避免絕對值小的數(shù)作除數(shù)，可將原式變形為(四) 要避免絕對值小的數(shù)作除數(shù)例：當(dāng)x很大時，的分母接近0，為避免絕

17、對值小的數(shù)作除數(shù)，可將原式變形為(五) 設(shè)法控制誤差的傳播許多算法具有遞推性。遞推法運算過程較規(guī)律，但多次遞推必然導(dǎo)致誤差的積累。例：求定積分 的值.解：直接積分可產(chǎn)生遞推公式若取初值可得遞推公式按公式就可以逐步算出What happened?!不穩(wěn)定的算法 ！這就是誤差傳播所引起的危害 ! 注意此公式精確成立，且由題設(shè)中的遞推公式（1）可看出， 的誤差擴(kuò)大了5倍后傳給 ，因而初值 的誤差對以后各步這就造成 的計算結(jié)果嚴(yán)重失真。計算結(jié)果的影響，隨著 的增大愈來愈嚴(yán)重。要怎么做才能解決這個問題呢?可求得I9 0.017，按改寫后的公式可逐次求得不妨設(shè)I9 I10，于是由將公式變?yōu)镮8 0.019 I7 0.021I6 0.024 I5 0.028I4 0.034 I3 0.043I2 0.058 I1 0.088I0 0.182 穩(wěn)定的算法 ！ 在我們今后的討論中，誤差將不可回避， 算法的穩(wěn)定性會是一個非常重要的話題。例：計算積分解：利用分部積分公式有從而有遞推公式又因為這說明由初始值E1的誤差在計算