數(shù)值分析 課程設(shè)計

1、數(shù)值分析課程設(shè)計 Gauss消元、LU分解、Jacobi迭代法比較分析院（系）名稱 信息工程學(xué)院 專 業(yè) 班 級 09普本信計1班 學(xué) 號 090111053 學(xué) 生 姓 名 李 豪 指 導(dǎo) 教 師 孔繁民 2012年05月21日數(shù)值分析 課程設(shè)計評閱書題目Gauss消元法、LU分解、Jacobi迭代法比較分析學(xué)生姓名李豪學(xué)號090111053指導(dǎo)教師評語及成績指導(dǎo)教師簽名： 年 月 日答辯評語及成績答辯教師簽名： 年 月 日教研室意見 總成績： 教研室主任簽名：年 月 日 課程設(shè)計說明書（論文） 第23頁課程設(shè)計任務(wù)書20112012學(xué)年第二學(xué)期專業(yè)班級： 09普本信計1班 學(xué)號： 0901

2、11053 姓名： 李豪 課程設(shè)計名稱： 數(shù)值分析 設(shè)計題目： Gauss消元法、LU分解、Jacobi迭代法比較分析 完成期限：自 2012 年 5月 21 日至 2012 年 5月 31 日共 10 天設(shè)計依據(jù)、要求及主要內(nèi)容：一、設(shè)計目的： 求解線性方程組的數(shù)值方法1.可直接求解，如進行LU分解，其中,LU分解又有Doolittle方法和Grout方法。2.可在計算機上通過設(shè)定和給定的迭代次數(shù)，無限接近所求的數(shù)，但必須保證所求方程是收斂的前提下。 二、設(shè)計內(nèi)容：1.用隨機數(shù)產(chǎn)生10*10階的線性方程組。2.用Gauss選主元消去法求解。3.用Doolittle方法（LU分解）求解。4.用

3、Crout方法（LU分解）求解。5.用Jacobi迭代法求解。6.用Gauss-Seidel迭代法求解 三、設(shè)計要求：先用Matlab數(shù)據(jù)庫中的相應(yīng)函數(shù)對給定的線性方程組求出具有一定精度的解；然后對所學(xué)的各種方法分別編寫Matlab程序進行求解；無論直接解法，要有條件數(shù)分析，對于迭代解法，給出收斂分析。 三、參考文獻 1 馮果忱，劉經(jīng)倫。數(shù)值代數(shù)基礎(chǔ)。長春：吉林大學(xué)出版社，1991. 2法捷耶夫 D K,法捷耶娃 B H.線代數(shù)計算方法。上海：上?？萍汲霭嫔?9653希圖爾特 G W.矩陣計算引論。上海：上海科技出版社，1980. 4蔣爾雄，高坤敏，吳景琨。線性代數(shù)。北京:人民教育出版社。19

4、78 計劃答辯時間：2012年5月31日工作任務(wù)與工作量要求：查閱文獻資料不少于3篇，課程設(shè)計報告1篇不少于3000字。指導(dǎo)教師（簽字）： 孔繁民 教研室主任（簽字）： 批準(zhǔn)日期： 2012 年 5 月 20 日 Gauss消元、LU分解、Jacobi迭代法比較分析摘 要 求解線性方程組有多種方法，總體可分為兩類：直接法和迭代法。兩種方法都有其優(yōu)點和局限的地方。本次課程設(shè)計采用綜合分析方法，對兩種方法中具有代表性的Gauss消元法，LU分解方法，Jacobi迭代法進行比較分析，力求能從中得到合理運用各種方法的經(jīng)驗。其中的一般思路是，首先透徹理解各種解法的原理，適用范圍和條件，然后通過Matla

5、b對解法進行編程，最后通過對運行程序得到的結(jié)果進行分析，從而得出各種方法的適用范圍，對每一種方程采用何種方法最優(yōu)的一般結(jié)論。關(guān)鍵詞：Gauss消元，LU分解，Jacobi迭代，Matlab目 錄1 方法分析11.1 Gauss消元法11.2 Doolittle分解51.3 Jacobi的原理92 比較分析102.1 Gauss算法運行結(jié)果122.2 LU分解運行結(jié)果132.3 Jacobi運行結(jié)果15附錄19總結(jié)21參考文獻22翻譯23 1 方法分析1.1 Gauss消元法 首先來考察Gauss消元法。Gauss消元法一種直接法，直接法是指在無舍入誤差的情況下，經(jīng)過有限步運算即可求得方程組精確

