Jacobi 迭代法與GaussSeidel迭代法算法比較_第1頁
Jacobi 迭代法與GaussSeidel迭代法算法比較_第2頁
Jacobi 迭代法與GaussSeidel迭代法算法比較_第3頁
Jacobi 迭代法與GaussSeidel迭代法算法比較_第4頁
Jacobi 迭代法與GaussSeidel迭代法算法比較_第5頁
已閱讀5頁,還剩5頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、Jacobi 迭代法與Gauss-Seidel迭代法算法比較 目錄1 引言11.1 Jacobi迭代法21.2 Gauss-Seidel迭代法21.3 逐次超松弛(SOR)迭代法32算法分析33 結(jié)論54 附錄程序5參考文獻8Jacobi 迭代法與Gauss-Seidel迭代法比較1 引言 解線性方程組的方法分為直接法和迭代法,直接法是在沒有舍入誤差的假設(shè)下,能在預(yù)定的運算次數(shù)內(nèi)求得精確解,而迭代法是構(gòu)造一定的遞推格式,產(chǎn)生逼近精確值的序列。這兩種方法各有優(yōu)缺點,直接法普遍適用,但要求計算機有較大的存儲量,迭代法要求的存儲量較小,但必須在收斂性得以保證的情況下才能使用。對于高階方程組,如一些偏

2、微分方程數(shù)值求解中出現(xiàn)的方程組,采用直接法計算代價比較高,迭代法則簡單又實用,所以比較受工程人員青睞。迭代法求解方程組就是構(gòu)造一個無限的向量序列,使它的極限是方程組的解向量。即使計算機過程是精確的,迭代法也不能通過有限次算術(shù)運算求得方程組的精確解,而只能逐步逼近它。因此迭代法存在收斂性與精度控制的問題。迭代法是常用于求解大型稀疏線性方程組(系數(shù)矩陣階數(shù)較高且0元素較多),特別是某些偏微分方程離散化后得到的大型稀疏方程組的重要方法。設(shè)n元線性微分方程組 (1) 的系數(shù)矩陣A非奇異,右端向量,因而方程組有唯一的非零解向量。而對于這種線性方程組的近似解,前輩們發(fā)展研究了許多種有效的方法,有Jacob

3、i迭代法、GaussSeidel迭代法,逐次超松弛迭代法(SOR法),這幾種迭代方法均屬一階線性定常迭代法,即若系數(shù)矩陣A分解成兩個矩陣N和P的差,即;其中N為可逆矩陣,線性方程組(1)化為:可得到迭代方法的一般公式: (2)其中:,對任取一向量作為方程組的初始近似解,按遞推公式產(chǎn)生一個向量序列,.,.,當(dāng)足夠大時,此序列就可以作為線性方程組的近似解。 一階定常迭代法收斂的充分必要條件是: 迭代矩陣G的譜半徑小于1,即;又因為對于任何矩陣范數(shù)恒有G,故又可得到收斂的一個充分條件為:G< 1。1.1 Jacobi迭代法若D為A的對角素構(gòu)成的對角矩陣,且對角線元素全不為零。可以將系數(shù)矩陣A分

4、解為: 其中,D為系數(shù)矩陣A的對角元素構(gòu)成的對角陣,L為嚴格下三角陣,U為嚴格上三角陣。在迭代法一般形式中,取,形成新的迭代公式,其中任取,則Jacobi迭代的迭代公式為: (3)式中: ; , 稱為Jacobi迭代矩陣. 其計算公式為: , (4) 如果迭代矩陣的譜半徑,則對于任意迭代初值,Jacobi迭代法收斂;如果GJ<1,則Jacobi迭代法收斂;如果方程組的系數(shù)矩陣是主對角線按行或按列嚴格占優(yōu)陣,則用Jacobi迭代法求解線性方程組必收斂。1.2 Gauss-Seidel迭代法從Jacobi迭代可以看出,用計算時,需要同時保留這兩個向量。事實上如果每次獲得的分量能夠在計算下一個

