雅可比迭代法與高斯-塞德?tīng)柕ňC述

1、第八節(jié) 雅可比迭代法與高斯一塞德?tīng)柕ㄑ趴杀鹊ㄔO(shè)線性方程組Ax = b的系數(shù)矩陣A可逆且主對(duì)角元素D =diaga11 ,a22 ,.,ann均不為零，令 a11,a22,.,ann并將A分解成A= A -從而（i）可寫(xiě)成Dx = D - A x bx = B1x f1其中 B1 = I - D A,f1 = D bB1為迭代矩陣的迭代法（公式）,(4)為xW）= B1x（k）+ f1稱(chēng)為雅可比（Jacobi）迭代法（公式），用向量的分量來(lái)表示x(k1)ani =1,2,.n,nzj 1j寸k(k) aij xj= 01,2，其中x嚴(yán)）=（x10）,X20 ）.父）為初始向量.由此看出，

2、雅可比迭代法公式簡(jiǎn)單，每迭代一次只需計(jì)算一次矩陣和向量的乘法 要兩組存儲(chǔ)單元，以存放 xf 兒 x”）例1例1用雅可比迭代法求解下列方程組10x1 - x2 -2x3 = 7.2-Xi 10x2 -2x3 =8.3.在電算時(shí)需- x1 -解將方程組按雅可比方法寫(xiě)成x1 =x2 5x3 =4.20.1x2 0.2x3 0.72x2 =0.1x10.2x3 0.83x3 =0.2x10.2x20.84取初始值xgxRxgxfN=（0,0,0,）按迭代公式Xik 1 =0.1x2k 0.2xJ 0.72X2k1 =0.1x1k0.2x3k0.83x3k 1 =0.2x1k0.2x2k0.84I進(jìn)行迭

3、代，其計(jì)算結(jié)果如表1所示表1由雅可比迭代公式可知，在迭代的每一步計(jì)算過(guò)程中是用有分量，顯然在計(jì)算第i個(gè)分量X時(shí)，已經(jīng)計(jì)算出的最新分量x，的全部分量來(lái)計(jì)算 x )的所k 1k 1x1，,X沒(méi)有被利k01234567x1(k)00.720.9711.0571.08531.09511.0983x2k)00.831.0701.15711.18531.19511.1983xC00.841.1501.24821.28281.29411.2980高斯塞德?tīng)柕ㄓ?，從直觀上看，最新計(jì)算出的分量可能比舊的分量要好些.因此，對(duì)這些最新計(jì)算出來(lái)的第k 1x k 1k +1次近似X1犧分量xj加以利用，就得到所謂解

4、方程組的高斯一塞德(Gauss-Seidel )迭代法.把矩陣A分解成A = D - L - U 其中D =diag( a11 ,電2 ,ann ), - L ,-U分別為A的主對(duì)角元除外的下三角和上三角 部分，于是，方程組(1)便可以寫(xiě)成D - L x = Ux b即x = B2xf2其中11B2 = D - L U ,f2 = D - L b 以B2為迭代矩陣構(gòu)成的迭代法(公式)xE= BzX” f2稱(chēng)為高斯一塞德?tīng)柕?公式)，用量表示的形式為1 4n.xi()b - v ajx；) - v aj xj ) aiiHG i=1,2，n, k = 0,1,2，(9)由此看出，高斯一塞德?tīng)?/p>

5、迭代法的一個(gè)明顯的優(yōu)點(diǎn)是，在電算時(shí)，只需一組存儲(chǔ)單元(計(jì)算出k1kk1kx后xi不再彳1用，所以用x 沖掉xi ,以便存放近似解.例2例2用高斯一一塞德?tīng)柕ㄇ蠼饫?.解取初始值xC）=（xF）x2°）x3）=（0，0，0，）,按迭代公式x1k1 二x>=0.1xik10.1x2k0.2x3k0.720.2x3k0.83x3k1 二0.2廣0.2x2k10.84a。=maxZ < 1B10Bi 1 = max"1j i 1aijI - DATn- 二max" j i=1i=jaijajj進(jìn)行迭代，其計(jì)算結(jié)果如下表2表2k01234567x1（k）00

