9.5 乘幂法乘幂法是适用于求一般矩阵按模最大特征值及相应特征向量的算法,
9.5.1 求 按模最大特征值和特征向量的乘幂法
设 A是 n阶矩阵，其 n个特征值按模从大到小排序为
1 2 3 n
又假设关于 λ1,λ2,…,λn的特征向量
v1,v2,…,vn线性无关,
任意取定初始向量 x0
0 1 1 2 2 1( 0 )nnx a v a v a v a
1 0 1 1 2 2
1 1 1 2 2 2
nn
n n n
x A x a A v a A v a A v
a v a v a v
2 2 2 22 1 0 1 1 1 2 2 2 n n nx Ax A x a v a v a v
…………..
建立迭代公式,1kkx A x
因为
),,3,2(1
1
nii
故当 k→∞ 时,xk→λ 1ka1v1.
因此,xk可看成是关于特征值 λ1的近似特征向量有一严重缺点，当 |?1|>1 （或 |?1 |<1时） {Vk}中不为零的分量将随 K的增大而无限增大，计算机就可能出现上溢（或随 K的增大而很快出现下溢）
1 0 1 1 1 2 2 2
2
1 1 1 2 2
11
[ ( ) ( ) ]
k k k k
k k n n n
k k kn
n
x A x A x a v a v a v
a v a v v
因此，在实际计算时，须按规范法计算，
每步先对向量 xk进行“规范化”。迭代格式改为
1,0,1,
k
k
k
kk
x
z
x
x A z k
对任意给定的初始向量 x0
类似地
01
1 0 1
10
,
|| || || ||
Azxx A z z
x A z
0
0 1 1 2 2
0
nn
x
z b v b v b v
x
0
0| | | |
k
k k
Az
z
Az?
当?1>0时
2
1 1 2 2
1 1 1
21
1 1 2 2
11
( ) ( )
||
|| ( ) ( ) ||
kk n
nnk
k k
kk n
nn
b v b v b v
z
b v b v b v
1
1
1
||
k
k
11
11| | | |
k
bv
z
bv?
11
11| | | |
k
bvz
bv?
当?1<0时
1
1
1
||
k
k
按模最大特征值 λ1及其相应的特征向量 v1
的乘幂法的计算公式：
1
1 1
1
,
0,1,
k
k
k
kk
TT
k k k k k
TT
k k k k
x
z
x
x Az
z x z Az
z z z z
k
9.7 QR方法
QR方法在特征值计算问题的发展上具有里程碑意义。在 1955年的时候人们还觉得特征值的计算是十分困扰的问题，到
1965年它的计算 —— 基于 QR方法的程序已经完全成熟。直到今天 QR方法仍然是特征值计算的有效方法之一。
9.7.1 两个基本定理定理 9.7.1 设 A是 n阶矩阵，其 n个 特征值为,那么存在一个酉矩阵 U，使
UＨ AU是以为 对角元的上三角矩阵,
12,,,n
12,,,n
定理 9.7.2 设 A是 n阶实矩 阵，那么，存在一个正交矩阵 Q，使 QＴ AQ为一个准上三角矩阵，
它的对角元是 A的一个特征值，对角元上的二阶块矩阵的两个特征值是 A的一对共轭复特征值,
9.7.2 相似约化为上 Hessenberg矩阵对一般 n阶矩阵,QR算法的每一个迭代步需要
O(n３ )次乘法运算,如果矩阵阶数稍大，这个算法几乎没有实际的应用价值,
通常采用的方法是先将矩阵相似约化为上
Hessenberg形式的矩阵，在此基础上应用 QR
迭代,这时，一个 QR迭代步的乘法运算次数只需 O(n２ ）次,
所谓上 Hessenberg矩阵是指一个 n阶矩阵 A，如果当 i>j+1时,aij=0，称 A为上 Hessenberg矩阵,例如：一个 5阶的上 Hessenberg矩阵具有如下的形式：
* * * * *
* * * * *
0 * * * *
0 0 * * *
0 0 0 * *
A
下面介绍 QR方法时，都假设矩阵 A是一个上 Hessenberg矩阵,
9.7.3 QR算法
设 A是 n阶矩阵且有 QR分解 A＝ QR,(2)
这里,Q是酉矩阵,R是上三角矩阵,如果 A
是满秩并规定 R有正对角元，这个分解是惟一的,
设 A是 n阶矩阵且有 QR分解 A＝ QR，
这里,Q是酉矩阵,R是上三角矩阵,如果 A是满秩并规定 R有正对角元，这个分解是惟一的,
QR方法是 1961年由作者 J.G.F.Francis和
V.N.Kublanovskaya设计的
QR分解是 QR算法的基础一,QR算法的基本思想
记 A＝ A１ 且有 A１ ＝ Q 1R1.将等号右边两个矩阵因子的次序交换，得 A２ ＝ R１ Q１,且
,(3) 即 A２ ～ A１,
不难证明,
即 Ak+1～ Ak～ … ～ A１,矩阵序列｛ Ak｝有相同的特征值,
记
12 1 1 1A Q A Q
1 1 11 1 1k k k k k k kA Q A Q Q Q A Q Q
12kkQ Q Q Q? 12kkR R R R?
容易得到 是 Ak的一个 QR分解
k k kA Q R?
如果 A是一个满秩的上 Hessenberg矩阵，可以证明，经过一个 QR迭代步得到的
A2＝ Q－１ １ A1Q１ 仍然是上 Hessenberg矩阵,
因为上 Hessenberg矩阵次对角线以下的元素全为 0，因此，只要证明，当 k→∞ 时，由迭 代格式 (4)产生的矩阵 Ak的次对角元趋向于零就可以了,
二,QR算法的收敛性
定理 9.7.3 设 n阶矩阵 A的 n个特征值满足
|λ１ |>|λ２ |>…>|λ n|>0，其相应的 n个线性无关特征向量为 x1,x2,…,xn.
记 X＝ (x1,x2,…,x n),Y= X－１,如果 Y存在
LU分解，那么，由 (4) 式产生的矩阵 Ak基本收敛于上三角矩阵 R.这里，基本收敛的含义指｛ Ak｝的元素中除对角线以下的元素趋于零外，可以不收敛于 R的元素,
三,QR算法的迭代过程
1,一个 QR迭代步的计算
①对 l=1,2,…,n-1，构造 n-1个平面旋转矩阵 Pl,l+1,使 A1的次对角元全部零化，实现 A1
的 QR分解的计算，
这里,
,1,1
,1,1 1,1,
,1,2,l l l l l l l j
l l l l l l l l
c s a a
j l l n
s c a a
1,
,1,12 2 2 2
1,1,
,lllll l l l
l l l l l l l l
aa
cs
a a a a
22
1,l l l lr a a
②用 Pl,l+1右乘 (24)，所得结果也放回矩阵 A相应的元素中,
,1,1
,,1,1
,1,1
(,) (,),
1,2,,1
l l l l
i l i l i l i l
l l l l
cs
a a a a
sc
il
2,QR算法的迭代控制
当迭代步数 k充分大时，由迭代格式 (4)产生的 Ak的次对角元趋于 0.在 实 际计算中，控制迭代次数常用的一种办法是，预先给定一个小的正数 ε，在一个迭代步的计 算结束后，对 l=n-1,n-2,…,1，依次判别次对角元的绝对值是否满足 或更严格的准则是 或不太严格的准则是如果上面三个不等式中有一个成立，
把 看做实际上为零,
1,llaA
1,1,1m in {,}l l ll l la a a
1,1,1{}l l ll l la a a
1,lla?
9.7.4 带原点位移的ＱＲ算法
由ＱＲ算法收敛性证明可以看出，ＱＲ
算法的收敛速度 依赖于矩阵相邻特征值的比 值,为了加快算法的收敛速度，在迭代过程中，对矩阵 Ak确定一个原点位移量 sk，称 Ak-skI为带原点位移量的矩阵，
再对 Ak-skI应用ＱＲ算法,这时，迭代格式改为称为带原点位移的 QR算法
1,k k k k k k k kA s I Q R A R Q s I
计算特征值问题的 QR方法，实际上总是分成 2个阶段：
一般矩阵 上 Hessenberg矩阵 上三角矩阵对称矩阵 三对角矩阵 对角矩阵
9.5.1 求 按模最大特征值和特征向量的乘幂法
设 A是 n阶矩阵，其 n个特征值按模从大到小排序为
1 2 3 n
又假设关于 λ1,λ2,…,λn的特征向量
v1,v2,…,vn线性无关,
任意取定初始向量 x0
0 1 1 2 2 1( 0 )nnx a v a v a v a
1 0 1 1 2 2
1 1 1 2 2 2
nn
n n n
x A x a A v a A v a A v
a v a v a v
2 2 2 22 1 0 1 1 1 2 2 2 n n nx Ax A x a v a v a v
…………..
建立迭代公式,1kkx A x
因为
),,3,2(1
1
nii
故当 k→∞ 时,xk→λ 1ka1v1.
因此,xk可看成是关于特征值 λ1的近似特征向量有一严重缺点，当 |?1|>1 （或 |?1 |<1时） {Vk}中不为零的分量将随 K的增大而无限增大，计算机就可能出现上溢（或随 K的增大而很快出现下溢）
1 0 1 1 1 2 2 2
2
1 1 1 2 2
11
[ ( ) ( ) ]
k k k k
k k n n n
k k kn
n
x A x A x a v a v a v
a v a v v
因此，在实际计算时，须按规范法计算，
每步先对向量 xk进行“规范化”。迭代格式改为
1,0,1,
k
k
k
kk
x
z
x
x A z k
对任意给定的初始向量 x0
类似地
01
1 0 1
10
,
|| || || ||
Azxx A z z
x A z
0
0 1 1 2 2
0
nn
x
z b v b v b v
x
0
0| | | |
k
k k
Az
z
Az?
当?1>0时
2
1 1 2 2
1 1 1
21
1 1 2 2
11
( ) ( )
||
|| ( ) ( ) ||
kk n
nnk
k k
kk n
nn
b v b v b v
z
b v b v b v
1
1
1
||
k
k
11
11| | | |
k
bv
z
bv?
11
11| | | |
k
bvz
bv?
当?1<0时
1
1
1
||
k
k
按模最大特征值 λ1及其相应的特征向量 v1
的乘幂法的计算公式：
1
1 1
1
,
0,1,
k
k
k
kk
TT
k k k k k
TT
k k k k
x
z
x
x Az
z x z Az
z z z z
k
9.7 QR方法
QR方法在特征值计算问题的发展上具有里程碑意义。在 1955年的时候人们还觉得特征值的计算是十分困扰的问题，到
1965年它的计算 —— 基于 QR方法的程序已经完全成熟。直到今天 QR方法仍然是特征值计算的有效方法之一。
9.7.1 两个基本定理定理 9.7.1 设 A是 n阶矩阵，其 n个 特征值为,那么存在一个酉矩阵 U，使
UＨ AU是以为 对角元的上三角矩阵,
12,,,n
12,,,n
定理 9.7.2 设 A是 n阶实矩 阵，那么，存在一个正交矩阵 Q，使 QＴ AQ为一个准上三角矩阵，
它的对角元是 A的一个特征值，对角元上的二阶块矩阵的两个特征值是 A的一对共轭复特征值,
9.7.2 相似约化为上 Hessenberg矩阵对一般 n阶矩阵,QR算法的每一个迭代步需要
O(n３ )次乘法运算,如果矩阵阶数稍大，这个算法几乎没有实际的应用价值,
通常采用的方法是先将矩阵相似约化为上
Hessenberg形式的矩阵，在此基础上应用 QR
迭代,这时，一个 QR迭代步的乘法运算次数只需 O(n２ ）次,
所谓上 Hessenberg矩阵是指一个 n阶矩阵 A，如果当 i>j+1时,aij=0，称 A为上 Hessenberg矩阵,例如：一个 5阶的上 Hessenberg矩阵具有如下的形式：
* * * * *
* * * * *
0 * * * *
0 0 * * *
0 0 0 * *
A
下面介绍 QR方法时，都假设矩阵 A是一个上 Hessenberg矩阵,
9.7.3 QR算法
设 A是 n阶矩阵且有 QR分解 A＝ QR,(2)
这里,Q是酉矩阵,R是上三角矩阵,如果 A
是满秩并规定 R有正对角元，这个分解是惟一的,
设 A是 n阶矩阵且有 QR分解 A＝ QR，
这里,Q是酉矩阵,R是上三角矩阵,如果 A是满秩并规定 R有正对角元，这个分解是惟一的,
QR方法是 1961年由作者 J.G.F.Francis和
V.N.Kublanovskaya设计的
QR分解是 QR算法的基础一,QR算法的基本思想
记 A＝ A１ 且有 A１ ＝ Q 1R1.将等号右边两个矩阵因子的次序交换，得 A２ ＝ R１ Q１,且
,(3) 即 A２ ～ A１,
不难证明,
即 Ak+1～ Ak～ … ～ A１,矩阵序列｛ Ak｝有相同的特征值,
记
12 1 1 1A Q A Q
1 1 11 1 1k k k k k k kA Q A Q Q Q A Q Q
12kkQ Q Q Q? 12kkR R R R?
容易得到 是 Ak的一个 QR分解
k k kA Q R?
如果 A是一个满秩的上 Hessenberg矩阵，可以证明，经过一个 QR迭代步得到的
A2＝ Q－１ １ A1Q１ 仍然是上 Hessenberg矩阵,
因为上 Hessenberg矩阵次对角线以下的元素全为 0，因此，只要证明，当 k→∞ 时，由迭 代格式 (4)产生的矩阵 Ak的次对角元趋向于零就可以了,
二,QR算法的收敛性
定理 9.7.3 设 n阶矩阵 A的 n个特征值满足
|λ１ |>|λ２ |>…>|λ n|>0，其相应的 n个线性无关特征向量为 x1,x2,…,xn.
记 X＝ (x1,x2,…,x n),Y= X－１,如果 Y存在
LU分解，那么，由 (4) 式产生的矩阵 Ak基本收敛于上三角矩阵 R.这里，基本收敛的含义指｛ Ak｝的元素中除对角线以下的元素趋于零外，可以不收敛于 R的元素,
三,QR算法的迭代过程
1,一个 QR迭代步的计算
①对 l=1,2,…,n-1，构造 n-1个平面旋转矩阵 Pl,l+1,使 A1的次对角元全部零化，实现 A1
的 QR分解的计算，
这里,
,1,1
,1,1 1,1,
,1,2,l l l l l l l j
l l l l l l l l
c s a a
j l l n
s c a a
1,
,1,12 2 2 2
1,1,
,lllll l l l
l l l l l l l l
aa
cs
a a a a
22
1,l l l lr a a
②用 Pl,l+1右乘 (24)，所得结果也放回矩阵 A相应的元素中,
,1,1
,,1,1
,1,1
(,) (,),
1,2,,1
l l l l
i l i l i l i l
l l l l
cs
a a a a
sc
il
2,QR算法的迭代控制
当迭代步数 k充分大时，由迭代格式 (4)产生的 Ak的次对角元趋于 0.在 实 际计算中，控制迭代次数常用的一种办法是，预先给定一个小的正数 ε，在一个迭代步的计 算结束后，对 l=n-1,n-2,…,1，依次判别次对角元的绝对值是否满足 或更严格的准则是 或不太严格的准则是如果上面三个不等式中有一个成立，
把 看做实际上为零,
1,llaA
1,1,1m in {,}l l ll l la a a
1,1,1{}l l ll l la a a
1,lla?
9.7.4 带原点位移的ＱＲ算法
由ＱＲ算法收敛性证明可以看出，ＱＲ
算法的收敛速度 依赖于矩阵相邻特征值的比 值,为了加快算法的收敛速度，在迭代过程中，对矩阵 Ak确定一个原点位移量 sk，称 Ak-skI为带原点位移量的矩阵，
再对 Ak-skI应用ＱＲ算法,这时，迭代格式改为称为带原点位移的 QR算法
1,k k k k k k k kA s I Q R A R Q s I
计算特征值问题的 QR方法，实际上总是分成 2个阶段：
一般矩阵 上 Hessenberg矩阵 上三角矩阵对称矩阵 三对角矩阵 对角矩阵
