解線性方程組的直接法

1、第2章 解線性方程組的直接法,2.1 GAUSS消元法2.2 改進平方根法2.3 追趕法2.4 LU分解法2.5 直接法的穩(wěn)定性分析,2.1 GAUSS消元法,特點: 矩陣的初等變換 (是對中學(xué)代數(shù)中加減消元法、代入消元法的綜合利用和升華)2.1.1 基本GAUSS消元法問題：求解n階線性方程組Ax=b的方法 ?解法：消元法(分2步)1. 消元(1) 目的：得到系數(shù)矩陣為上三角矩陣的方程組(2) 方法：

2、加減消元法(3) 過程：利用aii消aji(j=i+1,…,n)，其余對應(yīng)元素和bi作相應(yīng)變動。,2.1 GAUSS消元法,(4) 計算公式推導(dǎo)：假設(shè)已進行了i-1輪消元，方程組Ax=b已變成：,,,2.1 GAUSS消元法,相應(yīng)要計算和變動的矩陣元素為：,,,,2.1 GAUSS消元法,2. 回代求解xi：,2.1 GAUSS消元法,2.1.2 基本GAUSS消元法的計算實例[例1-例4] 用GAUSS消元法求解方程

3、組,2.1 GAUSS消元法,2.1.3 GAUSS列主元法方法要點在GAUSS消元法基礎(chǔ)上，第i輪消元前，先選出列主元素，并將列主元素所在行與第i行進行交換。[列主元素]在GAUSS消元法第i輪消元前， 中絕對值最大的元素稱為列主元素，記為：,2.1 GAUSS消元法,[求解過程]1.消元（找列主元素?交換?消元）(1) 確定列主元素所在行(記行號=p)。確定的方

4、法--按列主元素的定義。若列主元素近似為0，則表示選不出。(2) 將列主元素所在的第p行與第i行元素交換(3) 消元,2.1 GAUSS消元法,2. 回代求解xi：,2.1 GAUSS消元法,2.1.4 GAUSS列主元法的計算量1. 消元過程的計算量(1) 找列主元素：比較和絕對值計算(2) 交換2行的次數(shù)(3) 除法的次數(shù)：(4) 乘法和減法的次數(shù)：2. 回代過程的計算量除法次數(shù)乘法、加法、減法的次

5、數(shù)：,2.1 GAUSS消元法,2.1.5 GAUSS列主元法的計算步驟1. 輸入2. 輸出3. 計算：(1)消元，(2)回代2.1.6 GAUSS列主元法的計算實例[例] 求解方程組,2.1 GAUSS消元法,2.1.7 GAUSS全主元素法[全主元素] 在GAUSS消元法的第i輪消元前，從子矩陣Ain中按絕對值最大的原則所找到的元素稱為全主元素。[全主元消元法]找全主元素 ? 作列和行的交換 ? 消

6、元 ? 回代,2.4 LU分解法,從GAUSS消元法可知，系數(shù)矩陣A消元后，形成了一個上三角矩陣和一個下三角矩陣，因此可重點研究系數(shù)矩陣A的分解方法。LU分解法：2.4.1 LU分解法的算法推導(dǎo)對線性方程組Ax=b，令A(yù)=LU，其中,2.4 LU分解法,依據(jù)的原理：矩陣的乘積法則,2.4 LU分解法,LU分解公式(計算順序)的推導(dǎo)：,2.4 LU分解法,2.4.2 LU分解法的求解公式由 Ax=b 及 A=LU，有

7、LUx=b ; 令Ux=y， 有 Ly=b , 可解得：再由 Ux=y 可解得：,2.4 LU分解法,2.4.3 LU分解法的計算步驟1.輸入; 2.輸出; 3.計算過程：作LU分解，計算yi，計算xi2.4.4 LU分解法的計算實例[例1] 對矩陣A作LU分解[例2] 用LU分解法求線性方程組,2.2 改進平方根法,適用情況：系數(shù)矩陣A非奇異、是正定矩陣2.2.1

8、 正定矩陣的定義和性質(zhì)正定矩陣的定義設(shè)A∈Rn×n，若有： (1) AT=A, (2) 對任意x∈Rn(x≠0)都有xTAx>0則稱A是正定對稱矩陣。正定矩陣的性質(zhì) (簡記: 二個“正定”，三個“>0”)A的各階主子矩陣也是正定對稱矩陣 (正定)A非奇異，且A-1也是正定對稱矩陣 (正定)A的對角線元素aii>0