6、解的算法，因此，又稱為精確法，這種方法是通過矩陣約化將原方程組化成與之等價的三角形方程組和其他形式的可以直接求解的方程組而實現(xiàn)的.消元法是這類方法的典型.由于舍入誤差的存在，即便使用精確法也得不到精確解.所以一個直接方法只有舍入誤差是可以控制的時候才是可用的.其實，按自然消元過程等價于將方程組的增廣矩陣依次方程乘以具有恰當(dāng)形式的的Gauss的矩陣，將其約化為上三角形式.高斯消去法的求解過程,可大致分為兩個階段:首先,把原方程組化為上三角形方程組,稱之為“消元”過程;然后,用逆次序逐一求出三角方程組(原方程組的等價方程組)的解,并稱之為“回代”過程.,下面分別寫出“消去(消元)”和“回代” 兩個

7、過程的計算步驟. 消去(消元)過程: 第一步：設(shè)取做（消去第個方程組的）第一個方程第方程 則第方程變?yōu)?(1.1.1) 因為可得第一步消元方程 (1.1.2)第二步：設(shè)取做（消去第個方程組的，）第二個方程第個方程 類似可得到第二步消元后的方程組為 (1.1.3)第k步：設(shè)，取做（消去第個方程組的，） 第個方程第個方程 類似可得到第步消元后的方程組為 (1.1.4)繼續(xù)下去到步消元，可將線性方程組化為如下上三角方程組： (1.1.5)其中和的上標(biāo)表示第次消元后的系數(shù)，計算公式為：對 (1.1.6) 下面來分析Gauss消元的算法：線性方程組 其中 消元：回代：接下來說明一下Gauss消元法在程序

8、中的具體實現(xiàn)：輸入 輸出 步驟： 具體程序見附錄1.1.2 Doolittle分解 下面來考查另一種直接方法，Doolittle分解.將系數(shù)矩陣A轉(zhuǎn)變成等價兩個矩陣L和U的乘積 ，其中L和U分別是下三角和上三角矩陣.當(dāng)A的所有順序主子式都不為0時，矩陣A可以分解為A=LU，但不唯一.其中L是單位下三角矩陣，U是上三角矩陣，這就是LU分解.Doolittle分解屬于LU分解.LU分解在本質(zhì)上是高斯消元法的一種表達形式.實質(zhì)上是將A通過初等行變換變成一個上三角矩陣，其變換矩陣就是一個單位下三角矩陣.這正是所謂的杜爾里特算法（Doolittle algorithm）：從下至上地對矩陣A做初等行變換，

9、將對角線左下方的元素變成零，然后再證明這些行變換的效果等同于左乘一系列單位下三角矩陣，這一系列單位下三角矩陣的乘積的逆就是L矩陣，它也是一個單位下三角矩陣.Doolittle的范圍：對于非奇異矩陣（任n階順序主子式不全為0）的方陣A，都可以進行Doolittle分解，得到A=LU，其中L為單位下三角矩陣， U為上三角矩陣，且分解是唯一的（這里的Doolittle分解實際就是Gauss變換）.下面具體討論Doolittle分解是如何實現(xiàn)的：A的各階順序主子式均不為零，即：令用比較等式兩邊元素的方法逐行逐列求解各元素. (1.2.1) (1.2.2) (1.2.3) (1.2.4)即 (1.2.5

10、)各元素在計算機內(nèi)存于的各位再由及得 (1.2.6)接下來來討論關(guān)于Doolittle分解的具體算法：（1） 輸入：（2） 分解 i) ii) （3） 解及i) ii) （4） 輸出：方程組的解Dolittle的Matlab程序見附錄2.條件數(shù)分析：在計算過程中，由于計算機字長的有限性，不可避免地產(chǎn)生所謂的舍入誤差。同時，由于所求問題的初始數(shù)據(jù)（例如線性方程組的系數(shù)矩陣和右端項系數(shù)）往往是帶有一定誤差的。因此計算結(jié)果總是不可避免地帶有誤差，或者說，如果初始數(shù)據(jù)有擾動，勢必將帶來具有一定誤差的計算結(jié)果。對于來說，由于觀測或計算等原因，線性方程組兩端的系和都帶有誤差和，這樣實際建立的方程組是近似方

