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

目:高斯-賽德爾迭代法的算法及程序設(shè)計(jì)摘要本文通過理論與實(shí)例對線性方程組的解法、收斂性及誤差分析進(jìn)行了探討.在對線性方程組數(shù)值解法的討論下用到了高斯-賽德爾迭代法，進(jìn)一步研究和總結(jié)了高斯-賽德爾迭代法的理論與應(yīng)用，使我們在分析問題與編輯程序時(shí)能更好的把握對高斯-賽德爾迭代法的應(yīng)用。關(guān)鍵詞Gauss-Seidel迭代法；收斂性；誤差分析；流程圖；Mathematica編程目錄TOC\o"1-5"\h\z\o"CurrentDocument"第一章高斯-賽德爾迭代法1\o"CurrentDocument"§1.1高斯-賽德爾迭代法的提出1§1.1.1高斯-賽德爾迭代法的思想理論1\o"CurrentDocument"§1.1.2高斯-賽德爾迭代法的定義及表達(dá)形式2\o"CurrentDocument"§1.2高斯-賽德爾迭代法的收斂性1\o"CurrentDocument"§1.3高斯-賽德爾迭代法的誤差分析1\o"CurrentDocument"第二章高斯-賽德爾迭代法的程序設(shè)計(jì)1\o"CurrentDocument"§2.1高斯-賽德爾迭代法在上機(jī)中的應(yīng)用1§2.1.1高斯-賽德爾迭代法的流程圖1§2.1.2高斯-賽德爾迭代法的源程序1參考文獻(xiàn)錯(cuò)誤！未定義書簽。附錄錯(cuò)誤！未定義書簽。

第一章高斯-賽德爾迭代法考慮線性方程組Ax=b其中A為非奇異矩陣，對于由工程技術(shù)中產(chǎn)生的大型稀疏矩陣方程組（A的階數(shù)〃很大但零元素很多），利用迭代法求解線性方程組Ax=b是合適的.在計(jì)算機(jī)內(nèi)存和運(yùn)算兩方面，迭代法通常都可利用A中有大量零元素的特點(diǎn).本章將介紹迭代法中的高斯-賽德爾法的思想理論、收斂性及誤差分析.§1.1高斯"賽德爾迭代法的提出§1.1.1高斯-賽德爾迭代法的思想理論在研究雅可比迭代法時(shí)，計(jì)算XE時(shí)，已得XE1）,xd1）,...,x?+1）（這些分別為i12i-1x,X，…，x的第k+1次近似），Gauss-Seidel迭代法認(rèn)為在計(jì)算時(shí)啟用新值，從而產(chǎn)12i-1生x（k+x（k+1）

