cii aii



i1 j1
aij

n
aij
ji1

i1
n
n
aij aij cij
j1
ji1
j1
ji
(i 1,2,,n).
这说明，当 时，1矩阵 为严C格对角占优阵，
再由对角占优定理有 det(C) 0.
9
定理8 (SOR方法收敛的必要条件) 设解方程组 Ax b

4 1 1 0
A

an1
bn1 an
,
cn1
bnBiblioteka B
1 1 0
4 0 1
0 4 1
411.
(ai ,bi ,ci都不为零 )
则 A,都B 是不可约矩阵.
4
定理6 (对角占优定理) 如果 A (aij 为)n严n 格对角 占优矩阵或 A为不可约弱对角占优矩阵， 则 A为非奇异矩阵.
akj x j
akj x j xk
akj ,
j 1
j 1
j 1
ji
ji
ji
即 n
akk
akj ,
j 1
ji
与假设矛盾，故 det( A) 0.
6
定理7 设 Ax , b 如果： (1) 为A严格对角占优阵，则解 代法，高斯-塞德尔迭代法均收敛.
A的x雅可b比迭
(2) 0 2.
则解 Ax 的bSOR迭代法收敛.
11
证明 在上述假定下，只需证明 ，1 其中 为 L
的任一特征值.
事实上，设 为y对应 的 的特L征向量， 即
亦即
L y y, y ( y1, y2 ,, yn )T 0, (D L)1((1)D U ) y y,
显然 记
n
(Dy, y) aii yi 2 0, i1 (Ly, y) i ,
由于 A AT 所以 U L, T 故
(Uy, y) ( y,Ly) (Ly, y) i ,
0 ( Ay, y) ((D L U ) y, y) 2 ,
a12
a1n
C
(D L) U


a21

a22


a2n
,
an1 an2 ann
8
下面证明，当 时，1 de，t(C即) 的0特征值G 均满足 ，1 由基本定理，则有高斯-塞德尔迭代法收敛.
事实上，当 时，1 由 A为严格对角占优阵， 有
((1 )D U ) y (D L) y.
为了找出 的表达式，考虑数量积
(((1 )D U ) y, y) ((D L) y, y),
12
则 (Dy, y) (Dy, y) (Uy, y) , (Dy, y) (Ly, y)
定义4 (可约与不可约矩阵) 设 A (aij )nn ,(n 2) 如果存在置换阵 P使
PT
AP


A11 0
A12 A22
,
其中 A1为1 阶r 方阵， 为A22 阶n 方 r阵
A为可约矩阵.
（3.6） ，(1 r n) 则称
否则，如果不存在这样置换阵 使P(3.6)式成立，则
另一方面
det( L ) det[( D L)1]det((1)D U ) (1)n ,
10
从而 det( L ) 1/ n 1 1,
即 0 2.
定理8说明解 Ax的SObR迭代法，只有在 范(围0,2)
内取松弛因子 ，才可能收敛.
定理9 设 Ax ，b 如果： (1) 为A对称正定矩阵， A D L U ;
(2) 为A弱对角占优阵，且 为不A可约矩阵，则解 Ax 雅b可比迭代法，高斯-塞德尔迭代法均收敛.
证明 只证(1)中高斯-塞德尔迭代法收敛，其他同理.
由设可知， aii 0 (i ，1解,, n)的高斯A-x塞 b 德尔迭代法的迭代矩阵为
G (D L)1U ( A D L U )
b


d1 d2

其中 y1, 为d1 维向r 量.
于是，求解 Ax 化b为求解
2

A11
y1

A12 y2 A22 y2

d1 , d2.
由上式第2个方程组求出 y2, 再代入第1个方程组求出 y1.
显然，如果 所A有元素都非零，则 为A不可约阵.
3
例7 设有矩阵
b1 c1 a2 b2 c2
（3.7）
（3.8）
13
所以 从而
( ) i , ( ) i
称 A为不可约矩阵.
为A可约矩阵意即 可A经过若干行列重排化为(3.6)或
1
Ax 可b化为两个低阶方程组求解.
如果 经A过两行交换的同时进行相应两列的交换， 称对 A进行一次行列重排.
事实上，由 Ax可化b为
PT AP(PT x) PT b,
且记
y

PT
x


y1 y2
,
PT
7
下面考查 的G特征值情况.
det(I G) det(I (D L)1U ) det(( D L)1)det((D L)U ).
由于 det(( D L,)1) 0 于是 G特征值即为
det( (D L) U ) 0
之根. 记
a11
的SOR迭代法收敛，则 0 2.
证明 由SOR迭代法收敛，则由定理4的推论中的(3)
有 (L )， 1 设 L的 特征值为 1, 2 ,，, n 则
det( L ) 12n (L )n ,
或 det( L ) 1/n (L ) 1.
证明 只就 A为严格对角占优阵证明此定理.
采用反证法， 如果 det( A)， 0 则 Ax 有0非零解，
记为 x ( x1, x2 , , , xn )T 则
xk

max
1i n
xi
0.
由齐次方程组第 个k方程
则有
n
akj x j 0,
j 1
5
n
n
n
akk xk