11、程組。對近似方程組求出的解是原問題的真解加上誤差,即。而是由及引起的，它的大小將直接影響所求解的可靠性。這種解依賴于方程組系數(shù)的誤差及的問題，稱為線性方程組解對系數(shù)的敏感性。 程組的系數(shù)矩陣發(fā)生微小擾動，就有可能引起方程組性質(zhì)上的變化，這是方程組本身的“條件問題”。相對誤差關(guān)系式： 設(shè)原線性方程組： 近似方程組： 在 1. (1.2.7)2. (1.2.8)由這些關(guān)系式可看到，帶有擾動的近似方程組中，擾動的大小直接影響著所求解的相對誤差，故可作如下定義：定義：設(shè)A非奇異，稱為矩陣A的條件數(shù)，記 為，即 .可反映出方程組解對系數(shù)的敏感性.一般來說，方程組的條件數(shù)越小, 求得的解就越可靠; 反之，

12、解的可靠性就越差。但是由于實際問題的復(fù)雜性，需要求解的線性方程組的規(guī)模往往很大，利用直接法求解其計算效率將變得很差，甚至失效.這主要有兩方面的困難：1）存儲量太大；2）計算速度慢.一種有效的方法是利用迭代法.迭代解法的特點是，對于一個給定的離散代數(shù)系統(tǒng)，首先假設(shè)一個初始解，然后按一定的算法公式進行迭代.在每次迭代過程中對解的誤差進行檢查，并通過增加迭代次數(shù)不斷降低解的誤差，直到滿足解的精度要求，并輸出最后的解答.這類方法包括常用的迭代方法，如Jacobi、Gauss-Seidel,超松弛迭代（SOR）,共軛梯度法（CG），也包括現(xiàn)代計算方法中先進的迭代方法，如預(yù)處理共軛梯度法（PCG），多重網(wǎng)

13、格法（Multigrid method）等.在這里我只對Jacobi方法進行分析，和直接算法進行比較、分析來考察幾種方法的長處與劣勢。1.3 Jacobi的原理：設(shè)有如下方程組： (1.3.1)若系數(shù)矩陣非奇異，且，將方程組 (1.3.2)然后寫成迭代格式 (1.3.3)上式也可以簡單地寫為 (1.3.4)給出初值便可求得方程組的解。下面給出Jacobi迭代法的算法：1.輸入維數(shù)，最大容許迭代次數(shù)；2，置；3.對，；4.若，輸出，停機；否則轉(zhuǎn)5.5.若，置轉(zhuǎn)3；否則，輸出失敗信息，停機。程序見附錄3.Jacobi迭代法的收斂條件： 迭代格式收斂Ûr(B)<1 。若B<1&

14、#222;迭代法收斂. 對于Jacobi迭代，我們有一些保證收斂的充分條件.定理：若系數(shù)矩陣A滿足下列條件之一，則Jacobi迭代收斂。I） A為行對角占優(yōu)矩陣II） A為列對角占優(yōu)矩陣III） A滿足注：若A是嚴格對角占優(yōu)矩陣，則2 比較分析為了方便比較各個方法，最明了的方式就是使用例題進行說明，因此隨機生成10*10的矩陣，并用此矩陣進行說明。生成隨機矩陣：由條件數(shù)可知這個系數(shù)矩陣是病態(tài)的。2.1 Gauss算法運行結(jié)果：通過計算我們發(fā)現(xiàn)Gauss消去法的計算量為 (2.1.1)當(dāng)充分大時為.當(dāng)很大時，主要的工作量都會花在約化三角形形式上.而且，Gauss消元法是姐線性方程組的基本方法，它

15、是直接法的基礎(chǔ)，具有計算簡單的特點，但其消元過程有時不能進行到底而使求解出現(xiàn)失真的情況.高斯消元法可用在任何域中。 高斯消元法對于一些矩陣來說是穩(wěn)定的。對于普遍的矩陣來說，高斯消元法在應(yīng)用上通常也是穩(wěn)定的，不過亦有例外。 2.2 LU分解運行結(jié)果：通過計算我們發(fā)現(xiàn)這類算法的復(fù)雜度一般在 左右，他的計算量顯然要不Gauss消元法小很多.這就可以省下很多機器時間，這在進行有些復(fù)雜的大型計算時是很有益的. 同時，我們發(fā)現(xiàn)，兩種方法得到的結(jié)果十分接近，但是LU方法得到的結(jié)果的比Gauss方法的結(jié)果精確值更高。直接法比較分析：1.顯然，上述例題的計算結(jié)果都是精確值。但是實際情況我們求解的方程組得到的解大

