線性方程組的多種求解問題2

1、青海師范大學(xué)數(shù)學(xué)系2013屆信息與計算科學(xué)專業(yè)畢業(yè)論文多種求解線性方程組的方法比較知識就是力量 姓 名：李積鑫 班 級：2009級C班 指導(dǎo)教師：陳桂秀（職稱） 完成時間：2013年4月28日目 錄摘要 1Abstract 11 線性方程組的求解歷史起源12 線性方程組的多種求解方法22.1 高斯消去法 22.1.1 高斯順序消去法 22.1.2 高斯選主元素消去 32.1.1 列主元素消去法 3 2.2 克萊姆規(guī)則4 2.3 迭代法 62.3.1 雅可比迭代法 62.3.2 高斯-賽德爾迭代法7 2.4 MATLAB在求解線性方程組中的應(yīng)用 73 總結(jié) 104 參考文獻10多種求解線性方程組

2、的方法比較李積鑫青海師范大學(xué) 810008摘要：線性代數(shù)是數(shù)學(xué)的一個古老分支，廣泛應(yīng)用于現(xiàn)代科學(xué)的許多分支,其核心問題之一就是線性方程組的求解問題。而歷史上線性代數(shù)的第一個問題是關(guān)于解線性方程組的問題，且線性方程組是線性代數(shù)中一個最基礎(chǔ)的內(nèi)容，它在科學(xué)和工程計算等領(lǐng)域都發(fā)揮著重要的作用。本文首先介紹線性方程組的求解歷史，重點介紹了解線性方程組的幾種方法:消元法、克萊姆解線性方程組以及迭代法。最后介紹了如何利用Matlab等常用電腦軟件解線性方程。關(guān)鍵詞：線性方程組 Matlab 迭代法 高斯消元法 Abstract:Linear Algebra is an ancient branch f m

3、athematics, widely used in many branches f mdern science, ne f the cre issues is the prblem f slving linear equatins. The histry f linear algebra first questin is abut the prblem f slving linear equatins, linear equatins and linear algebra in the mst basic cntent, it plays an imprtant rle in the fie

4、ld f scientific and engineering cmputing. This paper first intrduces the histry f linear equatins, the highlights are several ways t understand linear equatins: eliminatin methd, Clem slving linear equatins and iterative methd. Finally, hw t use Matlab and ther cmmnly used cmputer sftware fr slving

5、linear equatins.Keywrd: Linear Algebra;Matlab;Iterative methd;Gaussian eliminatin 一、線性方程組的求解歷史起源我們把形如的這種方程叫做線性方程組的一般形式。同時線性方程組中的系數(shù)也可以寫成矩陣形式，即則方程組為的矩陣形式。九章算術(shù)是中國古代一部重要的數(shù)學(xué)經(jīng)典之作。其“方程術(shù)”解線性方程組的方法是世界上最早、最完整的線性方程組的解法，其中所述方法實質(zhì)上相當于現(xiàn)代的對方程組的增廣矩陣施行初等行變換從而消去未知量的方法，即高斯消元法。劉徽提出了比較系統(tǒng)的方程理論。在西方，線性方程組的研究是在 17 世紀后期由萊布尼茨開

6、創(chuàng)的。他曾研究含兩個未知量的三個線性方程組組成的方程組。線性方程組解結(jié)構(gòu)的早期研究，是由麥克勞林和克萊姆從線性方程組的求解入手，用線性方程組的系數(shù)給出解的表達式，雖然麥克勞林的發(fā)現(xiàn)要早兩年，但是相比之下，克萊姆的規(guī)律更簡明清晰，更加完美.18世紀下半葉，法國數(shù)學(xué)家貝祖對線性方程組理論進行了一系列研究，證明了元齊次線性方程組有非零解的條件是系數(shù)行列式等于零。19世紀，英國數(shù)學(xué)家史密斯 (H.Smith) 和道奇森 (C-L.Ddgsn) 繼續(xù)研究線性方程組理論，前者引進了方程組的增廣矩陣和非增廣矩陣的概念，后者證明了個未知數(shù)個方程的方程組相容的充要條件是系數(shù)矩陣和增廣矩陣的秩相同。這正是現(xiàn)代方程

7、組理論中的重要結(jié)果之一。大量的科學(xué)技術(shù)問題，最終往往歸結(jié)為解線性方程組。因此在線性方程組的數(shù)值解法得到發(fā)展的同時，線性方程組解的結(jié)構(gòu)等理論性工作也取得了令人滿意的進展。現(xiàn)在，線性方程組的數(shù)值解法在計算數(shù)學(xué)中占有重要地位。2、 線性方程組的多種求解方法1、 高斯消去法高斯消去法（又叫順序消去法或逐次消去法）是一個古老的求解線性方程組的直接方法（早在公元前250年我國就掌握了解三元線性方程組的方法），其基本思想是用逐次消去未知量的方法，把原來方程組化為其同解的三角形方程組，求解三角方程組就比較容易。高斯消去法主要包括高斯順序消去法、高斯完全主元素消去法、列主元素消去法等。下面舉例分析這三種方法的具

