線性方程組的數(shù)值解法與比較論文

1、目 錄1 引言12 線性方程組的相關(guān)概念13 討論線性方程組的數(shù)值解法23.1 高斯消元法解線性方程組23.1.1 高斯順序消元法23.1.2 高斯列主元素消元法63.2 矩陣三角分解法解線性方程組93.2.1 直接三角分解法93.2.2 追趕法124 總結(jié)16參考文獻(xiàn)17致謝18線性方程組的數(shù)值解法與比較摘要:本文給出了線性方程組數(shù)值解法的幾種直接求解方法,探討這些方法的主要思想,具體解法以及它們各自的特點(diǎn),針對(duì)幾種解法對(duì)于不同條件下的線性方程組的求解,進(jìn)行了一定的分析,并對(duì)其加以比較,以此來(lái)促進(jìn)對(duì)線性方程組數(shù)值解法的理解.關(guān)鍵詞:線性方程組;高斯消元法;直接三角分法;追趕法 the num

2、erical solution and compared of linear equationsabstract: this paper gives several direct solving methods of linear equations nume- rically, probing into the main ideas, the specific method and their respective conclu- sions.according to several solutions to different conditions of linear equations

3、of the solution, this paper analyzes and compares in order to promote the understanding of linear equations numerically.key word: linear equations; gaussian elimination; direct triangle points method; chase-after method 1 引言線性方程組是最簡(jiǎn)單也是最重要的一類代數(shù)方程組.在實(shí)際生活中,存在大量的解線性方程組的問(wèn)題,很多數(shù)值方法到最后都會(huì)涉及到線性方程組的求解問(wèn)題.它的數(shù)值解法

4、不僅在實(shí)際問(wèn)題中起到重要的作用,而且在計(jì)算數(shù)學(xué)中更是占有重要的地位.針對(duì)我們所學(xué)習(xí)的現(xiàn)有的中小型線性方程組,直接法就可以直接簡(jiǎn)明的對(duì)其進(jìn)行求解.我們所運(yùn)用的求解線性方程組的直接法,通常包括高斯消元法中的高斯順序消元法與高斯列主消元法,以及矩陣三角分解法中的直接三角分解法與追趕法.本文通過(guò)探討這幾種求解方法的思想,解法與結(jié)論,對(duì)其加以分析并進(jìn)行了相應(yīng)的比較. 2 線性方程組的相關(guān)概念一 線性方程組的一般形式含個(gè)方程,個(gè)未知量的線性方程組的一般形式為: 其中為未知量, 和為常數(shù); 稱為型線性方程組如果,則稱方程組為齊次線性方程組如果存在,則稱方程組為非齊次線性方程組例:型線性方程組的一般形式為:

5、其中每一個(gè)方程都表示平面上一條直線,一個(gè)型線性方程組中兩直線在平面上的位置有下列三種情況:(1)兩直線相交于一點(diǎn),則交點(diǎn)就是方程組的唯一解； (2)平行,則該方程組無(wú)解；(3)重合,則直線上任何一個(gè)點(diǎn)都是方程組的解. 例:型齊次線性方程組的一般形式為: 其中每一個(gè)方程都表示一個(gè)以向量為法向量,過(guò)點(diǎn)的平面,其解是一個(gè)與平行.,均正交的向量.(1)若,不共面,則方程組只有零解；(2)若,共面但不共線,則垂直于 ,的向量均是解,這些解彼此平行；(3)若,共線,則以為法向量的平面是所有向量,都是解.即解向量組成一個(gè)平面. 定義1.1: 設(shè)有型線性方程組(i)和型線性方程組(ii),如果(i)和(ii)

6、的解向量集合相等,則稱(i)和(ii)為等價(jià)的線性方程組. 齊次線性方程組可以看成是非齊次線性方程組常數(shù)列均0的情形,因而對(duì)于非齊次線性方程適用的結(jié)論對(duì)齊次方程也是適用的. 3 討論線性方程組的數(shù)值解法設(shè)有n元線性方程組 或 其中 設(shè)系行列式,則方程組有唯一解. 直接法解線性方程組:如果不計(jì)運(yùn)算過(guò)程的舍入誤差,經(jīng)過(guò)有限次運(yùn)算后可得到方程組的精確解的方法. 3.1 高斯消元法解線性方程組 3.1.1 高斯順序消元法寫(xiě)出方程組的增廣矩陣,并記, 若,則施行第一次消元:對(duì)計(jì)算 原增廣矩陣被變換成: 將這一過(guò)程繼續(xù)下去.第步的計(jì)算過(guò)程為若,則施行第一次消元: 對(duì) 計(jì)算 原增廣矩陣被變換成 若所有的,則

