jacobi 迭代法與gauss-seidel迭代法算法比較

1、<p>　　Jacobi 迭代法與Gauss-Seidel迭代法算法比較</p><p><b>　　目錄</b></p><p><b>　　1 引言1</b></p><p>　　1.1 Jacobi迭代法2</p><p>　　1.2 Gauss-Seidel迭代法2</

2、p><p>　　1.3 逐次超松弛（SOR）迭代法3</p><p><b>　　2算法分析3</b></p><p><b>　　3 結(jié)論5</b></p><p><b>　　4 附錄程序5</b></p><p><b>　　參考文獻

3、8</b></p><p>　　Jacobi 迭代法與Gauss-Seidel迭代法比較</p><p><b>　　1 引言 </b></p><p>　　解線性方程組的方法分為直接法和迭代法，直接法是在沒有舍入誤差的假設下，能在預定的運算次數(shù)內(nèi)求得精確解，而迭代法是構(gòu)造一定的遞推格式，產(chǎn)生逼近精確值的序列。這兩種方法各有優(yōu)缺點

4、，直接法普遍適用，但要求計算機有較大的存儲量，迭代法要求的存儲量較小，但必須在收斂性得以保證的情況下才能使用。對于高階方程組，如一些偏微分方程數(shù)值求解中出現(xiàn)的方程組，采用直接法計算代價比較高，迭代法則簡單又實用，所以比較受工程人員青睞。</p><p>　　迭代法求解方程組就是構(gòu)造一個無限的向量序列，使它的極限是方程組的解向量。即使計算機過程是精確的，迭代法也不能通過有限次算術(shù)運算求得方程組的精確解，而只能逐步逼

5、近它。因此迭代法存在收斂性與精度控制的問題。</p><p>　　迭代法是常用于求解大型稀疏線性方程組（系數(shù)矩陣階數(shù)較高且0元素較多），特別是某些偏微分方程離散化后得到的大型稀疏方程組的重要方法。設n元線性微分方程組</p><p>　　(1) </p><p>　　的系數(shù)矩陣A非奇異，右端向量,因而方程組有唯一的非

6、零解向量。而對于這種線性方程組的近似解，前輩們發(fā)展研究了許多種有效的方法，有Jacobi迭代法、Gauss—Seidel迭代法，逐次超松弛迭代法（SOR法），這幾種迭代方法均屬一階線性定常迭代法，即若系數(shù)矩陣A分解成兩個矩陣N和P的差，即；其中N為可逆矩陣，線性方程組(1)化為：</p><p>　　可得到迭代方法的一般公式：</p><p><b>　?。?）</b>

7、;</p><p>　　其中：，，對任取一向量作為方程組的初始近似解，按遞推公式產(chǎn)生一個向量序列，，...，，...，當足夠大時，此序列就可以作為線性方程組的近似解。</p><p>　　一階定常迭代法收斂的充分必要條件是: 迭代矩陣G的譜半徑小于1，即；又因為對于任何矩陣范數(shù)恒有‖G‖，故又可得到收斂的一個充分條件為：‖G‖< 1。</p><p>　　1.

8、1 Jacobi迭代法</p><p>　　若D為A的對角素構(gòu)成的對角矩陣，且對角線元素全不為零?？梢詫⑾禂?shù)矩陣A分解為： </p><p>　　其中，D為系數(shù)矩陣A的對角元素構(gòu)成的對角陣，L為嚴格下三角陣，U為嚴格上三角陣。在迭代法一般形式中，取，，形成新的迭代公式</p><p><b>　　，

9、</b></p><p>　　其中任取，則Jacobi迭代的迭代公式為：</p><p><b>　　(3)</b></p><p>　　式中: ; , 稱為Jacobi迭代矩陣. 其計算公式為: </p><p>　　， （4）</p><p>　　如果迭代矩陣的譜半

10、徑，則對于任意迭代初值，Jacobi迭代法收斂；如果‖GJ‖<1，則Jacobi迭代法收斂；如果方程組的系數(shù)矩陣是主對角線按行或按列嚴格占優(yōu)陣，則用Jacobi迭代法求解線性方程組必收斂。</p><p>　　1.2 Gauss-Seidel迭代法</p><p>　　從Jacobi迭代可以看出，用計算時，需要同時保留這兩個向量。事實上如果每次獲得的分量能夠在計算下一個分量時及時更新