5、分量時及時更新的話,既節(jié)省了存儲單元,又能使迭代加速,這就是Gauss-Seidel方法。對于非奇異方程組,若D為A的對角素構(gòu)成的對角矩陣,且對角線元素全不為零;系數(shù)矩陣A的一個分解: (5)在迭代法一般形式中,取,形成新的迭代公式,其中任取,則Gauss-Seidel迭代法的迭代公式為: (6)上式中: 是其右端常數(shù)項;為Gauss-Seidel迭代法的迭代矩陣,其計算公式為:, (7)若GS法收斂的充分必要條件是;如果GG<1,則GS法收斂;如果線性方程組的系數(shù)矩陣A為主對角線按行或按列嚴格占優(yōu)陣,或者為正定矩陣,則對于任意初值用GS法求解必收斂。1.3 逐次超松弛(SOR)迭代法

6、一般而言,因Jacobi迭代收斂速度不夠快,所以在工程中用的并不是太多。并且在Jacobi迭代收斂速度很慢的情況下,通常Gauss-Seidel迭代法也不會太快。可以對Gauss-Seidel迭代公式做適度修改,提高收斂速度,這就是逐次超松弛迭代法。設(shè)線性方程組的系數(shù)矩陣A滿足,。可將系數(shù)矩陣A分解為 (8)其中實常數(shù)>0稱為松弛因子。在迭代法一般形式中,取, 得到迭代公式 , (9)其中任取。這就是逐次超松弛迭代法,當(dāng)=1時該式就是高斯法。SOR法迭代矩陣是整理后得到SOR迭代法的實際計算公式為: ;(10) SOR方法收斂的充分必要條件是;如果GS<1,則SOR方法收斂;SOR

7、方法收斂的必要條件是;如果方程組的系數(shù)矩陣A是主對角線按行或者列嚴格占優(yōu)陣,則用的SOR方法求解必收斂;如果方程組的系數(shù)矩陣是正定矩陣,則用的SOR方法求解必收斂。2 算法分析例1 用雅可比迭代法求解下列方程組解 將方程組按雅可比方法寫成取初始值按迭代公式進行迭代,其計算結(jié)果如表1所示 。表1 01234567 00.720.9711.0571.08531.09511.098300.831.0701.15711.18531.19511.198300.841.1501.24821.28281.29411.2980例2 用高斯塞德爾迭代法求解例1.解 取初始值,按迭代公式進行迭代,其計算結(jié)果如下表

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

9、nclude <iostream>#include <cmath>using namespace std;/* 二維數(shù)組動態(tài)分配模板 */template <class T>T* Allocation2D(int m, int n) T *a; a = new T*m; for (int i=0; i<m; i+)ai = new Tn; return a;/* 一維數(shù)組動態(tài)分配模板 */template <class T>T* Allocation1D(int n) T *a; a = new Tn; return a;/* 求矩陣的一范

10、數(shù) */float matrix_category(float* x, int n)float temp = 0;for(int i=0; i<n; i+)temp = temp + fabs(xi);return temp;int main()const int MAX = 1000; / 最大迭代次數(shù)int i,j,k; / 循環(huán)變量int n; / 矩陣階數(shù)float* a; / 增廣矩陣float* x_0; / 初始向量float* x_k; / 迭代向量float precision; / 精度cout<<"輸入精度e:"cin>>

11、precision;/* 動態(tài)生成增廣矩陣 */cout<<endl<<"輸入系數(shù)矩陣的階數(shù),N:"cin>>n;a = Allocation2D<float>(n, n+1);/* 輸入增廣矩陣的各值 */cout<<endl<<"輸入增廣矩陣的各值:n"for(i=0; i<n; i+)for(j=0; j<n+1; j+)cin>>aij;/* 生成并初始化初始向量 */x_0 = Allocation1D<float>(n);cout<

12、;<endl<<"輸入初始向量:n"for(i=0; i<n; i+)cin>>x_0i; /* 生成迭代向量 */x_k = Allocation1D<float>(n);float temp;/* 迭代過程 */for(k=0; k<MAX; k+) for(i=0; i<n; i+)temp = 0;for(j=0; j<i; j+)temp = temp + aij * x_kj; x_ki = ain - temp;temp = 0;for(j=i+1; j<n; j+)temp = temp

13、 + aij * x_0j;x_ki = (x_ki - temp) / aii;/* 求兩解向量的差的范數(shù) */for(i=0; i<n; i+)x_0i = x_ki - x_0i;if(matrix_category(x_0,n) < precision)break;elsefor(i=0; i<n; i+)x_0i = x_ki;/* 輸出過程 */if(MAX = k)cout<<"迭代不收斂n" cout<<"迭代次數(shù)為:"<<k<<endl;cout<<"解向量為:n" for(i=0;

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論