高斯-賽德爾迭代法的算法及程序設(shè)計(jì)課程設(shè)計(jì)

1、<p>　　題 目：高斯-賽德爾迭代法的算法及程序設(shè)計(jì)</p><p><b>　　摘要</b></p><p>　　本文通過理論與實(shí)例對(duì)線性方程組的解法、收斂性及誤差分析進(jìn)行了探討.在對(duì)線性方程組數(shù)值解法的討論下用到了高斯-賽德爾迭代法，進(jìn)一步研究和總結(jié)了高斯-賽德爾迭代法的理論與應(yīng)用，使我們?cè)诜治鰡栴}與編輯程序時(shí)能更好的把握對(duì)高斯-賽德爾迭代法的應(yīng)用

2、。</p><p>　　關(guān)鍵詞 Gauss-Seidel迭代法；收斂性；誤差分析；流程圖；Mathematica編程 </p><p><b>　　目錄</b></p><p>　　第一章 高斯-賽德爾迭代法1</p><p>　　§1.1 高斯-賽德爾迭代法的提出1</p><p>

3、;　　§1.1.1 高斯-賽德爾迭代法的思想理論1</p><p>　　§1.1.2 高斯-賽德爾迭代法的定義及表達(dá)形式2</p><p>　　§1.2 高斯-賽德爾迭代法的收斂性1</p><p>　　§1.3 高斯-賽德爾迭代法的誤差分析1</p><p>　　第二章 高斯-賽德爾迭代法的程

4、序設(shè)計(jì)..................................... 1</p><p>　　§2.1 高斯-賽德爾迭代法在上機(jī)中的應(yīng)用1</p><p>　　§2.1.1 高斯-賽德爾迭代法的流程圖1</p><p>　　§2.1.2 高斯-賽德爾迭代法的源程序1</p><p><b&

5、gt;　　參考文獻(xiàn)22</b></p><p><b>　　附錄23</b></p><p><b>　　高斯-賽德爾迭代法</b></p><p><b>　　考慮線性方程組</b></p><p>　　其中為非奇異矩陣，對(duì)于由工程技術(shù)中產(chǎn)生的大型稀疏矩陣方程

6、組（的階數(shù)很大但零元素很多）,利用迭代法求解線性方程組是合適的.在計(jì)算機(jī)內(nèi)存和運(yùn)算兩方面，迭代法通常都可利用中有大量零元素的特點(diǎn).</p><p>　　本章將介紹迭代法中的高斯-賽德爾法的思想理論、收斂性及誤差分析.</p><p>　　§1.1 高斯-賽德爾迭代法的提出</p><p>　　§1.1.1 高斯-賽德爾迭代法的思想理論</p

7、><p>　　在研究雅可比迭代法時(shí)，計(jì)算時(shí)，已得（這些分別為的第k+1次近似），Gauss-Seidel迭代法認(rèn)為在計(jì)算時(shí)啟用新值，從而產(chǎn)生</p><p><b>　　.</b></p><p><b>　　具體原理如下圖所示</b></p><p>　　圖1.1 基本迭代原理</p>

8、<p>　　§1.1.2 高斯-賽德爾迭代法的定義及表達(dá)形式</p><p>　　定義1.1 我們注意到在雅可比迭代法中并沒有對(duì)新算出的分量，，，</p><p>　　進(jìn)行充分利用．不妨設(shè)想，在迭代收斂的條件下，我們把</p><p>　　式中第一個(gè)方程算出的立即投入到第二個(gè)方程中，代替進(jìn)行計(jì)算，當(dāng)算出后代替馬上投入到第三個(gè)方程中計(jì)算，依次進(jìn)行下

9、去，這樣也許會(huì)得到更好的收斂效果．根據(jù)這種思路建立的一種新的迭代格式，我們稱為高斯-賽德爾（Gauss-Seidel）迭代公式，</p><p>　　高斯=賽德爾迭代法的分量形式：</p><p>　　高斯-賽德爾迭代法的矩陣形式：</p><p><b>　　其中</b></p><p><b>　　，<

