第3章線性方程組迭代法

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

(IterationMethodsforLinearSystems)

直接法得到的解是理論上準(zhǔn)確的，但是它們的計(jì)算量是n3數(shù)量級(jí)，存儲(chǔ)量為n2量級(jí)，這在n比較小的時(shí)候還比較合適，但是對(duì)很多實(shí)際問題，往往要我們求解很大型的矩陣，而且這些矩陣含有大量的零元素。對(duì)于這類矩陣，在用直接法時(shí)就會(huì)耗費(fèi)大量的時(shí)間和存儲(chǔ)單元。因此引入一類新的方法：迭代法。

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

(IterationMethodsforLinearSystems)

迭代法的思想：逐次逼近；

將求一組解轉(zhuǎn)換為求一個(gè)近似解序列的過程?？紤]三個(gè)問題：1.迭代的初始值：選取是否有范圍限制，對(duì)迭代結(jié)果有無(wú)最終影響；2.迭代的算法：考慮怎樣由當(dāng)前的迭代結(jié)果得出下一次的初始值，不同的算法帶來不同的誤差，誤差是放大還是縮?。?.迭代的收斂性：迭代是否收斂，收斂過程的快慢。

將方程組Ax=b變形為x=Bx+g如：令，則

定義1

任取初始向量x

(0)

，由迭代公式得序列x

(k)

作為原方程組的近似解,這種方法為迭代法。B稱為迭代矩陣?！?.1

基本迭代法引言將方程組Ax=b變形為x=Bx+g

定義1

任取初始向量x

(0)

，由迭代公式得序列x

(k)

作為原方程組的近似解,這種方法為迭代法。B稱為迭代矩陣。引例

求解線性方程組解：

將原方程組或記為x=Bx+g其中取初始值

x(0)=(0,0,0)T迭代10次，得x(10)=(3.000032,1.999838,0.9998813)T精確解為：

x*=(3,2,1)T一、Jacobi迭代法1.迭代思想：設(shè)方程組為從第i個(gè)方程解出xi格式很簡(jiǎn)單：把迭代前的值代入左邊，由計(jì)算得到等式左邊的值作為一次迭代的新值帶入右邊，如此反復(fù)得到Jacobi迭代公式2.Jacobi迭代矩陣記A=-L-UDJacobi迭代矩陣表示為：Jacobi迭代矩陣為代入方程組得：二、Gauss－Seidel迭代法1.迭代思想：在Jacobi迭代中，使用最新計(jì)算出的分量值得2.Gauss－Seidel迭代矩陣?yán)?：用Jacobi迭代法求解解：解：仍取x(0)=(0,0,0)T,帶入迭代式得例2：用Gauss-Seidel迭代法求解如此繼續(xù)下去，得x(5)=(10.9989,11.9993,12.9996)T,精確解為x=(11,12,13)T

上例結(jié)果表明，Gauss-seidel迭代法比Jacobi迭代法效果好。事實(shí)上，對(duì)有些問題Gauss-seidel迭代確實(shí)比Jacobi迭代法收斂得快，但也有Gauss-seidel迭代比Jacobi迭代法收斂得慢，甚至有Jacobi迭代收斂而Gauss-seidel迭代發(fā)散的情形。只是Gauss-seidel與Jacobi相比，只需一組工作單元存放近似解。

松弛迭代法是高斯-賽德爾迭代法的一種加速方法，其基本思想是將高斯-賽德爾迭代法得到的第k+1次近似解向量與第k次近似解向量做加權(quán)平均，當(dāng)權(quán)因子選取適當(dāng)時(shí)，加速效果顯著。三、超松弛迭代法(SOR)

（SuccessiveOverRelaxationMethod）換個(gè)角度看Gauss-Seidel

方法：其中ri(m)=相當(dāng)于在的基礎(chǔ)上加個(gè)余項(xiàng)生成。=1Gauss-Seidel

法下面令，希望通過選取合適的來加速收斂，這就是逐次超松弛迭代法，簡(jiǎn)記SOR法

。稱為松弛因子1.基本思想記則可以看作在前一步上加一個(gè)修正量。若在修正量前乘以一個(gè)因子,有2.SOR迭代矩陣對(duì)Gauss－Seidel迭代格式引入松弛因子整理得所以BSORg例3

