計(jì)算方法-61Gauss消去法

2023/2/51第六章線性方程組的解法計(jì)算方法

6.1Gauss消去法第六章線性方程組的解法6.3對稱矩陣直接三角分解法

6.2直接三角分解法

6.5誤差分析

6.4追趕法(Thomas法)

6.6迭代法2

本章要點(diǎn)線性方程組的解法:直接解法和迭代法主要?dú)w結(jié)為三角形方程組的求解包括一般線性方程組的Gauss消去法、Gauss列主元法、對稱正定方程組的平方根法、三對角方程組的追趕法等及雅可比迭代和塞德爾迭代法2023/2/53實(shí)際問題中的線性方程組分類：按系數(shù)矩陣中零元素的個(gè)數(shù)：稠密線性方程組稀疏線性方程組按未知量的個(gè)數(shù)：高階線性方程組低階線性方程組(如1000)按系數(shù)矩陣的形狀對稱正定方程組三角形方程組三對角占優(yōu)方程組2023/2/54(80%)解線性方程組的兩類方法：直接法:經(jīng)過有限次運(yùn)算后可求得方程組精確解的方法(不計(jì)舍入誤差)迭代法：從解的某個(gè)近似值出發(fā)，通過構(gòu)造一個(gè)無窮序列去逼近精確解的方法。（一般有限步內(nèi)得不到精確解）直接法概述直接法是將原方程組化為一個(gè)或若干個(gè)三角形方程組的方法，共有若干種．對于線性方程組其中系數(shù)矩陣未知量向量常數(shù)項(xiàng)------------(1)2023/2/56根據(jù)Cramer(克萊姆)法則,若若用初等變換法求解,則對其增廣矩陣作行初等變換:經(jīng)過n-1次2023/2/57同解即以上求解線性方程組的方法稱為Gauss消去法則都是三角形方程組上述方法稱為直接三角形分解法------------(2)2023/2/582023/2/59其解為:回代方向2023/2/5106.1Gauss消去法一、消元與回代計(jì)算對線性方程組對其增廣矩陣施行行初等變換:2023/2/511定義行乘數(shù)2023/2/512且2023/2/513定義行乘數(shù)2023/2/5142023/2/5152023/2/516以上討論告訴我們，對具有上三角形系數(shù)矩陣的方程組求解極為方便。當(dāng)然,若方程組的系數(shù)矩陣為下三角形,則求解也很方便。于是對于一般形式的方程組，我們總設(shè)法把它化為系數(shù)矩陣呈上(或下)三角形的方程組來求解。為了達(dá)到目的，可利用消去法進(jìn)行?，F(xiàn)舉例如下:解方程組①②③2023/2/517(6―6)作②-①消去②中的x1，作③-①×4消去③中的x1，則方程組化為①②③對方程組(6―6′)作③-②×，得到三角形方程組①②③2023/2/518(6―6′)(6―6")

從方程組(6―6“)的方程③解出x3,將所得的結(jié)果代入方程②求出x2,再把x3、x2同時(shí)代入方程①解出x1。這樣可求出方程組的解為

上述求解方程組的方法就是高斯(Gauss)消去法。從式(6―6)到(6―6")的過程稱為消元過程而由(6―6")求出x3、x2、x1的過程稱為回代過程。因此用高斯消去法求解性方程組要經(jīng)過消元和回代兩個(gè)過程。2023/2/5192023/2/5二、Gauss消去法的運(yùn)算量計(jì)算機(jī)作乘除運(yùn)算所耗時(shí)間要遠(yuǎn)遠(yuǎn)多于加減運(yùn)算且在一個(gè)算法中，加減運(yùn)算和乘除運(yùn)算次數(shù)大體相當(dāng)故在衡量一個(gè)算法的運(yùn)算量時(shí)只需統(tǒng)計(jì)乘除的運(yùn)算次數(shù)乘法次數(shù)：除法次數(shù)：20全部回代過程需作乘除法的總次數(shù)為于是Gauss消去法的乘除法運(yùn)算總的次數(shù)為2023/2/521Gauss消去法乘除法約為2700次而如果用Cramer法則的乘除法運(yùn)算次數(shù)約為或用行列式定義用行列式性質(zhì)2023/2/522例1.用Gauss消去法解線性方程組(用3位十進(jìn)制浮點(diǎn)數(shù)計(jì)算）解:本方程組的精度較高的解為用Gauss消去法求解(用3位十進(jìn)制浮點(diǎn)數(shù)計(jì)算)Gauss列主元消去法的引入2023/2/523三、Gauss列主元消去法9999回代后得到與精確解相比,該結(jié)果誤差較大究其原因,在求行乘數(shù)時(shí)用了很小的數(shù)0.0001作除數(shù)主元2023/2/524前述順序消去法是按序通過用a11,a(1)22,…,a(n-2)n-1(a(k-1)kk≠0)作為除數(shù)來達(dá)到消元目的的。在實(shí)際計(jì)算時(shí),由于舍入誤差的影響,計(jì)算結(jié)果會改變很大,甚至于完全失真。2023/2/525如果在求解時(shí)將1,2行交換,即0.9999回代后得到該結(jié)果與精確解近似程度很高2023/2/526例2.解線性方程組(用8位十進(jìn)制尾數(shù)的浮點(diǎn)數(shù)計(jì)算)解:這個(gè)方程組和例1一樣,若用Gauss消去法計(jì)算會有小數(shù)作除數(shù)的現(xiàn)象,若采用換行的技巧,則可避免2023/2/527絕對值最大不需換行2023/2/528經(jīng)過回代后可得方程組的準(zhǔn)確解為2023/2/529例2所用的方法是在Gauss消去法的基礎(chǔ)上,利用換行避免小主元作除數(shù),該方法稱為Gauss列主元消去法2023/2/530

高斯列主元素消去法是順序消去法的一種改進(jìn)。它的基本思想是在逐次消元時(shí)總是選系數(shù)子矩陣的第一列元素中絕對值最大的元素(稱之為主元)做除數(shù),按順序消去法的步驟消元。除了列主元消去法，求解線性方程組常用的還有全主元消去法。四、Gauss-Jordan消去法

前面所述的消去法均要進(jìn)行兩個(gè)過程,即消元過程和回代過程。但對消元過程稍加改變可以把線性方程組的系數(shù)矩陣化為對角陣

2023/2/531

此時(shí)求解就不要回代了。這