10、;/b></p><p>　　稱為高斯-賽德爾迭代矩陣，稱為高斯-賽德爾迭代常量..</p><p>　　§1.2 高斯-賽德爾迭代法的收斂性</p><p>　　根據(jù)上節(jié)所述，高斯-賽德爾迭代法的迭代格式為</p><p><b>　?。?-1）</b></p><p><

11、b>　　其中</b></p><p>　　， . 本節(jié)要討論的問題就是任意選取初始值，利用迭代格式(1-1)得到的向量序列是否一定收斂，如果收斂的話需要滿足什么條件？</p><p>　　下面我們給出一般迭代收斂的條件:</p><p>　　定理1.2 簡(jiǎn)單迭代法(1-1)收斂的充分必要條件是迭代矩陣的譜半徑．</p>&l

12、t;p>　　定理1.3 若迭代矩陣的某種范數(shù)則（1-2-1）確定的迭代法對(duì)任意初值均收斂于方程組的唯一解。</p><p>　　特殊線性方程組迭代法的收斂性定理：</p><p>　　定理1.4 設(shè)對(duì)于方程組,若系數(shù)矩陣是嚴(yán)格對(duì)角占優(yōu)矩陣，則</p><p><b>　?。?）非奇異. </b></p><p>　

13、?。?）Gauss-Seidel迭代法收斂.</p><p>　　定理1.5 若系數(shù)矩陣對(duì)稱正定，則Gauss-Seidel迭代公式收斂.</p><p>　　例1.1 已知方程組</p><p><b>　　，</b></p><p>　　用Gauss-Seidel迭代法解此方程組的收斂性.</p>&l

14、t;p><b>　　方程組的系數(shù)矩陣</b></p><p><b>　　，</b></p><p><b>　　所以有</b></p><p><b>　　，，</b></p><p><b>　　=</b></p>

15、;<p><b>　　，</b></p><p><b>　　得</b></p><p>　　故，因此Gauss-Seidel迭代法不收斂.</p><p>　　§1.3 高斯-賽德爾迭代法的誤差分析</p><p>　　科學(xué)計(jì)算的主要過程是：對(duì)給定的實(shí)際問題建立數(shù)學(xué)模型，通

16、過已獲得的有關(guān)基本數(shù)據(jù)，建立近似數(shù)值方法，設(shè)計(jì)算法編制程序，最后上機(jī)進(jìn)行數(shù)值計(jì)算得到數(shù)值結(jié)果.其大致過程如下圖：</p><p>　　圖1.2 誤差分析表</p><p>　　定義1.2 假設(shè)某一量的標(biāo)準(zhǔn)值為近似解為，則與之差叫做近似解的絕對(duì)誤差（簡(jiǎn)稱誤差），記為，即</p><p>　　定義1.3 絕對(duì)誤差與準(zhǔn)確值之比</p><p>&l

17、t;b>　　稱為的相對(duì)誤差.</b></p><p>　　定理1.6 設(shè)是方程組的同解方程的準(zhǔn)確解，若迭代公式中迭代矩陣的某種范數(shù)，則有</p><p><b>　　1）</b></p><p><b>　　2）</b></p><p>　　第二章 高斯-賽德爾迭代法的程序設(shè)計(jì)&l

18、t;/p><p>　　第二章 高斯-賽德爾迭代法的程序設(shè)計(jì)20世紀(jì)50年代是用數(shù)字計(jì)算機(jī)求解電力系統(tǒng)潮流問題的開始階段，人們普通采用以節(jié)點(diǎn)導(dǎo)納矩陣為基礎(chǔ)的高斯-賽德爾迭代法.此方法原理簡(jiǎn)單，占用內(nèi)存量較小，編程容易實(shí)現(xiàn)，特別是對(duì)于配網(wǎng)潮流有其獨(dú)特優(yōu)勢(shì).但是此算法也有著其致命缺點(diǎn)那就是收斂速度比較慢，尤其是隨著電力系統(tǒng)的發(fā)展。網(wǎng)絡(luò)中的節(jié)點(diǎn)增多，這個(gè)問題將會(huì)更加突出.</p><p>　　本章將