11、的話，既節(jié)省了存儲單元，又能使迭代加速，這就是Gauss-Seidel方法。對于非奇異方程組，若D為A的對角素構(gòu)成的對角矩陣，且對角線元素全不為零；系數(shù)矩陣A的一個分解：</p><p><b>　　(5)</b></p><p>　　在迭代法一般形式中，取，，形成新的迭代公式</p><p><b>　　，</b><

12、;/p><p>　　其中任取，則Gauss-Seidel迭代法的迭代公式為: （6）</p><p>　　上式中: 是其右端常數(shù)項；為Gauss-Seidel迭代法的迭代矩陣，其計算公式為：</p><p>　　， （7）</p><p>　　若GS法收斂的充分必要條件是；如果‖GG‖<1,則GS法收斂；如

13、果線性方程組的系數(shù)矩陣A為主對角線按行或按列嚴格占優(yōu)陣，或者為正定矩陣，則對于任意初值用GS法求解必收斂。</p><p>　　1.3 逐次超松弛（SOR）迭代法</p><p>　　一般而言，因Jacobi迭代收斂速度不夠快，所以在工程中用的并不是太多。并且在Jacobi迭代收斂速度很慢的情況下，通常Gauss-Seidel迭代法也不會太快?？梢詫auss-Seidel迭代公式做適度修

14、改，提高收斂速度，這就是逐次超松弛迭代法。</p><p>　　設線性方程組的系數(shù)矩陣A滿足，?？蓪⑾禂?shù)矩陣A分解為</p><p><b>　　(8)</b></p><p>　　其中實常數(shù)>0稱為松弛因子。在迭代法一般形式中，取</p><p><b>　　, </b></p>

15、<p><b>　　得到迭代公式 </b></p><p><b>　　， （9）</b></p><p>　　其中任取。這就是逐次超松弛迭代法，當=1時該式就是高斯法。SOR法迭代矩陣是</p><p>　　整理后得到SOR迭代法的實際計算公式為：</p><p><b&

16、gt;　??；（10）</b></p><p>　　SOR方法收斂的充分必要條件是；如果‖GS‖<1，則SOR方法收斂；SOR方法收斂的必要條件是；如果方程組的系數(shù)矩陣A是主對角線按行或者列嚴格占優(yōu)陣，則用的SOR方法求解必收斂；如果方程組的系數(shù)矩陣是正定矩陣，則用的SOR方法求解必收斂。</p><p><b>　　2 算法分析</b></p&

17、gt;<p>　　用雅可比迭代法求解下列方程組</p><p>　　解 將方程組按雅可比方法寫成</p><p><b>　　取初始值按迭代公式</b></p><p>　　進行迭代，其計算結(jié)果如表1所示 。</p><p><b>　　表1</b></p><

18、p>　　例2 用高斯——塞德爾迭代法求解例1.</p><p>　　解 取初始值，按迭代公式</p><p>　　進行迭代，其計算結(jié)果如下表2</p><p><b>　　表2</b></p><p><b>　　3 結(jié)論</b></p><p>　　使用Ga

19、uss-Seidel迭代法迭代法，7次就可以求出方程的解，收斂速度要比Jacobi迭代法收斂快(達到同樣的精度所需迭代次數(shù)少)；但是這個結(jié)論,在一定條件下才是對的,甚至有這樣的方程組,雅可比方法收斂，而高斯—塞德爾迭代法卻是發(fā)散的.</p><p><b>　　4 附錄程序</b></p><p>　　/* 求解線性方程組--Gauss-Seidel迭代法 */<

20、;/p><p>　　#include <iostream></p><p>　　#include <cmath></p><p>　　using namespace std;</p><p>　　/* 二維數(shù)組動態(tài)分配模板 */</p><p>　　template <class T>&

21、lt;/p><p>　　T** Allocation2D(int m, int n)</p><p><b>　　{</b></p><p><b>　　T **a;</b></p><p>　　a = new T*[m];</p><p>　　for (int i=0; i&l

22、t;m; i++)</p><p><b>　　{</b></p><p>　　a[i] = new T[n];</p><p><b>　　}</b></p><p><b>　　return a;</b></p><p><b>　　}&l

