雅克比高斯赛德尔迭代法

1、-WORDB式一可编辑-第八节 雅可比迭代法与高斯一塞德尔迭代法雅可比迭代法设线性方程组Ax = b 的系数矩阵 A可逆且主对角元素all ,a22,，ann均不为零，令D = diagan,a22，.,ann并将A分解成A= A- D D 从而（i）可写成Dx = D - A x b令x = B1x f1 11.其中 B1 = I - D A, f1 = D b.以B1为迭代矩阵的迭代法（公式）xf= Bx（k）+fl称为雅可比（Jacobi）迭代法（公式），用向量的分量来表示，（4）为其中x(k1)I biaiii =1,2,.n,nzj 1j寸k(k) aij xj= 0,1,2,.乂期

2、）"）.为初始向量.在电算时需由此看出，雅可比迭代法公式简单，每迭代一次只需计算一次矩阵和向量的乘法要两组存储单元，以存放 x儿x”）例1例1用雅可比迭代法求解下列方程组10x1 - x2 - 2x3 = 7.2-Xi 10x2-2x3 =8.3Xix2 5x3 =4.2Xi 二x2 =0.1x1IX3 =0.2Xi将方程组按雅可比方法写成0.1x2 0.2x30.720.2x30.830.2x20.84取初始值xgxRxgxfN=（0,0,0,）按迭代公式Xik 1 =0.1x2k 0.2xJ 0.72X2k1 =0.1x1k0.2x3k0.83x3k 1 =0.2x1k0.2x2

3、k0.84I进行迭代，其计算结果如表1所示表1k01234567x1（k）00.720.9711.0571.08531.09511.0983x2k)00.831.0701.15711.18531.19511.1983xC00.841.1501.24821.28281.29411.2980高斯塞德尔迭代法由雅可比迭代公式可知，在迭代的每一步计算过程中是用xk）的全部分量来计算x（k*）的所k 1k 1k 1有分量，显然在计算第i个分量X 时，已经计算出的最新分量x1，,X-1没有被利用，从直观上看，最新计算出的分量可能比旧的分量要好些.因此，对这些最新计算出来的第k 1x k 1k +1次近似X

4、1牺分量xj加以利用，就得到所谓解方程组的高斯一塞德（Gauss-Seidel ） 迭代法.把矩阵A分解成A = D - L - U 其中D =diag（ a11 ,电2 ,ann ）, - L ,-U分别为A的主对角元除外的下三角和上三角 部分，于是，方程组（1）便可以写成D - L x = Ux b即x = B2xf2其中11B2 = D - L U ,f2 = D - L b 以B2为迭代矩阵构成的迭代法（公式）xE= BzX” f2称为高斯一塞德尔迭代法（公式），用量表示的形式为i 4n.xi（）b - v ajx；） - v aj xj ） aiiHG i=1,2，n, k = 0,

5、1,2，（9）（计算出由此看出，高斯一塞德尔迭代法的一个明显的优点是，在电算时，只需一组存储单元k1kk1kx后xi不再彳1用，所以用x 冲掉xi ,以便存放近似解.例2例2用高斯一一塞德尔迭代法求解例1.解取初始值xC）=（xF）x2°）x3）=（°，0,0，）,按迭代公式X1k1 二X2k1 =0.1x1k10.1x2k0.2x3k0.720.2x3k0.830.84x3k1 =0.2/k10.2x2k1进行迭代，其计算结果如下表2表2k01234567x1（k）00.721.043081.093131.099131.099891.099991.1短00.9021.16

6、7191.195721.199471.199931.199991.2x3k)01.16441.282051.297771.299721.299961.31.3从此例看出，高斯一塞德尔迭代法比雅可比迭代法收敛快 （达到同样的精度所需迭代次数少 ，但 这个名论，在一定条件下才是对的，甚至有这样的方程组，雅可比方法收敛，而高斯 一塞德尔迭代 法却是发散的.迭代收敛的充分条件定理1在下列任一条件下，雅可比迭代法（5）收敛.a/=maxZ < 1B10Bi 1 = max"1j i 1aijI - DATn- 二max" j i=1i=jaijajjaH定理2设B1，B2分别为