19、研究高斯-賽德爾迭代法的流程圖及程序應(yīng)用.</p><p>　　§2.1 高斯-賽德爾迭代法在上機(jī)中的應(yīng)用</p><p>　　§2.1.1 高斯-賽德爾迭代法的流程圖</p><p>　　在實(shí)際應(yīng)用中，有時(shí)需解決的問題中運(yùn)算很復(fù)雜且運(yùn)算量也很大，這時(shí)我們就需要借助計(jì)算機(jī)的幫助解決實(shí)際問題，即利用高斯-賽德爾迭代法在C語言中的編程實(shí)現(xiàn).高斯-賽德

20、爾迭代法在計(jì)算機(jī)中的主要實(shí)現(xiàn)過程如下圖所示</p><p>　　圖2.3 高斯-賽德爾迭代法流程圖</p><p>　　§2.1.2高斯-賽德爾迭代法在計(jì)算機(jī)中的應(yīng)用</p><p>　　在C語言環(huán)境中解線性方程組的問題需要進(jìn)行程序編輯，如果解決每一個(gè)線性方程組都需要重新編輯程序,就沒體現(xiàn)計(jì)算機(jī)語言的簡(jiǎn)便性，所以需要一個(gè)程序使其對(duì)大多數(shù)問題都適用.<

21、/p><p>　　例2.1 設(shè)方程組的系數(shù)矩陣的對(duì)角線元素，為迭代次數(shù)容許的最大值，為容許誤差。</p><p>　　1 取初始向量令k=0.</p><p>　　2 對(duì)i=1,2,…,n計(jì)算 </p><p>　　3 如果則輸出結(jié)束；否則執(zhí)行4</p><p>　　4 如果則不收斂，終止程序；否則，轉(zhuǎn)2</p&g

22、t;<p><b>　　源程序：</b></p><p>　　#include <stdio.h></p><p>　　#include <math.h></p><p>　　#define N 600</p><p>　　void main()</p><p&g

23、t;<b>　　{</b></p><p><b>　　int i;</b></p><p>　　double x[4];</p><p>　　double c[4][5]={10,-1,2,0,-11,0,8,-1,3,-11,2,-1,10,0,6,-1,3,-1,11,25};</p><p>

24、;　　void GaussSeidel(double *,int,double[]);</p><p>　　GaussSeidel(c[0],4,x);</p><p>　　for(i=0;i<=3;i++)</p><p>　　printf("x[%d]=%f\n",i,x[i]);}</p><p>　　void

