《計(jì)算方法》課件：Ch3_1 解線性方程組的直接解法

1、第三章 線性方程組數(shù)值解法 本章內(nèi)容 3.1 解線性方程組的直接解法 3.2 向量范數(shù)和矩陣范數(shù) 3.3 迭代法問題的提出 由Cramer法則，當(dāng) 時(shí)，方程有唯一的一組解： 因而Cramer法則是計(jì)算方程組的一種直接解法，但由于計(jì)算量為n+1個(gè)n階行列式，而每個(gè)n階行列式按展開成代數(shù)余子式計(jì)算，需要n!次乘法，故總的計(jì)算量為(n+1)!次乘法，過大！ 事實(shí)上，若取n=20，則 ,在每秒可作 次運(yùn)算的計(jì)算機(jī)上也需162年，因而需考慮其他解法。 線性方程組的數(shù)值解法分類 線性方程組的數(shù)值解法分為兩大類，分別針對(duì)實(shí)際問題中遇到的兩類方程組的系數(shù)矩陣提出： 低階稠密（n100）； 大型稀疏（n較大零元

2、較多）、直接法從給定方程組的A和b出發(fā)，經(jīng)過有限 次代數(shù)運(yùn)算，在沒有舍入誤差的情況下，可獲得 方程組的精確解；然而舍入誤差是不可避免的， 因而最終獲得近似解；適用于低階稠密矩陣 特點(diǎn)：運(yùn)算量小，解比較準(zhǔn)確可靠；但占用機(jī)器的存 儲(chǔ)單元較多，程序結(jié)構(gòu)復(fù)雜；、迭代法將Ax=b改寫成某種迭代格式，從方程 組解向量的某個(gè)近似值出發(fā)，經(jīng)過迭代遞推計(jì)算， 得到一組解向量序列；若解向量序列收斂，其極 限向量即是方程組的準(zhǔn)確解；然而迭代步驟只能 進(jìn)行有限步，因而也只能獲得近似解； 適用于大型稀疏矩陣 特點(diǎn)：程序結(jié)構(gòu)較為簡(jiǎn)單，但收斂性與收斂速度始終 是一個(gè)重要課題。 3.1 解線性方程組的直接解法本節(jié)內(nèi)容提要Ga

3、uss消去法 三角方程組的求解、 Gauss消去法及其運(yùn)算量、矩陣解釋 、條件 、追趕法 、列主元Gauss消去法矩陣的三角分解解法 Doolittle分解 、改進(jìn)平方根法 、選列主元的三角分解法 一、Gauss消去法 1、三角方程組的求解回代2、Gauss消去法 由于三角方程組可以通過回代求解，因而可將一般方程組作同解變形轉(zhuǎn)化為三角方程組來求解，由于 與增廣矩陣 一一對(duì)應(yīng)，因而這一過程等價(jià)于將增廣矩陣經(jīng)過一系列的初等行變換化為上三角矩陣。 逐個(gè)求解 的過程稱為回代過程。 其運(yùn)算量為： 次乘除運(yùn)算。 解： 例： Gauss法 消元 回代一般，Gauss消去法的消元過程由 步完成： 主元消元因子

4、 主元消元因子Gauss消去法的回代過程：3、Gauss消去法的運(yùn)算量 消元： 回代： 4、Gauss消去法的矩陣解釋 ，而初等行變換相當(dāng)于左乘相應(yīng)的初等方陣，因而有： 稱為Gauss變換 矩陣或消元矩陣 （見補(bǔ)證） 于是 L 單位下三角；U 上三角；因而Gauss消去法實(shí)際是在尋求A的LU分解中的U矩陣，一旦給出了U，即得與方程組 同解的上三角方程組 ，為此直接考慮對(duì)A進(jìn)行LU分解，由此可得直接三角分解法。 Gauss消去法的變形 補(bǔ)證：5、Gauss消去法的條件 Gauss消去法的消元過程對(duì)各階順序主子式而言，相當(dāng)于將某一行的倍數(shù)加到另一行上去，而由行列式的性質(zhì)，這種變換不改變行列式的值，

