第6部分解線方程組迭代法對方程組做等價變換如：令，則則，我們可以構(gòu)造序列若同時：所以，序列收斂與初值的選取無關(guān)定義：（收斂矩陣）定理：矩陣G為收斂矩陣，當(dāng)且僅當(dāng)G的譜半徑<1由知，若有某種范數(shù)則，迭代收斂6.1Jacobi迭代格式很簡單：Jacobi迭代算法1、輸入系數(shù)矩陣A和向量b，和誤差控制eps2、x1={0,0,…..,0},x2={1,1,…..,1}//賦初值3、while(||x1-x2||>eps){

x1=x2;//x1是第k步，x2是第k+1步

for(i=0;i<n;i++){

x2[i]=0;

for(j=0;j<i;j++){

x2[i]+=A[i][j]*x1[j]

}

for(j=i+1;j<n;j++){

x2[i]+=A[i][j]*x1[j]

}

x2[i]=-(x2[i]-b[i])/A[i][i]

}

}4、輸出解x2

迭代矩陣易知，Jacobi迭代有

收斂條件

迭代格式收斂的充要條件是G的譜半徑<1。對于Jacobi迭代，我們有一些保證收斂的充分條件定理：若A滿足下列條件之一，則Jacobi迭代收斂。①A為行對角占優(yōu)陣②A為列對角占優(yōu)陣③A滿足證明：②A為列對角占優(yōu)陣，則AT為行對角占優(yōu)陣，有＃證畢6.2Gauss－Seidel迭代在Jacobi迭代中，使用最新計算出的分量值是否是原來的方程的解？Gauss-Siedel迭代算法1、輸入系數(shù)矩陣A和向量b，和誤差控制eps2、x1={0,...,0},x2={1,1,…..,1}//賦初值3、while(||x1-x2||>eps){x1=x2;//x1是第k步，x2是第k+1步for(i=0;i<n;i++){t=0.0for(j=0;j<i;j++){

t+=A[i][j]*x2[j]}for(j=i+1;j<n;j++){

t+=A[i][j]*x2[j]}x2[i]=-(t-b[i])/A[i][i]}}4、輸出解x2

迭代矩陣記

迭代矩陣A=(D+L)-(-U)

收斂條件迭代格式收斂的充要條件是G的譜半徑<1。我們看一些充分條件定理：若A滿足下列條件之一，則Gauss-Seidel迭代收斂。①A為行或列對角占優(yōu)陣②A對稱正定陣證明：設(shè)G的特征多項式為，則為對角占優(yōu)陣，則時為對角占優(yōu)陣即即＃證畢注：二種方法都存在收斂性問題。有例子表明：Gauss-Seidel法收斂時，Jacobi法可能不收斂；而Jacobi法收斂時，Gauss-Seidel法也可能不收斂。1、預(yù)處理2、格式3、結(jié)果1、Jacobi迭代特征值為2、Gauss-Seidel迭代6.3松弛迭代記則可以看作在前一步上加一個修正量。，有對Gauss-Seidel迭代格式若在修正量前乘以一個因子是否是原來的方程的解？寫成分量形式，有松弛迭代算法1、輸入系數(shù)矩陣A、向量b和松弛因子omega，和誤差控制eps2、x1={0,...,0};x2={1,1,…..,1}//賦初值3、while(||x1-x2||>eps){x1=x2;//x1是第k步，x2是第k+1步for(i=0;i<n;i++){temp=0for(j=0;j<i;j++){temp+=A[i][j]*x2[j]}for(j=i+1;j<n;j++){temp+=A[i][j]*x2[j]}temp=-(x2[i]-b[i])/A[i][i]x2[i]=(1-omega)*x2[i]+omega*temp}}4、輸出解x2

迭代矩陣定理：松弛迭代收斂定理：A對稱正定，則松弛迭代收斂

SOR方法收斂的快慢與松弛因子的選擇有密切關(guān)系.但是如何選取最佳松弛因子,即選取=*,使(G)達(dá)到最小,是一個尚未很好解決的問題.實際上可采用試算的方法來確定較好的松弛因子.經(jīng)驗上可取1.4<<1.6.Lab06線性方程組求根的迭代法1.編寫Gauss-Seidel迭代和SOR迭代的通用程序2.用如上程序求根，并打印迭代步數(shù)和根。3.取松弛因子為{i/50,i=1,2,…,99}，試給出一個最佳的值SampleOutput(representsaspace)Gauss-Seidel迭代，根和迭代步數(shù)為0.1...0.95SOR迭代，迭代步數(shù)為1,100...99,5000

定理若SOR方法收斂,則0<<2.

證設(shè)SOR方法收斂,則(G)<1,所以

|det(G)|=|12…n|<1而det(G)=det[(D+L)-1((1-)D-U)]

=det[(I+D-1L)-1]det[(1-)I-D-1U)]=(1-)n于是

|1-|<1,或0<<2

定理設(shè)A是對稱正定矩陣,則解方程組Ax=b的SOR方法,當(dāng)0<<2時收斂.

證設(shè)是