第八节 雅可比迭代法与高斯—塞德尔迭代法
一 雅可比迭代法
设线性方程组
Ax?b (1) a,a,...,ann均不为零,令
的系数矩阵A可逆且主对角元素1122 并将A分解成
D?diag?a11,a22,...,ann?
A?从而(1)可写成 Dx令
?A?D??D (2)
??D?A?x?b
x?B1x?f1
?1?1B?I?DA,f?Db. (3) 1其中1以
B1为迭代矩阵的迭代法(公式)
x?k?1??B1x?k??f1 (4)
称为雅可比(Jacobi)迭代法(公式),用向量的分量来表示,(4)为
???x(k?1)i1?aiiT?bi??aijx(jk)j?1j?in? (5)
i?1,2,...n,k?0,1,2,...?0??0??0??0???x?x,x,...x12n其中
为初始向量.
由此看出,雅可比迭代法公式简单,每迭代一次只需计算一次矩阵和向量的乘法.在电算时需
?k??k?1?要两组存储单元,以存放x及x. 例1 例1 用雅可比迭代法求解下列方程组
?10x1?x2?2x3?7.2???x1?10x2?2x3?8.3??x?x?5x?4.223?1
解 将方程组按雅可比方法写成
?x1?0.1x2?0.2x3?0.72???0.2x3?0.83?x2?0.1x1?x3?0.2x1?0.2x2?0.84??
TT?0??0??0??0??x?x,x2,x3???0,0,0,?按迭代公式 1取初始值
?k??x1?k?1??0.1x2?0.2x3?k??0.72???k?1??k??0.2x3?k??0.83?x2?0.1x1??k?1??k??k?x?0.2x?0.2x?0.84312??
进行迭代，其计算结果如表1所示
表1
3 k 0 0 0 0 1 0.72 0.83 0.84 2 0.971 1.070 1.150 4 5 1.0951 1.1951 1.2941 6 1.0983 1.1983 1.2980 7 … … … x1?k? ?k?x2 1.057 1.0853 1.1571 1.2482 1.2828 1.1853 x3?k? 二 高斯—塞德尔迭代法
由雅可比迭代公式可知,在迭代的每一步计算过程中是用x?k?的全部分量来计算x?k?1??k?1?的所
x有分量,显然在计算第i个分量ik?1次近似x?k?1??k?1?没有被利
用，从直观上看,最新计算出的分量可能比旧的分量要好些.因此，对这些最新计算出来的第
的分量
x时,已经计算出的最新分量1,...,xi?1?k?1?xj?k?1?加以利用,就得到所谓解方程组的高斯—塞德（Gauss-Seidel）
迭代法.
把矩阵A分解成
A?D?L?U (6)
D?diag?a11,a22,...,ann?,?L,?U分别为A的主对角元除外的下三角和上三角其中
部分,于是,方程组(1)便可以写成 即 其中
?D?L?x?Ux?b
x?B2x?f2
B2??D?L?U,?1f2??D?L?b (7)
?1以
B2为迭代矩阵构成的迭代法(公式)
x?k?1??B2x?k??f2 (8)
称为高斯—塞德尔迭代法(公式),用 量表示的形式为
???x(k?1)ii?1n1(k?1)??bi??aijxj??aijx(jk)j?1j?i?1aii? (9)
i?1,2,?n,?k?1?k?0,1,2,...?k?由此看出,高斯—塞德尔迭代法的一个明显的优点是,在电算时,只需一组存储单元(计算出
xi?k?1?x后i?k?x不再使用,所以用ix冲掉i,以便存放近似解.
例2 例2 用高斯——塞德尔迭代法求解例1.
?0??0??0??0??x?x,x2,x3???0,0,0,?1解 取初始值
TT，按迭代公式
?k??x1?k?1??0.1x2?0.2x3?k??0.72??k?1??k?1??0.2x3?k??0.83?x2?0.1x1?x?k?1??0.2x?k?1??0.2x?k?1??0.8412?3
进行迭代，其计算结果如下表2
表2 0 1 2 k 3 1.09313 1.19572 1.29777 4 5 6 7 x1?k? ?k?x2 0 0 0 0.72 1.04308 1.09913 1.09989 1.09999 1.1 1.19947 1.19993 1.19999 1.2 1.29972 1.29996 1.3 1.3 0.902 1.16719 1.1644 1.28205 x3?k? 从此例看出,高斯—塞德尔迭代法比雅可比迭代法收敛快(达到同样的精度所需迭代次数少),但这个结论,在一定条件下才是对的,甚至有这样的方程组,雅可比方法收敛，而高斯—塞德尔迭代法却是发散的.
三 迭代收敛的充分条件
定理1 在下列任一条件下,雅可比迭代法(5)收敛.
nB1①
??max?iaijaii?1;
j?1j?iB1②
1?max?ji?1j?i?1T?naijaii?1;
nI?DA③ 定理2 设
?max?ji?1i?jaijajj?1
B1,B2分别为雅可比迭代矩阵与高斯—塞德尔迭代矩阵,则
B2??B1? (10)
从而，当
B1??max?inaijaii?1
j?1j?i时，高斯—塞德尔迭代法(8)收敛. 证明 由
B1,B2的定义,它们可表示成
B1?D?1?L?U?
?1?1B2??D?L?U??I?D?1L?D?1U
T??e?1,1,...,1用e表示n维向量,则有不等式
B1e?B1?e
这里,记号｜·｜表示其中矩阵的元素都取绝对值,而不等式是对相应元素来考虑的,于是
B1?D?1L?D?1UD?1Ue??B1?D?1L?e??I?D?1L??1?B1容易验证
???Ie
?DL??1n?DL?0可逆，且
?1n
?1I?DL所以,I?DL及
?1?I?D?1L??1?I?D?1L?...??D?1L??I?D?1L?...D?1Ln?1n?1??I?D?1L??1?I?DL??1
?1?I
从而有
B2e?I??D?1L??I?D?1L??I??1??B1?e因此必有
??1?D?1Ue?11??1???I?DL??1?B?I?e
B?I??I?DL??e?1?11?
B2因为已知
???B1?
B1??1所以B2?1.即高斯—塞德尔迭代法收敛.
若矩阵
A为对称，我们有
定理3 若矩阵A正定,则高斯—塞德尔迭代法收敛.
证明 把实正定对称矩阵A分解为
A?T?U?L?,则D为正定的,迭代矩阵
设?是
D?L?LT
B2??D?L?LT
?1B2的任一特征值,x为相应的特征向量,则
LT?x???x
T以D?L左乘上式两端,并由A?D?L?L有
?1???LTx??Ax
用向量x的共轭转置左乘上式两端,得
?1?D?L??1???x求上式左右两端的共轭转置,得
?TLx??xAx (11)
T??T???1???xTLx??xTAx????
?以1??和1??分别乘以上二式然后相加,得
????TTT????1????1???x?L?L?x??????2????xAx???? T由A?D?L?L,得
?????T?????1????1???x?D?A?x??????2???xTAx????
??即
1??xLx?1???xAx (12)
因为A和D都是正定的,且x不是零向量,所以由(11)式得?22?T?2??T?1,而由(12)式得
1???0, 即??1,从而??B2??1,因而高斯—塞德尔迭代法收敛.
定义1 设① ①如果
A??aij?n?nn为n阶矩阵.
aii??aij,j?ij?ii?1,2,...n (13)
即A的每一行对角元素的绝对值都严格大于同行其他元素绝对值之和，则称A为严格对角优势矩阵.
② ②如果
aii??aij,j?ij?ini?1,2,...n
且至少有一个不等式严格成立,则称A为弱对角优势矩阵.
?2?10??1?10??131??12?1??????013?3??是严格对角优势矩阵，??01?是弱对角优势矩阵. 例如??A11?0A??aij?n?n定义2 设是n阶矩阵，如果经过行的互换及相应列的互换可化为?即存在n阶排列矩阵P,使
A12?A22??,
?A11A12?PAP???0A?22?
A,A其中1122为方阵，则称A是可约的,否则称A为不可约的.
TA是可约矩阵,意味着Ax?b可经过若干次行列重排,化为两个低阶方程组,事实上,
TTTAx?b可化为 PAP?Px??Pb,记
?1??1?yd????TTPx?y???2??,Pb?d???2???y??d?
于是，求解Ax?b化为求解
?1??2??1?Ay?Ay?d??1112??2??2??Ay?d?22?
可以证明,如果A为严格对角优势矩阵或为不可约弱对角优势矩阵,则A是非奇异的.
定理4 如果A为严格对角优势矩阵或为不可约弱对角优势矩阵,则对任意x,雅可比迭代法(4)与高斯—塞德尔迭代法(8)均为收敛的.
证明 下面我们以A为不可约弱对角优势矩阵为例，证明雅可比迭代法收敛，其他证明留给读者.
要证明雅可比迭代法收敛，只要证用反证法,设矩阵
?0???B1??1,B1是迭代矩阵.
B1有某个特征值?,使得??1,则det??I?B1??0,由于A不可约,
?1且具有弱对角优势，所以D存在，且 从而
?I?B1??I??I?D?1A??D?1??D?A?D?
??D?A?D??0
另一方面，矩阵??D?A?D?与矩阵A的非零元素的位置是完全相同的，所以??D?A?D?也是不可约的,又由于??1,且A弱对角优势，所以
det?aii?aii??aij,j?ij?ini?1,2,...n并且至少有一个i使不等号严格成立.因此,矩阵
??D?A?D?为不可约弱对角优势矩阵.从而
det??D?A?D??0
矛盾，故
??D?A?D?弱对角优势，故
B1的特征值不能大于等于1，定理得证.
（完整版）第八节雅可比迭代法与高斯-塞德尔迭代法综述
