解線(xiàn)性方程組的直接法

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

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

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

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

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

6、元 ? 回代,2.4 LU分解法,從GAUSS消元法可知，系數(shù)矩陣A消元后，形成了一個(gè)上三角矩陣和一個(gè)下三角矩陣，因此可重點(diǎn)研究系數(shù)矩陣A的分解方法。LU分解法：2.4.1 LU分解法的算法推導(dǎo)對(duì)線(xiàn)性方程組Ax=b，令A(yù)=LU，其中,2.4 LU分解法,依據(jù)的原理：矩陣的乘積法則,2.4 LU分解法,LU分解公式(計(jì)算順序)的推導(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分解法的計(jì)算步驟1.輸入; 2.輸出; 3.計(jì)算過(guò)程：作LU分解，計(jì)算yi，計(jì)算xi2.4.4 LU分解法的計(jì)算實(shí)例[例1] 對(duì)矩陣A作LU分解[例2] 用LU分解法求線(xiàn)性方程組,2.2 改進(jìn)平方根法,適用情況：系數(shù)矩陣A非奇異、是正定矩陣2.2.1

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

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

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

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

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

14、一個(gè)實(shí)值函數(shù)，記為 ，當(dāng)滿(mǎn)足下列3個(gè)條件時(shí)：則稱(chēng) 是向量x的范數(shù)。,2.3 范數(shù)簡(jiǎn)介,2.3.2 常用向量范數(shù),2.3 范數(shù)簡(jiǎn)介,2.3.3 向量范數(shù)的性質(zhì),2.3 范數(shù)簡(jiǎn)介,,2.3 范數(shù)簡(jiǎn)介,2.3.4 矩陣范數(shù)的定義討論Ax與x之間的關(guān)系,2.3 范數(shù)簡(jiǎn)介,矩陣范數(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 常見(jiàn)穩(wěn)定性分析數(shù)據(jù)的測(cè)試誤差、舍入誤差（擾動(dòng)）等對(duì)解均有影響。[示例],2.4 直接法的穩(wěn)定性分析,1. 右端項(xiàng)擾動(dòng)對(duì)解的影響,2.4 直接法的穩(wěn)定性分析,2. 系數(shù)矩陣A的擾動(dòng)對(duì)解的影響,2.4 直接法的穩(wěn)定性分析,3. 當(dāng)系數(shù)矩陣A和右端項(xiàng)b均有擾動(dòng)時(shí),2.4 直接法的穩(wěn)定性

16、分析,,2.4 直接法的穩(wěn)定性分析,條件數(shù)不能反映算法的穩(wěn)定性：[例1] 分別用GAUSS消元法、列主元素法和改進(jìn)平方根法解下面線(xiàn)性方程組。,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法