數(shù)值分析 第六章 解線性方程組的迭代法

數(shù)值分析

NumericalAnalysis第六章解線性代數(shù)方程組的迭代法鄭州大學研究生課程（2014-2015學年第一學期）

ISCM2007,BeijingChina1第六章解線性代數(shù)方程組的迭代法

§6.1引言§6.2

范數(shù)與誤差分析§6.3幾種常用的迭代格式§6.4迭代法的收斂性及誤差估計§6.5判別收斂的幾個常用條件§6.6迭代法收斂判定的應用舉例ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.1引言線性方程組的數(shù)值解法有：直接法和迭代法。直接法：在假定沒有舍入誤差的情況下，經(jīng)過有限次運算可以求得方程組的精確解；迭代法：從一個初始向量出發(fā)，按照一定的迭代格式，構造出一個趨向于真解的無窮序列。ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.1引言當A為稀疏矩陣時，直接法將破壞矩陣A的稀疏性。系數(shù)矩陣的分類第一類：低階稠密方程組，即系數(shù)矩陣的階數(shù)不高，含零元素很少，在線性代數(shù)等課程學習中通常見到的，都屬這類方程組；第二類：高階稀疏方程組，系數(shù)矩陣的階數(shù)很高，如幾百階、甚至成千上萬階，其中零元素成片分布，數(shù)量上絕對占優(yōu)。ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis迭代法適用于解大型稀疏方程組(萬階以上的方程組,系數(shù)矩陣中零元素占很大比例,而非零元按某種模式分布)問題:(1)如何構造迭代格式？

(2)迭代格式是否收斂？

(3)如何進行誤差估計？§6.1引言ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.1引言迭代法的基本思想迭代法的基本思想是將線性方程組轉化為便于迭代的等價方程組，對任選一組初始值，按迭代格式，不斷地對所得到的值進行修正，最終獲得滿足精度要求的方程組的近似解。

ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis設非奇異，，則線性方程組

有惟一解，經(jīng)過變換構造出一個等價同解方程組將上式改寫成迭代式選定初始向量,反復不斷地使用迭代式逐步逼近方程組的精確解,直到滿足精度要求為止。這種方法稱為迭代法ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis如果向量序列存在極限則稱迭代法是收斂的，否則就是發(fā)散的。收斂時，在迭代公式中當時，,則

故是方程組的解。對于給定的方程組可以構造各種迭代公式。并非全部收斂。ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2范數(shù)與誤差分析為了研究線性方程組近似解的誤差估計和迭代法的收斂性,有必要對向量及矩陣的“大小”引進某種度量----范數(shù)的概念。向量范數(shù)是用來度量向量長度的,它可以看成是二、三維解析幾何中向量長度概念的推廣。用Rn表示n維實向量空間。ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2范數(shù)與誤差分析（一、向量范數(shù)）§6.2.1向量范數(shù)定義6.2.1設XRn，Ｘ

表示定義在Rn上的一個實值函數(shù)，稱之為X的范數(shù)，它具有下列性質(zhì)：（3）三角不等式：即對任意兩個向量X、YRn，恒有

(1)正定性：即對一切XRn，X

0,Ｘ

>0(2)齊次性：即對任何實數(shù)aR，XRn，ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis注:向量范數(shù)是向量長度概念的推廣.例如是向量

x的范數(shù)常見向量范數(shù)常用的范數(shù):1-范數(shù)2-范數(shù)

-范數(shù)ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析例5.7.1證明||x||2

是Rn

上的一種范數(shù)證：先證柯西不等式:|xTy|≤||x||2·||y||2對任意實數(shù)λ,有(x-λy)T(x-λy)≥0xTx–2λxTy+λ2yTy≥0|xTy|2

–(xTx)(yTy)≤0|xTy|≤||x||2·||y||2判別式ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis(三角不等式成立)(正定性成立)(齊次性成立)ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis例5.7.2.范數(shù)意義下的單位向量:X=[x1,x2]T1-11||X||1=111-1-1||X||2=1-111-1-1||X||∞=1ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析當不需要指明使用哪一種向量范數(shù)時，就用記號||.||泛指任何一種向量范數(shù)。有了向量的范數(shù)就可以用它來衡量向量的大小和表示向量的誤差。設x*為Ax=b的精確解，x為其近似解，則其絕對誤差可表示成||x-x*||，其相對誤差可表示成ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis例5.7.3

證明對任意同維向量x,y有

證：

即ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis例5.7.4

設x=(1,0,-1,2)T,計算

解:=1+0+|-1|+2=4ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析有限維空間的范數(shù)均等價ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis定理5.7.1

對于任意向量x,有證:∵

即

當p→∞，

∴ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis

定理5.7.2

