0 2
min ( L ) ( Lo p t ).
对某些特殊类型的矩阵，已建立了SOR方法最佳松弛因 子理论. 例如，对所谓具有“性质A ” 等条件的线性方程组 建立了最佳松弛因子公式
19
opt
2 1 1 ( ( J ))
2
,
其中 ( J ) 为解 Ax b 的雅可比迭代法的迭代矩阵的谱半径. 在实际应用中，对于某些椭圆型微分方程(模型问题)， 可以给出 opt 的计算方法， 但一般来说，计算 opt 是有困难的，可用试算的办法 来确定一个适当的 . 算法2 (SOR迭代法) 设 Ax b ，其中 A 为对称正定 矩阵或为严格对角占优阵或为弱对角占优不可约矩阵等，
8. 如果k N 0 则转3
9. 输出N0及有关信息
(k ) r 也可用
eps来控制迭代终止，其中 r ( k ) b Ax( k ) .
22
6.4
分块迭代法
23
上述迭代法，从 x ( k ) x ( k 1) 计算时，是逐个计算 x ( k 1) 的分量 xi( k 1) (i 1,2, , n)，这种迭代法又称为点迭代
7
定理7 设 Ax b , 如果： (1) A为严格对角占优阵，则解 Ax b 的雅可比迭 代法，高斯-塞德尔迭代法均收敛. (2) A为弱对角占优阵，且 A为不可约矩阵，则解
Ax b雅可比迭代法，高斯-塞德尔迭代法均收敛.
证明 只证(1)中高斯-塞德尔迭代法收敛，其他同理. 由设可知， aii 0 (i 1,, n)，解 Ax b的高斯-塞 德尔迭代法的迭代矩阵为
xk max xi 0.
1i n
由齐次方程组第 k 个方程
a
则有
j 1
n
kj
x j 0,
6
akk xk
a
j 1 j i
n
kj
x j akj x j xk
j 1 j i
n
a
j 1 j i
n
kj
,
即
akk akj ,
j 1 j i
n
与假设矛盾，故 det( A) 0.
所以
( ) i , ( ) i
从而

2
( ) 2 2 2 . 2 2 2 ( )
当 0 2 时，利用(3.7)，(3.8)，有
( ) 2 ( ) 2 ( 2 )( 2) 0,
10
定理8 (SOR方法收敛的必要条件) 设解方程组 Ax b 的SOR迭代法收敛，则 0 2.
证明
由SOR迭代法收敛，则由定理4的推论中的(3)
det( L ) 12 n ( L )n ,
有 ( L ) 1 ，设 L 的特征值为 1 , 2 ,, n ，则
法.
分块迭代法，就是一块或一组未知数同时被改进. 设 Ax b，其中 A R nn 为大型稀疏矩阵且将 A 分 块为三部分 A D L U ，
A11 A21 A A q1 A12 A22 Aq 2 A1q A11 A2 q , D Aqq A22 , Aqq
(i 1,2, , n).
且上式至少有一个不等式严格成立，称 A为弱对角占优阵.
1
定义4 (可约与不可约矩阵) 设 A (aij ) nn (n 2) , 如果存在置换阵 P 使
A11 P AP 0
T
A12 , A22
（3.6）
其中 A11为 r 阶方阵， A22为 n r 阶方阵 (1 r n)， 则称
且记
y1 d1 T y P x y , P b d 2 2
T
其中 y1 , d1 为 r 维向量. 于是，求解 Ax b化为求解
3
A11 y1 A12 y2 d1 , A22 y2 d 2 .
由上式第2个方程组求出 y 2 , 再代入第1个方程组求出 y1.
6.3.2
关于解某些特殊方程组迭代法的收敛性
定义3 (对角占优阵) 设 A (aij ) nn . (1) 如果 A的元素满足
aii aij
j 1 j i n
(i 1,2, , n).
称 A为严格对角占优阵. (2) 如果 A 的元素满足
aii aij
j 1 j i n
（3.10）
这说明，所需迭代次数与 R ln ( B) 成反比.
( B) 1 越小， R ln ( B) 越大，由(3.10)式所需
迭代次数越少，即迭代法收敛越快.
18
定义5
称 R( B) ln ( B) 为迭代法(3.9)的渐近收敛
速度，简称迭代法收敛速度. 对于SOR迭代法希望选择松弛因子 使迭代过程(2.10) 收敛较快，在理论上即确定 opt 使
或
det( L )
1/ n
( L ) 1.
另一方面
det( L ) det[( D L) 1 ]det((1 ) D U ) (1 ) n ,
11
从而
det( L )
1/ n
1 1,
即
0 2.
定理8说明解 Ax b的SOR迭代法，只有在 (0,2)范围 内取松弛因子 ，才可能收敛. 定理9 如果： 设 Ax b ，
cii aii
i1
n i1 aij aij j i1 j1

