雅克比高斯賽德爾迭代法

《雅克比高斯賽德爾迭代法》由會員分享，可在線閱讀，更多相關(guān)《雅克比高斯賽德爾迭代法（10頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第八節(jié) 雅可比迭代法與高斯一塞德爾迭代法 一雅可比迭代法 設線性方程組 Ax = b a ,a ,...,a 的系數(shù)矩陣A可逆且主對角元素11 22 nn均不為零，令 D = diagI a ,a ，…，a ) 并將A分解成 ；22 nn A = \A - D)+ D 、 ⑵ 從而(1)可寫成 Dx =(D - A)x + b 令 x = B x + f B = I - D-i A,f = D-ib 其中i i 以B i為迭代矩陣的迭代法(公式) x (k+i) = B x (k) + f [b - y a x(k) j =i " 7' j^i k

2、 = 0,i,2,... 稱為雅可比(Jacobi)迭代法(公式)，用向量的分量來表示，(4)為 x (k+偵= [b - y. a x(k)] r i a i i = i,2 ,...n, x (0) = x (0) ,x (0) ,...x (0 )力 其中 i 2 n 為初始向量. 由此看出，雅可比迭代法公式簡單，每迭代一次只需計算一次矩陣和向量的乘法.在電算時需 要兩組存儲單元，以存放x (k)及x" +i) 例1例1用雅可比迭代法求解下列方程組 ]0x - x - 2x = 7.2 < -xi +10x2 - 2x3 = 8.3 —x — x + 5 x = 4.

3、2 i 2 3 解將方程組按雅可比方法寫成 'x = 0.i x + 0.2 x + 0.72 < x = 0. ix 2 i + 0.2 x + 0.83 =0.2 x i + 0.84 + 0.2 x 2 取初始值 x(0) = *(°),x(0),x(0))= (0,0,0)按迭代公式 尤 Q+1)= 0.1x Q) + 0.2 x (k) + 0.72 1 2 3 < x(k+i)= 0.1 x(k) + 0.2x(k) + 0.83 x (k+1)= 0.2 x (k) + 0.2 x (k) + 0.84 3 1 2 進行迭代，其計算結(jié)果

4、如表1所示 表1 k 0 1 2 3 4 5 6 7 x (k) 1 0 0.72 0.971 1.057 1.0853 1.0951 1.0983 ■ ■ ■ x (k) 2 0 0.83 1.070 1.157 1 1.1853 1.1951 1.1983 ■ ■ ■ x (k ) 3 0 0.84 1.150 1.248 2 1.2828 1.2941 1.2980 ■ ■ ■ 二高斯一塞德爾迭代法 由雅可比迭代公式可知，在迭代的每一步計算過程中是用x (k)的全部分量來計算x(k+1)的所 x (

5、k+1) x (k+1)，…,x (k+1) 有分量，顯然在計算第i個分量i 時，已經(jīng)計算出的最新分量1 i-1 沒有被利 用，從直觀上看，最新計算出的分量可能比舊的分量要好些.因此，對這些最新計算出來的第 k + 1次近似人(k+1)的分量x j 加以利用,就得到所謂解方程組的高斯一塞德(Gauss-Seidel) 迭代法. A = D — L — U D = diag( a ,a ，…，a )-L,-U 其中 ° 11 22 nn , ' 部分,于是,方程組(1)便可以與成 VD — L )x = Ux + b 分別為A的主對角元除外的下三角和上三角 f =(D — L

6、 )-1 b 把矩陣A分解成 即 x = B x + f 其中 2 2 B =(D — L )-1 U, 以B2為迭代矩陣構(gòu)成的迭代法(公式) x (k+1) = B x (k) + f 2 2 稱為高斯一塞德爾迭代法(公式)，用 量表示的形式為 x(k+偵=一 [b 一另a x(k+偵一私 a x(k)] i a i . . ij j . . . ij j .. j=1 j=+1 ii (9) 組存儲單元(計算出 i = 1,2, n, k = 0,1,2,... 由此看出，高斯一塞德爾迭代法的一個明顯的優(yōu)點是,在電算時，只需 x (k+1) x (k) x

7、 (k+1) x (k) i 后i不再使用，所以用i 沖掉i ，以便存放近似解. 例2例2用高斯一一塞德爾迭代法求解例1. ，按迭代公式 0.1x (Q + 0.2 x (Q + 0.72 2 3 + 0.2 x (Q + 0.83 3 + 0.84 x (0) = 4 (0) ,x (0) ,x (0 ))=(0,0,0,> 解 取初始值 123 、 X (k+1)— 1 、八 1 ，、 < X (k+1) = 0. 1X (k+1) x (k+1) = 0.2 x (k+1) + 0.2 x (k+1) l 3 1 2 進行迭代，其計算結(jié)果如下表2 2 …1

8、 表2 k 0 1 2 3 4 5 6 7 x (k) 1 0 0.72 1.04308 1.093 13 1.09913 1.09989 1.09999 1.1 x (k ) 2 0 0.902 1.16719 1.195 72 1.19947 1.19993 1.19999 1.2 x (k) 3 0 1.164 4 1.28205 1.297 77 1.29972 1.29996 1.3 1.3 從此例看出，高斯一塞德爾迭代法比雅可比迭代法收斂快(達到同樣的精度所需迭代次數(shù)少)，但 這個結(jié)論，在

9、一定條件下才是對的，甚至有這樣的方程組，雅可比方法收斂，而高斯一塞德爾迭代 法卻是發(fā)散的. 三迭代收斂的充分條件 定理1在下列任一條件下,雅可比迭代法(5)收斂. "1 ① =max 8 i j=1 j & X氏< 1 a ii a |^ || = maxX^i- < 1 1 1 j i=1|a. j 圭i 11 a 11 - D-1 Ar | = max X—i- < 1 8 j i=1 0 ③ 定理2 l 女 j jj 設1, 2分別為雅可比迭代矩陣與高斯一塞德爾迭代矩陣，則 當I” (10) 從而，當 | = max 8 l j=1 j圭

10、i X% < 1 a ll 時，高斯一塞德爾迭代法(8)收斂. 證明 由1, 2的定義,它們可表示成 B = D-1。+ U ) BB =(D - L )-1 U = (I - D -1L L D -U 用°表示n維向量e二。1'…'1〉，則有不等式 b e < |b B i 這里，記號l?l表示其中矩陣的元素都取絕對值，而不等式是對相應元素來考慮的，于是 容易驗證 (D -i L)- D -i L ))e 3 所以，1 - D-i L及1 - (I - D -i L )-i D-i L 可逆，且 ( -I + D-iL +... + (D-i < I

11、+ D -i L + ...D -i L n-1 (I - D -i L >i D-U e =(B |- |D -iL|k <(I - D -i L - -D-i L)i > I 從而有 / 、 B e < I - ( D-i L )-i ={ I - -D-iU e D -i L i 3 -D -i L -《-1 |B -i )}e D -i L <1件 因此必有 因為已知Bi" 3 所以 若矩陣A為對稱，我們有 定理3 證明 IIB2II < I叩 HB2 l <〔.即高斯一塞德爾迭代法收斂. U = Lt ) 若矩陣A正定，則高斯一塞德爾迭

12、代法收斂. 把實正定對稱矩陣A分解為 A - D - L - Lt ，則D為正定的，迭代矩陣 、 B -(D - L)-i L 設X是B2的任一特征值，X為相應的特征向量，則 (D - L) iLt(x)=XX 以D - L左乘上式兩端，并由A= D - L - ￡,有 U - X)Ltx — XAx 用向量x的共軛轉(zhuǎn)置左乘上式兩端,得 G — X)jct Ltx - X Xt Ax (11) 求上式左右兩端的共軛轉(zhuǎn)置，得 i - X ) Xt L x - X jct Ax 以1 -X和1 -X分別乘以上二式然后相加，得 xt(LT + L 入二 -*“

13、-/? 由 A = D - L - Lt ,得 G-*{1-*)xt(D - A)x =「* + *- 2人尢 人+尢一 2人尢xt Ax k ) ) xt Ax 1-人 |2 XT Lx = 1 -|X| 2 久 x-t Ax (12) 因為A和D都是正定的，且x不是零向量,所以由(11)式得*。1,而由(12)式得 '、從而P f 1,因而高斯一塞德爾迭代法收斂. 1 - * 2〉0 * ,即 a = 定義1設 ①①如果 ij nxn為n階矩陣. >￡a , j=i , 、 j 也 (13) 即A的每一行對角元素的絕對值都嚴格大于

14、同行其他元素絕對值之和，則稱A為嚴格對角優(yōu)勢矩 陣. ②②如果 a ii ij a ii i = 1,2 ,...n Z￡a , j=i j.i 且至少有一個不等式嚴格成立，則稱A為弱對角優(yōu)勢矩陣. ij -1 例如 是嚴格對角優(yōu)勢矩陣， 是弱對角優(yōu)勢矩陣. A 11 0 A = (a ) 定義2 設 ij nxn是n階矩陣，如果經(jīng)過行的互換及相應列的互換可化為 即存在n階排列矩陣P,使 PtAP = a 11 0 a 12 a 22 A 12 a 22 其中A1 22為方陣，則稱a是可約的,否則稱A為不可約的. A是可約矩

15、陣,意味著Ax = b可經(jīng)過若干次行列重排,化為兩個低階方程組，事實上, Ax = bn PtAP(Ptx)= P’b 七 -'■ ，記 可化為 Ptx = y = y (1) PTb = d = d (1) d(2 ) 于是，求解AX = b化為求解 A y (1) + A y (2) = d (1) 11 12 + A y (2) = d (2) 22 可以證明，如果A為嚴格對角優(yōu)勢矩陣或為不可約弱對角優(yōu)勢矩陣，則A是非奇異的. 定理4如果A為嚴格對角優(yōu)勢矩陣或為不可約弱對角優(yōu)勢矩陣，則對任意X(0)，雅可比迭代 法(4)與高斯一塞德爾迭代法(8)均為收斂的

16、. 證明 下面我們以A為不可約弱對角優(yōu)勢矩陣為例，證明雅可比迭代法收斂，其他證明留給 讀者. ) )=0 要證明雅可比迭代法收斂，只要證p 1 , 1是迭代矩陣. 用反證法,設矩陣Bi有某個特征值*，使得* —，則det 1 — Bi ，由于A不可約, 且具有弱對角優(yōu)勢，所以D -1存在，且 *1 - B =*I-M - D-1 A)= D-1 (*D + A - D) 1 det (*D + A — D )= 0 另一方面，矩陣(*D + A — D)與矩陣A的非零元素的位置是完全相同的，所以 (*D + A — D).. L 也是不可約的，又由于 * a > a >2 a , 從而 ，且A弱對角優(yōu)勢，所以 i = 1,2,...n ii j=i j叔 ij 并且至少有一個i使不等號嚴格成立.因此，矩陣 l*D + A- D為不可約弱對角優(yōu)勢矩陣.從而 ? det l*D + A - D 上 0 弱對角優(yōu)勢，故 矛盾，故1的特征值不能大于等于1，定理得證.