（向量范數(shù)的等價性）設為上任意兩種向量范數(shù),則存在常數(shù)C1,,C2>0,使得對任意恒有有限維空間的范數(shù)等價定理ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis定義5.7.2(向量序列的極限)設為中的一向量序列，,記。如果(i=1,2,…,n)，則稱收斂于向量，記為ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis定理5.7.3

其中為向量中的任一種范數(shù)。

證由于

而對于上的任一種范數(shù),由定理5.7.2知存在常數(shù)C1，C2，使于是可得向量序列依范數(shù)收斂與依坐標收斂是等價的。ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis定義在Rn上的向量范數(shù)

是變量X分量的

連續(xù)函數(shù)。定理5.7.4ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析（二、矩陣范數(shù)）§5.7.2矩陣范數(shù)ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析證明:(1)ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析證明:(2)矩陣范數(shù)和向量范數(shù)的相容性ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysisISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis定理5.7.6

設n

階方陣A=(aij)nn，則（Ⅰ）與相容的矩陣范數(shù)是（Ⅱ）與相容的矩陣范數(shù)是其中1為矩陣ATA的最大特征值。（Ⅲ）與相容的矩陣范數(shù)是1-范數(shù)（列范數(shù)）2-范數(shù)（譜范數(shù)）-范數(shù)（行范數(shù)）ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析與前述三種向量范數(shù)相容的三種矩陣范數(shù)：ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析

,X=[-35]T,求A、X的“1-范數(shù)”,“2-范數(shù)”和“無窮大范數(shù)”例5.7.5ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析1=26.1803,2=3.8197ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析矩陣的譜半徑ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis定理5.7.8

對給定方陣G,若,則為非奇異矩陣,且

證:用反證法,若為奇異矩陣,則存在非零向量x,使,即有由相容性條件得

由于,兩端消去,有,與已知條件矛盾,假設不成立,命題得證。又由于有

即

將G分別取成G和-G，再取范數(shù)

又已知，有

ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis定義5.7.6設有矩陣序列及,如果個數(shù)列極限存在且有則稱收斂于，記為ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis例5.7.6且設，考查其極限.

解由于，當時，有設有矩陣序列所以ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis定理5.7.9設,則(零矩陣)的充分必要條件是矩陣的譜半徑（證明參見：關治，陳景良.數(shù)值計算方法,清華大學出版社，P410~412）ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析（三、誤差分析）方程組的性態(tài)在建立方程組時，其系數(shù)往往含有誤差（如觀測誤差或計算誤差），就是說，所要求解的運算是有擾動的方程組，因此需要研究擾動對解的影響。

ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析（三、誤差分析）矩陣的條件數(shù)ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析（三、誤差分析）Ｑ：產(chǎn)生這種現(xiàn)象的原因何在呢？Ａ：方程組對右端項的擾動太敏感！ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析（三、誤差分析）ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析（三、誤差分析）右端項b的擾動對解的影響ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析（三、誤差分析）系數(shù)矩陣Ａ的擾動對解的影響ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析（三、誤差分析）ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析（三、誤差分析）常用的條件數(shù)ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析（三、誤差分析）ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysisISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysisISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析（三、誤差分析）ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis“病態(tài)”方程的經(jīng)驗判斷ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysisISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis誤差分析§5.7范數(shù)與誤差分析（三、誤差分析）ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析（三、誤差分析）ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析（三、誤差分析）ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§5.7范數(shù)與誤差分析（三、誤差分析）ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式雅可比(Jacobi)迭代格式例6.2.1

建立迭代格式求解方程組

方程組的精確解x*=(3,2,1)T。

ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式建立迭代公式

ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis取初始向量進行迭代,可以逐步得出一個近似解的序列：（k=1,2,…）直到求得的近似解能達到預先要求的精度，則迭代過程終止，以最后得到的近似解作為線性方程組的解。當?shù)降?0次有計算結果表明，此迭代過程收斂于方程組的精確解x*=(3,2,1)T。

ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis考察一般的n元線性方程組

寫成ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis若,分離出變量ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式

（Jacobi迭代公式）(k=0,1,2,…)ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式

（Jacobi迭代公式）據(jù)此建立迭代公式上式稱為解方程組的Jacobi迭代公式。也稱為簡單迭代法。ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis雅可比迭代法的矩陣表示

設方程組的系數(shù)矩陣A非奇異，且主對角元素，則可將A分裂成

記作A=L+D+UISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis則等價于因為

，則這樣便得到一個迭代公式§6.2幾種常用的迭代格式

（Jacobi迭代公式）ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis其中

令則有（k=0,1,2…）稱為雅可比迭代公式,B稱為雅可比迭代矩陣§6.2幾種常用的迭代格式

（Jacobi迭代公式）ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis

雅可比迭代法的算法實現(xiàn)

ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式

