高等教育數值分析教案

1、ch1、引 論1、數值分析及其特點1、數值分析及其主要內容數值分析也稱計算方法，主要研究用計算機求解數學問題的數值方法及理論，內容主要包括：(1)數值逼近插值與擬合、多項式逼近、有理逼近等(ch2ch3)；(2)數值積分與微分(ch4)；(3)數值代數求解方程(組)以及特征問題的數值方法(ch6ch9)；(4)常微分方程的數值解法(ch5)。2、數值分析的特點(1)首先要有可靠的理論分析，以確保算法在理論上的收斂性和數值穩(wěn)定性；(2)其次要對計算結果進行誤差估計，以確定其是否滿足精度；（見例3）(3)還要考慮算法的運行效率，即算法的計算量與存儲量。例如cooley和tukey1965年提出ff

2、t，n=32k，1000倍。例1、分析用cramer法則解一個階線性方程組的計算量。解：計算機的計算量主要取決于乘除法的次數。用cramer法則解一個階線性方程組需計算個階行列式，而用定義計算階行列式需次乘法，故總計共需。此外，還需次除法。當時，計算量約為次乘法。即使用每秒百億次乘法的計算機，也需計算3000多年才能完成。可見，cramer法則僅僅是理論上的，不是面向計算機的。2、數值分析中的誤差1、誤差的類型與來源(1)模型誤差；(2)觀測誤差；(3)截斷誤差(方法誤差) 模型的準確解與數值方法準確解之間的誤差；(4)舍入誤差實數形式的原始數據與有限字長的計算機數據之間的誤差。數值分析主要研

3、究截斷誤差與舍入誤差。例2、根據taylor展式計算(誤差小于0.01)。解： (截斷誤差) (舍入誤差)。2、誤差的基本概念(1)誤差與誤差限設為某量的精確值，為的一個近似值，則稱為的（絕對）誤差，為的相對誤差。用某種方法確定的誤差的某個上界稱為的誤差限，顯然，即，稱為的相對誤差限。誤差限取決于測量工具和計算方法。(2)函數值的計算誤差設，為的近似值，則(多元函數一階taylor展式)，。3、算法的數值穩(wěn)定性與病態(tài)問題1、算法的數值穩(wěn)定性例3、計算，并做誤差分析。解：。算法1：，結果見下表。又, 。算法2：，結果見下表。 n算法1算法2準確值01234560.18230.08850.0575

4、0.04580.02080.0958-0.31250.18230.08840.05800.04310.03440.02810.02620.18230.08840.05800.04310.03430.02850.0243誤差分析:算法1：，即在計算過程中誤差放大了倍。算法2：，即誤差縮小了倍。定義1：若某算法受初始誤差或計算過程中產生的舍入誤差的影響較小，則稱之是數值穩(wěn)定的，反之稱為不穩(wěn)定算法。2、病態(tài)問題例4、將方程，即改為攝動方程，即，其中。wilkinson用精密方法計算出其根為：。令，其根為，則當時，。顯然反映了初始數據的微小攝動對的影響程度即問題的條件數。因，故 1 4 6 8 101

5、9 20 （壞條件問題）定義2：若初始數據的微小誤差都會對最終的計算結果產生極大的影響，則稱這種問題為病態(tài)問題（壞條件問題），反之稱其為良態(tài)問題。例5、分別將線性方程組的右端向量和系數矩陣中數據做一個微小變化，具體數據如下：然后用精確方法求解，發(fā)現其解與原方程解相比發(fā)生了很大的變化。 這表明此方程組為病態(tài)方程組。4、算法的實現與常用的數學軟件用計算機實現數值分析中的算法通常有兩種途徑：(1)用fortran、c、vb、vc等自編程序；(2)借助于現成的數學工具軟件。目前常用的數學軟件約30余個，可分為通用與專用兩大類。專用系統(tǒng)主要是為解決數學中某個分支的特殊問題而設計的。1、 sas和spss

6、（統(tǒng)計分析）；2、 lindo、lingo和cplex（運籌與優(yōu)化計算）；3、 cayley和gap（群論研究）；4、 pari（數論研究）；5、 origin（科技繪圖與數據分析）；6、 delia（微分方程分析）等。通用系統(tǒng)中又可分為數值計算型與解析計算型。數值計算型：matlab、xmath、gauss、mlab和origin等。解析計算型：maple、mathematica、macsyma、axiom和reduce等。其中matlab、mathematica、maple與另一個面向大眾的普及型數學軟件mathcad并稱數學軟件中的“四大天王”。matlab意思為“矩陣實驗室”，是美國計

