算法与程序设计课件

§1-1誤差的種類及來源模型誤差:在建立數學模型過程中,要將複雜的現象抽象歸結為數學模型,往往要忽略一些次要因素的影響,而對問題作一些簡化,因此和實際問題有一定的區別.測試誤差:絕大多數程式都有數據輸入,輸入數據中的不少數據是用儀器儀錶測得的,測量值和準確值之間的差稱為測試誤差.

舍入誤差:在數值計算過程中還會遇到無窮小數,因電腦受到機器字長的限制,它所能表示的數據只能有一定的有限位數,如按四捨五入規則取有限位數,由此引起的誤差如：

哪個更精確呢?定義3：定義4：

絕對誤差限相對誤差限往往未知代替相對誤差代替相對誤差限因此定義5：如：有4位有效數字有6位有效數字只有4位有效數字定理1：但如果利用遞推公式2、高效性編寫程式時，儘量選用高效率的演算法，即選用複雜性低的演算法。例2已知

都是n維向量，I是n階單位矩陣，求

編寫程式時，若計算過程為：

S1：計算，將結果存入二維數組A中S2：計算，將結果存入二維數組B中S3：計算AB,存入二維數組C中S4：計算Cx該演算法的複雜性為次乘法（S3的計算量）1、熟悉MATLAB軟體環境

2、選擇適當的演算法計算多項式：的值。本章主要闡明了誤差理論的基本概念，誤差在近似值運算中的傳播規律及其估算方法，以及數值穩定性的概念，使學生瞭解．1.誤差的來源以及舍入誤差、截斷誤差的定義；2.絕對誤差、相對誤差、誤差限和有效數字的定義和相互關係；3.函數計算的誤差估計和提高計算穩定性的一般規律．

基本要求定義行乘數且二、回代過程所以三、高斯消去法的計算量乘法次數：除法次數：於是Gauss消去法的乘除法運算總的次數為全部回代過程需作乘除法的總次數為四、高斯消去演算法輸入：輸出步驟S1對k=1,2,…,n-1做S11~S12S11S12S2S3S4回代後得到與精確解相比,該結果顯然是錯誤的究其原因,在求行乘數時用了很小的數0.0001作除數如果在求解時將1,2行交換,即回代後得到二、列主元素法具體步驟為：

如此至多經過n-1步,就得到與之同解的上三角形方程組的增廣矩陣,再用回代過程即可得方程組的解.

S1對k=1,2,…,n-1做S11~S14S11S12S13S14三、列主元素演算法目標輸入輸出步驟S3S4S2第k次消元相當於用矩陣左乘，其中因此從而故即二、矩陣的三角分解

定義1設A為n階方陣，若存在下三角方陣L和上三角方陣U，使得A=LU，則稱方陣A有三角分解或LU分解。特別，若L為單位下三角方陣，則稱它為杜利特爾(Doolittle)分解；若U為單位上三角方陣，則稱它為克勞特(Crout)分解.

定理1

則存在n階單位下三角方陣L和上三角方陣U，使得A=LU，即A有杜利特爾分解.且因此同樣,由因此可以推導出三、直接三角分解法對於線性方程組係數矩陣非奇異,經過Doolittle分解後線性方程組可化為下麵兩個三角形方程組由得到再由解的方程組的解：直接三角分解的Doolittle法可以用以下過程表示:該過程稱為緊湊格式的Doolittle法例1.用緊湊格式的Doolittle法解方程組L所以因此由回代過程得：有一類方程組,形式為:其中二、解三對角線性方程組的追趕法定理1：滿足引理1條件的三對角方陣A有如下形式的唯一的克勞特分解。=PQ其中得得顯然並且由於例1.求下列向量的各種常用範數解:定義2.二、矩陣範數根據向量的常用範數可以得到常用的矩陣範數例2.求矩陣A的各種常用範數解:由於特徵方程為定義3.顯然定理1.三、誤差分析即有所以又因為可得因此此式表明,由常數項產生的誤差,最多可將解的相對誤差放大倍如果假設可知且因此定義4.顯然因此根據定義4的定義有實驗專案二：編寫程式用追趕法求解線性方程組提示：演算法設計參考教材P33;

運算結果參考教材P34;基本要求1、使學生理解Gauss消去法的原理及實現條件；

2、掌握用Gauss消去法和列主元消去法消去過程計算公式和回代過程計算公式；

3、掌握用Doolittle分解法分解矩陣及求方程組的解；

4、能直接運用Doolittle法的緊湊格式進行的分解；

5、會使用追趕法和平方根法（Cholesky分解）解三對角方程組和對稱正定方程組．

輸入步驟輸出S1S2輸入“Methodfailed”；停機.定理1：迭代法求根演算法：目標輸入步驟輸出S1S2輸入“Methodfailed”；停機.三、Newton法的幾何意義四、Newton法的收斂性五、Newton迭代演算法輸入步驟輸出S1S2輸入“Methodfailed”；停機.目標例用Newton迭代法求取解：設則所以Newton法的迭代公式為：實驗專案一：編寫程式觀察兩種迭代公式產生的解的特點提示：演算法設計參考教材P59.基本要求1、掌握區間對分法的使用；2、掌握逐次迭代方法及原理；3、掌握收斂階的概念；4、掌握牛頓迭代法的迭代公。可得向量序列，其中如果，那麼就是原方程組的解.這種求線性方程組的解的方法稱為簡單迭代法.或稱為雅可比（Jacobi）迭代法.任給初始向量，由迭代公式二、Jacobi迭代的矩陣形式若令則方程組Ax=b化為等價方程組於是迭代公式為：為簡單迭代法的矩陣形式二、Seidel迭代的矩陣形式於是迭代公式為：為賽德爾迭代法的矩陣形式三、賽德爾迭代演算法S11~S13輸入輸出步驟S1S11S12S13S2輸出“N次迭代後不收斂”；停機.二、鬆弛法的矩陣形式在修正量前乘上一個參數，即在實際計算中，鬆弛法常採用以下形式：三、鬆弛法演算法S11~S13輸入輸出步驟S1S11S12S13S2輸出“N次迭代後不收斂”；停機.實驗專案一：分別用簡單迭代法和賽德爾迭代法解線性方程組比較兩種方法的收斂速度.提示：演算法設計可參考教材P72、P74簡單迭代法迭代公式賽德爾迭代法迭代公式基本要求1、熟練掌握向量和矩陣範數的定義及其性質；2、掌握條件數的定義，並能用條件數估計線性方程組接解的誤差和病態特徵；3、熟練掌握解線性方程組的Jacobi迭代法和G－S迭代法的構造和收斂性判別方法；4、熟練掌握解線性方程組的鬆弛法的構造和收斂性判別方法；5、掌握迭代法的收斂階的概念；

