第四章解線性方程組的迭代法

第一節(jié)迭代法概述直接法比較適用于中小型方程組對于高階方程組，一般使用迭代法一、迭代法的基本思想構造一串收斂到解的序列，即建立一種從已有近似解計算新的近似解的規(guī)則。二、迭代法的一般形式對線性方程組Ax=b其中A=(aij)為n×n階非奇異陣，b=(b1,﹒﹒﹒,bn)T構造形如：

x=Mx+g同解方程組，其中M為n階方陣，。任取初始向量代入迭代公式：

產生向量序列{x(k)},當x充分大時，以x(k)作為方程組Ax=b的近似解，這就是求解線性方程組的單步定常線性迭代法。M為迭代矩陣。三、向量序列與矩陣序列的收斂性定義：設{x(k)}為中的向量序列，如果：

則稱序列{x(k)}收斂與x，記為定理1：中的向量序列{x(k)}收斂于中的向量x，當且僅當其中，定義：設{A(k)}為n階方陣序列，A為n階方陣。如果：則稱序列{A(k)}收斂于矩陣A,記為定理2：設，均為n階方陣，則矩陣序列{A(k)}收斂于矩陣A的充要條件為第二節(jié)雅可比（Jacobi）迭代法設有方程：如系數(shù)矩陣非奇異，不妨設

