1第六章

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

B=M-1N

稱為迭代矩陣

A=M-NMx=Nx

+

bM非奇異A

的一個矩陣分裂4矩陣分裂迭代法k=0,1,2,…定義：若存在，則稱該迭代法收斂，否則稱為發散性質：若，則x*

為原方程組Ax=b

的解5向量序列的極限定義：設向量序列，

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

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

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

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

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

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迭代寫成矩陣形式:此迭代方法稱為高斯-塞德爾(Gauss-Seidel)迭代法k=0,1,2,…可得迭代矩陣記為：12SOR迭代寫成矩陣形式:可得——SOR(SuccessiveOver-Relaxation)迭代方法迭代矩陣記為：

SOR的優點：通過選取合適的

，可獲得更快的收斂速度

SOR的缺點：最優參數的選取比較困難13Jacobi、G-S、SOR

Jacobi迭代

SOR迭代

G-S迭代14舉例例：分別用Jacobi、G-S、SOR迭代解線性方程組取初始向量x(0)=(0,0,0)，迭代過程中小數點后保留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迭代中的最優松弛因子是一件很困難的事17Jacobi迭代收斂的充要條件

(J)<1

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

(G)<1

SOR迭代收斂的充要條件

(L

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

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

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

||<118對角占優矩陣且至少有一個不等式嚴格成立，則稱A

為弱對角占優；若所有不等式都嚴格成立，則稱A

為嚴格對角占優。(i=1,2,...,n)定義：設ARn

n，若19可約與不可約定義：設ARn

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

則稱A

為可約矩陣；否則稱為不可約矩陣。如果A

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

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

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

對稱正定，且0<

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

嚴格對角占優或不可弱約對角占優，且0<

1，則SOR迭代收斂。22舉例例：設，給出Jacobi和G-S收斂的充要條件解：A對稱，且對角線元素均大于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的迭代矩陣為設