为控制迭代终止的条件。 但要注意当q?1时，
q较大，尽管x(k)?x(k?1)很小，却有可能误差向量模q?1?(k)?x*?x(k)很大，迭代法收敛很慢。而且此充分性条件的结果(3)可以用来事先确定需要迭代多少次才能保证?(k)??。
定理6.3.10 解方程组Ax?b的G-S迭代法收敛的充分必要条件是?(G)?1，G为G-S迭代矩阵。
定义6.3.7 （对角占优矩阵）设A?(aij)n?n
(1) 若aii??aij?0(i?1~n)，即A的每一行对角元素绝对值严格大于同行其
j?1j?in他元素绝对值之和。则称A为严格对角占优矩阵。
(2) 若aii??aij?0(i?1~n)，且至少有一个不等式严格成立，则称A为弱对
j?1j?in角占优矩阵。
定义6.3.8 （可约与不可约矩阵）设A?(aij)n?n，当n?2时，如果存在n阶排列
?A矩阵p使pTAp??11?0A12?成立。其中A11为r阶子矩阵，A22为n?r阶子矩阵?A22?（1?r?n），则称矩阵A为可约的。若不存在排列矩阵p使上式成立，则称A为不可约矩阵。当A为可约矩阵，则Ax?b可经过若干行列重排化为两个低阶方程
?y??d?组求解。事实上，由Ax?b化为：设y?PTx??1?,PTb??1?，PTAP(PTx)?PTb，
?y2??d2?其中y1,d1为r维向量。
?Ay?Ay?d1 于是，求解Ax?b化为求解：?111122，另外A为可约矩阵的充要
?A22y2?d2条件：存在指标集J??1,2,,n?,J??使akj?0，k?J，j?J.
定理6.3.11（对角占优定理）：若A?(aij)n?n为严格对角占优阵或为不可约弱对角占优阵，则A是非奇异阵。 证明 (1)A为严格对角占优阵，采用反证法。若detA?0，则Ax?0有非零的解，
146 / 18
设为x?(x1x2xn)T?0。设xk?maxxi由齐次方程中的第k个方程得：
1?i?nxi?0?ai?1nkixj?0，则可得：
akkxk?n?aj?1j?knkjxj??akj?xj?xkj?1j?kn?aj?1j?knkj (6.3.10)
即有：akk??akj这与严格对角占优阵矛盾，故detA?0。
j?1j?k(2)A为不可约弱对角占优阵，采用反证法。 设?x?0,x?(x1xn)使Ax?0。并令m使amm??amj.(6.3.11)（由弱对角占
Tj?1j?mn优定义）成立。再定义下标集合：
J??kxk?xi,i?1n,xk?xj.对某个j?
在(6.3.10)中取k?m，将导致与(6.3.11)得矛盾。故J??（空集合）。对任意
k?J，有ak??jkaj?xk/x（由(6.3.10)），由此可见，当xk?xj时有akj?0。
j?1j?kn否则，上式就与A为弱对角占优阵矛盾。
但对任意k?J和j?J，必有xk?xj，因而akj?0,k?J,j?J从而A为可约矩阵，这与A为不可约矩阵假设矛盾。
定理6.3.12 若A?Rn?n为严格对角占优矩阵或为不可约对角占优矩阵，则对任意的初始向量x(0)，方程组Ax?b的Jacobi迭代法和G-S迭代法均收敛。且G-S迭代法比Jacobi迭代法收敛速度快。
证明 设A为不可约对角占优矩阵，先证明G-S迭代法收敛。由弱对角占优阵假设知aii?0,(i?1~n)，而G-S迭代矩阵为G?(D?L)?1U，又det(D?L)?1?0，
det(?I?G)?det(?I?(D?L)?1U)?det(D?L)?1，det(?(D?L)?U)?0即
det(?(d?l)?U)?0.，记C??(D?L)?U。则：
147 / 18
??a11a12??a?a22c??21????an1?an2a1n??a23???a2n? ???an3????ann?a13???下面来证明当??1时，detC?0，这是因为A为不可约阵，则C也不可约，由A为弱对角矩阵，可得：
(当??1)cii??aii???aij?j?1i?1j?i?1?anij??cij
j?i且至少有一个不可约等式严格成立，这表明当??1时，C为不可约弱对角占优矩阵，于是由前一个定理可知当??1时，detC?0，这一结论表明detC?0的根?满足：??1，即?(G)?1，故G-S法收敛。
在同一条件下，对于Jacobi方法（J?D?1(L?U)）完全类似于上可证。当A为严格对角占优阵时，证明方法完全类似。
6.3.4 超松弛代法
逐次超松弛迭代法（Successive Over Relaxation Method.简称为SOR法）是Gauss-Seidel法的一种加速方法。这是解大型矩阵方程组的有效方法之一，具有计算公式简单、程序设计容易、占用计算机内存较少等优点，但需要选择好的加速因子，即最佳的加速因子。
对Ax?b(6.3.12)其中A?Rn?n为奇异矩阵，且设aii?0.(i?1n)，分解：
A?D?L?U (6.3.13)
设已知第k次迭代向量x(k)，及第k?1次迭代向量xi(k?1)的分量 x(jk?1()j?1,2,?i，现在来计算分量：1)先用G-S迭代法求出辅助量xi(k?1)（预测）
xi(k?1)i?1n1(k?1)?(bi??aijxj??aijx(jk)),i?1~n (6.3.14) aiij?1j?i?1再取xi(k?1)为xi(k)与xi(k?1)的某种平均值（即加权平均），即
xi(k?1)?(1??)xi(k)??xi(k?1)?xi(k)??(xi(k?1)?xi(k)) (6.3.15)（校正）将(6.3.14)代入(6.3.15)即得解Ax?b的逐次超松弛迭代公式：
148 / 18
x(k?1)ix(k)???aijx(jk))?aiij?1j?i? (6.3.16) (k)(k)?(x1(k),x2,???xn),(k?0.1,???,i?1~n)???x(k)i??(bi??aijxi?1(k?1)jn其中称?为松弛因子，或写为：
??i?1n???xi?(bi??aijx(jk?1)??aijx(jk))? (6.3.17)
aiij?1j?i??(k?0,1,???,i?1,2,~n)?xi(k?1)?xi(k)??xi显然??1时，解(6.3.12)的SOR法即为Gauss-Seidel迭代法。
SOR法中每迭代一次，主要计算量是计算一次矩阵与向量乘法。由(6.3.16)可见在计算机上用SOR法解方程组只需一组工作单位元，以便存放近似解。迭代计算时，可用p?max?xi?maxxi(k?1)?xi(k)??来控制迭代终止。
i1?i?n当??1时，称(6.3.16)为低松弛法；当??1时，称(6.3.16)为超松弛法。 例6.3.5 用SOR法解：
??4111??x1??1??1?411??x??1????2???? ?11?41??x3??1???????111?4???x4??1?其精确解为x*?(?1,?1,?1,?1)T。 解 取x(0)?0，则SOR迭代公式为：
(k)(k)(k)?x1(k?1)?x1(k)??(1?4x1(k)?x2?x3?x4/4?(k?1)(k)(k?1)(k)(k)(k)?x2?x2??(1?x1?4x2?x3?x4/4 ?(k?1)(k)(k?1)(k?1)(k)(k)?x3?x3??(1?x1?x2?4x3?x4/4(k?1)(k)(k?1)(k?1)(k?1)(k)?x?x??(1?x?x?x?4x41234/4?4取??1.3，第11次迭代结果为：
x(11)?(?0.99999646,?1.00000310,?0.99999953,?0.99999912)T
?(11)2?x(11)?x*2?0.46?10?5
对?取其它值，迭代次数如下表，由此例可见，松弛因子选择得好，会使SOR迭代的收敛大大加速。本例中，??1.3是最佳松弛因子。
表6.3.1 结果表
松弛因子 1.0 1.1 满足误差x?k??x*?10?5的迭代次数 22 17 149 / 18
1.2 1.3* 1.4 1.5 1.6 1.7 1.8 1.9 12 11*最少迭代次数 14 17 23 33 53 109 下面考察SOR迭代公式的矩阵形式，由(6.3.16)可改写为： ax(k?1)iii?(1??)ax(k)iii??(bi??aijxj?1i?1(k?1)j?j?i?1?axijn(k)j),i?1n (6.3.17)
（k?1)由A?D?L?U，则：Dx??(b?Lx(k?1)?Ux(k))?(1??)Dx(k)即
均为奇异阵（D??L)x(k?1)?((1??)D??U)x(k)??b，由于对任意? ，（D??L）（设aii?0.i?1~n,而L为下三角阵，且对角线元素为0）则：
x(k?1)?(D??L)?1?(1??)D??U?x(k)??(D??L)?1b.
因此，若aii?0,i?1~n，则SOR迭代公式为：
x(k?1)?L?x(k)?f (6.3.18) 其中L??(D??L)?1?(1??)D??U?,称L?为SOR方法的迭代f??(D??L)?1b，
矩阵，应用关于迭代法的收敛性定理于(6.3.18)可得：
定理6.3.13 对Ax?b，且aii?0(i?1~n)则解方程组的充要条件是：?(L?)?1。引进超松弛法的想法是希望能选择松弛因子使迭代过程(6.3.16)收敛较快，也就
（L?*）?min?（L?*）是应选择因子?*使?。
? 下面考虑对于方程组(6.3.12)（aii?0,i?1~n），超松弛因子在什么范围内取值才可能收敛。
定理6.3.14 （必要条件）对Ax?b，（aii?,0i1~?0???2。
n）的SOR方法若收敛，则：
证明 由SOR法收敛及上定理，知?（L?）?1，设L?的特征值为?1，?2，???，?n则：
det(L?)??1?2????n?(?(L?))，即det(L?)??(L?)?1，而
n1n150 / 18
回归问题——线性方程组求解的迭代法