方程可化為：其中若記：如用系數(shù)矩陣表示則其中則方程可化為：選取初始向量代入上式右端，得到一新的向量，記為即：依次代入使得上述迭代法稱為Jacobi迭代，又叫簡單迭代法。算法1、輸入，維數(shù)n，，最大容許迭代次序N。2、置3、對4、若，輸出，停機，否則轉（5）。5、若，置，轉3，否則，輸出失敗信息。例題用Jacobi迭代法求解線性方程組解：取系數(shù)矩陣故有：取，代入迭代公式得如此下去，迭代結果如下：kx1kx2k01234567890.00007.20009.710010.570010.853510.951010.983410.994410.998110.99940.00008.300010.700011.570011.853411.951011.983411.998111.994111.9994x3k0.00008.400011.500012.482012.828212.941412.950412.993412.997812.9992方程組的精確解為：functionX=jacobi(A,B,P,delta,max1)N=length(B)fork=1:max1forj=1:NX(j)=(B(j)-A(j,[1:j-1,j+1:N])*P([1:j-1,j+1:N]))/A(j,j)enderr=abs(norm(X'-P))relerr=err/(norm(X)+eps)P=X'if(err<delta)|(relerr<delta)breakendend

X=X'第三節(jié)高斯-賽德爾（Gauss-Seidel）迭代法將上一節(jié)中迭代公式（3）用方程組表示為：如把迭代公式改寫為：即每算出一個新近似解的分量xik+1，再算下一個分量xi+1k+1時，用新的分量xik+1

代替老分量xik

進行計算。這樣，在整個計算過程中，只需用n個單元存儲近似解分量。選取初始向量x(0),用迭代公式（1）產生近似解序列{x(k)}的方法被稱為Gauss-Seidel迭代法。將迭代公式用矩陣表示：其中：移項得：因為，所以存在，上式可改寫成：如果用矩陣A表示則：

則于是：這樣將上式代入式(4)其中矩陣為Gauss-Seidel迭代法的迭代矩陣。算法：1、輸入，初始迭代向量維數(shù)n，，最大容許迭代次序N。2、置算法3、計算

4、若，輸出，停機，否則轉（5）。5、若，置，轉3，否則，輸出失敗信息。例題

用Gauss-Seidel迭代法求解線性方程組如此下去，迭代結果如下：kx1kx2k01234560.00007.200010.430810.931310.991310.998910.99990.00009.020011.671911.957211.994711.999311.9999x3k0.000011.644012.820512.977812.997212.999613.0000方程組的精確解為：結論：1、在例1計算中，使用Gauss-Seidel迭代法效果比Jacobi效果好。2、對實際問題，二者收斂快慢不一。NORMMatrixorvectornorm.Formatrices...NORM(X)isthelargestsingularvalueofX,max(svd(X)).NORM(X,2)isthesameasNORM(X).NORM(X,1)isthe1-normofX,thelargestcolumnsum,=max(sum(abs((X)))).NORM(X,inf)istheinfinitynormofX,thelargestrowsum,=max(sum(abs((X')))).NORM(X,'fro')istheFrobeniusnorm,sqrt(sum(diag(X'*X))).NORM(X,P)isavailableformatrixXonlyifPis1,2,infor'fro'.

Forvectors...NORM(V,P)=sum(abs(V).^P)^(1/P).NORM(V)=norm(V,2).NORM(V,inf)=max(abs(V)).NORM(V,-inf)=min(abs(V)).functionX=gseid(A,B,P,delta,max1)%inputAistheNxNnonsingularmatrix%BisanNx1matrix%PisanNx1matrix,theinitialguess%deltaisthetoleranceforP%outputXisanNx1matrix(results)

N=length(B);fork=1:max1forj=1:Nifj==1X(1)=(B(1)-A(1,2:N)*P(2:N))/A(1,1);elseifj==NX(N)=(B(N)-A(N,1:N-1)*(X(1:N-1))')/A(N,N);else

%XcontainsthekthapproximationsandPthe(k-1)st

X(j)=(B(j)-A(j,1:j-1)*X(1:j-1)-A(j,j+1:N)*P(j+1:N))/A(j,j)

endenderr=abs(norm(X'-P));%relerr=err/(norm(X)+eps);

P=X';

if(err<delta)%|(relerr<delta)

breakendendX=X'第四節(jié)超松弛迭代（SOR）法

為加速迭代過程的收斂，通過引入參數(shù)，在Gauss-Seidel迭代的基礎上得到一種新的迭代法即SOR法。記其中由Gauss-Seidel迭代法中的（1）式給出，則視為Gauss-Seidel迭代的修正項，則修正后的近似解可表示為：所謂的松弛法是將乘以一個參數(shù)因子作為修正項而得到新的近似解：即：其中為松弛因子。低松弛Gauss-Seidel迭代超松弛法迭代算法1、輸入，維數(shù)n，，參數(shù)，最大容許迭代次序N。

2、置3、對4、若，輸出，停機，否則轉（5）。5、若，置，轉3，否則，輸出失敗信息。例題用Gauss-Seidel迭代法求解線性方程組取迭代初值，如此下去，迭代結果如下：kx1kx2k01234561.00008.150011.117511.027510.996111.000211.00001.000010.146512.234611.992911.999911.999911.9999x3k1.000013.165213.060912.998412.999312.999313.0000方程組的精確解為：注：松弛因子的選取對收斂速度影響極大，但目前無可供實用的計算最佳松弛因子的方法。實際計算時，通常是系數(shù)矩陣的性質及計算經驗，通過試算來確定松弛因子的值。如沿用系數(shù)矩陣A的分裂記號，則迭代公式表示為：故有于是有：迭代矩陣為：定理1：對線性方程組Ax=b()此方程組的松弛法收斂的充要條件是定理2：設解線性方程組Ax=b（）的松弛方法收斂，則必有。定理2證明：設松弛法的迭代矩陣有特征值。因為由定理1，松弛法收斂必有則所以即例題取，代入迭代公式得x1kx2k01234567890.0000-83.0000-359.0000

-2.3410*103-1.6798*104-4.0927

*1040.0000-42.0000-319.0000-2.0130*103-0.6238*104-3.7096*104x3k0.0000-72.0000-466.0000-1.7075*103-1.0770*104-8.0943*104k第五節(jié)迭代法的收斂條件一、矩陣的譜半徑二、迭代法的收斂條件三、特殊系數(shù)矩陣迭代收斂的判定條件四、誤差估計第五節(jié)迭代法的收斂條件一、矩陣的譜半徑定義：設A為n階方陣，為A的特征值，稱特征值模的最大值為矩陣的A的譜半徑，記為（）稱為矩陣A的譜。由特征值的定義知：的譜為（）（）因而定理1：設A為任意n階方陣，為任意由向量范數(shù)誘導出的矩陣范數(shù)，則[證明]：對A的任一特征值及相應的特征值，都有：因為為非零向量，于是有由的任意性即得矩陣的譜半徑與范數(shù)的關系定理2：設A為n階方陣，則對任意正數(shù)，存在一種范數(shù)，使得注：對任意n階方陣A，一般不存在矩陣范數(shù)，使得但若A為對稱陣，則有。定理3：設A為n階方陣，則的充要條件為。證明：必要性：若由定義得：而于是有極限存在原則，有所以充分性：若，取，由定理2可知，存在一種矩陣范數(shù)，使得而所以二、迭代法的收斂條件定理4：對任意初始向量及任意，由迭代公式：產生的向量序列收斂的充要條件是：證明：設存在n維向量，使得：滿足：由迭代公式得：于是有：

因為的任意性，如上式成立，則必有：由定理3得：必要性：若，則不是M的特征值，因而有，于是對于任意n維向量g,方程組有唯一解，記為，即且又因為所以對任意初始向量，都有即向量序列收斂到例題：對于系數(shù)矩陣試分別討論Jacobi迭代法和

Seidel迭代關于A,B的收斂性10、關于系數(shù)矩陣A(1)對Jacobi迭代法，由于故有即，則所以Jacobi迭代法收斂（2）對Seidel迭代法，由于則有即有，則所以Seidel迭代法發(fā)散20、關于系數(shù)矩陣B(1)對Jacobi迭代法，由于故有則所以Jacobi迭代法發(fā)散（2）對Seidel迭代法，由