7、算機科學家cleve moler在70年代末開發(fā)出的以矩陣數值計算為主的數學軟件，如今已發(fā)展成為融科技計算、圖形可視化與程序語言為一體的功能強大的通用數學軟件。matlab最突出的特點是其帶有一系列的“工具包”，可廣泛應用于自動控制、信號處理、數據分析、通訊系統(tǒng)和動態(tài)仿真等領域。高版本的matlab也可進行符號計算，不過它的代數運算系統(tǒng)是從maple移植過來的。mathematica是美國物理學家stephen wolfram開發(fā)出的第一個將符號計算、數值計算和圖形顯示很好地結合在一起的數學軟件，在國內較為流行，擁有廣泛的用戶。mathcad是mathsoft公司在80年代開發(fā)的一個交互式數學

8、文字軟件，與matlab和mathematica不同的是，該軟件的市場定位是：向廣大教師、學生、工程技術人員提供一個兼?zhèn)湮淖?、數學和圖形處理能力的集成工作環(huán)境，而并不致力于復雜的數值計算與符號計算問題，具有面向大眾普及的特點。不過，新版mathcad的計算能力已遠遠超出了其早期的設計目標。maple是加拿大waterloo大學符號計算研究小組于80年代初開始研發(fā)，1985年才面世的計算機代數軟件，起初并不為人們所注意，但maple v release 2于1992年面世后，人們發(fā)現它是一個功能強大、界面友好的計算機代數系統(tǒng)。隨著版本的不斷更新，maple已日益得到廣泛的承認和歡迎，用戶越來越多

9、，聲譽越來越高，從1995年以后，maple一直在ieee的數學軟件評比中居符號計算軟件的第一名。目前，maple的最高版本為maple v release 11。第一章上機實驗目的：1、 熟悉maple中的定義函數、解方程、積分、循環(huán)語句和列表等命令；2、 通過具體問題的計算，加深對數值穩(wěn)定性和病態(tài)問題的理解。實驗內容：1、 設，由得算法一：；又，取，從而又得算法二：。分別用上述兩種算法計算，根據計算結果判定其數值穩(wěn)定性，并給予證明。2、將方程，即改為攝動方程，對不同的求解此方程，觀察對解的影響程度，判定此方程是否為病態(tài)方程。15、已知三角形面積，其中為弧度，且測量的誤差分別為，證明面積的誤

10、差滿足。證：根據零階多元taylor公式，令，則，因，從而，得，即。又，故，即。從而。ch2、插值法1、插值問題引例：礦井中某處的瓦斯?jié)舛扰c該處距地面的距離有關，現用儀器測得從地面到井下500米每隔50米的瓦斯?jié)舛葦祿?，根據這些數據完成下列工作：(1)尋找一個函數，要求從此函數中可近似求得從地面到井下500米之間任意一點處的瓦斯?jié)舛龋?2)估計井下600米處的瓦斯?jié)舛?。第一個問題可歸結為“已知函數在處的值，求函數在區(qū)間內其它點處的值”，這種問題適宜用插值方法解決。但對第二個問題不宜用插值方法，因為600米已超出所給數據范圍，用插值函數外推插值區(qū)間外的數據會產生較大的誤差。解決第二個問題的常用方

11、法是，根據地面到井下500處的數據求出瓦斯?jié)舛扰c地面到井下距離之間的函數關系，由求井下600米處的瓦斯?jié)舛取６x：設在中個點處的值為已知，現根據上述數據構造一個簡單函數，使，這種問題稱為插值問題。,分別稱為被插值函數、插值函數、插值節(jié)點和插值條件。若為多項式，則此問題稱為多項式插值或代數插值。定理1：在插值節(jié)點處，取給定值，且次數不高于的插值多項式是存在且唯一的。證：令，則根據插值條件有下列等式 （關于的階線性方程組），其系數行列式是范德蒙（vandermonde）行列式。根據克萊姆法則，此方程組存在唯一解，即存在且唯一。2、lagrange插值1、線性插值與拋物插值(1)線性插值，其中稱為線

12、性插值的基函數。(2)拋物插值設，分別令，即得， 故，其中稱為拋物插值的基函數。2、lagrange插值多項式定義：對個插值節(jié)點，令，則顯然。此時，滿足 稱之為langrange插值多項式，稱為lagrange插值的基函數。編程時宜用。3、插值公式的余項定理2：設上連續(xù)，在內可導，則以插值多項式逼近的截斷誤差（即余項）。例1、已知函數的數據如下，分別用線性插值和二次插值求的近似值。 0.5 0.6 0.7 -0.693147 -0.510826 -0.356675解：，3、逐次線性插值法對插值節(jié)點及對應的函數值，用表示一個非負整數序列，將個節(jié)點所確定的不高于次的插值多項式記為，則 ，即次插值多

