線性方程組的矩陣求解算法

1、線性方程組的矩陣求解算法摘要線性方程組的矩陣求解算法,只需在約當(dāng)消元法的基礎(chǔ)上,再對方程組的增廣矩陣的行最簡形進(jìn)行行(列)刪除和增加行,交換行等運(yùn)算即可得到方程組的解,并且這種方法既可求解有唯一解的方程組.因而算法簡單,易于實(shí)現(xiàn).關(guān)鍵詞 線性方程組;解向量;解法;約當(dāng)消元法1 矩陣求解算法設(shè)有線性方程組,其增廣矩陣,算法的步驟如下:第一步:利用約當(dāng)消元法,把增廣矩陣化為行最簡形,設(shè)行最簡形為.若則方程組無解;否則設(shè)并執(zhí)行以下步驟;第二步:刪除中的所有零行和每一行第一個(gè)非零元素(這個(gè)非零元素一定是1)所在的列,得到矩陣并記錄每行的第一個(gè)非零元所在的列標(biāo),放在一維數(shù)組中,如第行的第一個(gè)非零元在第列

2、,則;第三步:構(gòu)造矩陣,其中 第四步:對矩陣中的行作交換運(yùn)算:把中的第行(即從第行開始直到第一行)依次與其下一行交換,使之成為第行,交換運(yùn)算結(jié)果后的矩陣記為,則中的前個(gè)維列向量即為方程組的一個(gè)基礎(chǔ)解系,最后一列向量即為方程組的一個(gè)特解;第五步:寫出方程組的通解.2 算法證明先證一個(gè)特殊情形,增廣矩陣的行最簡形矩陣的左上角為一階的單位矩陣,即第行的第一個(gè)非零元的列標(biāo)為,即,所以設(shè)為則 由上述算法可得為由于,故從得到時(shí),中的行不需交換位置,即那么矩陣的增廣矩陣的線性方程組為令 , , 可以驗(yàn)證是方程組(1)所對應(yīng)的齊次線性方程組的解,是方程組(1)的特解,又的后個(gè)分量構(gòu)成的向量組,線性無關(guān),把它擴(kuò)

3、充成維向量組后也線性無關(guān),所以線性無關(guān),又因?yàn)?所以方程組(1)的基礎(chǔ)解系中有個(gè)向量,因此即為方程組(1)的基礎(chǔ)解系,特殊情形得證.對于行最簡形矩陣為一般情形時(shí),可以通過若干次列交換把它變形為上述特殊情形,但是,列交換將會導(dǎo)致最后結(jié)果中對應(yīng)未知數(shù)的次序混亂,即在進(jìn)行第列與第列的交換后,最后結(jié)果中與次序也就被交換了,因此,在這過程中,必須記住所進(jìn)行的一切列交換,以便在最后結(jié)果中恢復(fù),但若使用本矩陣求解算法,則可避免上述麻煩,為了敘述方便,還是只證一種特殊情形.設(shè)即則, 現(xiàn)在證明的前個(gè)列向量是所對應(yīng)的方程的基礎(chǔ)解系,的最后一列是該方程組的特解,把矩陣的第2列依次與第3列,第4列,第列交換,得到矩陣

4、設(shè)矩陣所對應(yīng)的方程組的解向量為,所對應(yīng)的方程組的解向量為,則有即若是所對應(yīng)的方程組的解向量,則是矩陣所對應(yīng)的方程組的解向量,而由上述所證的特殊情形,所對應(yīng)的方程組的基礎(chǔ)解系和一個(gè)特解分別為,由此可得矩陣所對應(yīng)的方程組的基礎(chǔ)解系和特解為, , , , 而,即為的列向量組,這一情形得證若為起它任意情形,只要重復(fù)上上述證明過程,即可得到證明.3 舉例 例 設(shè)有線性方程組求其通解. 解方程組的增廣矩陣為的行最簡形矩陣為劃掉中的最后兩個(gè)零行和每行的第一個(gè)非零元所在的第一列,第三列,第四列,得矩陣,并且構(gòu)造矩陣由于,所以應(yīng)把中第3行依次與其后的行交換,使之成為第4行,然后因?yàn)?所以把中第2行依次與其后的行

5、交換,使之成為第3行最后因,故第1行不需與任何行交換,這樣變得到矩陣,所以方程組的通解為4.算法分析事實(shí)上,本算法是約當(dāng)消元法的推廣,因?yàn)槿魰r(shí),最簡形矩陣的前列為階單位矩陣,所以由得時(shí),為矩陣,且為的最后一列所構(gòu)造成的矩陣,由構(gòu)造時(shí),不斷增加行,由得到時(shí),不需交換行,即,因而方程組的解向量為,這也是約當(dāng)消元法的結(jié)果也就是說約當(dāng)消元法是本算法當(dāng)時(shí)的特殊情形,由于本算法的所有加法和乘法都在把增廣矩陣化為行最簡形矩陣的著一過程中,所以有以下結(jié)論:1) 算法的計(jì)算量與約當(dāng)消元法的計(jì)算量相等;2) 算法所需的存貯空間略多于約當(dāng)消元法所需的存貯空間;3) 在求方程組的通解時(shí),其穩(wěn)定性與精度和約當(dāng)消元法的完

6、全一致.另外,由于本算法從輸入方程組到輸出通解(或唯一解),中間的所有運(yùn)算都是對矩陣進(jìn)行的,所以算法簡單,容易在計(jì)算機(jī)上實(shí)現(xiàn),當(dāng)然,由于本算法包含約當(dāng)消元法,因而它除了有與約當(dāng)消元法相同的缺點(diǎn)以外,它還有一個(gè)缺點(diǎn):有時(shí)需要移動(dòng)大量的元素,特別是當(dāng)未知數(shù)的個(gè)數(shù)與方程的個(gè)數(shù)都很大時(shí),元素的移動(dòng)量可能更大.總之,本算法在約當(dāng)消元法的基礎(chǔ)上,不需增加乘法和加法運(yùn)算,即可得到方程組的通解,因而本算法有一定的適用價(jià)值.參考文獻(xiàn)1徐士良 計(jì)算機(jī)常用算法M 北京: 清華大學(xué)出版社,1995.122同濟(jì)大學(xué) 線性代數(shù)M 北京: 高等教育出版社, 2002.13鄧建中等 計(jì)算方法M 西安: 西安交通大學(xué)出版社,2001.84劉仲奎 高