上一页 下一页1
第六章 矩阵特征值问题的解法上一页 下一页2
给出,若有 使得：
nnijaA )(
,xAx 0?x
0)d e t ( IA?
则称 为矩阵 的特征值,为相应的特征向量。
特征值 为特征方程的根。
A
x
上一页 下一页3
若干结果,
第六章 1.doc
上一页 下一页4
特征值的估计与扰动问题
特征值的估计
},|||:|{)(?
ij
iijiii aazczAD
ni,,2,1
称之为 Gerschgorin圆盘（盖尔圆）,
（ Gerschgorin 圆盘定理）
为 n阶实方阵,则nnijaA )(设在的某个 Gerschgorin圆盘之中,
A 的任一特征值必落定理上一页 下一页5
定理 （第二圆盘定理）
设 为 阶实方阵，如果 的 个 Gerschgorin
圆盘与其他圆盘不相连，则恰好有 的 个特征值落在该 个圆盘的并集之中，即：
A
n A kA
k
k
,
1 ji
k
j
DS
ji
n
kj
DT
1
特别地：孤立圆盘仅含有一个特征值,
为 的一个重新排列,,则 中含有 的 个特征值,
},,2,1{ n?
TS S A k
},,,,,{ 11 nkk iiii
上一页 下一页6
关于实对称矩阵的极大 —极小定理：
n
i
n
j
n
i
ijiijT
T
xxxaxx Axxxx xAxxR
1 1 1
2/
),(
),()(
为矩阵 关于向量 的 Rayleigh（雷利）商,A x
为 阶实对称矩阵，则其特征值皆为实数，
记做：
A n
n21
并且存在规范正交特征向量系满足：
,,,2,1,niuAu iii njiuu ijji,,2,1,,),(
设 为 阶实矩阵,.
我们称
A n nT
n Rxxxx,0),,( 1?
定义上一页 下一页7
),(m i n)(m i n 101
2
xAxxR xx
),,(m a x)(m a x 10
2
xAxxR xxn
由于,对于任意,可以取,使得,.
)()( xRxR x?
1|||| 2?x?
证明,假设 为 的规范正交特征向量组，则对任何向量,有
nuuu,,,21? A
nRx?
n
i
ii ux
1
设 为 阶实对称矩阵，其特征值为,则
A n
n21
定理上一页 下一页8
于是
,/
),(
),(
),(
),(
)(
1
22
1
1 1
1 1
n
i
ii
n
i
i
n
i
n
i
iiii
n
i
n
i
iiiii
uu
uu
xx
xAx
xR
因而,特别地，若取,这时
nxx
xAx
),(
),(
1
1ux?
1111
11
11 ),(
),(
),( uu
uu
uAu
从而,同理可证
)(m i n01 xRx )(m ax0 xRXn
上一页 下一页9
特征值的扰动问题
A?
EA?~
例：
a
a
a
A
1
1
讨论,的大小,~
a
a
a
EA
1
1
特征方程
0
~
1
~
1
~
))(
~
d e t (?
a
a
a
EAI
上一页 下一页10
,0)1()()1()~( 11 nnna na )~(
njea n
ji
nj,,2,,1,)(
21
nja njj,,2,1,|)(||
1
设 则,若 在的上角，则特征值并无扰动,
,20,10 20 n? 11 10n EA?
上一页 下一页11
定理 （ Bauer-Fike）
),,( 11 ndiagAPP
设矩阵 具有完全特征向量系，矩阵 使得A P
则 经扰动后的矩阵 的一个特征值 满足不等式,
A EA
pppini EPP
1
1 ||m i n
其中 为矩阵的 范数,p ),2,1(pp||.||
上一页 下一页12
经常使用的 但定理 5对一般 仍成立,
若 为对称矩阵,可选为正交矩阵，这时于是有结论：
A
,,2,1p 1?p
12?PP
A
EA?
若 为实对称矩阵，而 为 的任何一个扰动，则对 的任何一个特征值,
有
A EA?推论
21 |m i n Eini
上一页 下一页13
§ 2 乘幂法与反乘幂法计算矩阵的主特征根及对应的特征向量
乘 幂法条件,A 有特征根 |?1| > |?2|?…? |?n|? 0,对应 n个线性无关的特征向量
nxx,...,1
思路,从任意 出发，要求0)0(
0,1
1
)0(
n
i
ii x
)0()1( A?
n
i
iii x
1
)1()2( A?
n
i
iii x
1
2
… … …
n
i
i
k
i
i
k
n
i
i
k
ii
kk
x
xA
1 1
1
1
)1()(
|?i /?1 | < 1
当 k 充分大时，有
1111)1(111)(,xx kkkk
这是 A关于?1的近似特征向量
)(
1
111
)(
k
kk xAA
1)1(
)(
)(
)(?
i
k
i
k
( 0 ) 1(,) 0x
上一页 下一页14
定理 设 A?Rn?n为 非亏损矩阵,其主特征根?
1为实根，
且 |?1| > |?2|?…? |?n| 。则从任意非零向量 (满足 )出发,迭代 收敛到主特征向量,
收敛到?1。
)0( 0),( 1)0(1 xv
)0()( kk A? 1x? ikik )/()( )()1(
每个不同的特征根只对应一个 Jordan
块注,?结论对 重根?1 =?2 = … =?r 成立。
r
i
ii
kr
i
n
ri
i
k
i
iii
kk xxx
1
1
1 1 1
1
)(
若有?1 =2,则此法不收敛。
任取初始向量时，因为不知道,所以不能保证?1? 0,故所求得之 不一定是,而是使得 的第一个,同时得到的特征根是?m 。
1x?
)(k 1x?
0),( )0(?mx mx?
上一页 下一页15
规范化为避免大数出现，需将迭代向量 规范化,即每一步先保证,再代入下一步迭代。一般用 。1|||| ||m ax||||
1 iniv
记,|||||| )()( k
ik k
则有：
1
0
)(
)0(1
)1(
)1()1(
|||| 1 ks si
k
k
i
kk
sk v
vA
v
vu
1
0
)(
)0()1()(
||ks si
kkk
sv
vAuAv
|| )(
)()(
k
i
kk
kv
vu 1x? )(
)1(
)(
1 1
k
ik
i
k
i
kvu
v
算法：乘幂法给定一非零的初始向量，获得 n?n矩阵 A的主特征征值及其相应的特征向量,
Input,维数 n; 矩阵 a[ ][ ]; 初始向量 V0[ ]; 误差容限 TOL;
迭代的最大次数 Nmax.
Output:近似特征值?和规格化的近似特征向量或失败信息。
上一页 下一页16
算法,乘幂法
Step 1 Set k = 1;
Step 2 Find index such that | V0[ index ] | = || V0 ||? ;
Step 3 Set V0[ ] = V0[ ] / V0[ index ]; /*规格化 V0 */
Step 4 While ( k? Nmax) do steps 5-11
Step 5 V [ ] = A V0[ ]; /* 由 Uk?1 计算 Vk */
Step 6? = V[ index ];
Step 7 Find index such that | V[ index ] | = || V ||? ;
Step 8 If V[ index ] == 0 then
Output ( ―A has the eigenvalue 0‖; V0[ ] ) ; STOP,
/* 矩阵是奇异的，用户尝试新的 V0 */
Step 9 err = || V0? V / V[ index ] ||? ;
V0[ ] = V[ ] / V[ index ]; /* 计算 Uk */
Step 10 If (err < TOL) then
Output (? ; V0[ ] ) ; STOP,/*成功 */
Step 11 Set k ++;
Step 12 Output (Maximum number of iterations exceeded);
STOP,/* 失败 */
上一页 下一页17
求矩阵 A的按模最大的特征值解 取 x(0)=(1,0)T,计算 x(k)=Ax(k-1),结果如下例
6
1
5
1
5
1
4
1
A
k x1(k) x2(k) x1(k)/x1(k-1) x2(k)/x2(k-1)
0 1 0
1 0.25 0.2
2 0.10250 0.083333 0.41 0.41665
3 0.042292 0.034389 0.41260 0.41267
4 0.017451 0.014190 0.41263 0.41263
可取0.41263,x1?(0.017451,0.014190)T,
上一页 下一页18
原点位移法
n
i
i
k
iikkk xA
1 1
1)1()(
决定收敛的速度，特别是 |?2 /?1 |
希望 |?2 /?1 | 越小越好。
不妨设?1 >?2?…n,且 |?2 | > |?n |。
1?2?n
O p = (?2 +?n ) / 2
思路令 B = A? pI,则有 |?I?A | = |?I?(B+pI) | = | (p)I?B |
A? p =?B 。 而,所以求 B的特征根收敛快。 ||
|||| ||
1
2
1
2 pp
p为何取在这里呢？
上一页 下一页19
反幂法若 A 有 |?1 |? |?2 |?… > |?n |，则 A?1 有对应同样一组特征向量。
11
111
…nn
A?1 的主特征根 A的绝对值最小的特征根
Q,在每一步我们怎样计算?)(1)1( kk A
A,先对 A进行三角分解，再解线性系统,)()1( kkA
若知道某一特征根?i 的大致位置 p,即对任意 j? i
有 |?i? p | << |?j? p |,并且如果 (A? pI)?1存在，则可以用反幂法求 (A? pI)?1的主特征根 1/(?i?p ),收敛将非常快。
思路上一页 下一页20
§ 3 约化矩阵的 Householder方法
矩阵的约化目的：利用相似变换，将矩阵约化为,尽可能简单,
的形式的过程，称为矩阵的约化,
A ASS 1?
A?A?特征值
x xS 1?特征向量上一页 下一页21
Householder 矩阵称 为 Householder矩阵,1,2 2 wwwIH T
性质,1） （ Hermite矩阵）HH T?
( 2 )T T TH I ww H
2）正交性,IHH T?
( 2 ) ( 2 )T T T TH H I w w I w w
( 4 4 )T T TI w w w w w w I
上一页 下一页22
正交矩阵 作用于 上,仍有：H x
,22 xHx?即不改变向量的长度,
22(,) (,) (,)TH x H x H x H H x x x x x
定理 6 设,则总存在 Householder 22,,yxRyx n
yHx?矩阵 H 使：
证明,若,则只需取 即可,yx? xw?
若,并确定 w使yx?,)2( yxwwIHx T
据此应有,xywxw T )(2
上一页 下一页23
即,w应与向量 平行,xy?
因为,所以yx?,02 yx
又因为,所以可取12?w,
2xy
xyw
这时 即为所求的 Householder矩阵,TwwIH 2
可以设计,使得 变为所需要的形状,H x
求 （ 找 ）,使得：,nRx? H w 12||||
0
0
*
exHx
上一页 下一页24
Tnxxxx ),,,( 21
0
0
1
11
e
121 ||||)( exxs i gn
这里,211 ||||)( xxs i gn
Texex
exIH ))((||||
2
11112
11
还可构造,使得：H
上一页 下一页25
yx
mn
m
m
mn
m
H
1
1
0
0
*
*
*
*
*
*
*
即要求,且 的后面 个元素为零,22 yx? y 1 mn
上一页 下一页26
设,作,),,,,,( 11 Tnmm xxxxx,)()( mnmnm RH
使得,个分量1
0
0
1
1
mn
x
x
H
m
n
m
m
1 1 12 ( ),(,,),Tm m m nx s i g n x x x x
m
m
H
IH
0
0令上一页 下一页27
则,)0,0,,,( 11 TmmxxHx
显然，这样构造的 仍然是 Householder矩阵,H
约化矩阵为 Hessenberg形式
nnijT gGAQQ )(相似变换：
其中,当0?ijg,1 ji
定理 7：对任何矩阵,可以构造正交矩阵 nnRA
使得 为上 Hessenberg,21 nHHQ? GAQQ T?
矩阵，其中 为 Householder矩阵,21,,?nHH?
上一页 下一页28
推论,当 为对称矩阵时，可以构造出正交矩阵 nnRA
使得 为对称三对角矩阵,,221 nHHHQ?AQQT
矩阵的 分解QR
分解：,,为正交矩阵,为上三角阵,QRA? IQQ T? Q R
作法：用 表示 的列向量，令 )0()0(2)0(1,,,naaa?A
)0()0(2)0(1)0(,,,naaaAA
取 Householder矩阵 使得,1H,)0,,0,( 1)0(11 TaH
其中,则：( 0 )
1 1 1 12 ( ),a s i g n a
上一页 下一页29
)1()1(
2
)1(
2
)1(
22
)1(
1
)1(
121
)0(
1
0
0
nnn
n
n
aa
aa
aa
AH
1)1()1(2)1(1,,,Aaaa n
然后,构造 Householder矩阵
2
2 0
01
HH
其中 为 阶 Householder矩阵，使得：2H 1?n
TaaH )0,,0,,( 2)1(12)1(22
上一页 下一页30
则,具有如下形式,212 AAH?
)2()2(
3
)2(
3
)2(
33
)2(
2
)2(
232
)2(
1
)2(
13
)2(
12
)2(
11
2
00
00
0
nnn
n
n
n
aa
aa
aa
aaaa
A
构造出一串 Householder 矩阵,使 11,,?nHH?
.121 RAHHH nn
记,显然为正交矩阵,121 nT HHHQ?Q
上一页 下一页31
§ 4 求实对称矩阵特征值的二分法设 已知存在,,使得,.,nnT RAAA Q IQQ T?
nn
n
T
AQQC
0
0
22
21
不妨设,),,3,2(0 nii
上一页 下一页32
Sturm 序列定义,多项式序列,1)(,)( 00 pp nkk,
0
0
)(
2
21
kk
k
k
p
即为 的特征多项式,称为矩阵 的)(?np C)(?kp C
Sturm序列,
上一页 下一页33
),()()()(
,)(
2
2
1
11
kkkkk ppp
p
nk,,3,2
有：
性质 1,仅有实根,nkp k,,2,1,0)(
这是因为矩阵 的任意 k阶主子矩阵都是对称矩阵，C
为它的特征多项式，所以它的 k个零点都是)(?kp
实数,
上一页 下一页34
kk
k
k
C
0
0
22
21
性质 2 无根，相邻两多项式,无)(0?p )(?kp )(1kp
公共根,
性质 3 若 是 的根，则? )1,,2,1(0)( nkp k
0)()( 11 kk pp
上一页 下一页35
事实上,因为,而 0)(kp,0)(,0)( 11 kk pp
故有：
,0)()()( 212 111 kkkk ppp
性质 4 多项式序列 中相继两多项式 和)(?kp )(?kp
)(1kp 的零点交错隔开,即假设 nkkkkk,,2,1,)()(2)(1
为 的 k个零点，则：)(?kp
.)1( 1)()(2)1(2)(1)1(1 kkkkkkkk
上一页 下一页36
从而 每个的零点均为单重实零点,)(?kp
证明,（ 归纳法）
由于 0)()(,0)( )1(1022)1(12)1(11 ppp
又：,)(,)( 22 pp
故,)2(2)1(1)2(1
上一页 下一页37
同理：,0)(,0)( )2(11)2(12 pp
故：,0)()( )2(1123)2(13 pp
于是由,得出 )(3p,)2(1)3(1
类似可得,0)( )2(23p
于是又由 便得 )(3p
.,)3(3)2(2)2(2)3(2)2(1
对于,均有：k
.)1()(,0)( kkk pp
上一页 下一页38
性质 5 在 的邻域，所有多项式 都为正， )(?kp
且当 自左向右变动经过 的零? ),,2,1)(( nkp k
点 时,的下降或上升是与 或 )(?kp 0)(1kp
一致的,0)(1kp
多项式序列 称为 Sturm序列：)}({?kp
1.相邻多项式无公共根
2.若,0)()(,0)( 11 kkk ppp
3.相邻两多项式的根彼此交错上一页 下一页39
以下记,为数列 中相邻两数)(?s )(,),(),( 10 nppp?
符号一致的数目（同号数）,
,1,1,2,9,6,4,1 2)(s
,9,0,2,0,7,4,1 5)(s
例如,
注,若,则取它的符号与前一个 0)(kp 0)(
1kp
同号,
1200
2120
0212
0021
C
例如,矩阵上一页 下一页40
.3,2,1),(4)()1()(
,1)(,1)(
11
10
kppp
pp
kkk
此时必先求出 的表达式,)(?kp
求多项式 的值时，可用上述递推公式，不)(?kp
表 6.4
上一页 下一页41
-3 1 3 4 4.22 4.5 5
1 1 1 1 1 1 1
4 0 -2 -3 -3.22 -3.5 -4
12 -4 0 5 6.368 8.25 12
32 0 8 -3 -7.626 -14.875 -32
80 16 -16 -11 -0.917 19.062 80
4 2 1 1 1 0 0
)(0?p
)(1?p
)(2?p
)(3?p
)(4?p
)(?S
上一页 下一页42
定理 9 若实对称三对角矩阵 的所有次对角元素不为C
零，则 是 在区间 中根的数目，)(?S )(?np ),[
即矩阵 的 的特征根的数目,C
证明,由性质 5知,时 的同号数)(?kp,)( nS
现让 从 起从左向右变动。
当 不经过所有 的零点 时,显然不变；? )(?ip? )(?S
当 经过 的零点 时，? 1,,2,1),( nkp k )(?S
也不改变,
上一页 下一页43
事实上，对于充分小的,0
在 内 均不变号，),( )(),( 11 kk pp
根据性质 3和 5以及关于 的符号规定，)(?kp
)(?kp 在 内和 同号,和],( )(1kp )(1kp
反号在 内和 反号,和),(a )(1kp )(1kp
同 号它们的符号变化为表 6.5,6.6之一,
总之，通过 的零点时,不改变,))(( nkp k )(?S
上一页 下一页44
],( ),(
)(1kp
)(?kp
)(1kp
+ + ﹣ ﹣
+ ﹣ ﹣ +
﹣ – + +
],( ),(
)(1kp
)(?kp
)(1kp
表 6.5 表 6.6
上一页 下一页45
当 通过 的零点 时,根据同样的论证，? )(?np?
由与 （包括在点 ）同号变到与它反)(?np )(1np?
号，因而失去一个同号数，定理证毕,
计算实对称三对角矩阵特征值的二分法任意区间 中所含 C的特征值数目为),[
),()( SS?若 C的特征值排列为：
11nn
),()( SmS且 ).,[m则：
上一页 下一页46
求特征值 的二分法如下：m?
给定包含 的初始区间 （由特征值的位置m? ],[ 00 ba
估计定理 1，可取 ）对,,00 CbCa,2,1,0?i
（ 1）取 的中点],[ ii ba,2/)( iii bar
（ 2）计算 的同号数 nkik rp 0)}({? ).( irS
（ 3） 若 则,)( mrS i? ;,11 iiii bbra
否则,,11 iiii rbaa
（ 4）若 则令,|| 11 ii ab,2/)( 11 iim ba?
否则
1 ii
上一页 下一页47
特征向量的计算用反幂法求 的特征向量：C
（优势特征值），)0(x?
k
kk
k
k
k
m
k
myx
ym
xICy
/
)m a x (
)
~
(
)()(
)(
)1(1)(?
此时：,
mm
km ~
1
,m a x
)(
m
mk
u
ux?
即,mmm uCu
这样可求得 相应于 的特征向量,C m?
上一页 下一页48
§ 5 方法QR
方法的基本思想QR
首先作 的 分解：A QR
111 RQAA （ 对角元非负）1R
取,然后作 的 分解,,112 QRA? 2A QR
,,2,1,
)(,
1?kQRA
RRQA
kkk
kkkk 具有非负对角元要求一般地：
于是得矩阵序列,,1kkA
上一页 下一页49
可以证明：
(1) ∽kA AA?1
(2)
B
B
B
B
A
s
k
*
**
2
1
为一阶或二阶方阵,lB
于是 的特征值即为 的特征值,lB A
上一页 下一页50
定理 10 设 的 个特征值具有性质：A n
0|||||| 21 n
n
k
A
*
**
2
1
则：
证,（ 略）
上一页 下一页51
Hessenberg矩阵的 方法QR
先把 经相似变换约化为 Hessenberg矩阵，即：A
**
***
***
2112
GHAHHH
nn
∽ 且有很多零元,A G
设 为 Hessenberg矩阵,作 分解,A QR
111 RQAA
上一页 下一页52
112 QRA
,,2,1,
)(,
1?kQRA
RRQA
kkk
kkkk 具有非负对角元要求
问题在于 是否仍为 Hessenberg矩阵？kA
可以证明：
若 为 Hessenberg矩阵，A,111 RQAA
则,仍为 Hessenberg矩阵 。112 QRA
上一页 下一页53
带原点位移的 方法（略）QR
方法收敛的速度同于幂法,QR
第六章 矩阵特征值问题的解法上一页 下一页2
给出,若有 使得：
nnijaA )(
,xAx 0?x
0)d e t ( IA?
则称 为矩阵 的特征值,为相应的特征向量。
特征值 为特征方程的根。
A
x
上一页 下一页3
若干结果,
第六章 1.doc
上一页 下一页4
特征值的估计与扰动问题
特征值的估计
},|||:|{)(?
ij
iijiii aazczAD
ni,,2,1
称之为 Gerschgorin圆盘（盖尔圆）,
（ Gerschgorin 圆盘定理）
为 n阶实方阵,则nnijaA )(设在的某个 Gerschgorin圆盘之中,
A 的任一特征值必落定理上一页 下一页5
定理 （第二圆盘定理）
设 为 阶实方阵，如果 的 个 Gerschgorin
圆盘与其他圆盘不相连，则恰好有 的 个特征值落在该 个圆盘的并集之中，即：
A
n A kA
k
k
,
1 ji
k
j
DS
ji
n
kj
DT
1
特别地：孤立圆盘仅含有一个特征值,
为 的一个重新排列,,则 中含有 的 个特征值,
},,2,1{ n?
TS S A k
},,,,,{ 11 nkk iiii
上一页 下一页6
关于实对称矩阵的极大 —极小定理：
n
i
n
j
n
i
ijiijT
T
xxxaxx Axxxx xAxxR
1 1 1
2/
),(
),()(
为矩阵 关于向量 的 Rayleigh（雷利）商,A x
为 阶实对称矩阵，则其特征值皆为实数，
记做：
A n
n21
并且存在规范正交特征向量系满足：
,,,2,1,niuAu iii njiuu ijji,,2,1,,),(
设 为 阶实矩阵,.
我们称
A n nT
n Rxxxx,0),,( 1?
定义上一页 下一页7
),(m i n)(m i n 101
2
xAxxR xx
),,(m a x)(m a x 10
2
xAxxR xxn
由于,对于任意,可以取,使得,.
)()( xRxR x?
1|||| 2?x?
证明,假设 为 的规范正交特征向量组，则对任何向量,有
nuuu,,,21? A
nRx?
n
i
ii ux
1
设 为 阶实对称矩阵，其特征值为,则
A n
n21
定理上一页 下一页8
于是
,/
),(
),(
),(
),(
)(
1
22
1
1 1
1 1
n
i
ii
n
i
i
n
i
n
i
iiii
n
i
n
i
iiiii
uu
uu
xx
xAx
xR
因而,特别地，若取,这时
nxx
xAx
),(
),(
1
1ux?
1111
11
11 ),(
),(
),( uu
uu
uAu
从而,同理可证
)(m i n01 xRx )(m ax0 xRXn
上一页 下一页9
特征值的扰动问题
A?
EA?~
例：
a
a
a
A
1
1
讨论,的大小,~
a
a
a
EA
1
1
特征方程
0
~
1
~
1
~
))(
~
d e t (?
a
a
a
EAI
上一页 下一页10
,0)1()()1()~( 11 nnna na )~(
njea n
ji
nj,,2,,1,)(
21
nja njj,,2,1,|)(||
1
设 则,若 在的上角，则特征值并无扰动,
,20,10 20 n? 11 10n EA?
上一页 下一页11
定理 （ Bauer-Fike）
),,( 11 ndiagAPP
设矩阵 具有完全特征向量系，矩阵 使得A P
则 经扰动后的矩阵 的一个特征值 满足不等式,
A EA
pppini EPP
1
1 ||m i n
其中 为矩阵的 范数,p ),2,1(pp||.||
上一页 下一页12
经常使用的 但定理 5对一般 仍成立,
若 为对称矩阵,可选为正交矩阵，这时于是有结论：
A
,,2,1p 1?p
12?PP
A
EA?
若 为实对称矩阵，而 为 的任何一个扰动，则对 的任何一个特征值,
有
A EA?推论
21 |m i n Eini
上一页 下一页13
§ 2 乘幂法与反乘幂法计算矩阵的主特征根及对应的特征向量
乘 幂法条件,A 有特征根 |?1| > |?2|?…? |?n|? 0,对应 n个线性无关的特征向量
nxx,...,1
思路,从任意 出发，要求0)0(
0,1
1
)0(
n
i
ii x
)0()1( A?
n
i
iii x
1
)1()2( A?
n
i
iii x
1
2
… … …
n
i
i
k
i
i
k
n
i
i
k
ii
kk
x
xA
1 1
1
1
)1()(
|?i /?1 | < 1
当 k 充分大时，有
1111)1(111)(,xx kkkk
这是 A关于?1的近似特征向量
)(
1
111
)(
k
kk xAA
1)1(
)(
)(
)(?
i
k
i
k
( 0 ) 1(,) 0x
上一页 下一页14
定理 设 A?Rn?n为 非亏损矩阵,其主特征根?
1为实根，
且 |?1| > |?2|?…? |?n| 。则从任意非零向量 (满足 )出发,迭代 收敛到主特征向量,
收敛到?1。
)0( 0),( 1)0(1 xv
)0()( kk A? 1x? ikik )/()( )()1(
每个不同的特征根只对应一个 Jordan
块注,?结论对 重根?1 =?2 = … =?r 成立。
r
i
ii
kr
i
n
ri
i
k
i
iii
kk xxx
1
1
1 1 1
1
)(
若有?1 =2,则此法不收敛。
任取初始向量时，因为不知道,所以不能保证?1? 0,故所求得之 不一定是,而是使得 的第一个,同时得到的特征根是?m 。
1x?
)(k 1x?
0),( )0(?mx mx?
上一页 下一页15
规范化为避免大数出现，需将迭代向量 规范化,即每一步先保证,再代入下一步迭代。一般用 。1|||| ||m ax||||
1 iniv
记,|||||| )()( k
ik k
则有：
1
0
)(
)0(1
)1(
)1()1(
|||| 1 ks si
k
k
i
kk
sk v
vA
v
vu
1
0
)(
)0()1()(
||ks si
kkk
sv
vAuAv
|| )(
)()(
k
i
kk
kv
vu 1x? )(
)1(
)(
1 1
k
ik
i
k
i
kvu
v
算法：乘幂法给定一非零的初始向量，获得 n?n矩阵 A的主特征征值及其相应的特征向量,
Input,维数 n; 矩阵 a[ ][ ]; 初始向量 V0[ ]; 误差容限 TOL;
迭代的最大次数 Nmax.
Output:近似特征值?和规格化的近似特征向量或失败信息。
上一页 下一页16
算法,乘幂法
Step 1 Set k = 1;
Step 2 Find index such that | V0[ index ] | = || V0 ||? ;
Step 3 Set V0[ ] = V0[ ] / V0[ index ]; /*规格化 V0 */
Step 4 While ( k? Nmax) do steps 5-11
Step 5 V [ ] = A V0[ ]; /* 由 Uk?1 计算 Vk */
Step 6? = V[ index ];
Step 7 Find index such that | V[ index ] | = || V ||? ;
Step 8 If V[ index ] == 0 then
Output ( ―A has the eigenvalue 0‖; V0[ ] ) ; STOP,
/* 矩阵是奇异的，用户尝试新的 V0 */
Step 9 err = || V0? V / V[ index ] ||? ;
V0[ ] = V[ ] / V[ index ]; /* 计算 Uk */
Step 10 If (err < TOL) then
Output (? ; V0[ ] ) ; STOP,/*成功 */
Step 11 Set k ++;
Step 12 Output (Maximum number of iterations exceeded);
STOP,/* 失败 */
上一页 下一页17
求矩阵 A的按模最大的特征值解 取 x(0)=(1,0)T,计算 x(k)=Ax(k-1),结果如下例
6
1
5
1
5
1
4
1
A
k x1(k) x2(k) x1(k)/x1(k-1) x2(k)/x2(k-1)
0 1 0
1 0.25 0.2
2 0.10250 0.083333 0.41 0.41665
3 0.042292 0.034389 0.41260 0.41267
4 0.017451 0.014190 0.41263 0.41263
可取0.41263,x1?(0.017451,0.014190)T,
上一页 下一页18
原点位移法
n
i
i
k
iikkk xA
1 1
1)1()(
决定收敛的速度，特别是 |?2 /?1 |
希望 |?2 /?1 | 越小越好。
不妨设?1 >?2?…n,且 |?2 | > |?n |。
1?2?n
O p = (?2 +?n ) / 2
思路令 B = A? pI,则有 |?I?A | = |?I?(B+pI) | = | (p)I?B |
A? p =?B 。 而,所以求 B的特征根收敛快。 ||
|||| ||
1
2
1
2 pp
p为何取在这里呢？
上一页 下一页19
反幂法若 A 有 |?1 |? |?2 |?… > |?n |，则 A?1 有对应同样一组特征向量。
11
111
…nn
A?1 的主特征根 A的绝对值最小的特征根
Q,在每一步我们怎样计算?)(1)1( kk A
A,先对 A进行三角分解，再解线性系统,)()1( kkA
若知道某一特征根?i 的大致位置 p,即对任意 j? i
有 |?i? p | << |?j? p |,并且如果 (A? pI)?1存在，则可以用反幂法求 (A? pI)?1的主特征根 1/(?i?p ),收敛将非常快。
思路上一页 下一页20
§ 3 约化矩阵的 Householder方法
矩阵的约化目的：利用相似变换，将矩阵约化为,尽可能简单,
的形式的过程，称为矩阵的约化,
A ASS 1?
A?A?特征值
x xS 1?特征向量上一页 下一页21
Householder 矩阵称 为 Householder矩阵,1,2 2 wwwIH T
性质,1） （ Hermite矩阵）HH T?
( 2 )T T TH I ww H
2）正交性,IHH T?
( 2 ) ( 2 )T T T TH H I w w I w w
( 4 4 )T T TI w w w w w w I
上一页 下一页22
正交矩阵 作用于 上,仍有：H x
,22 xHx?即不改变向量的长度,
22(,) (,) (,)TH x H x H x H H x x x x x
定理 6 设,则总存在 Householder 22,,yxRyx n
yHx?矩阵 H 使：
证明,若,则只需取 即可,yx? xw?
若,并确定 w使yx?,)2( yxwwIHx T
据此应有,xywxw T )(2
上一页 下一页23
即,w应与向量 平行,xy?
因为,所以yx?,02 yx
又因为,所以可取12?w,
2xy
xyw
这时 即为所求的 Householder矩阵,TwwIH 2
可以设计,使得 变为所需要的形状,H x
求 （ 找 ）,使得：,nRx? H w 12||||
0
0
*
exHx
上一页 下一页24
Tnxxxx ),,,( 21
0
0
1
11
e
121 ||||)( exxs i gn
这里,211 ||||)( xxs i gn
Texex
exIH ))((||||
2
11112
11
还可构造,使得：H
上一页 下一页25
yx
mn
m
m
mn
m
H
1
1
0
0
*
*
*
*
*
*
*
即要求,且 的后面 个元素为零,22 yx? y 1 mn
上一页 下一页26
设,作,),,,,,( 11 Tnmm xxxxx,)()( mnmnm RH
使得,个分量1
0
0
1
1
mn
x
x
H
m
n
m
m
1 1 12 ( ),(,,),Tm m m nx s i g n x x x x
m
m
H
IH
0
0令上一页 下一页27
则,)0,0,,,( 11 TmmxxHx
显然，这样构造的 仍然是 Householder矩阵,H
约化矩阵为 Hessenberg形式
nnijT gGAQQ )(相似变换：
其中,当0?ijg,1 ji
定理 7：对任何矩阵,可以构造正交矩阵 nnRA
使得 为上 Hessenberg,21 nHHQ? GAQQ T?
矩阵，其中 为 Householder矩阵,21,,?nHH?
上一页 下一页28
推论,当 为对称矩阵时，可以构造出正交矩阵 nnRA
使得 为对称三对角矩阵,,221 nHHHQ?AQQT
矩阵的 分解QR
分解：,,为正交矩阵,为上三角阵,QRA? IQQ T? Q R
作法：用 表示 的列向量，令 )0()0(2)0(1,,,naaa?A
)0()0(2)0(1)0(,,,naaaAA
取 Householder矩阵 使得,1H,)0,,0,( 1)0(11 TaH
其中,则：( 0 )
1 1 1 12 ( ),a s i g n a
上一页 下一页29
)1()1(
2
)1(
2
)1(
22
)1(
1
)1(
121
)0(
1
0
0
nnn
n
n
aa
aa
aa
AH
1)1()1(2)1(1,,,Aaaa n
然后,构造 Householder矩阵
2
2 0
01
HH
其中 为 阶 Householder矩阵，使得：2H 1?n
TaaH )0,,0,,( 2)1(12)1(22
上一页 下一页30
则,具有如下形式,212 AAH?
)2()2(
3
)2(
3
)2(
33
)2(
2
)2(
232
)2(
1
)2(
13
)2(
12
)2(
11
2
00
00
0
nnn
n
n
n
aa
aa
aa
aaaa
A
构造出一串 Householder 矩阵,使 11,,?nHH?
.121 RAHHH nn
记,显然为正交矩阵,121 nT HHHQ?Q
上一页 下一页31
§ 4 求实对称矩阵特征值的二分法设 已知存在,,使得,.,nnT RAAA Q IQQ T?
nn
n
T
AQQC
0
0
22
21
不妨设,),,3,2(0 nii
上一页 下一页32
Sturm 序列定义,多项式序列,1)(,)( 00 pp nkk,
0
0
)(
2
21
kk
k
k
p
即为 的特征多项式,称为矩阵 的)(?np C)(?kp C
Sturm序列,
上一页 下一页33
),()()()(
,)(
2
2
1
11
kkkkk ppp
p
nk,,3,2
有：
性质 1,仅有实根,nkp k,,2,1,0)(
这是因为矩阵 的任意 k阶主子矩阵都是对称矩阵，C
为它的特征多项式，所以它的 k个零点都是)(?kp
实数,
上一页 下一页34
kk
k
k
C
0
0
22
21
性质 2 无根，相邻两多项式,无)(0?p )(?kp )(1kp
公共根,
性质 3 若 是 的根，则? )1,,2,1(0)( nkp k
0)()( 11 kk pp
上一页 下一页35
事实上,因为,而 0)(kp,0)(,0)( 11 kk pp
故有：
,0)()()( 212 111 kkkk ppp
性质 4 多项式序列 中相继两多项式 和)(?kp )(?kp
)(1kp 的零点交错隔开,即假设 nkkkkk,,2,1,)()(2)(1
为 的 k个零点，则：)(?kp
.)1( 1)()(2)1(2)(1)1(1 kkkkkkkk
上一页 下一页36
从而 每个的零点均为单重实零点,)(?kp
证明,（ 归纳法）
由于 0)()(,0)( )1(1022)1(12)1(11 ppp
又：,)(,)( 22 pp
故,)2(2)1(1)2(1
上一页 下一页37
同理：,0)(,0)( )2(11)2(12 pp
故：,0)()( )2(1123)2(13 pp
于是由,得出 )(3p,)2(1)3(1
类似可得,0)( )2(23p
于是又由 便得 )(3p
.,)3(3)2(2)2(2)3(2)2(1
对于,均有：k
.)1()(,0)( kkk pp
上一页 下一页38
性质 5 在 的邻域，所有多项式 都为正， )(?kp
且当 自左向右变动经过 的零? ),,2,1)(( nkp k
点 时,的下降或上升是与 或 )(?kp 0)(1kp
一致的,0)(1kp
多项式序列 称为 Sturm序列：)}({?kp
1.相邻多项式无公共根
2.若,0)()(,0)( 11 kkk ppp
3.相邻两多项式的根彼此交错上一页 下一页39
以下记,为数列 中相邻两数)(?s )(,),(),( 10 nppp?
符号一致的数目（同号数）,
,1,1,2,9,6,4,1 2)(s
,9,0,2,0,7,4,1 5)(s
例如,
注,若,则取它的符号与前一个 0)(kp 0)(
1kp
同号,
1200
2120
0212
0021
C
例如,矩阵上一页 下一页40
.3,2,1),(4)()1()(
,1)(,1)(
11
10
kppp
pp
kkk
此时必先求出 的表达式,)(?kp
求多项式 的值时，可用上述递推公式，不)(?kp
表 6.4
上一页 下一页41
-3 1 3 4 4.22 4.5 5
1 1 1 1 1 1 1
4 0 -2 -3 -3.22 -3.5 -4
12 -4 0 5 6.368 8.25 12
32 0 8 -3 -7.626 -14.875 -32
80 16 -16 -11 -0.917 19.062 80
4 2 1 1 1 0 0
)(0?p
)(1?p
)(2?p
)(3?p
)(4?p
)(?S
上一页 下一页42
定理 9 若实对称三对角矩阵 的所有次对角元素不为C
零，则 是 在区间 中根的数目，)(?S )(?np ),[
即矩阵 的 的特征根的数目,C
证明,由性质 5知,时 的同号数)(?kp,)( nS
现让 从 起从左向右变动。
当 不经过所有 的零点 时,显然不变；? )(?ip? )(?S
当 经过 的零点 时，? 1,,2,1),( nkp k )(?S
也不改变,
上一页 下一页43
事实上，对于充分小的,0
在 内 均不变号，),( )(),( 11 kk pp
根据性质 3和 5以及关于 的符号规定，)(?kp
)(?kp 在 内和 同号,和],( )(1kp )(1kp
反号在 内和 反号,和),(a )(1kp )(1kp
同 号它们的符号变化为表 6.5,6.6之一,
总之，通过 的零点时,不改变,))(( nkp k )(?S
上一页 下一页44
],( ),(
)(1kp
)(?kp
)(1kp
+ + ﹣ ﹣
+ ﹣ ﹣ +
﹣ – + +
],( ),(
)(1kp
)(?kp
)(1kp
表 6.5 表 6.6
上一页 下一页45
当 通过 的零点 时,根据同样的论证，? )(?np?
由与 （包括在点 ）同号变到与它反)(?np )(1np?
号，因而失去一个同号数，定理证毕,
计算实对称三对角矩阵特征值的二分法任意区间 中所含 C的特征值数目为),[
),()( SS?若 C的特征值排列为：
11nn
),()( SmS且 ).,[m则：
上一页 下一页46
求特征值 的二分法如下：m?
给定包含 的初始区间 （由特征值的位置m? ],[ 00 ba
估计定理 1，可取 ）对,,00 CbCa,2,1,0?i
（ 1）取 的中点],[ ii ba,2/)( iii bar
（ 2）计算 的同号数 nkik rp 0)}({? ).( irS
（ 3） 若 则,)( mrS i? ;,11 iiii bbra
否则,,11 iiii rbaa
（ 4）若 则令,|| 11 ii ab,2/)( 11 iim ba?
否则
1 ii
上一页 下一页47
特征向量的计算用反幂法求 的特征向量：C
（优势特征值），)0(x?
k
kk
k
k
k
m
k
myx
ym
xICy
/
)m a x (
)
~
(
)()(
)(
)1(1)(?
此时：,
mm
km ~
1
,m a x
)(
m
mk
u
ux?
即,mmm uCu
这样可求得 相应于 的特征向量,C m?
上一页 下一页48
§ 5 方法QR
方法的基本思想QR
首先作 的 分解：A QR
111 RQAA （ 对角元非负）1R
取,然后作 的 分解,,112 QRA? 2A QR
,,2,1,
)(,
1?kQRA
RRQA
kkk
kkkk 具有非负对角元要求一般地：
于是得矩阵序列,,1kkA
上一页 下一页49
可以证明：
(1) ∽kA AA?1
(2)
B
B
B
B
A
s
k
*
**
2
1
为一阶或二阶方阵,lB
于是 的特征值即为 的特征值,lB A
上一页 下一页50
定理 10 设 的 个特征值具有性质：A n
0|||||| 21 n
n
k
A
*
**
2
1
则：
证,（ 略）
上一页 下一页51
Hessenberg矩阵的 方法QR
先把 经相似变换约化为 Hessenberg矩阵，即：A
**
***
***
2112
GHAHHH
nn
∽ 且有很多零元,A G
设 为 Hessenberg矩阵,作 分解,A QR
111 RQAA
上一页 下一页52
112 QRA
,,2,1,
)(,
1?kQRA
RRQA
kkk
kkkk 具有非负对角元要求
问题在于 是否仍为 Hessenberg矩阵？kA
可以证明：
若 为 Hessenberg矩阵，A,111 RQAA
则,仍为 Hessenberg矩阵 。112 QRA
上一页 下一页53
带原点位移的 方法（略）QR
方法收敛的速度同于幂法,QR