13、項式可以用兩個次插值多項式通過線性插值獲得逐次線性插值。aitken算法：例2、根據下表近似計算在處的值。同理可得。類似可得。，故。4、均差與牛頓插值公式1、均差（差商）及其性質定義：稱為關于的一階均差； 稱為關于的二階均差；類似地可定義階均差 。定理：，即階均差可表示為的線性組合，從而階均差與節(jié)點的排列次序無關。證：當時，右左不妨假設成立，則 。2、牛頓插值公式設插值節(jié)點上的插值多項式為。分別令，則有；從而，故 牛頓插值公式。例3、 p340.400.550.650.800.901.05k=00.410750.578150.696750.888111.026521.25382k=11.116

14、001.186001.275731.384101.51533k=20.280000.358930.433480.52493k=30.197330.213000.22863k=40.031340.03126k=5-0.00012，。5、差分與等距節(jié)點插值公式1、差分及其性質定義：對等距節(jié)點，記。向前差分：；向后差分：；中心差分：；二階差分：；階差分：。不變算子與移位算子，即。由，得。(1)差分類似于微分的性質 (2)函數值與差分可相互線性表示(3)差分與均差的關系。證：時，。假設時成立，則。2、等距節(jié)點插值公式令，則，。代入牛頓插值公式得 。6、runge現象與高次插值的討論1、runge現象例

15、4、，節(jié)點，求插值多項式。解： 10次langrange插值多項式結果如下：2、討論(1)節(jié)點的增多固然能使插值函數在更多的地方與相等，但在兩個節(jié)點之間不一定能很好地逼近，有時差異很大，所以在實際中，高次插值（7次以上）很少使用；(2)可將分成若干小區(qū)間，在小區(qū)間內用低次（二次，三次）插值，即分段低次插值，如樣條函數插值。7、三次樣條插值分段低次插值：(1)分段線性插值(連續(xù))；(2)分段hermite插值(導數連續(xù))；(3)三次樣條插值(二階導數連續(xù))。1、三次樣條插值函數能夠逐段表示成三次多項式且二階導數連續(xù)(具有二階光滑度)的函數。定義：設，且在上為三次多項式，其中，則稱為上的三次樣條函

16、數。若對給定的，滿足，則稱為三次樣條插值函數。邊界條件：第一種邊界條件： 固支梁條件；第二種邊界條件： 簡支梁條件。特別地，時的樣條稱為自然樣條。2、三彎距方程與三次樣條的計算記彎距，因在上為三次多項式，故為一次多項式，可令lagrange線性插值。對積分兩次并代入，得其中。對求導得，從而可得，類似可得。利用得，其中。對第二種邊界條件，則關于彎距的矩陣方程為，其中。上述方程稱為三彎距方程，其系數矩陣為三對角，可用追趕法求解。求出代入即可得每個上的表達式。例5、 求6例中的三次樣條插值函數(自然樣條)。解：表達式如下： 3、三次樣條插值的存在唯一性定理：三彎矩方程中的系數矩陣是可逆的，即三次樣條

17、插值存在、唯一。證：設為的解，滿足，因，故。又有，即。若不可逆，則有非零解，由前所證，應有，矛盾，故可逆，存在唯一的。4、樣條函數的極性極性定理：對若為滿足的三次樣條插值函數，則，其中。證：，而，故，得，即，二階導數的范數最小。第二章上機實驗目的：3、 熟悉maple中的一般插值、樣條插值和序列等命令；4、 通過對具體數據做高次插值、樣條插值，加深對龍格現象以及樣條插值優(yōu)越性的理解與認識。實驗內容：對數據x1 2 5 6 7 8 10 13 17f(x)3.0 3.7 3.9 4.2 5.7 6.6 7.1 6.7 4.51、 做出折線圖，得出的大致形狀；2、 求出一般插值多項式（8次）；3、

18、 求出三次樣條插值多項式；4、 將與、與分別做圖對照，觀察高次插值的危害性以及樣條插值的優(yōu)越性。1矩形區(qū)域二元函數的分片線性插值已知平面上一矩形域內四個頂點頂點處的函數值分別為。分兩片的函數表達式如下：第一片(下三角形區(qū)域)：滿足，插值函數為：。第二片(上三角形區(qū)域)：滿足，插值函數為：。2矩形區(qū)域二元函數的雙線性插值雙線性插值函數的形式如下：，它是分片空間二次曲面。利用該函數在矩形的四個頂點（插值節(jié)點）的函數值，得到四個代數方程，可以確定四個待定系數。雙線性插值函數可按下方法計算。已知平面上一矩形域內四個頂點頂點處的函數值分別為，求函數，使其滿足條件：。令，則有。ch3、函數逼近與計算1、引