9、 (>0)A的所有特征值>0 (>0)A的各階主子式>0 (>0),2.2 改進平方根法,2.2.2 改進平方根法的算式推導(dǎo)方法要點: 對矩陣A作A=LDLT分解，再求解算法組成: 1. 三角分解：A=LDLT,2.2 改進平方根法,[計算順序的推導(dǎo)]

10、,2.2 改進平方根法,[計算公式的推導(dǎo)],2.2 改進平方根法,[計算公式的推導(dǎo)],2.2 改進平方根法,2. 求解: (1)令 Ux=y， 則有Ly=b，可得：(2)令 LTx=z， 則有Dz=y，可得：(3)再解LTx=z，可得：,2.2 改進平方根法,2.2.3 改進平方根法的計算步驟P21—22頁2.2.4 改進平方根法的計算實例[例] 求解下面線性方程組,2

11、.2 改進平方根法,2.2.5 改進平方根法的計算量三角分解的計算量Q1 + 求解Q2 = n3/62.2.6 變帶寬壓縮存儲改進平方根法,2.2.9 追趕法,適用情況：系數(shù)矩陣A是三對角矩陣[三對角矩陣]只有主對角線和兩條次對角線元素不為0的n階矩陣。,2.2.9 追趕法,1、追趕法的三角分解(Crout分解)[定理] 若A是三對角矩陣，且滿足： (1)

12、|b1|>|c1|，|bn|>|cn| (2) |bi|≥|ai|+|ci|, i=2,3,…,n-1則A非奇異，且A可作Crout分解。,2.2.9 追趕法,[三角分解(Crout分解)],2.2.9 追趕法,按矩陣的乘積法則有：,2.2.9 追趕法,2、方程組Ax=d的求解：(1) 令Qx=y，于是有：Py=d，則(2)由Qx=y有：,2.2.9 追趕法,3、追趕法的計算舉例[例] 求

13、解,2.3 范數(shù)簡介,引入范數(shù)的目的是什么？穩(wěn)定性分析什么是穩(wěn)定性分析？擾動對解的影響（或誤差的傳遞和放大問題）,2.3 范數(shù)簡介,穩(wěn)定性分析的內(nèi)容：給系數(shù)矩陣A一個小擾動(A+△A)，討論其對解的影響；給右端項b一個小擾動(b+△b)，討論其對解的影響。穩(wěn)定性分析的手段和方法：范數(shù)：一個與向量、矩陣相關(guān)但又能比較大小的數(shù)學(xué)量。范數(shù)符號：,2.3 范數(shù)簡介,2.3.1 向量范數(shù)的定義對任意向量x∈Rn，定義

14、一個實值函數(shù)，記為 ，當(dāng)滿足下列3個條件時：則稱 是向量x的范數(shù)。,2.3 范數(shù)簡介,2.3.2 常用向量范數(shù),2.3 范數(shù)簡介,2.3.3 向量范數(shù)的性質(zhì),2.3 范數(shù)簡介,,2.3 范數(shù)簡介,2.3.4 矩陣范數(shù)的定義討論Ax與x之間的關(guān)系,2.3 范數(shù)簡介,矩陣范數(shù)的定義,2.5 直接法的穩(wěn)定性分析,2.3.5 矩陣范數(shù)的性質(zhì),2.5 直接法的穩(wěn)定性分析,常用的矩陣范數(shù),2.5

15、直接法的穩(wěn)定性分析,矩陣的譜半徑及定理,2.5 直接法的穩(wěn)定性分析,,2.5 直接法的穩(wěn)定性分析,,2.4 直接法的穩(wěn)定性分析,2.4.1 常見穩(wěn)定性分析數(shù)據(jù)的測試誤差、舍入誤差（擾動）等對解均有影響。[示例],2.4 直接法的穩(wěn)定性分析,1. 右端項擾動對解的影響,2.4 直接法的穩(wěn)定性分析,2. 系數(shù)矩陣A的擾動對解的影響,2.4 直接法的穩(wěn)定性分析,3. 當(dāng)系數(shù)矩陣A和右端項b均有擾動時,2.4 直接法的穩(wěn)定性

16、分析,,2.4 直接法的穩(wěn)定性分析,條件數(shù)不能反映算法的穩(wěn)定性：[例1] 分別用GAUSS消元法、列主元素法和改進平方根法解下面線性方程組。,2.4 直接法的穩(wěn)定性分析,2.4.2 消元法的穩(wěn)定性分析GAUSS全主元素法消元和回代均穩(wěn)定GAUSS列主元素法消元穩(wěn)定、回代不太穩(wěn)定GAUSS消元法消元和回代都不太穩(wěn)定,2.4 直接法的穩(wěn)定性分析,2.4.3 三角分解法的穩(wěn)定性分析LU分解法LLT和LDLT法