i1—（ba1iiZax（k+1）j=1-Z具體原理如下圖所示圖1.1基本迭代原理§1.1.2高斯■賽德爾迭代法的定義及表達(dá)形式定義1.1我們注意到在雅可比迭代法中并沒有對新算出的分量xk+1，1Xk+1進(jìn)行充分利用.不妨設(shè)想，在迭代收斂的條件下，我們把i-11x(k+1)=(-ax(k)-ax(k)?.--ax(k)+b)1a1211331nn1111(-ax(k)-(-ax(k)-ax(k)??--ax(k)+ba2112332nn2221X(k+1)n(-ax(k)-ax(k)??--aX(k+1)nan1122n,n-1n-1nnn式中第一個(gè)方程算出的xk+1立即投入到第二個(gè)方程中，代替x(k)進(jìn)行計(jì)算，當(dāng)xk+1算112出后代替x(k)馬上投入到第三個(gè)方程中計(jì)算，依次進(jìn)行下去，這樣也許會(huì)得到更好的2收斂效果.根據(jù)這種思路建立的一種新的迭代格式，我們稱為高斯-賽德爾(Gauss-Seide1)迭代公式，高斯二賽德爾迭代法的分量形式：1x(k+1)1x(k+1)=1(-ax(k)-ax(k)..--ax(k)+b)a1211331n111+1)a22ax(k+1)-ax(k)…-a2112332x(k)+bx(k+1)—ax(k+1)…—a1x(k+1)—ax(k+1)…—a1122n,n-1x(k+1)+bn-1n高斯-賽德爾迭代法的矩陣形式：x(k+1)=Bx(k)+f,(k=0,1,2,)其中B=(D-L)-1U，f=(D-L)-1bB稱為高斯-賽德爾迭代矩陣，f稱為高斯-賽德爾迭代常量..§1.2高斯■賽德爾迭代法的收斂性根據(jù)上節(jié)所述，高斯-賽德爾迭代法的迭代格式為(1-1)x(k+1)=Bx(k)+f,(k=0,1,2,)其中B=(D-L)-1U，f=(D-L)-1b-(1-1)本節(jié)要討論的問題就是任意選取初始值x(0)，利用迭代格式(IT)得到的向量序列{x(k)}是否一定收斂，如果收斂的話需要滿足什么條件？下面我們給出一般迭代收斂的條件：定理1?2簡單迭代法(1-1)收斂的充分必要條件是迭代矩陣B的譜半徑p(B)<1.定理1.3若迭代矩陣b的某種范數(shù)|B||<1則(1-2-1)確定的迭代法對任意初值X(0)均收斂于方程組x=Bx+f的唯一解x*。特殊線性方程組迭代法的收斂性定理：定理1.4設(shè)對于方程組Ax=b，若系數(shù)矩陣A是嚴(yán)格對角占優(yōu)矩陣，則A非奇異.Gauss-Seidel迭代法收斂.定理1.5若系數(shù)矩陣A對稱正定，^UGauss-Seidel迭代公式收斂.例1.1已知方程組x+2x-2x=1<x+x+x=1，2x+2x+x=1TOC\o"1-5"\h\z1123用Gauss-Seidel迭代法解此方程組的收斂性.方程組的系數(shù)矩陣2-20IIIA=111，21所以有「1一0「0-22一D=1，L=-10，U=0-11_-2-200-100]-1「0-22一B=(D-L)-1U=1100-1221|_0_「0-22_=2-32X-22det(XI-B)=C0X-23，00X-2

故人(B)=2>1，因此Gauss-Seidel迭代法不收斂.§1.3高斯-賽德爾迭代法的誤差分析科學(xué)計(jì)算的主要過程是：對給定的實(shí)際問題建立數(shù)學(xué)模型，通過已獲得的有關(guān)基本數(shù)據(jù)，建立近似數(shù)值方法，設(shè)計(jì)算法編制程序，最后上機(jī)進(jìn)行數(shù)值計(jì)算得到數(shù)值結(jié)果.其大致過程如下圖：圖1.2圖1.2誤差分析表則X與X*之差叫做近似解X的絕定義1.2假設(shè)某一量的標(biāo)準(zhǔn)值為x近似解為X*對誤差則X與X*之差叫做近似解X的絕￡(X)=X一X*定義1.3絕對誤差與準(zhǔn)確值之比￡(X)=￡(X)一X一X*,X尹0'XX稱為X*的相對誤差.定理1.6設(shè)X*是方程組Ax=b的同解方程X=BX+f的準(zhǔn)確解，若迭代公式X(k+1)=Bxk)+f中迭代矩陣B的某種范數(shù)|B||=q＜1，則有||x(k)一x』＜-q-1|x(°一x(k-1)||1-qX(k)—X』＜-^^llx⑴—X(0)1-q第二章高斯-賽德爾迭代法的程序設(shè)計(jì)第二章高斯-賽德爾迭代法的程序設(shè)計(jì)20世紀(jì)50年代是用數(shù)字計(jì)算機(jī)求解電力系統(tǒng)潮流問題的開始階段，人們普通采用以節(jié)點(diǎn)導(dǎo)納矩陣為基礎(chǔ)的高斯-賽德爾迭代法.此方法原理簡單，占用內(nèi)存量較小，編程容易實(shí)現(xiàn)，特別是對于配網(wǎng)潮流有其獨(dú)特優(yōu)勢.但是此算法也有著其致命缺點(diǎn)那就是收斂速度比較慢，尤其是隨著電力系統(tǒng)的發(fā)展。網(wǎng)絡(luò)中的節(jié)點(diǎn)增多，這個(gè)問題將會(huì)更加突出.本章將研究高斯-賽德爾迭代法的流程圖及程序應(yīng)用.§2.1高斯-賽德爾迭代法在上機(jī)中的應(yīng)用§2.1.1高斯-賽德爾迭代法的流程圖在實(shí)際應(yīng)用中，有時(shí)需解決的問題中運(yùn)算很復(fù)雜且運(yùn)算量也很大，這時(shí)我們就需要借助計(jì)算機(jī)的幫助解決實(shí)際問題，即利用高斯-賽德爾迭代法在C語言中的編程實(shí)現(xiàn).高斯-賽德爾迭代法在計(jì)算機(jī)中的主要實(shí)現(xiàn)過程如下圖所示圖2.3高斯-賽德爾迭代法流程圖§2.1.2高斯-賽德爾迭代法在計(jì)算機(jī)中的應(yīng)用在C語言環(huán)境中解線性方程組的問題需要進(jìn)行程序編輯，如果解決每一個(gè)線性方程組都需要重新編輯程序，就沒體現(xiàn)計(jì)算機(jī)語言的簡便性，所以需要一個(gè)程序使其對大多數(shù)問題都適用.例2.1設(shè)方程組AX=b的系數(shù)矩陣的對角線元素(i=1,2,,n)，M為迭代次數(shù)容許的最大值，e為容許誤差。1取初始向量令k=0.2對i=1,2,…,n計(jì)算3如果則輸出結(jié)束；否則執(zhí)行44如果則不收斂，終止程序；否則，轉(zhuǎn)2源程序：#include<stdio.h>#include<math.h>#defineN600voidmain()(inti;doublex[4];doublec[4][5]={10,-1,2,0,-11,0,8,-1,3,-11,2,-1,10,0,6,-1,3,-1,11,25};voidGaussSeidel(double*,int,double[]);GaussSeidel(c[0],4,x);for(i=0;i<=3;i++)printf("x[%d]=%f\n",i,x[i]);}voidGaussSeidel(double*a,intn,doublex[])(inti,j,k=1;doubled,dx,eps;for(i=0;i<=3;i++)while(1){eps=0;for(i=0;i<=3;i++)(d=0;for(j=0;j<=4;j++)(if(j==i)continue;d+=*(a+i*(n+1)+j)*x[j];dx=(*(a+i*(n+1)+n)-d)/(*(a+i*(n+1)+i));eps+=fabs(dx-x[i]);x[i]=dx;}if(eps<1e-6){printf("迭代次數(shù)是:%d\n",k);return;}if(k>N)(printf(〃迭代發(fā)散n\n〃)；return;}}}輸出結(jié)果結(jié)果分析：從輸出結(jié)果可以看出此方程組的迭代次數(shù)為1,此時(shí)能得到精確結(jié)果是

x[0]=-1.467391,x[1]=-2.358696,x[2]=0.657609,x[3]=2.842391從結(jié)果和原有知識可以知道其系數(shù)矩陣是嚴(yán)格對角占優(yōu)的。所以此迭代解法有很好的收斂性.參考文獻(xiàn)賀俐、陳桂興.計(jì)算方法[M].武漢水利電力大學(xué)出版社.1998-8-1袁慰平等.計(jì)算方法與實(shí)習(xí)[M].東南大學(xué)出版社.2000-7-1徐士良.數(shù)值方法與計(jì)算機(jī)實(shí)現(xiàn)[M].清華大學(xué)出版社.2006-2-1李炳釗.數(shù)值分析基礎(chǔ)[M].上海：同濟(jì)大學(xué)出版,1998.張光澄.實(shí)用數(shù)值分析[M].四川：四川大學(xué)出版,2004.劉春鳳.應(yīng)用數(shù)值分析[M].北京：冶金工業(yè)出版社,2005附錄C語言編程源程序#include<stdio.h>#include<string.h>#include<math.h>#include<stdlib.h>#defineN3main()(inti,j,k,s;floata[N][N]={0},L[N][N]={0},U[N][N]={0},sigma1,sigma2;for(i=0;i<N;i++)(L[i][i]=1;}for(i=0;i<N;i++)(printf("請輸入矩陣第％d行元素：\n”,i+1);for(j=0;j<N;j++)scanf(〃%f〃,&a[i][j]);}for(i=0;i<N;i++)(U[0][i]=a[0][i];L[i][0]=a[i][0]/U[0][0];}for(k=1;k<N;k++)(for(j=k;j<N;j++)(sigma1=0;for(s=0;s<=k-1;s++)sigma1+=L[k][s]*U[s][j];U[k][j]=a[k][j]-sigma1;}for(i=k;i<N;i++)(sigma2=0;for(s=0;s<=k-1;s++)sigma2+=L[i][s]*U[s][k];L[i][k]=(a[i][k]-sigma2)/U[k][k];}printf("a矩陣為：\n〃);f