19、言1、引例某氣象儀器廠要在某儀器中設計一種專用計算芯片，以便于計算觀測中經常遇到的三角函數以及其它初等函數。設計要求在區(qū)間中變化時，近似函數在每一點的誤差都要小于某一指定的正數。(1)由于插值法的特點是在區(qū)間中的個節(jié)點處，插值函數與被插值函數無誤差，而在其它點處。對于，逼近的效果可能很好，也可能很差。在本問題中要求在區(qū)間中的每一點都要“很好”地逼近，應用一般的插值方法顯然是不可行的，龍格現象就是典型的例證。采用樣條插值固然可以在區(qū)間的每一點上滿足誤差要求。但由于樣條插值的計算比較復雜，需要求解一個大型的三對角方程組，在芯片中固化這些計算過程較為復雜。(2)可以采用泰勒展式解決本問題。將在特殊點

20、處做泰勒展開取其前項作為的近似，即但泰勒展式僅對附近的點效果較好，為了使得遠離的點的誤差也小于，只好將項數取得相當大，這大大增加了計算量，降低了計算速度。因此，從數值計算的角度來說，用泰勒展式做函數在區(qū)間上的近似計算是不合適的。(3)引例提出了一個新的問題，即能否找到一個近似函數，比如說，它仍然是一個次多項式，不一定要在某些點處與相等，但卻在區(qū)間中的每一點處都能“很好”地、“均勻”地逼近。2、逼近問題對，求一個多項式，使在某種衡量標準下最小。(1)一致逼近（均勻逼近）無窮范數：最小(2)平方逼近（均方逼近）歐氏范數：最小。3、維爾斯特拉斯定理定理：設，則對任意，有多項式，使在上一致成立。本定理

21、的證法很多，伯恩斯坦在1921年引入了一個多項式他證明了。伯恩斯坦多項式在自由外形設計中有較好的應用。但它有一個致命的缺點，就是收斂太慢。要提高逼近精度，只好增加多項式的次數，這在實際中是很不合算的。切比雪夫從另一個角度去研究逼近問題。他不讓多項式的次數趨于無窮，而是先把固定。對于，他提出在次多項式集合中，尋找一個多項式，使在上“最佳地逼近”。2、正交多項式一、正交多項式的概念及性質定義1：設區(qū)間上非負函數滿足(1)存在；(2)對非負連續(xù)函數，若，則在上，則稱為區(qū)間上的權函數。定義2：設，為上的權函數，則積分 稱為與在上的內積。定義3：設為上的次多項式，若滿足 ，則稱為上關于權函數的正交多項式

22、系。定理：上的正交多項式在內有個不同的實零點。二、legendre多項式1、定義，稱為legendre多項式。2、性質(1)正交性：。(2)奇偶性：，即為奇（偶）數時，為奇（偶）函數。(3)遞推公式：。三、chebyshev多項式1、定義稱為第一類chebyshev多項式。若記，即，則。2、性質(1)在上關于權正交，即。證：。(2)當為奇（偶）數時，為奇（偶）函數。證：。(3)遞推關系。證：，即。(4)是次多項式，其最高項系數為。證：由易知為次多項式。故，即最高項系數為。3、最佳平方逼近1、問題 對，在生成的子集中求一函數，使最小。2、求解記，令，得，即，也可改寫為下列矩陣形式 法方程。3、用

23、正交多項式做最佳平方逼近若取，因，由法方程可得，從而即為的最佳平方逼近多項式。若取，因，由法方程可得，從而即為的最佳平方逼近多項式。例1、用正交多項式求在上的三次最佳平方逼近多項式。解：用chebyshev多項式，故。用legendre多項式，故。4、函數按切比雪夫多項式展開定義：稱為切比雪夫級數或廣義傅立葉級數，其中 根據切比雪夫多項式的性質，切比雪夫級數的部分和可作為的近似最佳一致逼近多項式。例2、將在上展成切比雪夫級數。解：因為奇函數，從而也為奇函數，故從而注：的泰勒展式為 即切比雪夫展式可用較小的項數達到泰勒展式的精度，如對要達到10位有效數字，泰勒展式要25項，而切比雪夫展式僅要10

24、項。5、離散數據的擬合與最小二乘法1、離散數據的擬合問題引例1：礦井中某處的瓦斯?jié)舛扰c該處距地面的距離有關，現用儀器測得從地面到井下500米每隔50米的瓦斯?jié)舛葦祿?，根據這些數據完成下列工作：(1)尋找一個函數，要求從此函數中可近似求得從地面到井下500米之間任意一點處的瓦斯?jié)舛龋?2)估計井下600米處的瓦斯?jié)舛?。根據所學內容，分別給出解決上述問題的方法，并說明理由。對于第一個問題，可根據已有瓦斯?jié)舛葦祿?，求出其樣條插值函數，由即可較為準確地求得從地面到井下500米之間任意一點處的瓦斯?jié)舛取５珜Φ诙€問題不宜用插值方法，因為600米已超出所給數據范圍，用插值函數外推插值區(qū)間外的數據會產生較大