8、體做法及特點。1.1高斯順序消去法求解方程組其基本思想利用矩陣的初等變換（互換變換、倍數(shù)變換、消去變換）將方程組中的系數(shù)矩陣約化為具有簡單形式的矩陣（如上三角矩陣，單位矩陣等）。例1、用高斯順序消去法解線性方程組解： 解之得1.2高斯選主元素消去法其基本思想是對方程組中的系數(shù)矩陣進行行和列的交換，首先從的個元素中選取絕對值最大的元素作為主元素，然后進行消元和回代計算。例2用完全主元素消去法解線性方程組 解：于是對應(yīng)的上三角線方程組為解之得 1.3列主元素消去法其基本思想是每次選取主元素時，僅依次按列選取絕對值最大的元素作為主元素，并且進行交換兩行，然后進行消元和回代計算。例3用列主元素消去法解

9、線性方程組 解：解之得 經(jīng)過上述三種做法，我們直觀上首先可以看出高斯順序消元法相對比較簡便些，但是順序法也有它的局限性，在解線性方程組的消元過程中，可能會出現(xiàn)如下兩種情況：第一是的情形，致使消元過程無法繼續(xù)下去；第二即使，但其絕對值很小的時作除數(shù)可能會導(dǎo)致其他元素數(shù)量級的嚴重增長和舍入誤差的傳播，使計算結(jié)果不可靠。所以在采取高斯消元法解方程組時，小主元素可能會產(chǎn)生計算結(jié)果失真，故應(yīng)避免采用絕對值小的主元素。對一般矩陣來說，比較好每一步選取系數(shù)矩陣（或消元后的低階矩陣）中絕對值最大的元素作為主元素，以使高斯消去法具有良好數(shù)值穩(wěn)定性。所以我們可以采取選主元素的方法來克服高斯順序消去法的這一缺點。完

10、全主元素消去法是解低階稠密矩陣方程組的有效方法，但是這種方法在選主元素時會花費一些時間，而且由于變量之間的位置在消元過程中（列變換）發(fā)生了改變，這使得對最后解上三角形方程組時，變量的值容易發(fā)生錯誤，所以在計算過程中應(yīng)記住各變量的具體位置，最后按變量的原始順序輸出方程組的解。由于完全主元素這一局限性，在實際計算中也常用部分選主元素（即列主元素）消去法。2、 克萊姆法則定理1、（克萊姆規(guī)則）一個含有n個未知量n個方程的線性方程組當它的行列式D0時，有且只有一個解此處是把行列式的第j列元素換以方程組的常數(shù)項而得到的n階行列式。其中D是系數(shù)行列式，D是在系數(shù)行列式基礎(chǔ)之上結(jié)合方程組右邊常數(shù)形成的新行列

11、式，利用行列式的性質(zhì)計算行列式最為有效，對于二、三階行列式可以利用對角線法則計算?？巳R姆法則克服了消元法計算效率低甚至無法計算多元一次方程組的缺點，但是對于系數(shù)行列式等于零以及欠定或者超定方程組的情況，它是無能為力的)事實上，當未知元數(shù)過多時，克萊姆法則的計算效率就很低。例2.1解線性方程組解：這個方程組的行列式。因為,我們可以應(yīng)用克萊姆規(guī)則再計算以下的行列式由克萊姆規(guī)則，得方程組的解是：克萊姆法則建立了線性方程組的解和已知的系數(shù)與常數(shù)項之間的關(guān)系，它主要適用于理論推導(dǎo)?？巳R姆法則克服了消元法計算效率低甚至無法計算多元一次方程組的缺點，但是克萊姆也有它的不足：（1）克萊姆法則只能用于求解方程個

12、數(shù)與未知數(shù)個數(shù)相等的線性方程組；（2）克萊姆法則只能求得系數(shù)行列式不為零時的線性方程組的唯一解；即如果方程個數(shù)與未知數(shù)個數(shù)不相等，或系數(shù)行列式等于零，則克萊姆法則失效。（3）計算量大，要計算 n+1 個 n 階行列式的值。所以使用克萊姆法則求解線性方程組時應(yīng)該遵循兩個條件，首先方程個數(shù)和未知量個數(shù)必須相等；其次，系數(shù)行列式不為零。3、 迭代法線性方程組為A=b（A為非奇異矩陣），當系數(shù)矩陣A為低階稠密矩陣時，利用高斯消去法求解這類方程組是合適的，但如果矩陣A的階數(shù)n很大（n）且零元素很多的情況下，利用迭代法解這類方程組是比較合理的。所以以下介紹幾種迭代法及其基本思想。3.1雅可比迭代法(Jac

13、bi)對于n元線性方程組A=b中的系數(shù)矩陣A可分解為幾個特殊矩陣的和A=U+D+L，其中U為嚴格上三角矩陣，D為A的對角素構(gòu)成的對角矩陣，L為嚴格下三角陣，則A=b寫作（U+D+L）=b，（U+L)+D=b,D=-(U+L)+b,由此可得雅可比迭代公式的矩陣形式：=-D-1(U+L)(k)+D-1b，記B=-D-1(U+L)，f=D-1b,從而有(k+1)=B(k)+f，其中矩陣B稱作雅可比迭代法的迭代矩陣。例3.1用雅可比迭代法解線性方程組解：首先從上面的三個方程中分別分離出變量，由此將這個方程組改寫成便于迭代且等價的方程形式，據(jù)此建立迭代公式，取迭代初始解向量，代入上式并反復(fù)迭代，當?shù)?/p>