7、雅可比迭代矩阵与高斯一塞德尔迭代矩阵，则(10)B2B1从而，当旧” max骑<1时，高斯一塞德尔迭代法（8）收敛.证明 由B,B2的定义，它们可表示成1_ DLDUB1 = D L UB2 = D - L,U = I用e表示n维向量e =（1,1,.,1），则有不等式 B1e|B1|QCeB1 =| DL | + DU这里，记号I |表示其中矩阵的元素都取绝对值，而不等式是对相应元素来考虑的 ，于是D JU e = (Bi - D-L|e<0 - D,L - (1-|BL)】e 容易验证 11ni n(D L ) = D L =0所以，I D °L及1 D L可逆，且(

8、I -D,L 门=卜+D,L + (D,L尸11 n1< I +|D,L| +D,L =(I - D,L)iI - D L - I从而有B2e< I -( D'L DU e«(ID,L 忖 ( I -|DL T1-怛1日 Je= I - (1 -间3 (I -| DL)e*he因此必有B2B1 二因为已知IB11所以IB213 1.即高斯一塞德尔迭代法收敛.若矩阵A为对称，我们有定理3若矩阵A正定，则高斯一塞德尔迭代法收敛.证明 把实正定对称矩阵 A分解为A = D - L - LT(U = LT ),则d为正定的，迭代矩阵 1 TB2 = D - L LT设九是

9、B2的任一特征值，X为相应的特征向量，则D - L，LT x ) . x以D L左乘上式两端，并由A=DL LT有1 -飞 LT x - Ax用向量x的共知转置左乘上式两端 ，得1 - XT LT x - XT Ax (11)求上式左右两端的共斩转置，得1 - x jxT L x =九 xT Ax以1 一九和1 一 &分别乘以上二式然后相加，得(1 - 1 11 - x |：xT(LT + L 义=(九 十 九一2九 x XT Ax 由 A = D L LT,得1 -1- - XT D - Ax 二 一-2 一 XT AxA JIJ即2 T22 X T(12)1 九 x L x =(1

10、 九 x x Ax因为A和D都是正定的，且x不是零向量，所以由(11)式得九0 1,而由(12)式得 、21 一九0，即人< L从而P(B2 )< 1,因而高斯一塞德尔迭代法收敛.定义1设A=(aj)n刈为n阶矩阵.如果naH| > Z aj , i =1,2,.n j1(13)即A的每一行对角元素的绝对值都严格大于同行其他元素绝对值之和，则称A为严格对角优势矩阵.如果naii 之 £ aj , i = 1,2,.nj -*：且至少有一个不等式严格成立，则称A为弱对角优势矩阵.2-101-1 013112-1例如013是严格对角优势矩阵，013 :是弱对角优势矩阵A

11、n、_ a = (a ) 一 . n定义2 设八 aj 4沏是n阶矩阵，如果经过行的互换及相应列的互换可化为J 0即存在n阶排列矩阵P,使T AA2IPTAP =|：0A221其中A11 ,A22为方阵，则称A是可约的，否则称A为不可约的A是可约矩阵，意味着 Ax = b可经过若干次行列重排，化为两个低阶方程组，事实上Ax = b可化为PTAP(PTx)= PTb 记PT了"P x=y=y(2)于是，求解 Ax = b化为求解j A11y。a12y(2)= d(1)%y 2 = d 2，则A是非奇异的可以证明，如果A为严格对角优势矩阵或为不可约弱对角优势矩阵定理4 如果A为严格对角优势矩阵或为不可约弱对角优势矩阵，则对任意X(),雅可比迭代法(4)与高斯一塞德尔迭代法(8)均为收敛的.证明 下面我们以 A为不可约弱对角优势矩阵为例，证明雅可比迭代法收敛，其他证明留给读者.要证明雅可比迭代法收敛，只要证P(R )<1, Bi是迭代矩阵.用反证法,设矩阵Bi有某个特征值»，使得1至1,则det(因-Bi )= 0 ,由于A不可约,1且具有弱对角彳t势，所以D 存在，且T - Bi = ；I - I - DA = DD A - D从而det lD A - D =0另一方面，矩阵(ND + A D )与矩阵a的非零元素的位置是