25、的誤差。解決第二個問題的常用方法是，根據地面到井下500米處的數據求出瓦斯?jié)舛扰c地面到井下距離之間的函數關系，由求井下600米處的瓦斯?jié)舛取Ｒ?：在某化學反應中，根據實驗測得生成物濃度與時間的關系如下表，求濃度與時間的對應函數關系，并據此求出反應速度曲線。時間x12345678910濃度y4.006.408.008.809.229.509.709.8610.0010.2011121314151610.3210.4210.5010.5510.5810.60顯然，從理論上講是客觀存在的，但在實際中僅由離散數據 是不可能得出的精確表達式的，只能尋找的一個近似表達式，這種問題稱為離散數據的曲線擬合問

26、題。曲線擬合需解決如下兩個問題：(1)線型的選擇；(2)中參數的計算。2、線型的選擇通常主要根據專業(yè)知識和散點圖確定的線型，常見的線型有：(1)線性函數：；(2)可化為線性函數的非線性函數，如(1)(3)非線性函數。3、計算線性擬合的最小二乘法做數據的散點圖，若近似為直線，則可用線性函數擬合。對于本問題通常采用最小二乘法，即所求參數使得在處的值與之差的平方和最小，將上式視為關于的二元函數，對分別關于求偏導并令其為零 ，即，解上方程組得，。例1、觀測物體的直線運動，得出以下數據，求運動方程。時間t 0 0.9 1.9 3.0 3.9 5.0距離s 0 10 30 50 80 110解：數據點的折

27、線圖所求運動方程為可用相關系數衡量數據線性化程度，本例中相關系數，這表明數據的線性相關性較好。擬合運動方程與數據點對照圖4、可線性化的非線性擬合例2、根據本節(jié)引例中的數據擬合出生成物濃度與時間的近似表達式。解：數據的散點圖(1) 用雙曲線型擬合令，則為線性函數。經計算，從而(2) 用指數線型擬合兩邊取對數，令，則為線性函數。經計算，從而兩種線型的誤差分析：令（均方誤差），分別將和代入計算得，顯然，此結果表明，線型(2)優(yōu)于線型(1)。作業(yè)：在某化學反應中，根據實驗所得分解物的濃度與時間關系如下，求濃度y與時間t的擬合曲線。(用指數線型擬合)時間x510152025303540455055濃度y

28、1.272.162.863.443.874.154.374.514.584.624.64擬合結果的評價準則：設數據點為，擬合函數為，則稱為擬合殘差。準則1：最大誤差準則，即最小。準則2：平均誤差準則，即最小。準則3：均方誤差準則，即最小。上述三準則與數據的大小、量綱有關，不具可比性。下面給出一種規(guī)范的誤差準則，其中顯然，越接近于1，擬合效果越好。7、fourier逼近與fft一、周期函數的最佳平方逼近設以為周期，則稱為的傅立葉級數，其中。稱為傅立葉級數的部分和，也稱為次三角多項式，下面討論三角多項式對周期函數的最佳平方逼近。1、連續(xù)情形設是以為周期的平方可積函數，則因= 為上的正交函數系，事實

29、上， 故根據用正交多項式作最佳平方逼近的法方程，在上的最佳平方逼近多項式存在且唯一，其系數即傅氏級數的部分和即為的最佳平方逼近三角多項式。2、離散情形 在上取的個觀測值，其中記可證，即共個向量構成正交系。 取正交系對進行最佳逼近，則其中二、快速fourier變換(fft)1、fourier變換fourier級數的推廣對任意函數，則稱為的fourier變換，稱為的fourier逆變換，與稱為fourier變換對。 常用的fourier變換有(1) 方脈沖， 函數 (2)2、離散的fourier變換對給定序列，分別稱為離散fourier變換與離散fourier逆變換。若給出在上的值，則的離散fou

30、rier變換為。采樣定理：若的頻率范圍為，則只有當采樣間隔時，才能正確恢復。此時，采樣頻率，稱為nyguist頻率。3、快速fourier變換(fft)的計算從的表達式中可以看出，計算一個需要次乘法、次加法，計算所有需要次乘法。當較大時，就很大，即常規(guī)離散fourier變換計算量太大。1965年cooley和tukey提出了一種快速fourier變換，其乘法次數僅為 ，大大降低了計算量。例如，當時，。第三章上機實驗目的：5、 熟悉maple中的擬合、求相關系數等命令；6、 通過對具體數據做可線性化的非線性擬合，了解曲線擬合的具體步驟。實驗內容：在某化學反應中，根據實驗所得分解物的濃度與時間關系