用SOR法解方程組解從上表可見，本例的最佳松弛因子應(yīng)該在1和1.1之間。k0.10.20.30.40.50.60.70.80.911637749342620151296k1.11.21.31.41.51.61.71.81.968101317223151105SOR方法收斂的快慢與松弛因子的選擇有密切關(guān)系.但是如何選取最佳松弛因子,是一個(gè)尚未很好解決的問題.實(shí)際上可采用試算的方法來確定較好的松弛因子.當(dāng)時(shí)，上式稱為低松弛迭代法（SUR法），常用于使不收斂的迭代過程收斂；當(dāng)時(shí)，上式稱為超松弛迭代法（SOR法），常用于加速收斂的迭代過程；當(dāng)時(shí)即為高斯-賽德爾迭代法。

經(jīng)驗(yàn)上可取1.4<<1.6.幾點(diǎn)說明迭代法：將方程組Ax=b變形為x=Bx+g，構(gòu)造迭代公式任取初始向量x

(0)

，由迭代公式得序列{x

(k)}作為原方程組的近似解,這種方法為迭代法。B稱為迭代矩陣。迭代法JacobiiterationGauss-SeideliterationSORiteration迭代原理從第i個(gè)方程中解出xi，以右邊為初值，帶入左邊計(jì)算xi(k+1)時(shí)需要x(k)的i+1~n個(gè)分量對(duì)Gauss－Seidel迭代格式使用松弛因子迭代矩陣優(yōu)缺點(diǎn)計(jì)算x(k+1)時(shí)需要x(k)的所有分量，因此需開兩組存儲(chǔ)單元分別存放x(k)和x(k+1)x(k+1)的前i個(gè)分量可存貯在x(k)的前i個(gè)分量所占的存儲(chǔ)單元，無(wú)需開兩組存儲(chǔ)單元.選擇合適的松弛因子，可加快收斂速度§3.2范數(shù)及方程組的性態(tài)、條件數(shù)

1．向量的范數(shù)定義1：設(shè)xRn，x

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

(1)

非負(fù)性：即對(duì)一切xRn，x0,x>0(2)

齊次性：即對(duì)任何實(shí)數(shù)aR，xRn，

設(shè)X=(x1,x2,…,xn)T，則有

（1）（2）（3）三個(gè)常用的范數(shù)：定理1：定義在Rn上的向量范數(shù)

是變量X分量的

一致連續(xù)函數(shù)。定理2：在Rn上定義的任一向量范數(shù)

都與范數(shù)

等價(jià)，

即存在正數(shù)

M

與m(M>m)

對(duì)一切XRn，不等式成立。推論：Rn上定義的任何兩個(gè)范數(shù)都是等價(jià)的。

對(duì)常用范數(shù)，容易驗(yàn)證下列不等式：

定義1矩陣范數(shù)設(shè)A∈Rn×n，定義一個(gè)非負(fù)實(shí)值函數(shù)||A||，若滿足：

(1)非負(fù)性：||A||≥0，且||A||=0當(dāng)且僅當(dāng)A=0；(2)齊次性：||aA||=|a|||A||，a∈R；則稱||A||為A的矩陣范數(shù)。2．矩陣的范數(shù)(3)三角不等式：||A+B||≤||A||+||B||，A,B∈Rn×n;(4)相容性：；A,B∈Rn×n;定義2：設(shè)A為n

階方陣，Rn中已定義了向量范數(shù)，

則稱

為由向量范數(shù)導(dǎo)出的矩陣范數(shù)或模，

記為。矩陣范數(shù)與向量范數(shù)的相容性：||Ax||v||A||M·||x||v，xRn定理3：設(shè)n階方陣A=(aij)nn，則（Ⅰ）與相容的矩陣范數(shù)是（Ⅱ）與相容的矩陣范數(shù)是其中1為矩陣ATA的最大特征值。（Ⅲ）與相容的矩陣范數(shù)是（行和范數(shù)）（列和范數(shù)）（譜范數(shù)(spectralnorm

)

）矩陣范數(shù)的基本性質(zhì)：