7、經(jīng)過(guò)n-1次消元得到: 以為增廣矩陣的上三角線性方程組 與原方程組是同解方程組.回代過(guò)程就是由方程組的最后一個(gè)方程解出,然后通過(guò)逐步回代,依次求 . 具體算法為 例1 用順序gauss消去法解以下線性方程組 解:用增廣矩陣表示法求解: 消元過(guò)程 回代過(guò)程 同解方程組為 程序?yàn)?#include #include #define n 4 /* n 為方程組系數(shù)矩陣的階數(shù) */int gauss(float ann,float bn) int i,j,k,flag=1; float t; for(i=0;in-1;i+) if(aii=0) flag=0; break; else for(j=i+

8、1;jn;j+) /*消元過(guò)程開(kāi)始*/ t=-aji/aii; bj=bj+t*bi; for(k=i;kn;k+) ajk=ajk+t*aik; return(flag); void zg_matric(float ann,float bn) /* 輸出增廣矩陣 */ int i,j; for(i=0;in;i+) for(j=0;j=0;i-) xi=bi; for(j=i+1;jn;j+) xi=xi-aij*xj; xi=xi/aii; for(i=0;in;i+) /* 輸出方程組的解 */ printf( x%d=%11.7fn,i+1,xi); ;運(yùn)行結(jié)果截圖為: 3.1.2 高

9、斯列主元素消元法引例 考慮用順序gauss消去法求解以下方程組,在運(yùn)算中每次運(yùn)算保留到小數(shù)點(diǎn)后四位. 消元后的同解方程組為 回代求解得 與準(zhǔn)確解 相差很大.對(duì)此做改進(jìn)所得結(jié)果為:對(duì)調(diào)過(guò)程 消元后的同解方程組為 回代求解得 與準(zhǔn)確解 相差很大.由此,我們會(huì)發(fā)現(xiàn)對(duì)于這種用絕對(duì)值很小的數(shù)作除數(shù),舍入的誤差會(huì)增大,同時(shí)會(huì)嚴(yán)重影響計(jì)算結(jié)果的精度.因此,我們要選擇絕對(duì)值最大的元素做主元素,可以避免消元時(shí)消元系數(shù)絕對(duì)值大于1(即避免放大舍入誤差).也就是說(shuō),我們可以來(lái)用高斯列主消元法更精確的解此類線性方程組.高斯列主元消元法的主要過(guò)程如下: 1 消元過(guò)程 對(duì) 選主元 找, 使 若 , 則計(jì)算停止,若,則換行

10、 , 消元 對(duì) 計(jì)算 2 回代過(guò)程若, 則計(jì)算停止, ; 否則 對(duì) 例2 解方程組 四位有效數(shù)字精確解為 解:(1)順序高斯消元法 四位有效數(shù)字精確解為 由上,高斯順序消元法求解表明:所得結(jié)果會(huì)與我們的精確解相差較大,為避免這一誤差,我們引進(jìn)了高斯列主元消元法.(2)列主元素法 四位有效數(shù)字精確解為 由上,當(dāng)增加選主元后,所得結(jié)果會(huì)與精確解相差較小,即運(yùn)用高斯列主元消元法可以減小計(jì)算誤差. 3.2 矩陣三角分解法解線性方程組高斯消元法實(shí)質(zhì)上是對(duì)方程組進(jìn)行等價(jià)變形,即是對(duì)系數(shù)矩陣施行初等變換,這些初等變換又可以用矩陣表示.矩陣的三角分解是高斯消元法的另一種表示方法,或者說(shuō)是高斯消元法的變形.它在

11、解線性方程組的直接法中起著重要的作用. 3.2.1 直接三角分解法 如果方程組的系數(shù)矩陣能分解成 其中是下三角矩陣,是上三角矩陣,這時(shí)方程組就可化為兩個(gè)容易求解的三角形方程組 先由解出向量,再由解出向量,這就是原方程組的解. 若是單位下三角陣,則稱相應(yīng)的分解為 doolittle分解(也稱為分解).定理 1 矩陣有唯一的doolittle分解的充分必要條件是的前個(gè)順序主子式.設(shè)矩陣非奇異,且的前個(gè)順序主子式都不為零.則有dool-ittle分解 由矩陣的乘法可知 當(dāng)時(shí)有 對(duì)于doolittle分解算法,我們知道:(1)對(duì) (2)對(duì) 其中可以利用分解求解線性方程組的算法,則可以先求解,即 所以

12、再求解,即 回代求解 例3 利用doolittle分解求解以下方程組 解: 所以 回代求解 由此可知,矩陣分解中的直接三角分解法是以分解為基礎(chǔ)進(jìn)行矩陣分解,以上則是運(yùn)用doolittle分解求解線性方程組的解題過(guò)程.3.2.2 追趕法 設(shè)元線性方程組的系數(shù)矩陣為非奇異矩陣的三對(duì)角矩陣 這種方程組稱為三對(duì)角線性方程組.這類方程組具有許多明顯的應(yīng)用背景,在求微分方程數(shù)值解、三次樣條函數(shù)等問(wèn)題中, 都會(huì)遇到這樣的線性方程組.設(shè)的前個(gè)順序主子式都不為零,則有唯一的分解,并且的分解有如下形式 其中 三對(duì)角方程組的追趕法 1 向前追的過(guò)程 (1)(2) 對(duì)計(jì)算 2 往回趕的過(guò)程(2) 對(duì),計(jì)算 例4 設(shè)4