31、如下，求濃度y與時間x的擬合曲線。時間x510152025303540455055濃度y1.272.162.863.443.874.154.374.514.584.624.645、 做出數據的散點圖，根據的大致形狀，選擇相應的線型(用指數線型或雙曲線型擬合)；6、 將方程線性化，用maple相應命令求出此線性方程及相關系數；7、 將線性方程還原為原非線性方程，并將此方程的圖形與散點圖加以對照，觀察擬合效果。pade逼近（有理逼近）簡介借助函數的taylor級數來研究函數的性質，或直接用它的部分和逼近該函數，不僅是純數學領域中經常使用的手段，也是應用中賴以發(fā)展的方法之一。在數值計算領域中，用ta

32、ylor多項式來逼近一個函數并進而導致各種有效的數值方法巳司空見慣，并在很多情況下獲得了成功。但有時這種方法的應用顯露出某些缺陷。這些缺陷一般來說是由于函數的taylor級數的收斂速度較慢或其收斂范圍較狹。如果采用有理函數作為逼近工具則能常常獲得出人意外的好結果。例1、的taylor級數為其部分和為 用計算的近似值，收斂速度很慢。比如為了保證誤差不超過，就需要取。 若取有理函數對其進行逼近，則效果大不相同。例2、的taylor級數為當時，上述級數發(fā)散，但用有理函數逼近可擴大其逼近范圍。ch4、數值積分與數值微分1、引言1、對采用數值積分的原因的原函數不是初等函數或過于復雜，如等；為離散形式。2

33、、數值積分的基本思想機械求積 將表示為在若干點處值的線性組合即 ，、和分別稱為求積節(jié)點、求積系數和余項。稱為求積公式3、代數精度定義：若對于不高于次的多項式，余項，而總存在次多項式使，則稱求積公式代數精度為。4、插值型求積公式定義：對及，做插值，則，稱此求積公式為插值型求積公式。顯然，插值型求積公式的代數精度至少為。2、newton-cotes公式一、newton-cotes公式1、定義：對插值型求積公式，若取等距節(jié)點， ，則，此時稱求積公式為newton-cotes公式。當時， 梯形公式當時，稱為simpson公式當時，稱為simpson-3/8公式 2、余項 newton-cotes公式的

34、代數精度為3、收斂性與數值穩(wěn)定性 求積公式收斂的必要條件為有界； 對較大的，newton-cotes公式不穩(wěn)定，不宜采用。二、復化求積法將等分，在每個小區(qū)間上用低階newton-cotes公式求得該區(qū)間的積分值，則，此方法稱為復化求積法。1、復化梯形公式 2、復化simpson公式 例1、分別用復化梯形公式(n=8)和復化simpson公式(n=4)計算。解：x 0 1/8 2/8 3/8 4/8 5/8 6/8 7/8 1f(x) 1 0.9973978 0.9896158 0.9767267 0.9588510 0.9361556 0.9088516 0.8771925 0.8414709

35、3、復化公式的誤差復化公式余項為3、romberg加速收斂法1、加速收斂技巧在用序列逼近時，若能從產生出新序列，它比更快地收斂于，此即加速收斂技巧。例如用逼近時，類似地此加速收斂算法稱為richardson外推算法。2、romberg求積法將步長逐次減半，得序列，分析誤差可得新序列。 用逼近i的算法稱為romberg算法。4、高斯型求積公式1、高斯公式與高斯點定義：對插值型求積公式，若能選擇適當的使其具有次代數精度，則稱此求積公式為高斯公式，其節(jié)點稱為高斯點。2、高斯公式的構造定理：求積公式為高斯公式的充要條件是以為零點的多項式與任意不超過次的多項式均正交，即。證：必要性：設為次數不超過的多項

36、式，則不超過次，因為高斯公式，故，又，從而。充分性：對次數不超過的多項式，用除，商為，余式為，則次數均不超過，且，又，故推論：上次正交多項式的零點即為gauss點。證：因為正交多項式與比它次數低的任意多項式都正交，且上次正交多項式恰好有個不同的實零點，故得證。3、gauss-legendre公式對積分區(qū)間，取其上次legendre多項式的零點為節(jié)點，則稱為gauss-legendre求積公式。此時，令又故。兩點gauss公式：三點gauss公式：例、解：兩點gauss公式：兩點梯形公式：三點gauss公式：三點simpson公式：若積分區(qū)間為，可作代換，則4、高斯公式的穩(wěn)定性gauss公式中的

37、證：因為次多項式，為次，gauss公式準確成立，故。gauss公式是數值穩(wěn)定的。證：設的近似值，則為的近似值，ch5、常微分方程的數值解法1、基本概念與euler公式1、數值解法的必要性 不能給出解的解析表達式； 求封閉形式的解計算量太大。例如 2、數值解法的基本思想離散化對初值問題求出解在節(jié)點上值的近似值，其中。3、euler公式將在上積分，得，用數值積分法求。 （矩形公式），得 euler公式 （矩形公式），得 后退的euler公式 （梯形公式）得 梯形公式（隱形）4、改進的euler公式euler公式計算簡便，但精度差，梯形公式為隱式，計算較復雜，但精度較高，可將兩者結合。稱為改進的eu