（Jacobi迭代公式）functionX=jacobi(A,B,P,delta,max)%求解AX=B，A是非奇N階方陣dleta是誤差界，max是最大迭代次數(shù)N=length(B);fort=1:maxfork=1:N

X(k)=(B(k)-A(k,[1:k-1,k+1:N])*P([1:k-1,k+1:N]))/A(k,k);enderr=abs(norm(X'-P));if(err<delta)break;endendX=X';ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式高斯-塞德爾（Gauss-Seidel）迭代法在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用當前最新的迭代值，即在求時用新分量代替舊分量ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式Gauss-Seidel迭代法(i=1,2,…,n

k=0,1,2,…)高斯-賽德爾迭代法的迭代法格式為：ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式Gauss—Seidel迭代法的矩陣表示將A分裂成A=L+D+U，則等價于

(L+D+U)x=b

于是,則高斯—塞德爾迭代過程

ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式Gauss—Seidel迭代法的矩陣表示因為,所以

故則高斯-塞德爾迭代形式為：令ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式高斯-塞德爾迭代法高斯—塞德爾迭代算法實現(xiàn)高斯-塞德爾迭代算法的計算步驟與流程圖與雅可比迭代法大致相同，只是一旦求出變元的某個新值后,就改用新值替代老值進行這一步剩下的計算。

ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式functionX=gseid(A,B,P,delta,max)%求解AX=B，A是非奇N階方陣dleta是誤差界，max是最大迭代次數(shù)N=length(B);fort=1:max

fork=1:Nifk==1X(1)=(B(1)-A(1,2:N)*P(2:N))/A(1,1);elseifk==NX(N)=(B(N)-A(N,1:N-1)*(X(1:N-1))')/A(N,N);elseX(k)=(B(k)-A(k,1:k-1)*X(1:k-1)'-A(k,k+1:N)*P(k+1:N))/A(k,k);endend

err=abs(norm(X'-P));if(err<delta)break;endendX=X';高斯-塞德爾迭代法ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis例6.2.2，按高斯-塞德爾迭代公式迭代7次，得，

用高斯-塞德爾迭代法解下面線性方程組ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis由此例可知，用高斯-塞德爾迭代法，雅可比迭代法解線性方程組(且取)均收斂.而高斯-塞德爾迭代法比雅可比迭代法收斂較快(即取相同，達到同樣精度所需迭代次數(shù)較少).但這結論只當滿足一定條件時才是對的.且ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式超松弛迭代法（SOR方法）使用迭代法的困難在于難以估計其計算量。有時迭代過程雖然收斂，但由于收斂速度緩慢，使計算量變得很大而失去使用價值。因此，迭代過程的加速具有重要意義。

逐次超松弛迭代（SuccessiveOverrelaxaticMethod，簡稱SOR方法）法，可以看作是帶參數(shù)的高斯—塞德爾迭代法，實質(zhì)上是高斯-塞德爾迭代的一種加速方法。

ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式超松弛迭代法的基本思想

超松弛迭代法目的是為了提高迭代法的收斂速度，在高斯—塞德爾迭代公式的基礎上作一些修改。這種方法是將前一步的結果與高斯-塞德爾迭代方法的迭代值適當加權平均，期望獲得更好的近似值。是解大型稀疏矩陣方程組的有效方法之一，有著廣泛的應用。

ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式SOR方法⑴用高斯—塞德爾迭代法定義輔助量。⑵把取為與的加權平均，即

合并表示為：

ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式SOR方法式中系數(shù)ω稱為松弛因子，為了保證迭代過程收斂，要求0<ω<2。

當ω=1時，便為高斯-塞德爾迭代法。當0<ω<1時，低松弛法；當1<ω<2時稱為超松弛法。但通常統(tǒng)稱為超松弛法(SOR)。

ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式故

令則超松弛迭代公式可寫成SOR迭代法的矩陣表示ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式顯然對任何一個ω值,(D+ωL)非奇異,(因為假設

)于是超松弛迭代公式為(k=0,1,2,…)ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis例6.2.3它的精確解為取，迭代公式為用SOR方法解方程組解ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.2幾種常用的迭代格式取，取其他值，迭代次數(shù)如下表.第11次迭代結果為ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis從此例看到，松弛因子選擇得好，會使SOR迭代法的收斂大大加速.本例中是最佳松弛因子.ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.3迭代法的收斂性及誤差估計對于給定的方程組可以構造成雅可比迭代公式、高斯-塞德爾迭代公式和超松弛迭代公式，但并非一定收斂?，F(xiàn)在分析它們的收斂性。對于方程組經(jīng)過等價變換構造出的等價方程組

在什么條件下迭代序列收斂？ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis定理6.3.1

迭代公式收斂的充分必要條件是迭代矩陣G的譜半徑證:必要性設迭代公式收斂,當k→∞時,則在迭代公式兩端同時取極限得記,則收斂于0(零向量),且有

于是由于可以是任意向量,故收斂于0當且僅當收斂于零矩陣，即當時所以必ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis充分性:設,則必存在正數(shù)ε,使則存在某種范數(shù)

,使,,則,所以

,即。故收斂于0,

收斂于由此定理可知，不論是雅可比迭代法、高斯—塞德爾迭代法還是超松弛迭代法，它們收斂的充要條件是其迭代矩陣的譜半徑。

§6.3迭代法的收斂性及誤差估計ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis定理6.3.2

(迭代法收斂的充分條件)若迭代矩陣G的一種范數(shù),則迭代公式收斂,且有誤差估計式,且有誤差估計式及§6.3迭代法的收斂性及誤差估計ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.3迭代法的收斂性及誤差估計證:矩陣的譜半徑不超過矩陣的任一種范數(shù),已知,因此,根據(jù)定理6.3.1可知迭代公式收斂又因為,則det(I-G)≠0,I-G為非奇異矩陣,故x＝Gx＋d有惟一解,即與迭代過程相比較,有ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis∴

兩邊取范數(shù)§6.3迭代法的收斂性及誤差估計ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.3迭代法的收斂性及誤差估計由迭代格式，有

兩邊取范數(shù)，代入上式，得證畢ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.3迭代法的收斂性及誤差估計由定理知，當時，其值越小，迭代收斂越快，在程序設計中通常用相鄰兩次迭代

（ε為給定的精度要求）作為控制迭代結束的條件ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.4判別收斂的幾個常用條件迭代法收斂的判別條件：1.Jacobi迭代法（簡單迭代法）的收斂判定。2.Gauss-Seidel迭代法的收斂判定。3.SOR迭代法的收斂判定。ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis定理6.4.1

設n階方陣為對角占優(yōu)陣,則它是非奇異的。證:因A為對角占優(yōu)陣,其主對角元素的絕對值大于同行其它元素絕對值之和,且主對角元素全不為0,故對角陣為非奇異。作矩陣ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.4判別收斂的幾個常用條件利用對角占優(yōu)知知非奇異,從而A非奇異,證畢

系數(shù)矩陣為對角占優(yōu)陣的線性方程組稱作對角占優(yōu)方程組。

ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.4判別收斂的幾個常用條件定理6.4.2

對角占優(yōu)線性方程組的雅可比迭代公式和高斯-賽德爾迭代公式均收斂。證:雅可比迭代公式的迭代矩陣為

由定理6.4.1知,這時,再由定理6.3.2知迭代收斂.再考察高斯-賽德爾迭代公式的迭代矩陣ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.4判別收斂的幾個常用條件令，則有即寫出分量形式有設

而由上式得ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.4判別收斂的幾個常用條件由此整理得利用對角占優(yōu)條件知上式右端小于1,(如果右端大于1,則得出與對角占優(yōu)條件矛盾的結果)故有據(jù)定理6.3.2知G-S法收斂ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis定理6.4.3

當系數(shù)矩陣A為正定矩陣，高斯-塞德爾迭代收斂。定理6.4.4

松弛迭代收斂的必要條件是0<ω<2§6.4判別收斂的幾個常用條件ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis定理6.4.6

若A為對稱正定矩陣時，則松弛迭代收斂的充要條件是.

定理6.4.5(松弛法收斂的充分條件)

如果系數(shù)矩陣A為嚴格對角占優(yōu)，當松弛因子

時，松弛迭代法收斂?！?.4判別收斂的幾個常用條件ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.5迭代法收斂判定的應用舉例例6.5.1

已知線性方程組考察用Jacobi迭代和G-S迭代求解時的收斂性解:⑴雅可比迭代矩陣ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.5迭代法收斂判定的應用舉例故Jacobi迭代收斂

ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.5迭代法收斂判定的應用舉例故高斯—塞德爾迭代收斂。

ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.5迭代法收斂判定的應用舉例例6.5.2

設有迭代格式

X(k+1)=BX(k)+g(k=0,1,2……）

其中B=I-A,如果A和B的特征值全為正數(shù)，試證：該迭代格式收斂。分析:根據(jù)A，B和單位矩陣I之間的特征值的關系導出(B)<1,從而說明迭代格式收斂。

ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.5迭代法收斂判定的應用舉例證:因為B=I-A,故(B)=(I)-(A)=1-(A)(A)+(B)=1

由于已知(A)和(B)全為正數(shù)，故

0<(B)<1,從而(B)<1

所以該迭代格式收斂。ISCM2007,BeijingChina/68鄭州大學研究生2014-2015學年課程數(shù)值分析

NumericalAnalysis§6.5迭代法收斂判定的應用舉例例6.5.3

設方程組寫出解方程組的Jacobi迭代公式和迭代矩陣并討論迭代收斂的條件