aij aij cij
j 1 j i1
j 1 j i
n
n
(i 1,2,, n).
这说明，当 1 时，矩阵 C为严格对角占优阵， 再由对角占优定理有 det(C ) 0.
det( ( D L) U ) 0
之根. 记
a11 a21 C ( D L) U a n1 a12 a22 a1n a2 n , ann
9
an 2
下面证明，当 1时，det( C ) 0 ，即 G的特征值 均满足 1，由基本定理，则有高斯-塞德尔迭代法收敛. 事实上，当 1 时， 由 A为严格对角占优阵，有
0 1 . 1 4
(ai ,bi ,ci 都不为零 )
则 A, B 都是不可约矩阵.
5
定理6 (对角占优定理) 如果 A (aij ) nn 为严格对角 占优矩阵或 A为不可约弱对角占优矩阵，则 A为非奇异矩阵. 证明 只就 A为严格对角占优阵证明此定理. 采用反证法， 如果 det( A) 0 ，则 Ax 0 有非零解， 记为 x ( x1 , x2 , , xn )T, 则
A为可约矩阵.
否则，如果不存在这样置换阵 P 使(3.6)式成立，则 称 A为不可约矩阵.
A为可约矩阵意即 A可经过若干行列重排化为(3.6)或
2
Ax b可化为两个低阶方程组求解.
如果 A 经过两行交换的同时进行相应两列的交换， 称对 A进行一次行列重排. 事实上，由 Ax b 可化为
PT AP( PT x) PT b,
G ( D L) 1U ( A D L U )
8
下面考查 G的特征值情况.
det( I G) det( I ( D L) 1U ) det(( D L) 1 )det( ( D L) U ).
由于 det(( D L) 1 ) 0, 于是 G特征值即为
迭代法收越快.
16
现设有方程组
x Bx f , B R nn
及一阶定常迭代法
x ( k 1) Bx ( k ) f
k
(k 0,1,),
（3.9）
， 则 x* Bx * f . 且设迭代法收敛，记 lim x ( k ) x *
由基本定理有 0 ( B) 1, 且误差向量 ( k ) x ( k ) x *
24
0 A21 L A q1
0 Aq 2
0 , U 0
A12 0

q
A1q A2 q . 0
( D L) 1 ((1 ) D U ) y y,
亦即
((1 ) D U ) y ( D L) y.
为了找出 的表达式，考虑数量积
(((1 ) D U ) y, y ) (( D L) y, y ),
13
则

显然
( Dy , y ) ( Dy , y ) (Uy, y ) , ( Dy , y ) ( Ly, y )
( Dy , y ) aii yi
i 1
n
2
0,
（3.7）
记 由于 A AT
( Ly, y ) i ,
所以 U LT , 故 （3.8）
14
(Uy, y ) ( y, Ly ) ( Ly, y ) i , 0 ( Ay, y ) (( D L U ) y, y ) 2 ,
显然，如果 A 所有元素都非零，则 A为不可约阵.
4
例7 设有矩阵
b1 a2 A c1 b2 c2 an1 bn1 an 4 , 1 B 1 cn1 0 bn
1 4 0 1
1 0 4 1
即 L 的任一特征值满足 1， 故SOR方法收敛 当 0 2 时， 可以证明 ( ) 2 2 2 0.