5、因而有：注： 特別地，對(duì)嚴(yán)格對(duì)角占優(yōu)矩陣以及對(duì)稱正定矩陣，總能 作Gauss消去法。嚴(yán)格對(duì)角占優(yōu)矩陣： 對(duì)稱正定矩陣：各階順序主子式大于0； 按行 6、追趕法 針對(duì)三對(duì)角矩陣的Gauss消去法 （1）定義 三對(duì)角陣：（2）條件若三對(duì)角陣滿足對(duì)角占優(yōu)條件： 則Gauss消去法能進(jìn)行到底，且每步消元只需消去一個(gè)元素。（3）追趕法同解上三角方程組回代得： 計(jì)算量：3(n-1)+2(n-1)+1=5n-4次乘除。“追”“趕”例： 注：存儲(chǔ)時(shí)只需4個(gè)一維數(shù)組分別存放： 解： 7、列主元Gauss消去法 為控制舍入誤差 Gauss消去法要求 ，然后以 作除，因而當(dāng) 較小時(shí)，舍入誤差影響較大，會(huì)導(dǎo)致精度不高

6、，甚至消元過程失敗，主元素消去法即是為克服這一問題提出的，目的是保證主元不太?。?例： 解： 用Gauss消去法，取5位有效數(shù)字 列主元消去法 可見列主元Gauss消去法是避開小數(shù)作除的Gauss消去法，是它的變形。 設(shè)已完成k-1步消元，則在進(jìn)行第k步消元時(shí)，增加選列主元的工序，即：從 中選出絕對(duì)值最大者作為第k步的主元； 設(shè) 則交換第 行與第k行，然后對(duì)交換過行后的矩陣進(jìn)行第k步消元。 注： 除選列主元以外，也可考慮行主元及全主元，但由于需 記錄交換信息，以便整理解，并且工作量大（全主元）， 故列主元更實(shí)用； 嚴(yán)格對(duì)角占優(yōu)陣及對(duì)稱正定陣是穩(wěn)定的（Gauss消去）， 無需選列主元； 矩陣解釋

7、：PA=LU （P為排列陣之積）二、矩陣的三角分解解法 由Gauss消去法的矩陣解釋，相當(dāng)于 單位下三角 上三角 因而Gauss消去法的兩個(gè)過程： 消元 回代 事實(shí)上，我們可以從矩陣乘積的角度，直接計(jì)算出L、U，從而可以避開消元過程。1、LU分解的緊湊格式 Doolittle分解（i）（j）步驟： 定出U的第一行，L的第一列； 上述計(jì)算公式右端均為已知數(shù)，故而可算出U的第k行，L的第k列；Doolittle分解 假設(shè)已定出了U的前k-1行，L的前k-1列， 則可定出U的第k行，L的第k列； 解下三角形方程： 比較 的計(jì)算公式，改記可知，對(duì) 作LU分解，其中b作相應(yīng)運(yùn)算，則分解后的最后一列元素即是y。 解上三角形方程： 注：LU分解的緊湊格式即有：具體計(jì)算時(shí)，可依次算出U的第一行，L的第一列； U的第二行，L的第二列； ； U的第k行，L的第k列； ；例： 解：注： Doolittle分解求解方程組的計(jì)算量與Gauss消去法基 本相當(dāng)，但它可以將系數(shù)矩陣的計(jì)算與右端項(xiàng)的計(jì)算 分開，這使我們?cè)谟?jì)算一組同系數(shù)矩陣方程組時(shí)變得 特別方便。如：法一：法二：例： 解：(法二)注： 并非所有非奇異矩陣均有LU分解；反例： 事實(shí)上，特別，對(duì)稱正定矩陣由于各階順序主子式均大于0，故而必存在LU分解。2、改進(jìn)平方根法 針對(duì)對(duì)稱正定矩陣步驟 因而，對(duì)于對(duì)稱正定矩陣，L矩陣中