16、多是近似解。由高斯消去法和直接三角求解法的求解過程可知道，這兩類方法多適用于求解低階稠密矩陣，其優(yōu)點是若計算過程中沒有舍入誤差，即可求得方程組的精確解。兩類求解法的局限性分別為：對于直接三角求解法要求矩陣的各級順序主子式不為零，否則無法求解；對于高斯消去法，當(dāng)矩陣的各級順序主子式不為零時在不換行的前提下，可以順利求解，若消去過程中出現(xiàn)主元素為零情形，則需要換行再進行消去最后化成上三角型方程組。2.高斯消去法、矩陣LU分解、直接三角分解法之間的聯(lián)系：觀察高斯消去過程，的各順序主子式均不為零時，高斯消去法實質(zhì)上產(chǎn)生了一個將分解為兩個三角矩陣相乘的因式分解，這為三角直接法做了鋪墊。而當(dāng)?shù)乃许樞蛑髯?/p>

17、行列式都不為零時就保證了計算過程中不會有分母為零情形出現(xiàn)，此時高斯消去法等價于把矩陣A分解成上下三角矩陣的乘積。一旦實現(xiàn)了矩陣A的LU分解，那求解的問題就等價于求解兩個三角形方程組（1）求 ； (2),求。即直接三角分解法。2.3 Jacobi運行結(jié)果：由運行結(jié)果，所給系數(shù)矩陣迭代不收斂，得到的結(jié)果是不可用的。我們可編制一個判斷矩陣是否對角占優(yōu)的函數(shù)IsDiagominant(A),來說明函數(shù)不收斂的原因。程序編制如下：function x=IsDiagominant(A)%判斷輸入的矩陣A是否具有嚴格對角優(yōu)勢或A不可約且具有對角優(yōu)勢%返回值為1,表示A是具有嚴格對角優(yōu)勢或A不可約且具有對角優(yōu)