23、t;/b></p><p>　　/* 一維數(shù)組動態(tài)分配模板 */</p><p>　　template <class T></p><p>　　T* Allocation1D(int n)</p><p><b>　　{</b></p><p><b>　　T *a;&

24、lt;/b></p><p>　　a = new T[n];</p><p><b>　　return a;</b></p><p><b>　　}</b></p><p>　　/* 求矩陣的一范數(shù) */</p><p>　　float matrix_category(

25、float* x, int n)</p><p><b>　　{</b></p><p>　　float temp = 0;</p><p>　　for(int i=0; i<n; i++)</p><p><b>　　{</b></p><p>　　temp = te

26、mp + fabs(x[i]);</p><p><b>　　}</b></p><p>　　return temp;</p><p><b>　　}</b></p><p>　　int main()</p><p><b>　　{</b></p&

27、gt;<p>　　const int MAX = 1000; // 最大迭代次數(shù)</p><p>　　int i,j,k; // 循環(huán)變量</p><p>　　int n; // 矩陣階數(shù)</p><p>　　float** a; // 增廣矩陣</p>&

28、lt;p>　　float* x_0; // 初始向量</p><p>　　float* x_k; // 迭代向量</p><p>　　float precision; // 精度</p><p>　　cout<<"輸入精度e:";</p><p>　

29、　cin>>precision;</p><p>　　/* 動態(tài)生成增廣矩陣 */</p><p>　　cout<<endl<<"輸入系數(shù)矩陣的階數(shù)，N：";</p><p><b>　　cin>>n;</b></p><p>　　a = Allocat

30、ion2D<float>(n, n+1);</p><p>　　/* 輸入增廣矩陣的各值 */</p><p>　　cout<<endl<<"輸入增廣矩陣的各值：\n";</p><p>　　for(i=0; i<n; i++)</p><p><b>　　{</b

31、></p><p>　　for(j=0; j<n+1; j++)</p><p><b>　　{</b></p><p>　　cin>>a[i][j];</p><p><b>　　}</b></p><p><b>　　}</b>

32、;</p><p>　　/* 生成并初始化初始向量 */</p><p>　　x_0 = Allocation1D<float>(n);</p><p>　　cout<<endl<<"輸入初始向量:\n";</p><p>　　for(i=0; i<n; i++)</p>

33、;<p><b>　　{</b></p><p>　　cin>>x_0[i];</p><p><b>　　}</b></p><p>　　/* 生成迭代向量 */</p><p>　　x_k = Allocation1D<float>(n);</p>

34、;<p>　　float temp;</p><p>　　/* 迭代過程 */</p><p>　　for(k=0; k<MAX; k++)</p><p><b>　　{</b></p><p>　　for(i=0; i<n; i++)</p><p><b>

35、;　　{</b></p><p><b>　　temp = 0;</b></p><p>　　for(j=0; j<i; j++)</p><p><b>　　{</b></p><p>　　temp = temp + a[i][j] * x_k[j];</p>&l

36、t;p><b>　　}</b></p><p>　　x_k[i] = a[i][n] - temp;</p><p><b>　　temp = 0;</b></p><p>　　for(j=i+1; j<n; j++)</p><p><b>　　{</b><

37、/p><p>　　temp = temp + a[i][j] * x_0[j];</p><p><b>　　}</b></p><p>　　x_k[i] = (x_k[i] - temp) / a[i][i];</p><p><b>　　}</b></p><p>　　/*

38、求兩解向量的差的范數(shù) */</p><p>　　for(i=0; i<n; i++)</p><p><b>　　{</b></p><p>　　x_0[i] = x_k[i] - x_0[i];</p><p><b>　　}</b></p><p>　　if(mat

39、rix_category(x_0,n) < precision)</p><p><b>　　{</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　else</b></

40、p><p><b>　　{</b></p><p>　　for(i=0; i<n; i++)</p><p><b>　　{</b></p><p>　　x_0[i] = x_k[i];</p><p><b>　　}</b></p>&

41、lt;p><b>　　}</b></p><p><b>　　}</b></p><p>　　/* 輸出過程 */</p><p>　　if(MAX == k)</p><p><b>　　{</b></p><p>　　cout<<&

42、quot;迭代不收斂\n";</p><p><b>　　}</b></p><p>　　cout<<"迭代次數(shù)為："<<k<<endl;</p><p>　　cout<<"解向量為：\n";</p><p>　　for(i

43、=0; i<n; i++)</p><p><b>　　{</b></p><p>　　cout<<"x"<<i<<": "<<x_k[i]<<endl;</p><p><b>　　}</b></p>

44、<p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　參考文獻</b></p><p>　　[1]顏慶津. 數(shù)值分析[M]. 北京:航空航天大學出版社，1999.</p><p>　　[2]黎建玲，簡金寶，