第3章線性方程組迭代法

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

(IterationMethodsforLinearSystems)

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

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

(IterationMethodsforLinearSystems)

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

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

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

定義1

任取初始向量x

(0)

，由迭代公式得序列x

(k)

作為原方程組的近似解,這種方法為迭代法。B稱為迭代矩陣。§3.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.迭代思想：設方程組為從第i個方程解出xi格式很簡單：把迭代前的值代入左邊，由計算得到等式左邊的值作為一次迭代的新值帶入右邊，如此反復得到Jacobi迭代公式2.Jacobi迭代矩陣記A=-L-UDJacobi迭代矩陣表示為：Jacobi迭代矩陣為代入方程組得：二、Gauss－Seidel迭代法1.迭代思想：在Jacobi迭代中，使用最新計算出的分量值得2.Gauss－Seidel迭代矩陣例1：用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

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

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

（SuccessiveOverRelaxationMethod）換個角度看Gauss-Seidel

方法：其中ri(m)=相當于在的基礎上加個余項生成。=1Gauss-Seidel

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

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

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

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

(0)

，由迭代公式得序列{x

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

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

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

(1)

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

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

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

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

是變量X分量的

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

都與范數(shù)

等價，

即存在正數(shù)

M

與m(M>m)

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

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

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

(1)非負性：||A||≥0，且||A||=0當且僅當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：設A為n

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

則稱

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

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

)

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

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

的范數(shù)與A

的特征值之間的關系定理4：矩陣A

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

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

.

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

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

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

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

2(A)特別地，A為對稱矩陣時，（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ì)：精確解為例計算cond

2(A)

。A1=解：考察A

的特征根39206>>1定義2

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

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

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

定理2：若AX=b

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

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

nn

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

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是有正對角元的n階對稱矩陣例

定理2

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

證設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