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

數(shù)值分析

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

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

§6.1引言§6.2

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

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

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

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

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

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

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

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

NumericalAnalysis設(shè)非奇異，，則線性方程組

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

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

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

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

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

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

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

0,Ｘ

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

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

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

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

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

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

是Rn

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

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

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

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

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

NumericalAnalysis例5.7.3

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

證：

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

NumericalAnalysis例5.7.4

設(shè)x=(1,0,-1,2)T,計(jì)算

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

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

NumericalAnalysis定理5.7.1

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

即

當(dāng)p→∞，

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

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

NumericalAnalysis

定理5.7.2

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

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

NumericalAnalysis定理5.7.3

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

證由于

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

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

是變量X分量的

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

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

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

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

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

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

NumericalAnalysis定理5.7.6

設(shè)n

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

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

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

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

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

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

NumericalAnalysis定理5.7.8

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

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

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

即

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

又已知，有

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

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

NumericalAnalysis例5.7.6且設(shè)，考查其極限.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

建立迭代格式求解方程組

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

NumericalAnalysis則等價(jià)于因?yàn)?/p>

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

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

NumericalAnalysis其中

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

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

NumericalAnalysis

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

ISCM2007,BeijingChina/68鄭州大學(xué)研究生2014-2015學(xué)年課程數(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鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

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

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

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

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

(L+D+U)x=b

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

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

NumericalAnalysis§6.2幾種常用的迭代格式Gauss—Seidel迭代法的矩陣表示因?yàn)?所以

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

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

ISCM2007,BeijingChina/68鄭州大學(xué)研究生2014-2015學(xué)年課程數(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鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

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

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

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

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

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

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

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

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

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

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

合并表示為：

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

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

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

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

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

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

NumericalAnalysis§6.2幾種常用的迭代格式顯然對任何一個(gè)ω值,(D+ωL)非奇異,(因?yàn)榧僭O(shè)

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

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

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

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

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

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

NumericalAnalysis定理6.3.1

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

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

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

,使,,則,所以

,即。故收斂于0,

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

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

NumericalAnalysis定理6.3.2

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

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

NumericalAnalysis∴

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

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

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

NumericalAnalysis§6.3迭代法的收斂性及誤差估計(jì)由定理知，當(dāng)時(shí)，其值越小，迭代收斂越快，在程序設(shè)計(jì)中通常用相鄰兩次迭代

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

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

NumericalAnalysis定理6.4.1

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

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

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

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

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

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

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

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

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

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

NumericalAnalysis定理6.4.3

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

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

NumericalAnalysis定理6.4.6

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

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

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

時(shí)，松弛迭代法收斂。§6.4判別收斂的幾個(gè)常用條件ISCM2007,BeijingChina/68鄭州大學(xué)研究生2014-2015學(xué)年課程數(shù)值分析

NumericalAnalysis§6.5迭代法收斂判定的應(yīng)用舉例例6.5.1

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

NumericalAnalysis§6.5迭代法收斂判定的應(yīng)用舉例故Jacobi迭代收斂

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

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

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

NumericalAnalysis§6.5迭代法收斂判定的應(yīng)用舉例例6.5.2

設(shè)有迭代格式

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

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

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

NumericalAnalysis§6.5迭代法收斂判定的應(yīng)用舉例證:因?yàn)锽=I-A,故(B)=(I)-(A)=1-(A)(A)+(B)=1

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

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

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

NumericalAnalysis§6.5迭代法收斂判定的應(yīng)用舉例例6.5.3

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