25、 GaussSeidel(double *a,int n,double x[])</p><p><b>　　{</b></p><p>　　int i,j,k=1;</p><p>　　double d,dx,eps;</p><p>　　for(i=0;i<=3;i++)</p><p>

26、;<b>　　while(1)</b></p><p><b>　　{eps=0;</b></p><p>　　for(i=0;i<=3;i++)</p><p><b>　　{</b></p><p><b>　　d=0;</b></p>

27、;<p>　　for(j=0;j<=4;j++)</p><p><b>　　{</b></p><p>　　if(j==i)continue;</p><p>　　d+=*(a+i*(n+1)+j)*x[j];</p><p><b>　　}</b></p>&l

28、t;p>　　dx=(*(a+i*(n+1)+n)-d)/(*(a+i*(n+1)+i));</p><p>　　eps+=fabs(dx-x[i]);</p><p><b>　　x[i]=dx;</b></p><p><b>　　}</b></p><p>　　if(eps<1e-6

29、)</p><p>　　{printf("迭代次數(shù)是:%d\n",k);return;}</p><p><b>　　if(k>N)</b></p><p><b>　　{</b></p><p>　　printf("迭代發(fā)散n\n");</p&g

30、t;<p><b>　　return;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　輸出結(jié)果</b><

31、/p><p><b>　　結(jié)果分析：</b></p><p>　　從輸出結(jié)果可以看出此方程組的迭代次數(shù)為1，此時(shí)能得到精確結(jié)果是</p><p>　　x[0]=-1.467391,x [1]=-2.358696,x[2] =0.657609,x[3] =2.842391</p><p>　　從結(jié)果和原有知識(shí)可以知道其系數(shù)矩陣

32、是嚴(yán)格對(duì)角占優(yōu)的。所以此迭代解法有很好的收斂性.</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 賀俐、陳桂興.計(jì)算方法[M].武漢水利電力大學(xué)出版社.1998-8-1</p><p>　　[2] 袁慰平等.計(jì)算方法與實(shí)習(xí)[M].東南大學(xué)出版社.2000-7-1</p><p>　　[3] 徐士

33、良.數(shù)值方法與計(jì)算機(jī)實(shí)現(xiàn)[M].清華大學(xué)出版社.2006-2-1</p><p>　　[4] 李炳釗.數(shù)值分析基礎(chǔ)[M].上海:同濟(jì)大學(xué)出版,1998. </p><p>　　[5] 張光澄. 實(shí)用數(shù)值分析[M].四川:四川大學(xué)出版,2004. </p><p>　　[6] 劉春鳳.應(yīng)用數(shù)值分析[M].北京: 冶金工業(yè)出版社,2005</p><

34、p><b>　　附錄 C語言編程</b></p><p><b>　　源程序</b></p><p>　　#include <stdio.h></p><p>　　#include <string.h></p><p>　　#include <math.h>

35、;</p><p>　　#include <stdlib.h></p><p>　　#define N 3</p><p><b>　　main()</b></p><p><b>　　{</b></p><p>　　int i,j,k,s;</p>

36、<p>　　float a[N][N]={0},L[N][N]={0},U[N][N]={0},sigma1,sigma2;</p><p>　　for(i=0;i<N;i++)</p><p><b>　　{</b></p><p>　　L[i][i]=1;</p><p><b>　　}&

37、lt;/b></p><p>　　for(i=0;i<N;i++)</p><p><b>　　{</b></p><p>　　printf("請(qǐng)輸入矩陣第%d行元素：\n",i+1);</p><p>　　for(j=0;j<N;j++)</p><p>　

38、　scanf("%f",&a[i][j]);</p><p><b>　　}</b></p><p>　　for(i=0;i<N;i++)</p><p><b>　　{</b></p><p>　　U[0][i]=a[0][i];</p><p

39、>　　L[i][0]=a[i][0]/U[0][0];</p><p><b>　　}</b></p><p>　　for(k=1;k<N;k++)</p><p><b>　　{</b></p><p>　　for(j=k;j<N;j++)</p><p>

40、;<b>　　{</b></p><p><b>　　sigma1=0;</b></p><p>　　for(s=0;s<=k-1;s++)</p><p>　　sigma1+=L[k][s]*U[s][j];</p><p>　　U[k][j]=a[k][j]-sigma1;</p&g

41、t;<p><b>　　}</b></p><p>　　for(i=k;i<N;i++)</p><p><b>　　{</b></p><p><b>　　sigma2=0;</b></p><p>　　for(s=0;s<=k-1;s++)<

42、/p><p>　　sigma2+=L[i][s]*U[s][k];</p><p>　　L[i][k]=(a[i][k]-sigma2)/U[k][k];</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("

43、;a矩陣為：\n");</p><p>　　for(i=0;i<N;i++)</p><p><b>　　{</b></p><p>　　for(j=0;j<N;j++)</p><p>　　printf("%5.1f ",a[i][j]);</p><p&g

44、t;　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("L矩陣為：\n");</p><p>　　for(i=0;i<N;i++)</p><p><b>　　{</b></p>&l

45、t;p>　　for(j=0;j<N;j++)</p><p>　　printf("%5.1f ",L[i][j]);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("U矩陣為：\n&q

46、uot;);</p><p>　　for(i=0;i<N;i++)</p><p><b>　　{</b></p><p>　　for(j=0;j<N;j++)</p><p>　　printf("%5.1f ",U[i][j]);</p><p>　　printf