6、.721.043081.093131.099131.099891.099991.1x2k)00.9021.167191.195721.199471.199931.199991.2x3k)01.16441.282051.297771.299721.299961.31.3從此例看出，高斯一塞德?tīng)柕ū妊趴杀鹊ㄊ諗靠?（達(dá)到同樣的精度所需迭代次數(shù)少 ），但 這個(gè)2論，在一定條件下才是對(duì)的，甚至有這樣的方程組，雅可比方法收斂，而高斯 一塞德?tīng)柕?法卻是發(fā)散的.迭代收斂的充分條件定理1在下列任一條件下，雅可比迭代法（5）收斂.aH定理2設(shè)B1，B2分別為雅可比迭代矩陣與高斯一塞德?tīng)柕仃?，則(

7、10)B2B1從而，當(dāng)舊” max騎<1時(shí)，高斯一塞德?tīng)柕ǎ?）收斂.證明 由B,B2的定義，它們可表示成1_ DLDUB1 = D L UB2 = D - L,U = I用e表示n維向量e = （1,1,.,1），則有不等式 B1e|B1|QCeB1 二| DL | + DU這里，記號(hào)I |表示其中矩陣的元素都取絕對(duì)值，而不等式是對(duì)相應(yīng)元素來(lái)考慮的，于是D1U e = (Bi - D-L|e<0 - DAL'-(1-|Bi|)e 容易驗(yàn)證11ni n(D L ) = D L =0所以，I D °L及1 一 . D L可逆，且(I -D,L 門(mén)=卜+D,L +

8、 (D,L尸11 n1< I +|D,L| +D,L =(I - D,L) iI - D L - I從而有B2e< I -( D'L DU e<(I - D,L 廣 ( I - D/L -(1 - B1 )I 於 o= I - (1 -間3 (I - D'L)eVB1Le因此必有B2L-IIB1II：因?yàn)橐阎猆 B11所以IIB2 U< 1.即高斯塞德?tīng)柕ㄊ諗?若矩陣a為對(duì)稱(chēng)，我們有定理3若矩陣A正定，則高斯一塞德?tīng)柕ㄊ諗?證明 把實(shí)正定對(duì)稱(chēng)矩陣 A分解為A = D - L - LT(U = LT ),則d為正定的，迭代矩陣 1 TB2 = D

9、- L LT設(shè)九是B2的任一特征值，X為相應(yīng)的特征向量，則D - L，LT x ) . x以D L左乘上式兩端，并由A=DL LT有1 -飛 LT x - Ax用向量x的共知轉(zhuǎn)置左乘上式兩端 ，得1 -XT LT x - XT Ax (11)求上式左右兩端的共斬轉(zhuǎn)置，得1 - x jxT L x =九 xT Ax以1 一九和1 一 &分別乘以上二式然后相加，得(1 - 1 11 - x |：xT(LT + L )x =(九 十 九一2九 x XT Ax 由 A = D L LT,得1 -1- - XT D - Ax 二 一-2 一 XT AxA JIJ即2 T22 X T(12)1 九

10、 x L x =(1 九 x x Ax因?yàn)锳和D都是正定的，且x不是零向量，所以由(11)式得九0 1,而由(12)式得 、21 一九0，即人< L從而P(B2 )< 1,因而高斯一塞德?tīng)柕ㄊ諗?定義1設(shè)A=(aj)n刈為n階矩陣.如果naH| > Z aj , i =1,2,.n j1(13)即A的每一行對(duì)角元素的絕對(duì)值都嚴(yán)格大于同行其他元素絕對(duì)值之和，則稱(chēng)A為嚴(yán)格對(duì)角優(yōu)勢(shì)矩陣.如果naj 之 £ aj , i = 1,2,.nj -*：且至少有一個(gè)不等式嚴(yán)格成立，則稱(chēng)A為弱對(duì)角優(yōu)勢(shì)矩陣.2-101-1 013112-1例如013：是嚴(yán)格對(duì)角優(yōu)勢(shì)矩陣，0131

11、是弱對(duì)角優(yōu)勢(shì)矩陣An、_ a = (a ) 一 . n定義2 設(shè)八 aj 4沏是n階矩陣，如果經(jīng)過(guò)行的互換及相應(yīng)列的互換可化為J 0即存在n階排列矩陣P,使T A A2IPTAP =|其中A11 ,A22為方陣，則稱(chēng)A是可約矩陣，意味著：0 A221A是可約的，否則稱(chēng)A為不可約的.Ax = b可經(jīng)過(guò)若干次行列重排，化為兩個(gè)低階方程組，事實(shí)上,Td1P b = d = | .P b d*2)Ax = b可化為 PTAP(PTx)=PTb 記PT必P x=y= y"于是，求解 Ax = b化為求解j A11y。a12y(2)= d(1)%y 2 = d 2可以證明，如果A為嚴(yán)格對(duì)角優(yōu)勢(shì)矩

12、陣或?yàn)椴豢杉s弱對(duì)角優(yōu)勢(shì)矩陣，則A是非奇異的定理4 如果A為嚴(yán)格對(duì)角優(yōu)勢(shì)矩陣或?yàn)椴豢杉s弱對(duì)角優(yōu)勢(shì)矩陣，則對(duì)任意X(),雅可比迭代法(4)與高斯一塞德?tīng)柕?8)均為收斂的.證明 下面我們以 A為不可約弱對(duì)角優(yōu)勢(shì)矩陣為例，證明雅可比迭代法收斂， 其他證明留給讀者.要證明雅可比迭代法收斂，只要證P(R )<1, Bi是迭代矩陣.用反證法,設(shè)矩陣Bi有某個(gè)特征值»，使得1至1,則det(因-Bi )= 0 ,由于A不可約,1且具有弱對(duì)角彳t勢(shì)，所以D 存在，且T - Bi = ；I - I - DA = DD A - D從而det lD A - D =0另一方面，矩陣(ND + A D )與矩陣a的非零元素的