第2章解線性方程組的直接法

第2章解線性方程組的直接法2.1GAUSS消元法2.2改進(jìn)平方根法2.3追趕法2.4LU分解法2.5直接法的穩(wěn)定性分析2.1GAUSS消元法特點(diǎn):矩陣的初等變換(是對(duì)中學(xué)代數(shù)中加減消元法、代入消元法的綜合利用和升華)2.1.1基本GAUSS消元法問(wèn)題：求解n階線性方程組Ax=b的方法?解法：消元法(分2步)1.消元(1)目的：得到系數(shù)矩陣為上三角矩陣的方程組(2)方法：加減消元法(3)過(guò)程：利用aii消aji(j=i+1,…,n)，其余對(duì)應(yīng)元素和bi作相應(yīng)變動(dòng)。2.1GAUSS消元法(4)計(jì)算公式推導(dǎo)：假設(shè)已進(jìn)行了i-1輪消元，方程組Ax=b已變成：2.1GAUSS消元法相應(yīng)要計(jì)算和變動(dòng)的矩陣元素為：2.1GAUSS消元法2.回代求解xi：2.1GAUSS消元法2.1.2基本GAUSS消元法的計(jì)算實(shí)例[例1-例4]用GAUSS消元法求解方程組2.1GAUSS消元法2.1.3GAUSS列主元法方法要點(diǎn)在GAUSS消元法基礎(chǔ)上，第i輪消元前，先選出列主元素，并將列主元素所在行與第i行進(jìn)行交換。[列主元素]在GAUSS消元法第i輪消元前，中絕對(duì)值最大的元素稱為列主元素，記為：2.1GAUSS消元法[求解過(guò)程]1.消元（找列主元素

交換

消元）(1)確定列主元素所在行(記行號(hào)=p)。確定的方法--按列主元素的定義。若列主元素近似為0，則表示選不出。(2)將列主元素所在的第p行與第i行元素交換(3)消元2.1GAUSS消元法2.回代求解xi：2.1GAUSS消元法2.1.4GAUSS列主元法的計(jì)算量1.消元過(guò)程的計(jì)算量(1)找列主元素：比較和絕對(duì)值計(jì)算(2)交換2行的次數(shù)(3)除法的次數(shù)：(4)乘法和減法的次數(shù)：2.回代過(guò)程的計(jì)算量除法次數(shù)乘法、加法、減法的次數(shù)：2.1GAUSS消元法2.1.5GAUSS列主元法的計(jì)算步驟1.輸入2.輸出3.計(jì)算：(1)消元，(2)回代2.1.6GAUSS列主元法的計(jì)算實(shí)例[例]求解方程組2.1GAUSS消元法2.1.7GAUSS全主元素法[全主元素]在GAUSS消元法的第i輪消元前，從子矩陣Ain中按絕對(duì)值最大的原則所找到的元素稱為全主元素。[全主元消元法]找全主元素

作列和行的交換

消元

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

;

令Ux=y，有

Ly=b

,可解得：再由Ux=y可解得：2.4LU分解法2.4.3LU分解法的計(jì)算步驟1.輸入;2.輸出;3.計(jì)算過(guò)程：作LU分解，計(jì)算yi，計(jì)算xi2.4.4LU分解法的計(jì)算實(shí)例[例1]對(duì)矩陣A作LU分解[例2]用LU分解法求線性方程組2.2改進(jìn)平方根法適用情況：系數(shù)矩陣A非奇異、是正定矩陣2.2.1正定矩陣的定義和性質(zhì)正定矩陣的定義設(shè)A∈Rn×n，若有：

(1)AT=A,(2)對(duì)任意x∈Rn(x≠0)都有xTAx>0則稱A是正定對(duì)稱矩陣。正定矩陣的性質(zhì)(簡(jiǎn)記:二個(gè)“正定”，三個(gè)“>0”)A的各階主子矩陣也是正定對(duì)稱矩陣(正定)A非奇異，且A-1也是正定對(duì)稱矩陣(正定)A的對(duì)角線元素aii>0(>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=LDLT2.2改進(jìn)平方根法[計(jì)算順序的推導(dǎo)]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í)例[例]求解下面線性方程組2.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ì)角線和兩條次對(duì)角線元素不為0的n階矩陣。2.2.9追趕法1、追趕法的三角分解(Crout分解)[定理]若A是三對(duì)角矩陣，且滿足：

(1)|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ì)算舉例[例]求解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，定義一個(gè)實(shí)值函數(shù)，記為，當(dāng)滿足下列3個(gè)條件時(shí)：則稱是向量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直接法的穩(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)定性分析2.4直接法的穩(wěn)定性分析條件數(shù)不能反映算法的穩(wěn)定性：[例1]分別用GAUSS消元法、列主元素法和改進(jìn)平方根法解下面線性方程組。2.4直接法的穩(wěn)定性分析2.4.2消元法的穩(wěn)定性分析GAUSS全主元素法消元