18、勢%若返回值為0則沒有上述性質(zhì)m,n=size(A); if m=n error('A不是方陣'); return; end %先判斷是否為嚴格對角占優(yōu) B=abs(A); for i=1:n b=B(i,i); temp=B(i,:); temp(i)=; if b>sum(temp) T(i)=1; else T(i)=0; end end if sum(T)=sum(ones(n,1) Fg1=1;%輸入方陣為嚴格對角占優(yōu)矩陣 else Fg1=0;%輸入方陣產(chǎn)不是嚴格對角占優(yōu)矩陣 end %以下判斷它是否為不可約且具有對角優(yōu)勢 %先判斷是否為不可約矩陣 D=A;

19、D=rref(D); d=D(n-1,:); if sum(d)=0 flag=1;%A為不可約矩陣 else flag=0;%A為可約矩陣 end for i=1:n b=B(i,i); temp=B(i,:); temp(i)=; if b>=sum(temp) T1(i)=1; else T1(i)=0; end end Fg2=0;%先假定A為可約矩陣且不具有對角優(yōu)勢 if sum(T1)>sum(ones(n,1) & flag=1Fg2=1;%A為不可約矩陣且具有對角優(yōu)勢 end if Fg1=1 | Fg2=1 x=1;%A為期望的方陣 else x=0;%A

20、不滿足要求 end運行結(jié)果如下：可見這個矩陣A是具有嚴格對角優(yōu)勢或不可約且具有對角優(yōu)勢，因此所得結(jié)果不收斂。這也說明Jacobi迭代方法使用是有一定的局限性的。同時，雅克比迭代法的優(yōu)點也很明顯。計算公式簡單，每迭代一次只需計算一次矩陣和向量的乘法，且計算過程中原始矩陣A始終不變，比較容易并行計算。然而這種迭代方式收斂速度較慢，而且占據(jù)的存儲空間較大。但是作為求解大型稀疏矩陣提供了可行的方法。由上面的分析我們可以看到，Gauss消元法，LU分解，Jacobi迭代法都是解線性方程組的好方法，但是同時它們自身都一定的使用限制，對于有些矩陣所得結(jié)果是不可用的，所以在計算中選擇合適的解題的方法顯得尤為重

21、要。附錄1. function RA,RB,n,X=gaus(A,b)B=A b; n=length(b); RA=rank(A); RB=rank(B);zhica=RB-RA;if zhica>0,disp('請注意：因為RA=RB，所以此方程組無解.')returnendif RA=RB if RA=ndisp('請注意：因為RA=RB=n，所以此方程組有唯一解.') X=zeros(n,1); C=zeros(1,n+1); for p= 1:n-1for k=p+1:n m= B(k,p)/ B(p,p); B(k,p:n+1)= B(k,p:n

22、+1)-m* B(p,p:n+1);endend b=B(1:n,n+1);A=B(1:n,1:n); X(n)=b(n)/A(n,n); for q=n-1:-1:1 X(q)=(b(q)-sum(A(q,q+1:n)*X(q+1:n)/A(q,q); endelse disp('請注意：因為RA=RB<n，所以此方程組有無窮多解.') end end2. L(2:n,1)=A(2:n,1)/U(1,1);for k=2:n U(k,k:n)=A(k,k:n)-L(k,1:k-1)*U(1:k-1,k:n); L(k+1:n,k)=(A(k+1:n,k)-L(k+1:n

23、,1:k-1)*U(1:k-1,k)/U(k,k); endL %輸出L矩陣U %輸出U矩陣 y=zeros(n,1); %開始解方程組Ux=y y(1)=b(1);for k=2:n y(k)=b(k)-L(k,1:k-1)*y(1:k-1);endx=zeros(n,1);x(n)=y(n)/U(n,n);for k=n-1:-1:1 x(k)=(y(k)-U(k,k+1:n)*x(k+1:n)/U(k,k);endfor k=1:n fprintf('x%d=%fn',k,x(k);end3. function x,n=jacobi(A,b,x0,eps) eps= 1.

24、0e-4; M = 200;D=diag(diag(A); %求A的對角矩陣L=-tril(A,-1); %求A的下三角陣U=-triu(A,1); %求A的上三角陣B=D(L+U);f=Db;x=B*x0+f;n=1; %迭代次數(shù)while norm(x-x0)>=eps x0=x; x=B*x0+f; n=n+1; if(n>=M) disp('Warning: 迭代次數(shù)太多，可能不收斂！'); return; endend總結(jié)我本次課程設(shè)計所做的是對線性方程組直接解法和迭代解法的淺析。我分析的對象包括Gauss消元法，LU分解法，Jacobi迭代法。其中前兩種

25、方法是直接法，后一種方法是迭代法。通過課堂上的學(xué)習(xí)，我認識到對于直接解法比較方便求解中小型稠密矩陣，其中Gauss消元法是直接法的基礎(chǔ)，LU分解在進行分解的時候，每次只是計算跟主元同行和同列標(biāo)號在主元之后的元，而Gauss消去法是標(biāo)號在主元之后的每個元素都要計算，因此LU分解的計算速度比Gauss消去法快很多。但其原理是一樣的。對于Jacobi迭代方法，適合于解大型稀疏矩陣，只要給定初值，在有限步內(nèi)便可得到收斂的準(zhǔn)確值。但是Jacobi方法會存在不收斂的情況，在應(yīng)用此方法時應(yīng)注意進行判斷。這次課程設(shè)計對我來說是一個很好的鍛煉。首先，對于線性方程組的各種解法有了自己的深刻的認識，理解了各種方法的

26、妙處以及每種方法的適用范圍，從而在解題時可以挑選最優(yōu)解法。其次，鍛煉對WORD文檔，公式編輯器的使用熟練程度。老師的嚴格要求使我充分認識到做任何事情都必須一心一意，不可草草了事。因此，對文檔的格式進行了反復(fù)的修改，盡力做到完美。從中我也學(xué)到了文檔編輯的很多知識，具備了一定的編輯經(jīng)驗。本次課程設(shè)計雖然艱辛但卻收獲頗豐。學(xué)習(xí)了知識，磨礪了意志。對于以后做任何事都是寶貴的經(jīng)驗。參考文獻1 黃明游，馮國忱.數(shù)值分析M.北京：高等教育出版社,20082 曹弋，MATLAB教程及實訓(xùn)M.北京：機械工業(yè)出版社,20083 石博強,趙金.MATLAB數(shù)學(xué)計算與工程分析范例教程M.北京:中國鐵道出版社,2005

27、.翻譯RAND函數(shù)的使用方法：RAND Uniformly distributed random numbers. RAND(N) is an N-by-N matrix with random entries, chosen from a uniform distribution on the interval (0.0,1.0). RAND(M,N) and RAND(M,N) are M-by-N matrices with random entries. RAND(M,N,P,.) or RAND(M,N,P,.) generate random arrays. RAND with no arguments is a scalar whose value changes each time it is referenced. RAND(SIZE(A) is the same size as A. RAND produces pseudo-random numbers. The sequence of numbers generated is determined by the sta