（1）當(dāng)A=0時(shí)，＝0，當(dāng)A0時(shí)，>0（2）對(duì)任意實(shí)數(shù)和任意A，有（3）對(duì)任意兩個(gè)n階矩陣A、B有（4）對(duì)任意向量XRn，和任意矩陣A，有A

的范數(shù)與A

的特征值之間的關(guān)系定理4：矩陣A

的任一特征值的絕對(duì)值不超過A的范數(shù)。定義3：矩陣A的諸特征值的最大絕對(duì)值稱為A的譜半徑，記為：

定義：若方程組Ax=b的系數(shù)矩陣A與右端向量b的微小變化（小擾動(dòng)）,將引起解向量x產(chǎn)生巨大變化，則稱此方程組為病態(tài)方程組，其系數(shù)矩陣A稱為病態(tài)矩陣，否則稱Ax=b為良態(tài)方程組，稱A為良態(tài)矩陣

.

方程組的病態(tài)程度與Ax=b對(duì)A和b的擾動(dòng)的敏感程度有關(guān)。方程組的病態(tài)與良態(tài)是關(guān)鍵的誤差放大因子，稱為A的條件數(shù)，記為cond(A),越大，則A越病態(tài)，難得準(zhǔn)確解。注:

1）cond(A)的具體大小與||·||的取法有關(guān)，但相對(duì)大小一致，常用的范數(shù)為:2）cond(A)取決于A，與解題方法無(wú)關(guān)。cond

(A)=||A||||A-1||cond

1(A)=||A||1||A-1||1，cond

2(A)特別地，A為對(duì)稱矩陣時(shí)，（1）A可逆，則cond

p

(A)1；（2）A可逆，R

則cond(

A)=cond(A)；（3）A正交，則cond

2

(A)

=1；（4）A可逆，R正交，則cond

2

(RA)

=cond

2

(AR)=cond(A)2

。條件數(shù)的性質(zhì)：精確解為例計(jì)算cond

2(A)

。A1=解：考察A

的特征根39206>>1定義2

設(shè)有矩陣序列及，如果則稱收斂于A，記為定理1：若，稱該迭代法收斂，否則稱該迭代法發(fā)散定義1§3.3收斂性分析

定義3：（收斂矩陣）定理2：至少存在一種從屬范數(shù)||·||<1定理3迭代法收斂的充要條件是迭代矩陣B的譜半徑由迭代法收斂定義可得：所以，序列收斂與初值的選取無(wú)關(guān)

定理4（迭代法收斂的充分條件）若迭代矩陣B的某種范數(shù)||B||<1，則迭代法收斂。1.Jacobi迭代法與G-S迭代法收斂性Jacobi迭代法收斂G-S迭代法收斂定理1

定理2：若AX=b

的系數(shù)矩陣A∈R

nn為嚴(yán)格對(duì)角占優(yōu)陣，則解此方程組的雅可比迭代法和高斯-賽德爾迭代法都收斂。定理3：若AX=b的系數(shù)矩陣A∈R

nn

為對(duì)稱正定矩陣，則解此線性方程組的高斯-賽德爾迭代法收斂；Jacobi迭代收斂的充要條件為矩陣2D-A也對(duì)稱正定注意的問題（2）Jacobi迭代法和Gauss-Seidel迭代法的收斂性沒有必然的聯(lián)系：即當(dāng)Gauss-Seidel法收斂時(shí)，Jacobi法可能不收斂；而Jacobi法收斂時(shí)，

Gauss-Seidel法也可能不收斂。（1）Jacobi迭代法和Gauss-Seidel迭代法的迭代矩陣不同：BJ=D-1(L+U),B

G-S=(D-L)-1U用Jacobi迭代法求解收斂，但用G-S法不收斂。

BJ的特征值為0,0,0,而BG－S的特征值為0,2,2.例系數(shù)矩陣A是正定矩陣，因此用Gauss-Seidel法收斂不是正定矩陣，因此用Jacobi迭代法不收斂A是有正對(duì)角元的n階對(duì)稱矩陣?yán)?/p>

定理2

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

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

|det(B)|=|12…n|<1

而

det(B)=det[(D-L)-1((1-)D+U)]

=det[(E-D-1L)-1]det[(1-)E+D-1U)]

=(1-)n于是

|1-|<1,或

0<<2定理1