ch06a線(xiàn)性方程組迭代解法基本概念

1第六章

線(xiàn)性方程組的迭代解法數(shù)值分析——迭代法基本概念2線(xiàn)性方程組迭代解法運(yùn)算量大，不適合大規(guī)模的線(xiàn)性方程組求解無(wú)法充分利用系數(shù)矩陣的稀疏性直接法的缺點(diǎn)：從一個(gè)初始向量出發(fā)，按照一定的迭代格式，構(gòu)造出一個(gè)趨向于真解的無(wú)窮序列只需存儲(chǔ)系數(shù)矩陣中的非零元素運(yùn)算量不超過(guò)O(kn2)，其中k為迭代步數(shù)迭代法迭代法是目前求解大規(guī)模稀疏線(xiàn)性方程組的主要方法3矩陣分裂迭代法矩陣分裂迭代法基本思想Ax=bk=0,1,2,…給定一個(gè)初始向量x(0)，可得迭代格式其中

B=M-1N

稱(chēng)為迭代矩陣

A=M-NMx=Nx

+

bM非奇異A

的一個(gè)矩陣分裂4矩陣分裂迭代法k=0,1,2,…定義：若存在，則稱(chēng)該迭代法收斂，否則稱(chēng)為發(fā)散性質(zhì)：若，則x*

為原方程組Ax=b

的解5向量序列的極限定義：設(shè)向量序列，

，若存在向量，使得i=1,2,…,n則稱(chēng)向量序列收斂到x，記作定理：6向量序列的極限定理：定理：(其中||·||為任一算子范數(shù))相類(lèi)似地，可以定義矩陣序列的極限與收斂7收斂性分析基本定理：對(duì)任意初始向量x(0)，上述迭代格式收斂的充要條件是定理：若存在算子范數(shù)||·

||，使得||B||<1，對(duì)任意的初始向量x(0)，上述迭代格式收斂。例：考慮迭代法x(k+1)=Bx(k)+f

的收斂性，其中8收斂性分析B=M-1N定理：若存在算子范數(shù)||·

||，使得||B||=q<1，則迭代法收斂

9Jacobi迭代考慮線(xiàn)性方程組Ax=b其中A=(aij)n

n

非奇異，且對(duì)角線(xiàn)元素全不為0。將A

分裂成A=D-L-

U，

其中10Jacobi迭代k=0,1,2,…令M=D，N

=L

+U，可得雅可比(Jacobi)迭代方法Jacobi迭代迭代矩陣記為：分量形式：i=1,2,…,

n，k=0,1,2,…A=M-N11Gauss-Seidel迭代寫(xiě)成矩陣形式:此迭代方法稱(chēng)為高斯-塞德?tīng)?Gauss-Seidel)迭代法k=0,1,2,…可得迭代矩陣記為：12SOR迭代寫(xiě)成矩陣形式:可得——SOR(SuccessiveOver-Relaxation)迭代方法迭代矩陣記為：

SOR的優(yōu)點(diǎn)：通過(guò)選取合適的

，可獲得更快的收斂速度

SOR的缺點(diǎn)：最優(yōu)參數(shù)的選取比較困難13Jacobi、G-S、SOR

Jacobi迭代

SOR迭代

G-S迭代14舉例例：分別用Jacobi、G-S、SOR迭代解線(xiàn)性方程組取初始向量x(0)=(0,0,0)，迭代過(guò)程中小數(shù)點(diǎn)后保留4位。解：Jacobi迭代：迭代可得：x(1)=(0.5000,2.6667,-2.5000)Tx(21)=(2.0000,3.0000,-1.0000)T

exJ_GS_SOR.m15舉例G-S迭代：x(1)=(0.5000,2.8333,-1.0833)Tx(9)=(2.0000,3.0000,-1.0000)T迭代可得：16舉例SOR迭代：取

=1.1，迭代可得x(1)=(0.5500,3.1350,-1.0257)Tx(7)=(2.0000,3.0000,-1.0000)T如何確定SOR迭代中的最優(yōu)松弛因子是一件很困難的事17Jacobi迭代收斂的充要條件

(J)<1

G-S迭代收斂的充要條件

(G)<1

SOR迭代收斂的充要條件

(L

)<1收斂性收斂性定理Jacobi迭代收斂的充分條件||J||<1

G-S迭代收斂的充分條件||G||<1

SOR迭代收斂的充分條件||L

||<118對(duì)角占優(yōu)矩陣且至少有一個(gè)不等式嚴(yán)格成立，則稱(chēng)A

為弱對(duì)角占優(yōu)；若所有不等式都嚴(yán)格成立，則稱(chēng)A

為嚴(yán)格對(duì)角占優(yōu)。(i=1,2,...,n)定義：設(shè)ARn

n，若19可約與不可約定義：設(shè)ARn

n，若存在排列矩陣P使得

則稱(chēng)A

為可約矩陣；否則稱(chēng)為不可約矩陣。如果A

是可約矩陣，則方程組Ax=b

等價(jià)于y即可以把原方程組化成兩個(gè)低階的方程組來(lái)處理。f20Jacobi、G-S收斂性定理：若A嚴(yán)格對(duì)角占優(yōu)或不可約弱對(duì)角占優(yōu)，則A非奇異定理：若A嚴(yán)格對(duì)角占優(yōu)或不可約弱對(duì)角占優(yōu)，則Jacobi迭代和G-S迭代均收斂定理：若A對(duì)稱(chēng)，且對(duì)角線(xiàn)元素均大于0，則Jacobi迭代收斂的充要條件是A與2D-A均正定；G-S迭代收斂的充要條件是A正定。21SOR收斂性定理：若SOR迭代收斂，則0<

<2。SOR收斂的必要條件定理：若A

對(duì)稱(chēng)正定，且0<

<2，則SOR迭代收斂。SOR收斂的充分條件定理：若A

嚴(yán)格對(duì)角占優(yōu)或不可弱約對(duì)角占優(yōu)，且0<

1，則SOR迭代收斂。22舉例例：設(shè)，給出Jacobi和G-S收斂的充要條件解：A對(duì)稱(chēng)，且對(duì)角線(xiàn)元素均大于0，故(1)Jacobi收斂的充要條件是A和2D-A均正定(2)G-S收斂的充要條件是A正定A

正定2D-A

正定Jacobi收斂的充要條件是：-0.5<a<0.5G-S收斂的充要條件是：-0.5<a<123舉例解法二：Jacobi的迭代矩陣為設(shè)