38、ler公式，上式也可寫為 例1、求解初值問題 ()解：euler公式 改進的euler公式 x0.10.20.30.40.50.60.70.80.91.0euler1.1001.1921.2771.3581.4351.5091.5801.6501.7171.785euler改1.0961.1841.2661.3431.4161.4861.5531.6161.6781.738準確1.0951.1831.2651.3421.4141.4831.5491.6121.6731.7322、runge-kutta方法1、taylor級數方法與階對，有taylor級數將此級數截斷，并用代替，得階taylor

39、公式 顯然截斷誤差為定義：若某方法的截斷誤差為，則稱此方法精度為階。2、runge-kutta方法基本思想， 平均斜率取，即為euler公式；取，即為后退的euler公式；取，即為梯形公式。借用taylor級數法的思想，將中的(平均斜率)表示為在若干點處值的線性組合，通過選擇組合系數使公式達到一定的階。3、二階runge-kutta方法選為在某兩點處值的線性組合，即，其中，待定。將代入得將上式與二階taylor公式對比得（*）。根據euler公式， ，代入得，其中滿足（*）式，稱之為二階runge-kutta公式。特別地，當時， 改進的euler公式4、四階runge-kutta方法三階run

40、ge-kutta方法較少使用，仿二階runge-kutta方法，可得四階runge-kutta公式，經典的四階runge-kutta公式為特點：單步、自開始；精度高，誤差為，四階；數值穩(wěn)定；要計算四次函數值；對解的光滑性要求高。3、單步法的收斂性與穩(wěn)定性1、收斂性定義：若某數值解法對固定的，當時（此時），則稱此方法收斂。例2、對典型方程考察euler方法的收斂性。解：euler公式為，而，即， 故收斂。定理：若數值方法中的關于滿足lipschitz條件，則該方法收斂。2、穩(wěn)定性定義：若某方法在節(jié)點值上有大小為的攝動，而其后各節(jié)點上的誤差無效不超過，則稱此方法是穩(wěn)定的。例3、對方程，考察eule

41、r公式和后退的euler公式的穩(wěn)定性。解：對應的euler公式為，若在上有攝動值，而它使產生的攝動值為，則，顯然，即時，euler公式穩(wěn)定，稱之為條件穩(wěn)定。后退的euler公式為， 即后退的euler公式無條件穩(wěn)定。ch6、解非線性方程的數值方法1、二分法零點定理：設，且，則在內至少有一根。令為的中點，若，則內有根，否則內有根。類似地進行步之后，設有根區(qū)間為，則，可取為的近似根，顯然誤差。特點：2、迭代法1、迭代格式對非線性方程，給定一個初值，按照某種方法產生一個序列，使得，且。例如，將改寫為，令(picard迭代)2、收斂性與誤差估計定理1：若對任意，有(壓縮映射)；存在正數，使對任意，有(

42、lipschitz條件)，則對任意，迭代序列收斂于的唯一根，且有誤差估計式證：令，由lipschitz條件，又若，則即為的根，否則由零點定理，在內至少有一根，故在上至少有一根。（存在性）若有兩個根，即從而有矛盾，故。（唯一性）由于，故 即 。（收斂性）而得令，則有3、收斂速度與收斂階定義：設迭代公式收斂于的根，如迭代誤差滿足，則稱為p階收斂，特別地p=1，2時稱為線性、平方收斂。定理2：對迭代公式，若，為的根，則迭代在附近是p階收斂的。（局部收斂）3、牛頓法（切線法）1、迭代格式設為根的近似值，由taylor公式若，則略去最后一項后作為新的近似值，即 稱之為牛頓公式2、牛頓法的幾何意義 如圖，

43、作曲線在處的切線，令，即為此切線在軸上的截距。3、牛頓法的收斂性設為的單根，即，此時， ，故在的某鄰域內，從而，由定理1，牛頓法對附近的初值收斂，即局部收斂，再由定理2知，牛頓法為二階收斂的。例1、用牛頓法求的一個根。解：例2、應用牛頓法于方程，導出求立方根的迭代公式，并討論其收斂性。解：，因，即有下界，又，即單調下降，故收斂。ch7、解線性方程組的直接方法1、引言對線性方程組 (1)令，則(1)可記為 (2)求解的數值方法有如下兩類：1、直接法 2、迭代法存貯量大； 存貯量??；計算時間短； 計算時間長；程序復雜； 程序簡單；適用于a為低階矩。 適用于a為高階稀疏矩陣。2、 gauss消去法1