13、階方程組為 這就是一個(gè)三對(duì)角方程組,既系數(shù)矩陣除了對(duì)角線的三斜線以外的元素均為0.用追趕法求解三對(duì)角方程組的一種做法是把系數(shù)矩陣寫(xiě)成下列形式的分解(這里采用doolittle分解): 即為單位上三角陣,兩斜行,主對(duì)角線元素為1,其下方的斜行元素待定；為上三角陣,也是兩斜行,主對(duì)角線元素待定,其上方斜行的元素與對(duì)應(yīng)的斜行元素相同(直接驗(yàn)算可知道). 利用矩陣乘法規(guī)則按順序依次考慮的,并對(duì)比兩端可得 即得分解 于是用前推過(guò)程求解下三角方程組 得 再用回代過(guò)程求解上三角方程組 得 即的方程組的解 從實(shí)例看到,三對(duì)角方程組的追趕法是三角分解發(fā)的一種特殊應(yīng)用,因此,一般地,如果對(duì)三角矩陣非奇異,其順序主

14、子式,則解三對(duì)角方程組: 的追趕法可描述如下:令,則 利用矩陣乘法規(guī)則,可求和的計(jì)算公式: 于是,求解得 再求解,得三對(duì)方程組的解 上述3個(gè)公式便組成解三角方程組的追趕法.當(dāng)然,這是在假定三角矩陣 非奇異,其順序主子式的條件下才能實(shí)現(xiàn)的.從公式和看出,關(guān)鍵在于有. 4 總結(jié)線性方程組的各個(gè)數(shù)值解法之間有著一定的聯(lián)系,同時(shí)也存在不同之處.矩陣直接三角分解法是高斯消元法的變形方法.高斯消元法有多種變形,有的是高斯消元法的改進(jìn),有的是用于某種特殊系數(shù)矩陣的化簡(jiǎn).高斯消元法解線性方程組先消元,然后再帶回.當(dāng)用矩陣描述時(shí),是對(duì)系數(shù)矩陣分解為一個(gè)上三角矩陣和一個(gè)下三角矩陣的乘積,即分解.因此,高斯消元法與

15、矩陣三角分解法中的分解是一致的.當(dāng)然,針對(duì)線性方程組不同的形式與所具備的條件所選擇的方法也是有區(qū)別的. 高斯消元法的基本思想是通過(guò)行變換,逐步消元,把方程組化為系數(shù)矩陣為三角形矩陣的等價(jià)的方程組,然后用回代法解此三角形方程組得原方程組的解.對(duì)于高斯順序消元法,標(biāo)記元素的絕對(duì)值很小時(shí),若用它作除數(shù),則根據(jù)數(shù)值運(yùn)算中用絕對(duì)值很小的數(shù)作除數(shù),舍入誤差會(huì)增大,而且嚴(yán)重影響計(jì)算結(jié)果的精度的原則,表明這種方法在一定程度上是具有局限性的.因此,在高斯順序消元法的基礎(chǔ)上,我們引進(jìn)了高斯列主元消元法.它是在高斯消元法的消去過(guò)程中第k步增加選主元操作,成為首先在第列中,從中選出絕對(duì)值最大的元素.經(jīng)過(guò)行交換(把絕對(duì)

16、值最大者所在的行與第行交換)把絕對(duì)值最大的元素?fù)Q到akk的單位中；然后做高斯順序消去法的消去過(guò)程中第k步,初等變換產(chǎn)生第列的個(gè)零元素.對(duì)于非奇異矩陣的方陣,我們則利用直接三角分解法推導(dǎo)得到的公式(doolittle分解公式或者crout分解公式)進(jìn)行求解.追趕法是針對(duì)帶狀矩陣(尤其是三對(duì)角矩陣)這一大稀疏矩陣的特殊結(jié)構(gòu),得出的一種保帶性分解的公式推導(dǎo),進(jìn)行求解線性方程組.因此,針對(duì)不同類型的方程組應(yīng)該選擇合適的數(shù)值解法.參考文獻(xiàn):李書(shū)剛.線性代數(shù).m.北京:科學(xué)出版社,2010,第91-109頁(yè).盧剛.線性代數(shù).m.北京:高等教育出版社,2002,第80-86頁(yè).李慶揚(yáng).王能超.易大義.數(shù)值分析.m.4版.武漢:華中科技大學(xué)出版社,2006,第29-36頁(yè).居余馬.線性代