14、數(shù)增加時迭代結(jié)果就越來越逼近準確解，這種迭代過程是收斂的吧，迭代得到的解向量序列是以為極限，這種方式則稱為雅可比迭代法。3.2高斯賽德爾迭代法（G-S）對于n元線性方程組A=b中的系數(shù)矩陣A作分解A=U+D+L，其中U為嚴格上三角矩陣，D為A的對角素構(gòu)成的對角矩陣，L為嚴格下三角陣，則A=b寫作（U+D+L)=b，D=-L=U+b,根據(jù)分量形式就有D(k+1)=-L(k+1)-U(k)+b，從而（D+L）(k+1)=-U(k)+b,如果（D+L）-1存在，則高斯-賽德爾迭代公式的矩陣形式為(k+1)=-（D+L）-1U(k)+（D+L）-1b,即B=-(D+L)-1U,f=(D+L)-1b,于

15、是有(k+1)=B(k)+f，其中矩陣B稱作高斯-賽德爾迭代法的迭代矩陣。例3.2用高斯-賽德爾迭代法解線性方程組解：從上面的三個方程中分別分離出變量，由此將這個方程組改寫成便于迭代且等價的方程組形式，據(jù)此建立迭代公式，取迭代初始解向量，代入上式并反復(fù)迭代，從而得到迭代公式。兩種迭代法的比較：一般情況下，J法與GS法比較并無優(yōu)劣，收斂情況與速度均不一定。但是，具有相容次序的矩陣，在相同精度要求下，GS法比J法快一倍。若線性方程組系數(shù)A是嚴格對角占優(yōu)或不可約對角占優(yōu)矩陣，則J法和GS法都收斂。4、 MATLAB在求解線性方程組中的應(yīng)用MATLAB是功能強大的科學(xué)及工程計算軟件，它不但具有以矩陣計

16、算為基礎(chǔ)的強大計算和分析功能，而且還具有豐富的可視化圖形表現(xiàn)功能和方便的程序設(shè)計能力。對于線性方程組其中為此線性方程組的系數(shù)矩陣為列向量,矩陣為由構(gòu)成的此方程組的增廣矩陣。則線性方程組的解可分為以下三種個情況：（1） 當m=n且rank(A) = rank(B) = n時線性方程組有唯一解，可通過求出解。例4.1求解方程組解：>> A=1 2 3 4;4 3 2 1;1 3 2 3;4 1 3 2;b=5;4;3;2;>> b=5;4;3;2;>> B=A,b;>> n=4;>> RA=rank(A)>> RB=rank(

17、B)>> =Ab = -8.2000 4.0000 18.8000 -12.8000（2） 若 rank(A)rank(B)則方程組 無解.例4.2求解方程組解：>> A=1 -5 2 -3;-3 1 -4 2;-1 -9 0 -4;5 3 6 -4;>> b=11;-5;-1;1;>> B=A,b;>> n=4;>> RA=rank(A)RA = 3>> RB=rank(B)RB = 4RA<RB 無解（3）當rank(A) = rank(B) = r < n 時線性方程組 A = b 有無窮多解

18、.例4.3求齊次方程組的解解：>> clear>> A=1 2 4 -3;3 5 6 -4;4 5 -2 3;3 8 24 -19;>> frmat rat>> n=4;>> RA=rank(A)RA = 2 >> if(RA=n)elseA=null(A,'r')endA= 8 -7 -6 5 1 0 0 1 >> syms k>> =kA = 8k, -7k -6k, 5k k, 0 0, k可見，MATLAB語言實現(xiàn)線性方程組的求解具有程序簡單、直觀的特點，同時還具有計算效率高的優(yōu)點，在實際計算巾擺脫了系數(shù)矩陣階數(shù)未知元數(shù)等的限制。3、 總結(jié)本文首先介紹了線性方程組求解的起源問題，然后主要介紹了線性方程組的幾種解法。消元法，克萊姆法則和迭代法求解線性方程組。高斯消去法的計算量非常大，我認為我們不僅要學(xué)會做題目時會用方法解題，也需要具備在電腦