44、、消元過程記為 (3)若，令，用乘第一個方程后加到第個方程上，則(3)變?yōu)?記為一般地，對若，令，類似地可消去從第到第個方程中的，直至將方程化為上三角方程。 記為2、回代過程3、矩陣的lu分解矩陣a的第一行乘后加到第行的變換，相當于用矩陣左乘矩陣a一般地，第步所用變換對應于矩陣gauss消去法可用矩陣描述如下： ，即，記上三角，下三角，則 矩陣的lu分解。定理1：當方陣a的順序主子式時，a可唯一地分解為單位下三角陣l與上三角陣u之積，即a=lu。設，則對，即，只要經兩次回代即可解出方程。3、gauss列主元消去法1、gauss消去法中的稱為主元，從理論上講僅需即可，但從數值計算的角度來看，其絕

45、對值越小，引起的舍入誤差就越大，反之舍入誤差就小。為了減小舍入誤差，提高算法的數值穩(wěn)定性，可在每步消元過程中選主元，具體有：總體選主元(每步系數矩陣中絕對值最大者)按列選主元(在第k步中，從中選絕對值最大者)2、計算過程只須在gauss消去法中加入選主元過程。在中選出絕對值最大者，然后放在(k,k)位置（交換行）。4、追趕法與cholesky分解1、追趕法對三對角方程 首先由第一個方程解出，令，則，代入第二個方程得，即，令，有，類似地可推出下列公式 其中 ，將代入最后一個方程，令，則，代入即可依次求出。上述求解過程可分為兩個部分：依次確定，稱之為追的過程；依相反次序確定，稱之為趕的過程。即2、

46、對稱正定陣的分解定理2：設a對稱，且a的各階順序主子式均不為零，則a可唯一地分解為，其中l(wèi)為單位下三角陣，d為對角陣。定理3：設a對稱正定，則a可唯一地分解為，其中l(wèi)為對角元大于零的下三角陣。證：由定理2，又a正定，有中的，故其中為下三角。（cholesky分解）設a對稱正定，則可化為，即，經回代即可解。計算機解法：a為一般方陣時，用lu分解（gauss消去法）；a對稱正定時，用cholesky分解。5、向量和矩陣的范數一、向量的范數1、定義：設或，為定義在上的一個實值函數，若滿足非負性：，當且僅當；齊次性：對，有；三角不等式：對，有；則稱為上的一個向量范數。2、常用向量范數對，有范數 ；1-

47、范數 ；2-范數 ；p-范數 定理4：中的一切范數都是等價的，即對任意兩種范數，總有正數m和m，使3、向量序列的收斂性定義：設為中的向量序列，并記，若，則稱收斂于，記為定理5：，為任一范數。二、矩陣的范數1、定義：若矩陣的某個實值函數滿足； 相容性；則稱為上的一個矩陣范數。2、常用矩陣范數 行范數； 列范數 2-范數； f-范數3、譜半徑定義：設a的特征值為，稱為a的譜半徑。定理6：a的譜半徑不超過a的范數，即。證：設為a的任一特征值，為相應的特征向量，即，則 相容性，故，即。定理7：若，則可逆，且。證：若不可逆，即，有非零解亦即有，使， ，矛盾，故可逆。，得6、誤差分析和矩陣的條件數1、右端

48、向量誤差對解的影響設的右端向量有誤差，相應的解為，則，又，故2、系數矩陣誤差對解的影響設的系數矩陣有誤差，相應的解為，則，由定理7，若，則可逆，且，故3、矩陣的條件數定義：設a非奇異，則稱為的條件數。；若a為正交陣，則。 常用條件數：；4、病態(tài)方程組 條件數刻畫了方程組的解對原始數據誤差的敏感程度。當條件數很大時，或的擾動所引起的的誤差可能很大，此時稱為病態(tài)的或壞條件的，對應的方程組稱為病態(tài)方程組，反之稱為良態(tài)的或好條件的。例、，ch8、解線性方程組的迭代法1、基本概念1、迭代法對線性方程組，給定初始向量，按某種方法生成向量序列 ，且，使。2、迭代法的一般格式設，其中可逆，則。令，則，故可建立迭代公式。若收斂，即，則，即為的解。3、誤差向量令 (誤差向量)，顯然，即，迭代收斂，即。2、jacobi迭代與gauss-seidel迭代設的主對角元均不為零，將分解為，其中為對角陣，和分別為的除主對角元以外的下三角和上三角部分，即，1、jacobi迭代由，即，得迭代公式，或。2、gauss-seidel迭代由，即，得迭代公式, 或 3、迭代法的收斂性例1、取，分別用jacobi迭代與gauss-seidel迭代解下列方程組。； ； ； 解：方程精確解為，jacobi和g-s迭代均發(fā)散。方程精確解為，