上一页 下一页1
第五章 线性方程组的解法上一页 下一页2
bxA?
12,,,Tnx x x x12,,Tnb b b b?
注：如果没有特别说明，下面总假定系数行列式的值 | | 0A?
其中
1 1 1 2 1
2 1 2 2 2
12
n
n
n n n n
a a a
a a a
A
a a a
且 | | 0A?
上一页 下一页3
利用 法则求解时存在的困难是：当方程组的阶数 很大时，计算量为
C ram er
n
常用计算方法,
直接解法,它是一类精确方法，即若不考虑计算过程中的舍入误差，那么通过有限步运算可以获得方程解的精确结果,
Gauss 逐步（顺序）消去法、
Gauss主元素法、矩阵分解法等；
( ( 1 ) ( 1 ) ! )O n n n
上一页 下一页4
迭代解法,所谓迭代方法，就是构造某种极限过程去逐步逼近方程组的解,
经典迭代法有,
迭代法,迭代法、Jacobi G a u s s S e i d e l?
逐次超松弛（ SOR）迭代法等；
上一页 下一页5
§ 1 预备知识上一页 下一页6
向量范数
向量范数定义 Rn空间的 向量范数 || · || 对任意 满足条件：
nRyx,
00||||;0||||)1( xxx （ 非负性 )
||||||||||)2( xx C对任意 (齐次性 )
||||||||||||)3( yxyx （ 三角不等式 )
常用向量范数：
n
i
ixx
1
1 ||||||
n
i i
xx
1
2
2 ||||||
pn
i
p
ip xx
/1
1
||||||
||max||||
1 ini
xx
注：
||||||||lim xx pp
上一页 下一页7
定义 对于任意两种范数 || · ||A,|| · ||B,总存在常数 C1,C2 > 0
使得,则称 || · ||A 和 || · ||B 等价 。
（范数等价性）
BAB xCxxC |||||||||||| 21
定理 Rn 上一切范数都等价。
上一页 下一页8
设 是在 上的一个范数，则 是的分量 的连续函数,
x nR x
x 12,,,nx x x
证明,对任何 1(,,),Tnx x x? 1(,,) Tny y y? 有
11
,
nn
j j j j
jj
x x e y y e
其中 是第 个基向量,je j
x y x y从而有
11
( ) | |
nn
j j j j j j
jj
x y e x y e
引理 1
上一页 下一页9
1
m a x | |
n
j j jj
j
e x y
因而当 时，yx? yx?
即 为 的连续函数,x x
（范数的等价性）对于 中任意两种范数nR
,,pq总存在常数 和,使对一切m M nxR?
都有
q p qm x x M x（ *）
证毕定理上一页 下一页10
证明 我们只需证明任意范数 px
与 Euclid范数 等价即可2x
考虑单位球面 2{,1 }nS y R y
它是 中的有界闭集，据引理 1,连续，nR py
并且它在 上达到最大值 和最小值S M m
0Mm其中于是对于任何,0nx R x 2/x x S?有
2/ pm x x M从而上一页 下一页11
故 时,（ *）成立0x?
当 时，（ *）显然成立
0x?
证毕对于常用的范数,,可以算出px 1,2,p
1 2 1
1 x x x
n
1x x n x
2x x n x
上一页 下一页12
定义 向量序列 收敛 于向量 是指对每一个 1? i? n 都有 。
}{ )(kx? *x?
*)(lim iki
k xx
可以理解为 0||*|| )(xx k
可以理解为对任何向量范数都成立。
向量序列的收敛性上一页 下一页13
Krylov子空间定义
210 0 0 0,,,,kr A r A r A r?
210 0 0 0 0(,,),,,,kK A r k s p a n r A r A r A r
0r A给定向量 和矩阵,我们称由向量
0r A k张成的线性子空间为关于 和 的 维 Krylov子空间,
Krylov子空间是投影类方法中的一个很重要的概念,
0(,,)K A r k 即记为上一页 下一页14
矩阵范数定义 Rm?n空间的 矩阵范数 || · || 对任意 满足：
nmRBA,
00||||;0||||)1( AAA （ 正定性 )
||||||||||)2( AA C对任意 (齐次性 )
||||||||||||)3( BABA （ 三角不等式 )
(4)* || AB ||? || A || · || B || （ 相容性,当 m = n 时 )
注,一般来说，如果下面的关系式成立
|| AB || || A ||? · || B ||?,
则三种范数称为是相容的,
上一页 下一页15
常用矩阵范数：
Frobenius 范数
n
i
n
j
ijF aA
1 1
2|||||| —向量 || · ||2的直接推广对方阵 以及 有nnRA nRx
22 |||||||||||| xAxA F
利用 Cauchy 不等式可证。 22 |||||||||| yxyx
从属 范数由向量范数 || · ||p 导出关于矩阵 A? Rn?n 的 p 范数,
px
p
p
p xAx
xAA
px
||||m ax|||| ||||m ax||||
10 ||||
则
ppp
ppp
xAxA
BAAB
||||||||||||
||||||||||
特别有,?
n
j
ijaA ni
1
||m a x||||
1
（ 行和范数 ）
n
i
ijaA nj
1
1 ||m a x|||| 1
（ 列和范数 ）
)(|||| m a x2 AAA T （ 谱范数 ）
矩阵 ATA 的最大特征根
12
2
2
1
(,,,)
()
T
n
n
i
i
Ax x x x
Ax x
上一页 下一页16
对任何 1 1x?
1
1 1 1 1
| | | | | |
n n n n
i j j i j j
i j i j
A x a x a x
1
1 1 1
| | | | m ax | |,
n n n
j i j i jj
j i i
x a a x
从而 1
1
m a x | |
n
ijj
i
A x a
n
i
ijaA nj
1
1 ||m a x|||| 1
（ 列和范数 ）
上一页 下一页17
现设
11
m a x | | | |
nn
i j i kj
ii
aa
令
1,,
0,,j
jky
jk
若若
12(,,,) Tny y y y?显然 1 1y?满足
1
111
11
m a x | |
nn
i j jx
ij
A x A y a y
且
11
| | m a x | |
nn
i k i jj
ii
aa
上一页 下一页18
1 3 1 2 10 14
2 4 3 4 14 20
TAA
210 14 30 4 0
14 20
TI A A
1 5 2 2 1
2 ( ) 1 5 2 2 1 5,4 6,
TA A A
解,1 6A? 7A按定义例 已知矩阵
12,
34A
,1,2,pAp求上一页 下一页19
注,?Frobenius 范数 不是 从属范数。
我们只关心有相容性的范数,从属范数 总是相容的。
即使 A中元素全为实数，其特征根和相应特征向量仍可能是复数。将上述定义中绝对值换成 复数模 均成立。
若不然，则必存在某个向量范数
|| · ||v 使得 对任意 A 成立。
v
vF
x
xAA
x ||||
||||m a x||||
0?
反例?
1|||| ||||m a x||||
0
v
vF
x
xIIn
x?
上一页 下一页20
矩阵范数的等价定理：
A A?对,,存在常数 和,使得：m M
m A A M A
几种常用范数的等价关系：
22FA A n A
2
1 A A n A
n
1 2 1
1 A A n A
n
上一页 下一页21
谱半径定义 矩阵 A的 谱半径 记为
(A) =,其中?i 为
A 的特征根。
||m ax1 ini
Re
Im
(A)
上一页 下一页22
定理 对任意从属范数 || · || 有 ||||)( AA
证明,由从属范数的相容性，得到 |||||||||||| xAxA
将任意一个特征根?所对应的特征向量 代入u?
|||||||||||| uAuA |||||||||| uu
定理 若 A对称，则有 )(||||
2 AA
证明,)()(|||| 2
m a xm a x2 AAAA T
A对称若?是 A 的一个特征根，则?2 必是 A2 的特征根。
又：对称矩阵的特征根为实数，即?2(A) 为非负实数，
故得证。
)()( 22m a x AA 对某个 A 的特征根?成立所以 2-范数亦称为谱范数 。
上一页 下一页23
定理 若矩阵 B 对某个从属范数满足 ||B|| < 1，则必有
① BI? 可逆 ②
||||1
11
BBI
证明,① 若不然，则 有非零解，即存在非零向量 使得
0)( xBI
0x? 00 xxB 1
||||
||||
0
0
x
xB 1|||| B?
② IBIBI 1))(( 11 )()( BIBBI
11 )()( BIBIBI?
||)(||||||1||)(|| 11 BIBBI
上一页 下一页24
定义 设,
.)(,)( )( nnnnkijknnij RaAaA
AAk
k
lim 是指 ij
k
ijk aa
)(lim 对所有 1? i,j? n 成立。
等价于对任何从属范数有
kAA k as0||||
矩阵级数的收敛性上一页 下一页25
定理 Bk?0 B? < 1
证明：,?” 若?是 B 的特征值,则?k 是 Bk 的特征值 。
则 [B?]k = [ max |? | ]k = |?mk | Bk || Bk ||? 0
B? < 1?
“?” 首先需要一个引理对任意? > 0,存在从属范数 || · || 使得 || A ||A 。
由B?< 1 可知存在从属范数 || · || 使得 || B || < 1。
|| Bk ||? || B ||k? 0 as k Bk? 0
Bk?0 B? < 1
证明,对 A 做 Jordan 分解，有,其中
，,?i 为 A 的 特征值。
令,则有易证：
是由 导出的从属范数。
所以只要取? <?，就有 || A ||? <A 。
rJ
J
APP,..
1
1
inini
i
iJ
1
01
r
i
i nn
1
1
2
1
n
D
r
r
AP DPD
1
1
11
)()||(m ax|||||||| 1111 AA P DPDA iri
11 ||)(|||||| xPDx v
上一页 下一页26
定理 6（ Neumann引理） 矩阵幂级数收敛的充分必要条件为,且当时有
0
k
k
A
( ) 1A? <
( ) 1A? < 1()kI A A I A
证明,若 收敛，则
0
k
k
A
0kA?
( ) 1,A? <从而反之，若 ( ) 1A? <
则 的特征值IA? 1 i ( 1,2,,)in? 不等于零
（ 为 的特征值）i? A
上一页 下一页27
因此 非奇异IA?
于是由恒等式
1( ) ( )kkI A I A A I A
11( ) ( ) ( )kkI A A I A I A得到
( ) 1,A? <由于 因而有 1 0kA
1()kI A A I A即得证毕上一页 下一页28
是关键的误差放大因子，称为
A的 条件数,记为 cond (A),
越 则 A 越病态，
难得准确解。
|||||||| 1 AA
矩阵的条件数上一页 下一页29
注,?cond (A) 的具体大小与 || · || 的取法有关。
cond (A) 取决于 A，与解题方法无关。
常用条件数有：
cond (A)1 cond (A)? cond (A)2 )(/)(
m i nm a x AAAA TT
特别地，若 A 对称，则
||m in
||m a x)(
2?
Aco n d
条件数的性质：
A可逆，则 cond (A)p? 1；
A可逆, R 则 cond (? A) = cond (A) ；
A正交，则 cond (A)2=1；
A可逆,R正交，则 cond (RA)2 = cond (AR)2 = cond (A)2 。
上一页 下一页30
几种特殊矩阵上一页 下一页31
§ 1 高斯消元法
高斯消元法：
思路
(1) 将 A化为上三角阵，
(2) 回代求解 。
=
上一页 下一页32
消元 记
,)( )1()1( nnijaAA
)1(
)1(
1
)1(
...
nb
b
bb
Step 1,设,计算因子0)1(
11?a ).,,,,2(/ )1(11)1( 11 niaam ii
将增广矩阵 第 i 行? mi1? 第 1行,得到
)1(1)1(1)1(12)1(11,,,baaa n
)2(A )2(b? ).,,,,2,(
)1(
11
)1()2(
)1(
11
)1()2(
nji
bmbb
amaa
iii
jiijij
其中
Step k,设,计算因子且计算
0)(?kkka )...,,1(/ )()( nkiaam kkkkikik
)...,,1,(
)()()1(
)()()1(
nkji
bmbb
amaa
k
kik
k
i
k
i
k
kjik
k
ij
k
ij
共进行？ 步n? 1
)(
)2(
2
)1(
1
2
1
)(
)2(
2
)2(
22
)1(
1
)1(
12
)1(
11
..
.
..
.
..
....
...
...
n
nn
n
nn
n
n
b
b
b
x
x
x
a
aa
aaa
上一页 下一页33
回代
)()( / nnnnnn abx?
)1.,,,,1()( 1
)()(
ni
a
xab
x i
ii
n
ij
j
i
ij
i
i
i
定理 若 A的所有 顺序主子式 均不为 0，则高斯消元无需换行即可进行到底，得到唯一解。
iii
i
i
aa
aa
A
...
.........
...
)d e t (
1
111
注,事实上，只要 A 非奇异，即 A
1 存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。
上一页 下一页34
选主元消去法例,单精度解方程组
2
110
21
21
9
xx
xx
/* 精确解为 和 */.,,1000.,,00.1
101
1
91
x
8个
.,,8 9 99.,,99.02 12 xx
8个用 Gaussian 消去法计算：
9112121 10/ aam
999
2122 10101010.,,0.011ma
8个
9212 1012mb
99
9
10100
1110
0,1 12 xx
小主元可能导致计算失败。
上一页 下一页35
全主元消去法每一步选绝对值最大的元素为主元素，保证 。1||?ikm
Step k,① 选取 ;0||m ax||
, ijnjikji aa kk
② If ik? k then 交换第 k 行与第 ik 行 ;
If jk? k then 交换第 k 列与第 jk 列 ;
③ 消元注,列交换改变了 xi 的顺序，须记录 交换次序,解完后再换回来。
列主元消去法省去换列的步骤，每次仅选一列中最大的元。
0||m a x||, iknikki aa k
上一页 下一页36
例：
211
1110 9
1,1 12 xx
110
211
1110
211
9
注,列主元法没有全主元法稳定。
0,1 12 xx
例：
211 10101
99
99
99
10100
10101
注意：这两个方程组在数学上 严格等价 。
上一页 下一页37
运算量由于计算机中乘除运算的时间远远超过加减 运算的时间，故估计某种算法的运算量时，往往只估计 乘除的次数,
而且通常以乘除次数 的 最高次幂 为运算量的 数量级 。
Gaussian 消去法,
Step k,设,计算因子且计算
0)(?kkka )...,,1(/ )()( nkiaam kkkkikik
)...,,1,(
)()()1(
)()()1(
nkji
bmbb
amaa
k
kik
k
i
k
i
k
kjik
k
ij
k
ij
共进行 n? 1步
)(
)2(
2
)1(
1
2
1
)(
)2(
2
)2(
22
)1(
1
)1(
12
)1(
11
............
...
...
n
nn
n
nn
n
n
b
b
b
x
x
x
a
aa
aaa
)()( / nnnnnn abx?
)1.,,,,1()( 1
)()(
ni
a
xab
x i
ii
n
ij
j
i
ij
i
i
i
(n? k) 次(n )2 次次
(n? k) (n? k + 2) 次
nnn
knkn
n
k
6
5
23
)2)((
23
1
1
消元乘除次数：
1 次(n? i +1) 次
22)1(1
21
1
nninn
i
回代乘除次数：
Gaussian 消去法的总乘除次数为
，运算量为 级。nnn
3
1
3 2
3
3
3n
上一页 下一页38
完全选主元法比 Gaussian Elimination多出,保证稳定，但费时。
3
3nO
列主元法比 Gaussian Elimination只多出,略省时，但不保证稳定。
2
2nO
上一页 下一页39
§ 2 矩阵的三角分解
高斯消元法的矩阵形式
Step 1,)0(/
111111 aaam ii
记 L1 =
1
..
.
1
1
1
21
nm
m
,则
][ )1()1(1 bAL?
)1(1)1(1)1(11,.,baa n
)2(A )2(b?
Step n? 1:
)(
)2(
2
)1(
1
)(
)2(
2
)2(
22
)1(
1
)1(
12
)1(
11
121
..
.
..
..,,
.,,
.,,
.,,
n
n
n
nn
n
n
nn
b
b
b
a
aa
aaa
bALLL
其中
Lk =
1
..
.
1
1
,
,1
kn
kk
m
m
上一页 下一页40
1kL
1
..
.
1
1
,
,1
kn
kk
m
m
1 11211,.,nLLL
1
1
1
jim,
记为 L
单位下三角阵记 U =
)(
)2(
2
)2(
22
)1(
1
)1(
12
)1(
11
..
....
...
...
n
nn
n
n
a
aa
aaa
LUA
A 的 LU 分解上一页 下一页41
定理 若 A的所有顺序主子式均不为 0，则 A 的 LU 分解唯一（其中 L 为 单位 下三角阵）。
证明,由 § 1中定理可知,LU 分解存在。下面证明唯一性。
若不唯一，则可设 A = L1U1 = L2U2,推出
121 UU 211122211 LLUULL
上三角阵对角元为 1
的下三角阵
I
注,L 为一般下三角阵而 U 为 单位 上三角阵的分解称为
Crout 分解 。
实际上只要考虑 A* 的 LU 分解，即,则即是 A 的 Crout 分解。
ULA ~~*?
*~*~ LUA?
上一页 下一页42
Doolittle分解：
—— LU 分解的紧凑格式反复计算,
很浪费哦 ……
通过比较法直接导出 L 和 U 的计算公式。思路
nn
n
nnnn
n
u
uu
l
l
aa
aa
..
.
..
..,,
.,,
1.,,
.,,...
1
1
.,,
..
.
..
.
..
.
..
.
.,,111
1
21
1
111
),m in (
1
ji
k
jkki ul
jia
上一页 下一页43
),m in ( 1 jik jkkiji ula
固定 i,
对 j = i,i+1,…,n 有
ijkj
i
k
ikij uula
1
1
lii = 1
kj
i
k
ikijij ulau?
1
1
a
将 i,j 对换，对 j = i,i+1,…,n 有
iijiki
i
k
jkji ulula
1
1
ii
i
k
kijkjiji uulal /)(
1
1
b
算法,Doolittle分解
Step 1,u1j = a1j; lj1 = aj1 / u11; ( j = 1,…,n )
Step 2,compute and for i = 2,…,n?1;
Step 3,
a b
11nk knnknnnn ulau
一般采用 列主元法增强稳定性。但注意也必须做相应的行交换。
b?
上一页 下一页44
平方根法 /* Choleskiy分解 */：
——对称正定 矩阵的分解法定义 一个矩阵 A = ( aij )n?n 称为 对称阵,如果 aij = aji 。
定义 一个矩阵 A 称为 正定阵,如果 对任意非零向量 都成立。
0?xAx T
x?
回顾,对称正定阵的几个重要性质
A?1 亦对称正定，且 aii > 0?
若不然，则 0xA 存在非零解，即
0?xAx T 存在非零解。
1111 )()(, AAIAAIAA TTT
对任意,存在,使得,
即 。
0x 0y xyA
xAy 1 011 yAyyAAAyxAx TTT
其中0 xAxa Tii Tx )0...1...0(
第 i 位
A 的顺序主子阵 Ak 亦对称正定对称性显然。对任意 有
,其中 。
kk Rx 0
0 xAxxAx TkkTk nk Rxx
0
0
A 的特征值?i > 0
设对应特征值? 的非零特征向量为,则 。 20 xxxxAx TT<x?
A 的全部顺序主子式 det ( Ak ) > 0
因为?
n
i
iA
1
)d et (?
上一页 下一页45
将 对称 正定阵 A 做 LU 分解
U = uij =
u11 u
ij / uii
1 1
1
u22
unn
记为
UD~
A 对称 TUL ~? 即 TL D LA?
记 D1/2 =
11u
22u
nnu
为什么 uii > 0?因为 det(Ak) > 0
2/1~ LDL?则 仍是下三角阵
TLLA ~~?
nnRL
定理 设矩阵 A对称正定，则存在非奇异下三角阵使得 。若限定 L 对角元为正，则分解唯一。TLLA?
注,对于对称正定阵 A,从 可知对任意 k? i
有 。 即 L 的元素不会增大，误差可控，不需选主元。
ik ikii la 1 2
iiik al?||
上一页 下一页46
算法,Choleskiy分解将对称正定 n?n矩阵 A分解成 LLT,这里 L是下三角阵
Input,矩阵 A的维数 n; 矩阵 A的元素 aij 1?i,j? n,
Output:矩阵 L的元素 lij,1?j? i and 1? i? n,
Step 1 Set ;
Step 2 For j = 2,…,n,set ;
Step 3 For i = 2,…,n?1,do steps 4 and 5
Step 4 Set ;
Step 5 For j = i+1,…,n,set ;
Step 6 Set ;
Step 7 Output ( lij for j = 1,…,i and i = 1,…,n );
STOP,
1111 al?
1111 / lal jj?
11 2ik ikiiii lal
iiik ikjkjiji lllal 11
11 2nk nknnnn lal
因为 A 对称，所以只需存半个 A，即其中
nnn aaaaannA,..,,...,,,,2/)1( 1222111
jiiAa ij 2/)1(
运算量为 O( 3/6),比普通 LU
分解少一半，但有 n 次开方。用 A = LDLT
分解，可省开方时间。
上一页 下一页47
解 三对角方程组 的追赶法
nnnn
nnn
f
f
f
x
x
x
ba
cba
cba
cb
2
1
2
1
111
222
11
Step 1,对 A 作 Crout 分解
1
1
1
1
2
1
n
nn
A
直接比较等式两边的元素，可得到计算公式。
Step 2,追 ——即解,fyL,
1
11?fy? ),...,2()( 1 niyrfy
i
iiii
Step 3,赶 ——即解,yxU )1,...,1(,1 nixyxyx iiiinn?
与 Gauss消去法类似，一旦
i = 0 则算法中断，故并非任何三对角阵都可以用此方法分解。
上一页 下一页48
定理 若 A 为 对角占优 /* diagonally dominant */ 的三对角阵，且满足,则追赶法可解以 A 为系数矩阵的方程组。
0,0,0||||,0|||| 11 iinn caabcb
嗨，对角占优意味着什么它意味着矩阵的对角元是非常大,多大算大呢?
它们满足下面的不等式,
ij ijii
aa ||||
注,
如果 A 是 严格 对角占优阵，则不要求三对角线上的所有元素非零。
根据不等式可知：分解过程中，矩阵元素不会过分增大，算法保证稳定。
运算量为 O(6n)。
||||||||||,1|| 1 iiiiiiii abbab?<?<?<
上一页 下一页49
§ 4 线性方程组的误差分析求解 时,A 和 的误差对解 有何影响？bxA b? x?
设 A 精确,有误差,得到的解为,即b? b xx
bbxxA )(
bAx 1 |||||||||||| 1 bAx
绝对误差放大因子
|||||||||||||||| xAxAb又
||||
||||
||||
1
b
A
x
||||
||||||||||||
||||
|||| 1
b
bAA
x
x
相对误差放大因子上一页 下一页50
设 精确,A有误差,得到的解为,即b? A? xx
bxxAA ))((
bxxAxxA )()(
)(1 xxAAx
||||
||||
||||||||
||||||||
||||
||||
1
1
A
A
AA
AA
xx
x
bxAAxAA )()(
xAxAA )(
xAxAAIA )( 1
xAAAAIx 111 )(
稍等 …
为什么 ( I + A?1?A )可逆?
(只要?A充分小，使得
)1|||||||||||| 11 < AAAA
||||
||||
||||||||1
||||
||||
||||||||
||||||||1
||||||||
||||
||||
1
1
1
1
A
A
AA
A
A
AA
AA
AA
x
x
是关键的误差放大因子，称为
A的 条件数,记为 cond (A),
越 则 A 越病态，
难得准确解。
|||||||| 1 AA
大上一页 下一页51
注,?cond (A) 的具体大小与 || · || 的取法有关。
cond (A) 取决于 A，与解题方法无关。
||||
||||
||||
||||
||||||||)(1
)(
||||
||||
b
b
A
A
AAAc o n d
Ac o n d
x
x
常用条件数有：
cond (A)1 cond (A)? cond (A)2 )(/)(
m i nm a x AAAA TT
特别地，若 A 对称，则
||m in
||m a x)(
2?
Aco n d
条件数的性质：
A可逆，则 cond (A)p? 1；
A可逆, R 则 cond (? A) = cond (A) ；
A正交，则 cond (A)2=1；
A可逆,R正交，则 cond (RA)2 = cond (AR)2 = cond (A)2 。
上一页 下一页52
精确解 为,
1
1
x?例,
97.1
99.1,
98.099.0
99.01 bA?
计算 cond (A)2 。?
100 00990 0
990 0980 0A?1 =
解,考察 A 的特征根
0)d e t ( AI?
0 0 0 0 5 0 5 0 4.0
9 8 0 0 5 0 5 0 4.1
2
1
2
1
2)(?
Ac o n d 39206 >> 1
测试病态程度：
给 一个扰动b?
3
4
10106.0
1097.0b,其相对误差为
%01.010513.0|||| |||| 4
2
2 <
b
b 此时 精确解 为
020 3.1
3*x?
0203.2
2* xxx
2
2
||||
||||
x
x 2.0102 > 200%
上一页 下一页53
例,Hilbert 阵
12
1
1
11
3
1
2
1
1
2
11
nnn
n
nH
cond (H2)?= 27 cond (H3) 748
cond (H6)?= 2.9? 106 cond (Hn) as n
注,一般判断矩阵是否病态，并不计算 A?1，而由经验得出。
行列式很大或很小（如某些行、列近似相关）；
元素间相差大数量级，且无规则；
主元消去过程中出现小主元；
特征值相差大数量级。
上一页 下一页54
对于大型线性方程组,Gauss消去法的计算工作量很大，用 向前误差分析方法 非常困难。
Ax b?
下面介绍利用 向后误差分析方法,即
Gauss消去法的舍入误差将实际计算过程的误差转换为原始数据的误差,
上一页 下一页55
具体提法是：
对两种扰动：,A A A b b b
考查对 的解 的影响，Ax b? x
x x x即
,Ab 的大小可以估计在十进制且 16位字长的计算机上：
3 2 1 51,0 1 ( 3 ) 1 0
A
A
nn
A
上一页 下一页56
其中 ()1,,
1 m a x | |,k
A i ji j k n aA
()
,kija
表示 Gauss消元过程中 的元素()kA
2 1 51,01 10
b
b
n
b
()
1,
1 m a x | |,k
bi i k n bb
()kib其中表示 Gauss消元过程中 的元素()kb
上一页 下一页57
特别，对 Gauss消去法,3 2 1 5() [ 1.01 ( 3 ) 10 ]
1 ( )
A
x c on d A
nn
Ax
c on d A
A
只要 不是很大，则 Gauss消去法是数值稳定的
()c o nd A?
结论：条件数越大，扰动对解的影响越大,
上一页 下一页58
§ 5 解线性方程组的迭代法求解 bxA
思路将 等价bxA
改写为 形式，建立迭代 。
从初值 出发，得到序列 。
fxBx fxBx kk )()1(
)0(x? }{ )(kx?
计算精度可控，特别适用于求解系数为大型稀疏矩阵的方程组。
研究 内容：
如何建立迭代格式？收敛速度？
向量序列的收敛条件？ 误差估计？
上一页 下一页59
的收敛条件 fxBx kk )()1(
*)1()1( xxe kk )()()( *)()*()( kkk eBxxBfxBfxB
)0()( eBe kk ||||||||...|||||||||||| )0()1()( eBeBe kkk
充分条件,||B|| < 1 kB k as0||||
0|||| )( ke?
必要条件,kk Bke as0)(？
定义 设,
.)(,)( )( nnnnkijknnij RaAaA
AAk
k
lim 是指 ij
k
ijk aa
)(lim 对所有 1? i,j? n 成立。
等价于对任何从属范数有
kAA k as0||||
迭代法的收敛性上一页 下一页60
0||||?xB k? 对 任意非零向量 成立x?
定理 设 fxBx 存在唯一解，则从任意 出发，)0(x?
迭代 fxBx kk )()1( 收敛? 0?kB
证明,Bk? 0 || Bk ||? 0 0
||||
||||m a x
0
x
xB k
x?
“?”：对任意非零向量有x?
0|||||||| |||| kk Bx xB?
“?”：取则
Tix )0...1...0()(
第 i 位0)(?kijb
0xB k 对 任意非零向量 成立x?
从任意 出发,记,则)0(x? *)0()0( xxe
0)0()( eBe kk as k
}{ )( kx? 收敛上一页 下一页61
定理 Bk?0 B? < 1
证明：,?” 若?是 B 的特征值,则?k 是 Bk 的特征值 。
则 [B?]k = [ max |? | ]k = |?mk | Bk || Bk ||? 0
B? < 1?
“?” 首先需要一个引理对任意? > 0,存在从属范数 || · || 使得 || A ||A 。
由B?< 1 可知存在从属范数 || · || 使得 || B || < 1。
|| Bk ||? || B ||k? 0 as k Bk? 0
迭代从任意向量出发收敛 Bk?0 B? < 1
证明,对 A 做 Jordan 分解，有,其中
，,?i 为 A 的 特征值。
令,则有易证：
是由 导出的从属范数。
所以只要取? <?，就有 || A ||? <A 。
rJ
J
APP,..
1
1
inini
i
iJ
1
01
r
i
i nn
1
1
2
1
n
D
r
r
AP DPD
1
1
11
)()||(m ax|||||||| 1111 AA P DPDA iri
11 ||)(|||||| xPDx v
上一页 下一页62
定理 （充分条件） 若存在一个矩阵范数使得 || B || = q < 1,
则 迭代收敛，且有下列误差估计：
①
||||1||*|| )1()()( kkk xxqqxx
②
||||1||*|| )0()1()( xxqqxx
k
k
证明,①
)*(
)*(*
)1()()(
)1()(
kkk
kk
xxxxB
xxBxx
||)||||*( ||||*|| )1()()()( kkkk xxxxqxx
② )(...)( )0()1(1)2()1()1()( xxBxxBxx kkkkk
|||||||| )0()1(1)1()( xxqxx kkk
上一页 下一页63
Jacobi 法和 Gauss - Seidel 法
Jacobi 迭代方法
nnnnnn
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
.,,
.,,.,,.,,.,,
.,,
.,,
2211
22222121
11212111
nnnnn
nn
n
nn
nn
bxaxa
a
x
bxaxa
a
x
bxaxa
a
x
1111
22121
22
2
11212
11
1
.,,
1
.,,.,,.,,.,,
.,,
1
.,,
1
0?iia
写成 矩阵形式,
A =
L
UD bxULxD bxULDbxA )( )(
bDxULDx 11 )(
B f?
Jacobi 迭代阵 bDxULDx kk 1)(1)1( )(
上一页 下一页64
算法,Jacobi迭代方法求解 给定初始值,
Input,方程和未知量的个数 n; 矩阵元素 a[ ][ ];
元素 b[ ]; 初始近似值 X0[ ]; 误差容限 TOL;
最大迭代次数 Nmax.
Output:近似解 X[ ]或失败的信息,
Step 1 Set k = 1;
Step 2 While ( k? Nmax) do steps 3-6
Step 3 For i = 1,…,n
Set ; /* 计算 xk */
Step 4 If then Output (X[ ]);
STOP; /* 成功 */
Step 5 For i = 1,…,n Set X 0[ ] = X [ ]; /* 更新 X0 */
Step 6 Set k ++;
Step 7 Output (超过最大迭代次数 );
STOP,/* 失败 */
bxA )0(x?
ii
n
j
ij
jiji
i a
Xab
X
1
)0(
T O LXXXX iini < |0|m a x||0|| 1
如果 aii = 0,怎么办?
迭代过程中,A的元素不改变，故可以 事先调整 好 A 使得
aii? 0,否则 A不可逆 。
必须等 X(k)完全计算好了才能计算 X(k+1)，因此需要 两组向量 存储。
有点浪费，
不是吗?
上一页 下一页65
Gauss - Seidel 迭代方法
)(1 1)(1)(414)(313)(212
11
)1(
1 bxaxaxaxaax
k
nn
kkkk
)(1 2)(2)(424)(323)1(121
22
)1(
2 bxaxaxaxaax
k
nn
kkkk
)(1 3)(3)(434)1(232)1(131
33
)1(
3 bxaxaxaxaax
k
nn
kkkk
)(1 )1( 11)1(33)1(22)1(11)1( nknnnknknkn
nn
k
n bxaxaxaxaax
… … … …
只存一组向量即可。
写成 矩阵形式,bDxUxLDx kkk 1)()1(1)1( )(
bxUxLD kk )()1()(
bLDxULDx kk 1)(1)1( )()(
B f?Gauss-Seidel
迭代阵上一页 下一页66
定理 （充分条件） 若 A为 严格对角占优阵,则解的 Jacobi 和 Gauss - Seidel 迭代均收敛。
bxA
证明,首先需要一个引理若 A 为严格对角占优阵，则 det(A)? 0，且所有的 aii? 0。
证明,若不然，即 det(A) = 0，则 A 是奇异阵。
存在非零向量 使得 T
nxxxx ),,( 210,00
xA
记 ||m a x||
1 inim xx
n
i
iim xa
1
0
mi
imm
mi
iimmmm axxaxa ||||||
显然我们需要对 Jacobi 迭代和 Gauss-Seidel迭代分别证明：任何一个 |? |? 1 都 不可能 是对应迭代阵的特征根，即 |?I? B |? 0 。
Jacobi,BJ =?D?1( L + U )
|)(||| 1 ULDIBI
|||||)(| 11 ULDDULDD
aii? 0
ija
ija?
nna
a
11
如果 |? |? 1 则?
ij ijiiii
aaa ||||||? 是严格对角占优阵
|?I? B |? 0?
关于 Gauss-Seidel迭代的证明与此类似。
上一页 下一页67
注,二种方法都存在 收敛性问题 。
有例子表明,Gauss-Seidel法收敛时,Jacobi法可能不收敛；而 Jacobi法收敛时,Gauss-Seidel法也可能不收敛。
p.210 -211给出了例子。
上一页 下一页68
例：给出方程组 其中,iiA x b? 1,2,i?
1
1 2 2
1 1 1,
2 2 1
A
2
2 1 1
1 1 1
1 1 2
A
问,Jacobi迭代法和 Gauss-Seidel迭代法是否收敛？
解,11A x b?对 0 2 2
1 0 1,
2 2 0
JG
0 2 2
0 2 1
0 8 6
GG
上一页 下一页69
3d e t( ) 0JIG( ) 0JG
2d e t ( ) ( 4 4 ) 0GIG而
1 2,30,2 2 2
( ) 2 2 2GG即所以，对 11,A x b? Jacobi方法收敛,G-S方法发散同理，对于 22,A x b?
2
2 1 1
1 1 1
1 1 2
A
其中上一页 下一页70
0 1 / 2 1 / 2
1 0 1,
1 / 2 1 / 2 0
JG
0 1 / 2 1 / 2
0 1 / 12 1 / 2
0 0 1 / 2
GG
3 5d e t ( ) 0
4JIG
2,3 5 / 2i1 0,
( ) 5 / 2JG即得
2d e t ( ) ( 1 / 2) 0GIG而
1 2,30,1 / 2
上一页 下一页71
( ) 1 / 2GG则
22,A x b?所以，对 Jacobi方法发散,G-S方法收敛,
说明,Jacobi方法和 G-S方法的收敛条件大多数是互不包含的,
上一页 下一页72
定理 20 若线性方程组 的系数矩阵 是对角元素为正的实对称阵，则 Jacobi方法收敛的充分必要条件是 和 同时正定,
AX b? A
A 2 DA?
定理 21 设线性方程组 的系数矩阵 为实对称正定的，则 G-S方法收敛
AX b? A
上一页 下一页73
例,给定,其中AX b?
1
1
1
aa
A a a
aa
⑴ 证明当 时 对称正定，从而
G-S迭代方法收敛。
1 / 2 1a? < <A
⑵ 证明当 时 Jacobi迭代方法收敛，否则发散,
1 / 2 1 / 2a? < <
上一页 下一页74
（ 1）由题设知,为对称阵A证明,
1 0,? 2
1 0 1 0 1 1
1
a aa
a < <
3 2 2
1
1 0 2 3 1 ( 1 ) ( 2 1 ) 0
1
1 / 2
aa
a a a a a a
aa
a
要求：
1 / 2 1a < <时 对称正定，从而 G-S迭代方法收敛A
上一页 下一页75
（ 2）由定理 20,是对角元素为正的实对称阵，A
A 2DA?和 同时正定 Jacobi迭代方法收敛由（ 1）知,当 时,对称正定1 / 2 1a? < <A 1
21
1
aa
D A a a
aa
当且仅当 时正定同理可得,2 DA? 1 1 / 2a? < <
所以，当 时 Jacobi迭代方法收敛，
否则发散,
1 / 2 1 / 2a? < <
上一页 下一页76
松弛法换个角度看 Gauss - Seidel 方法：
n
ij
k
jij
i
j
k
iiji
ii
k
i xaxabax
1
)(
1
1
)1()1( ][1
ii
k
ik
i a
rx )1()( 其中 ri(k+1) =
<?
ij ij
kjijkjiji xaxab )()1(
残量相当于在 的基础上 加个余项 生成 。)(kix )1(?kix
下面令,希望通过选取合适的?来加速收敛，这就是 松弛法 。ii
k
ik
i
k
i a
rxx )1()()1(
0 <? < 1 低松弛法
= 1 Gauss - Seidel 法
> 1 (渐次 )超松弛法上一页 下一页77
写成 矩阵形式,
ii
k
ikiki arxx
)1()()1(
<
ij
i
k
jij
ij
k
jijii
k
i bxaxaax ][)1(
)()1()(
][)1( )()1(1)()1( bxUxLDxx kkkk
bLDxUDLDx kk 1)(1)1( )(])1[()(
H f
松弛迭代阵定理 设 A 可逆，且 aii? 0,松弛法从任意 出发对某个? 收敛 H < 1。
)0(x?
H?的计算是太复杂啦，
难于获得正确的谱半径 !
应该有捷径 …
上一页 下一页78
定理 （ Kahan 必要条件） 设 A 可逆，且 aii? 0,松弛法从任意 出发收敛? 0 <? < 2 。)0(x?
证明,从 出发 ])1[()( 1 UDLDH
n
i
iH
1
)d et (
利用,而且收敛? |?i | < 1 总成立可知收敛?| det(H?) | < 1
n
i iiaLD
LD
1
1 1
)d et (
1))d et ( (
n
i
ii
n aUD
1
)1())1d et ( (
nH )1()d et (
| det(H?) |? | 1|n < 1? 0 <? < 2
上一页 下一页79
定理 （ Ostrowski-Reich 充分条件） 若 A 对称正定，且有
0 <? < 2，则 松弛法从任意 出发收敛 。)0(x?
Q,什么因素决定收敛的速度?
考察迭代 fxBx kk )()1(,设 B 有特征根?1,…,?n 对应 n 个线性无关的特征向量 。则从任意 出发,可表为 的线性组合，即
n,...,1
)0(x?
*)0()0( xxe n,...,1
n
i
iie
1
)0(
n
i
i
k
ii
kk eBe
1
)0()(
~ )0()]([ eB kA, B? 越小，迭代收敛越快,
对于 SOR法，希望找? 使得 H 最小 。
上一页 下一页80
定理 若 A 为 对称正定三对角阵,则且 SOR的 最佳松弛因子为
,此时 。
1)]([)( 2 < JSG BB
2)]([11
2
JB?
1)(H
例：
2
1,
21
12 bA?，考虑迭代格式 )( )()()1( bxAxx kkk
问,取何值可使迭代收敛？
取何值时迭代收敛最快？
解,考察 B = I +? A 的特征根?1 = 1+?,?2 = 1+ 3?
收敛要求 B?<1?2/3 <? < 0
B? = max { | 1+? |,| 1+ 3? | }
当?取何值时 最小？
2/3?1/3 0
=? 1/2
上一页 下一页81
作业,P223
题 2
作业,P223
题 4
作业,P223
题 5
定理作业,P223-224
题 7,题 11
作业,p.225-226
题 22，题 25
作业,P225
题 16,18,19
作业,P224
题 14
第五章 线性方程组的解法上一页 下一页2
bxA?
12,,,Tnx x x x12,,Tnb b b b?
注：如果没有特别说明，下面总假定系数行列式的值 | | 0A?
其中
1 1 1 2 1
2 1 2 2 2
12
n
n
n n n n
a a a
a a a
A
a a a
且 | | 0A?
上一页 下一页3
利用 法则求解时存在的困难是：当方程组的阶数 很大时，计算量为
C ram er
n
常用计算方法,
直接解法,它是一类精确方法，即若不考虑计算过程中的舍入误差，那么通过有限步运算可以获得方程解的精确结果,
Gauss 逐步（顺序）消去法、
Gauss主元素法、矩阵分解法等；
( ( 1 ) ( 1 ) ! )O n n n
上一页 下一页4
迭代解法,所谓迭代方法，就是构造某种极限过程去逐步逼近方程组的解,
经典迭代法有,
迭代法,迭代法、Jacobi G a u s s S e i d e l?
逐次超松弛（ SOR）迭代法等；
上一页 下一页5
§ 1 预备知识上一页 下一页6
向量范数
向量范数定义 Rn空间的 向量范数 || · || 对任意 满足条件：
nRyx,
00||||;0||||)1( xxx （ 非负性 )
||||||||||)2( xx C对任意 (齐次性 )
||||||||||||)3( yxyx （ 三角不等式 )
常用向量范数：
n
i
ixx
1
1 ||||||
n
i i
xx
1
2
2 ||||||
pn
i
p
ip xx
/1
1
||||||
||max||||
1 ini
xx
注：
||||||||lim xx pp
上一页 下一页7
定义 对于任意两种范数 || · ||A,|| · ||B,总存在常数 C1,C2 > 0
使得,则称 || · ||A 和 || · ||B 等价 。
（范数等价性）
BAB xCxxC |||||||||||| 21
定理 Rn 上一切范数都等价。
上一页 下一页8
设 是在 上的一个范数，则 是的分量 的连续函数,
x nR x
x 12,,,nx x x
证明,对任何 1(,,),Tnx x x? 1(,,) Tny y y? 有
11
,
nn
j j j j
jj
x x e y y e
其中 是第 个基向量,je j
x y x y从而有
11
( ) | |
nn
j j j j j j
jj
x y e x y e
引理 1
上一页 下一页9
1
m a x | |
n
j j jj
j
e x y
因而当 时，yx? yx?
即 为 的连续函数,x x
（范数的等价性）对于 中任意两种范数nR
,,pq总存在常数 和,使对一切m M nxR?
都有
q p qm x x M x（ *）
证毕定理上一页 下一页10
证明 我们只需证明任意范数 px
与 Euclid范数 等价即可2x
考虑单位球面 2{,1 }nS y R y
它是 中的有界闭集，据引理 1,连续，nR py
并且它在 上达到最大值 和最小值S M m
0Mm其中于是对于任何,0nx R x 2/x x S?有
2/ pm x x M从而上一页 下一页11
故 时,（ *）成立0x?
当 时，（ *）显然成立
0x?
证毕对于常用的范数,,可以算出px 1,2,p
1 2 1
1 x x x
n
1x x n x
2x x n x
上一页 下一页12
定义 向量序列 收敛 于向量 是指对每一个 1? i? n 都有 。
}{ )(kx? *x?
*)(lim iki
k xx
可以理解为 0||*|| )(xx k
可以理解为对任何向量范数都成立。
向量序列的收敛性上一页 下一页13
Krylov子空间定义
210 0 0 0,,,,kr A r A r A r?
210 0 0 0 0(,,),,,,kK A r k s p a n r A r A r A r
0r A给定向量 和矩阵,我们称由向量
0r A k张成的线性子空间为关于 和 的 维 Krylov子空间,
Krylov子空间是投影类方法中的一个很重要的概念,
0(,,)K A r k 即记为上一页 下一页14
矩阵范数定义 Rm?n空间的 矩阵范数 || · || 对任意 满足：
nmRBA,
00||||;0||||)1( AAA （ 正定性 )
||||||||||)2( AA C对任意 (齐次性 )
||||||||||||)3( BABA （ 三角不等式 )
(4)* || AB ||? || A || · || B || （ 相容性,当 m = n 时 )
注,一般来说，如果下面的关系式成立
|| AB || || A ||? · || B ||?,
则三种范数称为是相容的,
上一页 下一页15
常用矩阵范数：
Frobenius 范数
n
i
n
j
ijF aA
1 1
2|||||| —向量 || · ||2的直接推广对方阵 以及 有nnRA nRx
22 |||||||||||| xAxA F
利用 Cauchy 不等式可证。 22 |||||||||| yxyx
从属 范数由向量范数 || · ||p 导出关于矩阵 A? Rn?n 的 p 范数,
px
p
p
p xAx
xAA
px
||||m ax|||| ||||m ax||||
10 ||||
则
ppp
ppp
xAxA
BAAB
||||||||||||
||||||||||
特别有,?
n
j
ijaA ni
1
||m a x||||
1
（ 行和范数 ）
n
i
ijaA nj
1
1 ||m a x|||| 1
（ 列和范数 ）
)(|||| m a x2 AAA T （ 谱范数 ）
矩阵 ATA 的最大特征根
12
2
2
1
(,,,)
()
T
n
n
i
i
Ax x x x
Ax x
上一页 下一页16
对任何 1 1x?
1
1 1 1 1
| | | | | |
n n n n
i j j i j j
i j i j
A x a x a x
1
1 1 1
| | | | m ax | |,
n n n
j i j i jj
j i i
x a a x
从而 1
1
m a x | |
n
ijj
i
A x a
n
i
ijaA nj
1
1 ||m a x|||| 1
（ 列和范数 ）
上一页 下一页17
现设
11
m a x | | | |
nn
i j i kj
ii
aa
令
1,,
0,,j
jky
jk
若若
12(,,,) Tny y y y?显然 1 1y?满足
1
111
11
m a x | |
nn
i j jx
ij
A x A y a y
且
11
| | m a x | |
nn
i k i jj
ii
aa
上一页 下一页18
1 3 1 2 10 14
2 4 3 4 14 20
TAA
210 14 30 4 0
14 20
TI A A
1 5 2 2 1
2 ( ) 1 5 2 2 1 5,4 6,
TA A A
解,1 6A? 7A按定义例 已知矩阵
12,
34A
,1,2,pAp求上一页 下一页19
注,?Frobenius 范数 不是 从属范数。
我们只关心有相容性的范数,从属范数 总是相容的。
即使 A中元素全为实数，其特征根和相应特征向量仍可能是复数。将上述定义中绝对值换成 复数模 均成立。
若不然，则必存在某个向量范数
|| · ||v 使得 对任意 A 成立。
v
vF
x
xAA
x ||||
||||m a x||||
0?
反例?
1|||| ||||m a x||||
0
v
vF
x
xIIn
x?
上一页 下一页20
矩阵范数的等价定理：
A A?对,,存在常数 和,使得：m M
m A A M A
几种常用范数的等价关系：
22FA A n A
2
1 A A n A
n
1 2 1
1 A A n A
n
上一页 下一页21
谱半径定义 矩阵 A的 谱半径 记为
(A) =,其中?i 为
A 的特征根。
||m ax1 ini
Re
Im
(A)
上一页 下一页22
定理 对任意从属范数 || · || 有 ||||)( AA
证明,由从属范数的相容性，得到 |||||||||||| xAxA
将任意一个特征根?所对应的特征向量 代入u?
|||||||||||| uAuA |||||||||| uu
定理 若 A对称，则有 )(||||
2 AA
证明,)()(|||| 2
m a xm a x2 AAAA T
A对称若?是 A 的一个特征根，则?2 必是 A2 的特征根。
又：对称矩阵的特征根为实数，即?2(A) 为非负实数，
故得证。
)()( 22m a x AA 对某个 A 的特征根?成立所以 2-范数亦称为谱范数 。
上一页 下一页23
定理 若矩阵 B 对某个从属范数满足 ||B|| < 1，则必有
① BI? 可逆 ②
||||1
11
BBI
证明,① 若不然，则 有非零解，即存在非零向量 使得
0)( xBI
0x? 00 xxB 1
||||
||||
0
0
x
xB 1|||| B?
② IBIBI 1))(( 11 )()( BIBBI
11 )()( BIBIBI?
||)(||||||1||)(|| 11 BIBBI
上一页 下一页24
定义 设,
.)(,)( )( nnnnkijknnij RaAaA
AAk
k
lim 是指 ij
k
ijk aa
)(lim 对所有 1? i,j? n 成立。
等价于对任何从属范数有
kAA k as0||||
矩阵级数的收敛性上一页 下一页25
定理 Bk?0 B? < 1
证明：,?” 若?是 B 的特征值,则?k 是 Bk 的特征值 。
则 [B?]k = [ max |? | ]k = |?mk | Bk || Bk ||? 0
B? < 1?
“?” 首先需要一个引理对任意? > 0,存在从属范数 || · || 使得 || A ||A 。
由B?< 1 可知存在从属范数 || · || 使得 || B || < 1。
|| Bk ||? || B ||k? 0 as k Bk? 0
Bk?0 B? < 1
证明,对 A 做 Jordan 分解，有,其中
，,?i 为 A 的 特征值。
令,则有易证：
是由 导出的从属范数。
所以只要取? <?，就有 || A ||? <A 。
rJ
J
APP,..
1
1
inini
i
iJ
1
01
r
i
i nn
1
1
2
1
n
D
r
r
AP DPD
1
1
11
)()||(m ax|||||||| 1111 AA P DPDA iri
11 ||)(|||||| xPDx v
上一页 下一页26
定理 6（ Neumann引理） 矩阵幂级数收敛的充分必要条件为,且当时有
0
k
k
A
( ) 1A? <
( ) 1A? < 1()kI A A I A
证明,若 收敛，则
0
k
k
A
0kA?
( ) 1,A? <从而反之，若 ( ) 1A? <
则 的特征值IA? 1 i ( 1,2,,)in? 不等于零
（ 为 的特征值）i? A
上一页 下一页27
因此 非奇异IA?
于是由恒等式
1( ) ( )kkI A I A A I A
11( ) ( ) ( )kkI A A I A I A得到
( ) 1,A? <由于 因而有 1 0kA
1()kI A A I A即得证毕上一页 下一页28
是关键的误差放大因子，称为
A的 条件数,记为 cond (A),
越 则 A 越病态，
难得准确解。
|||||||| 1 AA
矩阵的条件数上一页 下一页29
注,?cond (A) 的具体大小与 || · || 的取法有关。
cond (A) 取决于 A，与解题方法无关。
常用条件数有：
cond (A)1 cond (A)? cond (A)2 )(/)(
m i nm a x AAAA TT
特别地，若 A 对称，则
||m in
||m a x)(
2?
Aco n d
条件数的性质：
A可逆，则 cond (A)p? 1；
A可逆, R 则 cond (? A) = cond (A) ；
A正交，则 cond (A)2=1；
A可逆,R正交，则 cond (RA)2 = cond (AR)2 = cond (A)2 。
上一页 下一页30
几种特殊矩阵上一页 下一页31
§ 1 高斯消元法
高斯消元法：
思路
(1) 将 A化为上三角阵，
(2) 回代求解 。
=
上一页 下一页32
消元 记
,)( )1()1( nnijaAA
)1(
)1(
1
)1(
...
nb
b
bb
Step 1,设,计算因子0)1(
11?a ).,,,,2(/ )1(11)1( 11 niaam ii
将增广矩阵 第 i 行? mi1? 第 1行,得到
)1(1)1(1)1(12)1(11,,,baaa n
)2(A )2(b? ).,,,,2,(
)1(
11
)1()2(
)1(
11
)1()2(
nji
bmbb
amaa
iii
jiijij
其中
Step k,设,计算因子且计算
0)(?kkka )...,,1(/ )()( nkiaam kkkkikik
)...,,1,(
)()()1(
)()()1(
nkji
bmbb
amaa
k
kik
k
i
k
i
k
kjik
k
ij
k
ij
共进行？ 步n? 1
)(
)2(
2
)1(
1
2
1
)(
)2(
2
)2(
22
)1(
1
)1(
12
)1(
11
..
.
..
.
..
....
...
...
n
nn
n
nn
n
n
b
b
b
x
x
x
a
aa
aaa
上一页 下一页33
回代
)()( / nnnnnn abx?
)1.,,,,1()( 1
)()(
ni
a
xab
x i
ii
n
ij
j
i
ij
i
i
i
定理 若 A的所有 顺序主子式 均不为 0，则高斯消元无需换行即可进行到底，得到唯一解。
iii
i
i
aa
aa
A
...
.........
...
)d e t (
1
111
注,事实上，只要 A 非奇异，即 A
1 存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。
上一页 下一页34
选主元消去法例,单精度解方程组
2
110
21
21
9
xx
xx
/* 精确解为 和 */.,,1000.,,00.1
101
1
91
x
8个
.,,8 9 99.,,99.02 12 xx
8个用 Gaussian 消去法计算：
9112121 10/ aam
999
2122 10101010.,,0.011ma
8个
9212 1012mb
99
9
10100
1110
0,1 12 xx
小主元可能导致计算失败。
上一页 下一页35
全主元消去法每一步选绝对值最大的元素为主元素，保证 。1||?ikm
Step k,① 选取 ;0||m ax||
, ijnjikji aa kk
② If ik? k then 交换第 k 行与第 ik 行 ;
If jk? k then 交换第 k 列与第 jk 列 ;
③ 消元注,列交换改变了 xi 的顺序，须记录 交换次序,解完后再换回来。
列主元消去法省去换列的步骤，每次仅选一列中最大的元。
0||m a x||, iknikki aa k
上一页 下一页36
例：
211
1110 9
1,1 12 xx
110
211
1110
211
9
注,列主元法没有全主元法稳定。
0,1 12 xx
例：
211 10101
99
99
99
10100
10101
注意：这两个方程组在数学上 严格等价 。
上一页 下一页37
运算量由于计算机中乘除运算的时间远远超过加减 运算的时间，故估计某种算法的运算量时，往往只估计 乘除的次数,
而且通常以乘除次数 的 最高次幂 为运算量的 数量级 。
Gaussian 消去法,
Step k,设,计算因子且计算
0)(?kkka )...,,1(/ )()( nkiaam kkkkikik
)...,,1,(
)()()1(
)()()1(
nkji
bmbb
amaa
k
kik
k
i
k
i
k
kjik
k
ij
k
ij
共进行 n? 1步
)(
)2(
2
)1(
1
2
1
)(
)2(
2
)2(
22
)1(
1
)1(
12
)1(
11
............
...
...
n
nn
n
nn
n
n
b
b
b
x
x
x
a
aa
aaa
)()( / nnnnnn abx?
)1.,,,,1()( 1
)()(
ni
a
xab
x i
ii
n
ij
j
i
ij
i
i
i
(n? k) 次(n )2 次次
(n? k) (n? k + 2) 次
nnn
knkn
n
k
6
5
23
)2)((
23
1
1
消元乘除次数：
1 次(n? i +1) 次
22)1(1
21
1
nninn
i
回代乘除次数：
Gaussian 消去法的总乘除次数为
，运算量为 级。nnn
3
1
3 2
3
3
3n
上一页 下一页38
完全选主元法比 Gaussian Elimination多出,保证稳定，但费时。
3
3nO
列主元法比 Gaussian Elimination只多出,略省时，但不保证稳定。
2
2nO
上一页 下一页39
§ 2 矩阵的三角分解
高斯消元法的矩阵形式
Step 1,)0(/
111111 aaam ii
记 L1 =
1
..
.
1
1
1
21
nm
m
,则
][ )1()1(1 bAL?
)1(1)1(1)1(11,.,baa n
)2(A )2(b?
Step n? 1:
)(
)2(
2
)1(
1
)(
)2(
2
)2(
22
)1(
1
)1(
12
)1(
11
121
..
.
..
..,,
.,,
.,,
.,,
n
n
n
nn
n
n
nn
b
b
b
a
aa
aaa
bALLL
其中
Lk =
1
..
.
1
1
,
,1
kn
kk
m
m
上一页 下一页40
1kL
1
..
.
1
1
,
,1
kn
kk
m
m
1 11211,.,nLLL
1
1
1
jim,
记为 L
单位下三角阵记 U =
)(
)2(
2
)2(
22
)1(
1
)1(
12
)1(
11
..
....
...
...
n
nn
n
n
a
aa
aaa
LUA
A 的 LU 分解上一页 下一页41
定理 若 A的所有顺序主子式均不为 0，则 A 的 LU 分解唯一（其中 L 为 单位 下三角阵）。
证明,由 § 1中定理可知,LU 分解存在。下面证明唯一性。
若不唯一，则可设 A = L1U1 = L2U2,推出
121 UU 211122211 LLUULL
上三角阵对角元为 1
的下三角阵
I
注,L 为一般下三角阵而 U 为 单位 上三角阵的分解称为
Crout 分解 。
实际上只要考虑 A* 的 LU 分解，即,则即是 A 的 Crout 分解。
ULA ~~*?
*~*~ LUA?
上一页 下一页42
Doolittle分解：
—— LU 分解的紧凑格式反复计算,
很浪费哦 ……
通过比较法直接导出 L 和 U 的计算公式。思路
nn
n
nnnn
n
u
uu
l
l
aa
aa
..
.
..
..,,
.,,
1.,,
.,,...
1
1
.,,
..
.
..
.
..
.
..
.
.,,111
1
21
1
111
),m in (
1
ji
k
jkki ul
jia
上一页 下一页43
),m in ( 1 jik jkkiji ula
固定 i,
对 j = i,i+1,…,n 有
ijkj
i
k
ikij uula
1
1
lii = 1
kj
i
k
ikijij ulau?
1
1
a
将 i,j 对换，对 j = i,i+1,…,n 有
iijiki
i
k
jkji ulula
1
1
ii
i
k
kijkjiji uulal /)(
1
1
b
算法,Doolittle分解
Step 1,u1j = a1j; lj1 = aj1 / u11; ( j = 1,…,n )
Step 2,compute and for i = 2,…,n?1;
Step 3,
a b
11nk knnknnnn ulau
一般采用 列主元法增强稳定性。但注意也必须做相应的行交换。
b?
上一页 下一页44
平方根法 /* Choleskiy分解 */：
——对称正定 矩阵的分解法定义 一个矩阵 A = ( aij )n?n 称为 对称阵,如果 aij = aji 。
定义 一个矩阵 A 称为 正定阵,如果 对任意非零向量 都成立。
0?xAx T
x?
回顾,对称正定阵的几个重要性质
A?1 亦对称正定，且 aii > 0?
若不然，则 0xA 存在非零解，即
0?xAx T 存在非零解。
1111 )()(, AAIAAIAA TTT
对任意,存在,使得,
即 。
0x 0y xyA
xAy 1 011 yAyyAAAyxAx TTT
其中0 xAxa Tii Tx )0...1...0(
第 i 位
A 的顺序主子阵 Ak 亦对称正定对称性显然。对任意 有
,其中 。
kk Rx 0
0 xAxxAx TkkTk nk Rxx
0
0
A 的特征值?i > 0
设对应特征值? 的非零特征向量为,则 。 20 xxxxAx TT<x?
A 的全部顺序主子式 det ( Ak ) > 0
因为?
n
i
iA
1
)d et (?
上一页 下一页45
将 对称 正定阵 A 做 LU 分解
U = uij =
u11 u
ij / uii
1 1
1
u22
unn
记为
UD~
A 对称 TUL ~? 即 TL D LA?
记 D1/2 =
11u
22u
nnu
为什么 uii > 0?因为 det(Ak) > 0
2/1~ LDL?则 仍是下三角阵
TLLA ~~?
nnRL
定理 设矩阵 A对称正定，则存在非奇异下三角阵使得 。若限定 L 对角元为正，则分解唯一。TLLA?
注,对于对称正定阵 A,从 可知对任意 k? i
有 。 即 L 的元素不会增大，误差可控，不需选主元。
ik ikii la 1 2
iiik al?||
上一页 下一页46
算法,Choleskiy分解将对称正定 n?n矩阵 A分解成 LLT,这里 L是下三角阵
Input,矩阵 A的维数 n; 矩阵 A的元素 aij 1?i,j? n,
Output:矩阵 L的元素 lij,1?j? i and 1? i? n,
Step 1 Set ;
Step 2 For j = 2,…,n,set ;
Step 3 For i = 2,…,n?1,do steps 4 and 5
Step 4 Set ;
Step 5 For j = i+1,…,n,set ;
Step 6 Set ;
Step 7 Output ( lij for j = 1,…,i and i = 1,…,n );
STOP,
1111 al?
1111 / lal jj?
11 2ik ikiiii lal
iiik ikjkjiji lllal 11
11 2nk nknnnn lal
因为 A 对称，所以只需存半个 A，即其中
nnn aaaaannA,..,,...,,,,2/)1( 1222111
jiiAa ij 2/)1(
运算量为 O( 3/6),比普通 LU
分解少一半，但有 n 次开方。用 A = LDLT
分解，可省开方时间。
上一页 下一页47
解 三对角方程组 的追赶法
nnnn
nnn
f
f
f
x
x
x
ba
cba
cba
cb
2
1
2
1
111
222
11
Step 1,对 A 作 Crout 分解
1
1
1
1
2
1
n
nn
A
直接比较等式两边的元素，可得到计算公式。
Step 2,追 ——即解,fyL,
1
11?fy? ),...,2()( 1 niyrfy
i
iiii
Step 3,赶 ——即解,yxU )1,...,1(,1 nixyxyx iiiinn?
与 Gauss消去法类似，一旦
i = 0 则算法中断，故并非任何三对角阵都可以用此方法分解。
上一页 下一页48
定理 若 A 为 对角占优 /* diagonally dominant */ 的三对角阵，且满足,则追赶法可解以 A 为系数矩阵的方程组。
0,0,0||||,0|||| 11 iinn caabcb
嗨，对角占优意味着什么它意味着矩阵的对角元是非常大,多大算大呢?
它们满足下面的不等式,
ij ijii
aa ||||
注,
如果 A 是 严格 对角占优阵，则不要求三对角线上的所有元素非零。
根据不等式可知：分解过程中，矩阵元素不会过分增大，算法保证稳定。
运算量为 O(6n)。
||||||||||,1|| 1 iiiiiiii abbab?<?<?<
上一页 下一页49
§ 4 线性方程组的误差分析求解 时,A 和 的误差对解 有何影响？bxA b? x?
设 A 精确,有误差,得到的解为,即b? b xx
bbxxA )(
bAx 1 |||||||||||| 1 bAx
绝对误差放大因子
|||||||||||||||| xAxAb又
||||
||||
||||
1
b
A
x
||||
||||||||||||
||||
|||| 1
b
bAA
x
x
相对误差放大因子上一页 下一页50
设 精确,A有误差,得到的解为,即b? A? xx
bxxAA ))((
bxxAxxA )()(
)(1 xxAAx
||||
||||
||||||||
||||||||
||||
||||
1
1
A
A
AA
AA
xx
x
bxAAxAA )()(
xAxAA )(
xAxAAIA )( 1
xAAAAIx 111 )(
稍等 …
为什么 ( I + A?1?A )可逆?
(只要?A充分小，使得
)1|||||||||||| 11 < AAAA
||||
||||
||||||||1
||||
||||
||||||||
||||||||1
||||||||
||||
||||
1
1
1
1
A
A
AA
A
A
AA
AA
AA
x
x
是关键的误差放大因子，称为
A的 条件数,记为 cond (A),
越 则 A 越病态，
难得准确解。
|||||||| 1 AA
大上一页 下一页51
注,?cond (A) 的具体大小与 || · || 的取法有关。
cond (A) 取决于 A，与解题方法无关。
||||
||||
||||
||||
||||||||)(1
)(
||||
||||
b
b
A
A
AAAc o n d
Ac o n d
x
x
常用条件数有：
cond (A)1 cond (A)? cond (A)2 )(/)(
m i nm a x AAAA TT
特别地，若 A 对称，则
||m in
||m a x)(
2?
Aco n d
条件数的性质：
A可逆，则 cond (A)p? 1；
A可逆, R 则 cond (? A) = cond (A) ；
A正交，则 cond (A)2=1；
A可逆,R正交，则 cond (RA)2 = cond (AR)2 = cond (A)2 。
上一页 下一页52
精确解 为,
1
1
x?例,
97.1
99.1,
98.099.0
99.01 bA?
计算 cond (A)2 。?
100 00990 0
990 0980 0A?1 =
解,考察 A 的特征根
0)d e t ( AI?
0 0 0 0 5 0 5 0 4.0
9 8 0 0 5 0 5 0 4.1
2
1
2
1
2)(?
Ac o n d 39206 >> 1
测试病态程度：
给 一个扰动b?
3
4
10106.0
1097.0b,其相对误差为
%01.010513.0|||| |||| 4
2
2 <
b
b 此时 精确解 为
020 3.1
3*x?
0203.2
2* xxx
2
2
||||
||||
x
x 2.0102 > 200%
上一页 下一页53
例,Hilbert 阵
12
1
1
11
3
1
2
1
1
2
11
nnn
n
nH
cond (H2)?= 27 cond (H3) 748
cond (H6)?= 2.9? 106 cond (Hn) as n
注,一般判断矩阵是否病态，并不计算 A?1，而由经验得出。
行列式很大或很小（如某些行、列近似相关）；
元素间相差大数量级，且无规则；
主元消去过程中出现小主元；
特征值相差大数量级。
上一页 下一页54
对于大型线性方程组,Gauss消去法的计算工作量很大，用 向前误差分析方法 非常困难。
Ax b?
下面介绍利用 向后误差分析方法,即
Gauss消去法的舍入误差将实际计算过程的误差转换为原始数据的误差,
上一页 下一页55
具体提法是：
对两种扰动：,A A A b b b
考查对 的解 的影响，Ax b? x
x x x即
,Ab 的大小可以估计在十进制且 16位字长的计算机上：
3 2 1 51,0 1 ( 3 ) 1 0
A
A
nn
A
上一页 下一页56
其中 ()1,,
1 m a x | |,k
A i ji j k n aA
()
,kija
表示 Gauss消元过程中 的元素()kA
2 1 51,01 10
b
b
n
b
()
1,
1 m a x | |,k
bi i k n bb
()kib其中表示 Gauss消元过程中 的元素()kb
上一页 下一页57
特别，对 Gauss消去法,3 2 1 5() [ 1.01 ( 3 ) 10 ]
1 ( )
A
x c on d A
nn
Ax
c on d A
A
只要 不是很大，则 Gauss消去法是数值稳定的
()c o nd A?
结论：条件数越大，扰动对解的影响越大,
上一页 下一页58
§ 5 解线性方程组的迭代法求解 bxA
思路将 等价bxA
改写为 形式，建立迭代 。
从初值 出发，得到序列 。
fxBx fxBx kk )()1(
)0(x? }{ )(kx?
计算精度可控，特别适用于求解系数为大型稀疏矩阵的方程组。
研究 内容：
如何建立迭代格式？收敛速度？
向量序列的收敛条件？ 误差估计？
上一页 下一页59
的收敛条件 fxBx kk )()1(
*)1()1( xxe kk )()()( *)()*()( kkk eBxxBfxBfxB
)0()( eBe kk ||||||||...|||||||||||| )0()1()( eBeBe kkk
充分条件,||B|| < 1 kB k as0||||
0|||| )( ke?
必要条件,kk Bke as0)(？
定义 设,
.)(,)( )( nnnnkijknnij RaAaA
AAk
k
lim 是指 ij
k
ijk aa
)(lim 对所有 1? i,j? n 成立。
等价于对任何从属范数有
kAA k as0||||
迭代法的收敛性上一页 下一页60
0||||?xB k? 对 任意非零向量 成立x?
定理 设 fxBx 存在唯一解，则从任意 出发，)0(x?
迭代 fxBx kk )()1( 收敛? 0?kB
证明,Bk? 0 || Bk ||? 0 0
||||
||||m a x
0
x
xB k
x?
“?”：对任意非零向量有x?
0|||||||| |||| kk Bx xB?
“?”：取则
Tix )0...1...0()(
第 i 位0)(?kijb
0xB k 对 任意非零向量 成立x?
从任意 出发,记,则)0(x? *)0()0( xxe
0)0()( eBe kk as k
}{ )( kx? 收敛上一页 下一页61
定理 Bk?0 B? < 1
证明：,?” 若?是 B 的特征值,则?k 是 Bk 的特征值 。
则 [B?]k = [ max |? | ]k = |?mk | Bk || Bk ||? 0
B? < 1?
“?” 首先需要一个引理对任意? > 0,存在从属范数 || · || 使得 || A ||A 。
由B?< 1 可知存在从属范数 || · || 使得 || B || < 1。
|| Bk ||? || B ||k? 0 as k Bk? 0
迭代从任意向量出发收敛 Bk?0 B? < 1
证明,对 A 做 Jordan 分解，有,其中
，,?i 为 A 的 特征值。
令,则有易证：
是由 导出的从属范数。
所以只要取? <?，就有 || A ||? <A 。
rJ
J
APP,..
1
1
inini
i
iJ
1
01
r
i
i nn
1
1
2
1
n
D
r
r
AP DPD
1
1
11
)()||(m ax|||||||| 1111 AA P DPDA iri
11 ||)(|||||| xPDx v
上一页 下一页62
定理 （充分条件） 若存在一个矩阵范数使得 || B || = q < 1,
则 迭代收敛，且有下列误差估计：
①
||||1||*|| )1()()( kkk xxqqxx
②
||||1||*|| )0()1()( xxqqxx
k
k
证明,①
)*(
)*(*
)1()()(
)1()(
kkk
kk
xxxxB
xxBxx
||)||||*( ||||*|| )1()()()( kkkk xxxxqxx
② )(...)( )0()1(1)2()1()1()( xxBxxBxx kkkkk
|||||||| )0()1(1)1()( xxqxx kkk
上一页 下一页63
Jacobi 法和 Gauss - Seidel 法
Jacobi 迭代方法
nnnnnn
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
.,,
.,,.,,.,,.,,
.,,
.,,
2211
22222121
11212111
nnnnn
nn
n
nn
nn
bxaxa
a
x
bxaxa
a
x
bxaxa
a
x
1111
22121
22
2
11212
11
1
.,,
1
.,,.,,.,,.,,
.,,
1
.,,
1
0?iia
写成 矩阵形式,
A =
L
UD bxULxD bxULDbxA )( )(
bDxULDx 11 )(
B f?
Jacobi 迭代阵 bDxULDx kk 1)(1)1( )(
上一页 下一页64
算法,Jacobi迭代方法求解 给定初始值,
Input,方程和未知量的个数 n; 矩阵元素 a[ ][ ];
元素 b[ ]; 初始近似值 X0[ ]; 误差容限 TOL;
最大迭代次数 Nmax.
Output:近似解 X[ ]或失败的信息,
Step 1 Set k = 1;
Step 2 While ( k? Nmax) do steps 3-6
Step 3 For i = 1,…,n
Set ; /* 计算 xk */
Step 4 If then Output (X[ ]);
STOP; /* 成功 */
Step 5 For i = 1,…,n Set X 0[ ] = X [ ]; /* 更新 X0 */
Step 6 Set k ++;
Step 7 Output (超过最大迭代次数 );
STOP,/* 失败 */
bxA )0(x?
ii
n
j
ij
jiji
i a
Xab
X
1
)0(
T O LXXXX iini < |0|m a x||0|| 1
如果 aii = 0,怎么办?
迭代过程中,A的元素不改变，故可以 事先调整 好 A 使得
aii? 0,否则 A不可逆 。
必须等 X(k)完全计算好了才能计算 X(k+1)，因此需要 两组向量 存储。
有点浪费，
不是吗?
上一页 下一页65
Gauss - Seidel 迭代方法
)(1 1)(1)(414)(313)(212
11
)1(
1 bxaxaxaxaax
k
nn
kkkk
)(1 2)(2)(424)(323)1(121
22
)1(
2 bxaxaxaxaax
k
nn
kkkk
)(1 3)(3)(434)1(232)1(131
33
)1(
3 bxaxaxaxaax
k
nn
kkkk
)(1 )1( 11)1(33)1(22)1(11)1( nknnnknknkn
nn
k
n bxaxaxaxaax
… … … …
只存一组向量即可。
写成 矩阵形式,bDxUxLDx kkk 1)()1(1)1( )(
bxUxLD kk )()1()(
bLDxULDx kk 1)(1)1( )()(
B f?Gauss-Seidel
迭代阵上一页 下一页66
定理 （充分条件） 若 A为 严格对角占优阵,则解的 Jacobi 和 Gauss - Seidel 迭代均收敛。
bxA
证明,首先需要一个引理若 A 为严格对角占优阵，则 det(A)? 0，且所有的 aii? 0。
证明,若不然，即 det(A) = 0，则 A 是奇异阵。
存在非零向量 使得 T
nxxxx ),,( 210,00
xA
记 ||m a x||
1 inim xx
n
i
iim xa
1
0
mi
imm
mi
iimmmm axxaxa ||||||
显然我们需要对 Jacobi 迭代和 Gauss-Seidel迭代分别证明：任何一个 |? |? 1 都 不可能 是对应迭代阵的特征根，即 |?I? B |? 0 。
Jacobi,BJ =?D?1( L + U )
|)(||| 1 ULDIBI
|||||)(| 11 ULDDULDD
aii? 0
ija
ija?
nna
a
11
如果 |? |? 1 则?
ij ijiiii
aaa ||||||? 是严格对角占优阵
|?I? B |? 0?
关于 Gauss-Seidel迭代的证明与此类似。
上一页 下一页67
注,二种方法都存在 收敛性问题 。
有例子表明,Gauss-Seidel法收敛时,Jacobi法可能不收敛；而 Jacobi法收敛时,Gauss-Seidel法也可能不收敛。
p.210 -211给出了例子。
上一页 下一页68
例：给出方程组 其中,iiA x b? 1,2,i?
1
1 2 2
1 1 1,
2 2 1
A
2
2 1 1
1 1 1
1 1 2
A
问,Jacobi迭代法和 Gauss-Seidel迭代法是否收敛？
解,11A x b?对 0 2 2
1 0 1,
2 2 0
JG
0 2 2
0 2 1
0 8 6
GG
上一页 下一页69
3d e t( ) 0JIG( ) 0JG
2d e t ( ) ( 4 4 ) 0GIG而
1 2,30,2 2 2
( ) 2 2 2GG即所以，对 11,A x b? Jacobi方法收敛,G-S方法发散同理，对于 22,A x b?
2
2 1 1
1 1 1
1 1 2
A
其中上一页 下一页70
0 1 / 2 1 / 2
1 0 1,
1 / 2 1 / 2 0
JG
0 1 / 2 1 / 2
0 1 / 12 1 / 2
0 0 1 / 2
GG
3 5d e t ( ) 0
4JIG
2,3 5 / 2i1 0,
( ) 5 / 2JG即得
2d e t ( ) ( 1 / 2) 0GIG而
1 2,30,1 / 2
上一页 下一页71
( ) 1 / 2GG则
22,A x b?所以，对 Jacobi方法发散,G-S方法收敛,
说明,Jacobi方法和 G-S方法的收敛条件大多数是互不包含的,
上一页 下一页72
定理 20 若线性方程组 的系数矩阵 是对角元素为正的实对称阵，则 Jacobi方法收敛的充分必要条件是 和 同时正定,
AX b? A
A 2 DA?
定理 21 设线性方程组 的系数矩阵 为实对称正定的，则 G-S方法收敛
AX b? A
上一页 下一页73
例,给定,其中AX b?
1
1
1
aa
A a a
aa
⑴ 证明当 时 对称正定，从而
G-S迭代方法收敛。
1 / 2 1a? < <A
⑵ 证明当 时 Jacobi迭代方法收敛，否则发散,
1 / 2 1 / 2a? < <
上一页 下一页74
（ 1）由题设知,为对称阵A证明,
1 0,? 2
1 0 1 0 1 1
1
a aa
a < <
3 2 2
1
1 0 2 3 1 ( 1 ) ( 2 1 ) 0
1
1 / 2
aa
a a a a a a
aa
a
要求：
1 / 2 1a < <时 对称正定，从而 G-S迭代方法收敛A
上一页 下一页75
（ 2）由定理 20,是对角元素为正的实对称阵，A
A 2DA?和 同时正定 Jacobi迭代方法收敛由（ 1）知,当 时,对称正定1 / 2 1a? < <A 1
21
1
aa
D A a a
aa
当且仅当 时正定同理可得,2 DA? 1 1 / 2a? < <
所以，当 时 Jacobi迭代方法收敛，
否则发散,
1 / 2 1 / 2a? < <
上一页 下一页76
松弛法换个角度看 Gauss - Seidel 方法：
n
ij
k
jij
i
j
k
iiji
ii
k
i xaxabax
1
)(
1
1
)1()1( ][1
ii
k
ik
i a
rx )1()( 其中 ri(k+1) =
<?
ij ij
kjijkjiji xaxab )()1(
残量相当于在 的基础上 加个余项 生成 。)(kix )1(?kix
下面令,希望通过选取合适的?来加速收敛，这就是 松弛法 。ii
k
ik
i
k
i a
rxx )1()()1(
0 <? < 1 低松弛法
= 1 Gauss - Seidel 法
> 1 (渐次 )超松弛法上一页 下一页77
写成 矩阵形式,
ii
k
ikiki arxx
)1()()1(
<
ij
i
k
jij
ij
k
jijii
k
i bxaxaax ][)1(
)()1()(
][)1( )()1(1)()1( bxUxLDxx kkkk
bLDxUDLDx kk 1)(1)1( )(])1[()(
H f
松弛迭代阵定理 设 A 可逆，且 aii? 0,松弛法从任意 出发对某个? 收敛 H < 1。
)0(x?
H?的计算是太复杂啦，
难于获得正确的谱半径 !
应该有捷径 …
上一页 下一页78
定理 （ Kahan 必要条件） 设 A 可逆，且 aii? 0,松弛法从任意 出发收敛? 0 <? < 2 。)0(x?
证明,从 出发 ])1[()( 1 UDLDH
n
i
iH
1
)d et (
利用,而且收敛? |?i | < 1 总成立可知收敛?| det(H?) | < 1
n
i iiaLD
LD
1
1 1
)d et (
1))d et ( (
n
i
ii
n aUD
1
)1())1d et ( (
nH )1()d et (
| det(H?) |? | 1|n < 1? 0 <? < 2
上一页 下一页79
定理 （ Ostrowski-Reich 充分条件） 若 A 对称正定，且有
0 <? < 2，则 松弛法从任意 出发收敛 。)0(x?
Q,什么因素决定收敛的速度?
考察迭代 fxBx kk )()1(,设 B 有特征根?1,…,?n 对应 n 个线性无关的特征向量 。则从任意 出发,可表为 的线性组合，即
n,...,1
)0(x?
*)0()0( xxe n,...,1
n
i
iie
1
)0(
n
i
i
k
ii
kk eBe
1
)0()(
~ )0()]([ eB kA, B? 越小，迭代收敛越快,
对于 SOR法，希望找? 使得 H 最小 。
上一页 下一页80
定理 若 A 为 对称正定三对角阵,则且 SOR的 最佳松弛因子为
,此时 。
1)]([)( 2 < JSG BB
2)]([11
2
JB?
1)(H
例：
2
1,
21
12 bA?，考虑迭代格式 )( )()()1( bxAxx kkk
问,取何值可使迭代收敛？
取何值时迭代收敛最快？
解,考察 B = I +? A 的特征根?1 = 1+?,?2 = 1+ 3?
收敛要求 B?<1?2/3 <? < 0
B? = max { | 1+? |,| 1+ 3? | }
当?取何值时 最小？
2/3?1/3 0
=? 1/2
上一页 下一页81
作业,P223
题 2
作业,P223
题 4
作业,P223
题 5
定理作业,P223-224
题 7,题 11
作业,p.225-226
题 22，题 25
作业,P225
题 16,18,19
作业,P224
题 14