於是由假設所以只要就有這說明序列收斂於A的與相對應的特徵向量，當k充分大時所以即兩相鄰迭代向量分量的比值收斂於這種由已知非零向量及矩陣A的乘冪構造向量序列以計算A的按模最大特徵值及相應特徵向量的方法稱為乘冪法，簡稱為冪法.

通常把迭代向量歸一化，即把的最大分量化為1.因此通常採用的冪法迭代公式為：由此可得：而所以從而

上式說明歸一化向量序列收斂於按模最大的特徵值所對應的特徵向量.因此，當k充分大時，就是特徵向量的近似值.同理所以故因此，當k充分大時，就是按模最大的特徵值的近似值，即.二、冪法演算法求的按模最大特徵值及相應的特徵向量目標輸入輸出步驟S1S2S3S4S41S42S43S44S45S46S47S5輸出“Maximumnumberofiterationsexceeded”;停機.§5-2原點平移法冪法的收斂速度主要取決於比值,若比值越小則收斂越快;當接近於1時,則收斂很慢,這時採用原點平移法可加快冪法的收斂速度.設A的特徵值為應用冪法,則有速收斂的方法稱為原點平移法

在實際計算中，p的選取或憑藉於經驗或通過多次試算而得到。但對於一些簡單情形，p可以估計的.例如當矩陣即任給初始向量由迭代公式得到向量序列,可改寫成：具體計算時，可以將A進行三角分解.於是,逆冪法的迭代步驟如下：二、冪法演算法求的按模最小特徵值及相應的特徵向量目標輸入輸出步驟S1S2S3S4S51S52S53S5實驗專案一：用逆冪法求矩陣接近2.93的特徵值及相應的特徵向量提示：演算法設計可參考教材P98的演算法基本要求1、熟悉特徵值和特徵向量的定義；2、熟悉冪法求主特徵值的計算過程；3、瞭解原點平移法的思想；4、瞭解逆冪法的思路.則滿足插值條件的插值多項式存在且唯一.定理1二、代數插值多項式的存在唯一性二、拋物線插值令三、n階Lagrange插值可令（3）式(3)稱為n次Lagrange代數插值多項式四、Lagrange插值演算法輸入輸出步驟五、Lagrange插值多項式的截斷誤差二、二次Newton插值三、n次Newton插值稱定義1.顯然依此類推)()()()()(33221100xfxxfxxfxxfxxfxkk三階差商二階差商一階差商差商的計算方法(差商表):零階差商性質2差商具有對稱性,即任意調換節點的次序,差商的值不變如定義2

稱推論n次牛頓插值公式的截斷誤差（餘項）為例1作一不高於4階的Newton插值多項式，使得解：作（傳統）差商表00111223344301100.50-0.5-0.5-0.50

根據Newton插值多項式定義有：c0c1c2c3c4四、Newton基本插值公式的演算法設計輸入輸出步驟五、帶多重節點的Newton插值多項式係數計算若選作插值多項式節點的函數值和導數值以至高階導數值都已知，這些節點稱為重節點.若只知函數值和導數值稱為二重節點，簡稱重節點.例2作一不高於4階的Newton插值多項式，使得解：仿例1作改進差商表：0011112224220203-1.553.251-23由此知該四階Newton插值多項式為實驗專案一：已知函數f(x)在若干點的函數值：X0

0.3

0.6

0.9

1.2F(x)1.0000060.98506740.94107080.87036320.7766992選用適當插值法求f(0.5),f(0.45),f(0.75)和f(1)的近似值.基本要求1、掌握插值多項式存在唯一性條件；2、熟練掌握Lagrange插值多項式及其餘項運算式，3、能熟練使用均差表和差分表構造Newton插值公式

稱式(1)或式(2)為數值積分公式.二、構造數值積分公式的基本方法利用插值多項式來構造數值求積公式,具體步驟如下:三、代數精確度則稱該求積公式具有m次的代數精確度如果求積公式0xyabAB二、梯形公式幾何意義三、梯形公式的截斷誤差四、複合梯形公式所謂複合方法，然後在每個社區間上使用低階求積公式，最後將每個社區間上的積分的近似值相加為複合梯形公式的近似值為複合梯形公式的截斷誤差五、複合梯形公式演算法目標輸入輸出步驟S1S2S3S4二、Simpson公式幾何意義三、Simpson公式的截斷誤差0xyabAB四、複合Simpson公式為複合Simpson公式的截斷誤差五、複合Simpson公式演算法目標輸入輸出步驟S1S2S3這種等距節點的插值型求積公式(2)稱為牛頓—柯特斯公式在Newton-Cotes公式中,n=1,2時的公式是梯形公式和Simpson公式1.梯形公式Cotes係數為於是2.Simpson