7.3.2 矩阵的 QR分解
定理 7.3.1 设矩阵 nnRA ??,且非奇异，则一定存在正交矩
阵 Q,上三角矩阵 R,使
)2.3.7( QRA ?
且当要求 R 的主对角元素均为正数时，则分解式 ( 7.3,2) 是唯一的。
证明 存在性 有矩阵 A 的非奇异性及 H ouse hol der 变换矩
阵的性质 ( 3) 知，一定可构造
1?n
个 H 矩阵：
121,,,?nHHH ?
使
)1,,2,1( 1 ???? nkAHA kkk ?
其中
AA ?1
,而
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
)(
)(
11
)(
22
)(
1
)(
121
n
nn
n
nnn
n
n
n
n
n
n
a
aσ
aσ
aaσ
A ??
?
?
R
?
?
因此有
RAHHHH
nn
?
?? 1221
?
即有
QRA ?
其中,121 ?
?
n
HHHQ ?
为正交矩阵。
唯一性 假设矩阵 A 有两种正交三角分解，即
2211
RQRQA ??
其中,21
,QQ
为正交矩阵,21
,RR
为上三角矩阵，且
主对角元素均为正数。于是有
DRRQQ
T
?
?
??
1
2121
这里,D 必是既为正交矩阵又是上三角矩阵，故
),,(d i a g
21 n
dddD ??
且
),,2,1(1
2
nid
i
???
，因此,21
DRR ?
，由于 21
,RR
对角元均为正数，故
),,2,1(1 nid
i
???
，即有
2121
,,QQRRID ???
。
例 7,3.2 设矩阵
?
?
?
?
?
?
?
?
?
?
?
5 4 2
1 1 2
1 1 1
-
--A
试作矩阵
QRA ?
分解。
解 为直观起见，下面给出 H 矩 阵形式 。
( 1) 求
1H
，作
AHA 12 ?
。
;3))((s i g n 1 2
13
1
2
1111
?? ?
?i
i
aa?
?
;)2,2,4(,2,4 2 21111 Tuuau ????? ??;1243 3 111 ???? u???
?
?
?
?
?
?
?
?
?
?
???
?
213
122
221
3
1
1
11
--
- -
- --
uuIH
T
?
?4
?
?
?
?
?
?
?
?
?
?
??
3 3 0
3 0 0
3 3 3
12
-
-
--
AHA
( 2) 求
2H
，作
RAHA ?? 223
);1)0(si g n( 3))((si g n 1
2
2
)2(
2
)2(
222
2
??? ?
?
约定
i
i
aa?
?
? ? ;)3,3,0(,3,3,0 2 2
3232
)2(
2221
Tuauauu ????????? ??
;9 3 222 ?? u???
?
?
?
?
?
?
?
?
?
?
???
?
010
100
001
3
1
1
22
uuIH
T
?
?4
R--
--
AHA ?
?
?
?
?
?
?
?
?
?
?
??
3 0 0
3 3 0
3 3 3
223
?
?
?
?
?
?
?
?
?
?
?
??
???
??
1 2 2
2 1 2
2 2 1
3
1
21
HHQ
由矩阵乘法可直接验证
QRA ?
。
7.3.3 QR算法
设
nn
ij RaA
??? )(
,QR 算法是对 A 进行一系列的
正交相似变换，达到求出矩阵 A 的全部特征值和相应的
特征向量。算法如下,
分解：
kkk RQA ?
构造：
,.,,)3,2,1(1 ???? kQRQAQA kkkkTkk
这里 Q
k
为 正交矩阵, R
k
为 上 三角矩阵, 且 当 R
k
主对角
元 均为正数 时, 则 上述 正交三角分解唯一 。
例 7,3.3 设矩阵
?
?
?
?
?
?
?
?
?
?
?
4 1 0
1 2 1
0 1 2
A
试用 QR 算法 ( 7.3,3) 求它的特征值。
解 令
AA ?1
，并对
1A
作 QR 分解得
11
1
2 8 6 3 3 5.3 0 0
4 4 9 4 9 0.2 4 4 9 4 9 0.2 0
4 4 7 2 1 4.0 2 3 6 0 6 8.2 5
9 1 2 8 7 1.0 4 0 8 2 4 8.0 0
3 6 5 1 4 8.0 8 1 6 4 9 7.0 4 4 7 2 1 4.0
1 8 2 5 7 4.0 4 0 8 2 4 8.0 8 9 4 4 2 7.0
RQ
A
?
?
?
?
?
?
?
?
?
?
?
??
???
?
?
?
?
?
?
?
?
?
?
?
???
?
?
于是
,0 0 0 03 3 4 1 6.1 0
3 4 1 6.1, 0 0 0 03, 0 9 5 41
0, 0 9 5 41, 0 0 0 03
112
?
?
?
?
?
?
?
?
?
?
?
??? QRA
同理作
222 QRA ?
，又有
?
?
?
?
?
?
?
?
?
?
??
,7 7 2 71, 9 7 3 80 0
,9 7 3 80, 5 2 1 43, 9 5 5 80
0 9 5 5 8.0, 7 0 5 93
223
QRA
如此下去，可得
?
?
?
?
?
?
?
?
?
?
??
,2 6 8 01, 0 0 4 80 0
,0 0 4 80, 0 0 8 73, 1 2 9 90
0 1299.0, 7 2 3 34
999
QRA
?
?
?
?
?
?
?
?
?
?
???
,2 6 8 01, 0 0 4 80 0
,0 0 2 00, 0 0 3 53, 0 7 8 10
0 0 7 8 1.0, 7 2 8 24
101010
QRA
从
10
A 可以看出，已近似接近对角矩阵，即有特征值
,2680.1,0035.3,7282.4
321
??? ???
与矩阵 A 的三个精确解
2679.133,3,7321.433
321
??????? ???
相比，已有良好精确度。随着迭代次数增加,n
A
将收敛到矩阵
A 的三个精确特征值。
定义 7,3.2 设矩阵
nnijaA ?? )(
，如果对
1?? ji
，均有，
则称矩阵 A 为上 H e ss e n be r g 矩阵，即
( 7, 3, 4 )
1
33332
2232221
1131211
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? nnnn
n
n
n
aa
aaa
aaaa
aaaa
A
???
?
?
?
如果
)1,,2,1(01 ???? nia ii ?
,则 称 矩阵 A 为 不可 约 上
H e ss e n b e r g 阵。
1,约化矩阵 A为上 Hessenberg矩阵
定义 7.3.2 设矩阵
nnijaA ?? )(
，如果对
1?? ji
，均有，则称
矩阵 A 为上 H es se nb er g 矩阵，即
( 7, 3, 4 )
1
33332
2232221
1131211
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? nnnn
n
n
n
aa
aaa
aaaa
aaaa
A
???
?
?
?
如果
)1,,2,1(01 ???? nia ii ?
，则称矩阵 A 为不可约上 H es se nb er g
阵。
算法 7,3,1 约化矩阵 A 为上 H essen b er g 阵。
(1 ) 输入,);,,2,1,( njia
ij
??
(2 ) 对
2,,2,1 ?? nk ?
做
1) 构造初等反射矩阵
T
kkkk
uuIR
1?
?? ?
使;
1
ecR
kkk
???
;))((s i g n 1
2
1
1
2
1 ?
??
?
?
n
ki
ikkkk
aa?
?
2 ? if
kkk a 1???
t hen 做
①
);,,2(;;11 nkjauau jkjkkkk ?????? ?? ?
②;1?? kkk u??
③;1 kka ????
2) 约化计算
?
?
?
?
?
?
??
k
k
kkk
R
I
HAHHA
0
0
,
即计算
k
k
k
k
k
k
k
k
k
R
AR
A
RAR
RA
A
A
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
)(
22
)(
12
)(
22
)(
12
22
12
?1 左变换：
2222 ARA k?
①
);,,1(
1
nkjauv
n
ki
kijij
???? ?
??
?
②
);,,1,( nkjivuaa jiijij ?????
?2 右变换：
k
R
A
A
A
A
?
?
?
?
?
?
??
?
?
?
?
?
22
12
22
12
①
);,,2,1(
1
niuaw
n
kj
kjijj
??? ?
??
?
②
);,,1,( nkjiuwaa jiijij ?????
( 3) 输出：
),,2,1,( njia ij ??
,结束。
? 说明 上述算法对矩阵 A为实对称矩阵约
化为三对角矩阵也实用，如希望减少一
些工作量，则右变换只做 A22Rk→ A22，
即计算 即可。
),.,,2,1( njw j ?
例 7,3.4 设矩阵
?
?
?
?
?
?
?
?
?
?
?
?
??
?
??
?
6 2 4 2
1 4 3 1
3 1 6 2
2 2 1 5
A
试用初等反射矩阵作正交相似变换，约化为上 H ess enb erg
矩阵。
解 1?k
(1) 构造初等反射矩阵
TuuIR
11
1
11
??? ?
使
。1111 ecR ???
1)
。3)21)2)((1())((s i g n 2
1
2222
14
2
2
1211
???????? ?
?i
i
aa?
2)
5321212 ??????? ?au
，
。Tu )2,1,5( ??
。15)5()3(111 ?????? u??
3)
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
0
0
3
,
11 2 10
2 14 5
10 5 10
15
1
1111
1
11
CRuuIR
T
?
（ 2 ） 约化计算
11 AHHA ?
，即
1
221
12
22
12
R
AR
A
A
A
?
?
?
?
?
?
?
?
???
?
?
?
?
?
?
1) 左变换：
22122 ARA ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
89 04 10
11 55 08
52 10 85
15
1
6 2 4
1 4 3
3 1 6
11 2 10
2 14 5
10 5 10
15
1
22122
ARA
2) 右变换：
1
22
12
22
12
R
A
A
A
A
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
2581 706 806
695 1921 635
595 335 1501
204 354 003
15
1
11 2 10
2 14 5
10 5 10
98 40 10
11 55 80
25 01 85
30 03 15
15
1
2
1
22
12
22
12
R
A
A
A
A
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
?
222
1211
11
9 5 1 1 1 1 1 1.5 1 3 7 7 7 7 7 8.3 0 2 2 2 2 2 2 2.3 0
5 2 8 8 8 8 8 9.2 2 9 7 7 7 7 7 8.5 8 2 2 2 2 2 2 2.2 0
6 4 4 4 4 4 4 4.2 4 8 8 8 8 8 8 9.1 1 1 1 1 1 1 1 1.5 3
9 6 6 6 6 6 6 7.1 1, 9 3 3 3 3 3 3 3 3 3 3 3 3 3 3.1 5
Ac
AA
AHHA
2?k
( 1) 构造
TuuIR
22
1
22
??? ?
使
2222 ecR ???
1)
1 3 5 0 6 5 3 4 8.4))((s i g n 2
14
3
2
2322
??? ?
?i
i
aa?
2)
85728757.62323 ???? ?au
T)0 2 2 2 2 2 2 2 2.3,9 5 7 2 8 7 5 7.6( ??u
7 6 8 8 3 8 7 5.28322 ?? u??
3)
??
?
?
??
?
? ?
??? ?
6 8 2 5 0 9 7 0 2.0 7 3 0 8 7 6 5 3 2.0
7 3 0 8 7 6 5 3 2.0 6 8 2 5 0 9 7 0 2.0
22
1
22
TuuIR ?
( 2) 约化计算
22 AHHA ?
，即
2
222
12
22
12
R
AR
A
A
A
?
?
?
?
?
?
??
?
?
?
?
?
1) 变换：
22222 ARA ?
?
?
?
?
?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
??
,6 6 4 2 9 3 1 2 55, 7 3 0 4 5 7 6 71
,3 6 0 4 2 0 6 9 72 9 0 9 1 1 2 8 7 3.5
9 5 1 1 1 1 1 1.5 1 3 7 7 7 7 7 8.3
5 2 8 8 8 8 8 9.2 2 9 7 7 7 7 7 8.5
6 8 2 5 0 9 7 0 2.0 7 3 0 8 7 6 5 3 2.0
7 3 0 8 7 6 5 3 2.0 6 8 2 5 0 9 7 0 2.0
22222
ARA
2) 右变换：
2
22
12
22
12
R
A
A
A
A
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
,1 3 0 6 8 5 9 1 85, 9 5 8 8 4 4 7 82
52, 7 0 7 8 2 1 8 9 7 5 8 2 0 2 9 5 9.5
8 9 3 0 5 2 9 4.2 9 1 6 5 8 1 2 7.0
42, 6 8 7 0 4 6 0 7 30, 0 4 4 7 5 4 1 0
6 8 2 5 0 9 7 0 2.0 7 3 0 8 7 6 5 3 2.0
7 3 0 8 7 6 5 3 2.0 6 8 2 5 0 9 7 0 2.0
,6 6 4 2 9 3 1 2 55, 7 3 0 4 5 7 6 71
,3 6 0 4 2 0 6 9 72 9 0 9 1 1 2 8 7 3.5
6 4 4 4 4 4 4 4.2 4 8 8 8 8 8 8 9.1
9 6 6 6 6 6 6 7.1 1, 9 3 3 3 3 3 3 3
2
22
12
22
12
R
A
A
A
A
最后有
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
1 3 0 6 8 5 9 1 8.5 9 5 8 8 4 4 7 8.2 0 0
7 0 7 8 2 1 8 9 5.2 7 5 8 2 0 2 9 5 9.5 1 3 5 0 6 5 3 4 8.4 0
8 9 3 0 5 2 8 4.2 9 1 6 5 8 1 2 7.0 1 1 1 1 1 1 1 1 1.5 3
6 8 7 0 4 6 0 7 4.2 0 4 4 7 8 4 1 0 3.0 3 3 3 3 3 3 3 3 3.1 5
22
AHHA
2,上 Hessenberg矩阵的单步 QR算法
设上 H e ss e n be r g 矩阵形如式（ 7.3.4 ），即
1
33332
2232221
1131211
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? nnnn
n
n
n
aa
aaa
aaaa
aaaa
A
???
?
?
?
采用 J a c o bi 旋转变换对 A 作 QR 分解。另 p= I,q= i + 1,用
),1,( iiiJ ??
左乘 A,即
)5.3.7()1,...,2,1(),1,( ???? niAiiJA
i
?
取
2
1
22
1
2
1
c o s,si n
iiii
ii
i
iiii
ii
i
aa
a
aa
a
??
?
?
?
?
? ??
这样我们有
1121 ),2,1(),...,,1,2(),,1( RAJnnJnnJ ii ???? ?? ???
即
11 RQA ?
其中
),,1(),,,,2,1( 111 ??? nTT nnJJQ ??
于是令
)1,.,,,2,1)(,1,(1112 ????? niiiJRQRA iT ?
则
)7.3.7)(1,.,.,2,1)(,1,(,~ 112 ????? niiiJRAAAA iT ?即
上述过程反复若干次，直到收敛为止。
为加速收敛，常采用平移方法。
设第 k 次迭代平移量为
k?
，则 QR 算法为,
分解：
kkkk RQIA ?? ?
构造：
IQRQAQA kkkkkTkk ????? 1
平移量
k?
选取应满足
||...|||| k2211 k?????? ??????
这时收敛速度依赖于因子
k
kj
kj
nj
C
??
??
?
?
?
?
???
1
11
m a x
算法 7.3.2 上 H es se nber g 矩阵带平移量的单步 QR 算法。
( 1) 输入：
);0,1(),,,2,1,( ???? ijij ajinjia 时当??
( 2) 计算：;1;m a x
1
1
?? ?
?
??
?
kaA
n
j
ij
ni
( 3);nnk a??
( 4) 分解：
kkkk RQIA ?? ?
1)
);,,2,1( niaa kiiii ???? ?
2) 对
ni,,2,1 ??
做;; 1
2
1
2
1
2
1
2
iiii
ii
i
iiii
ii
i
aa
a
s
aa
a
c
?
?
?
?
?
?
?
?
?2 对
niij,,1,???
做;
11 ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?? ji
ij
ii
ii
ji
ij
a
a
cs
sc
a
a
（ 5 ） 构造
IQRA kkkk ???? 1
1) 对
1,,2,1 ?? ni ?
，
1,,2,1 ?? il ?
做;
)1,()1,( ?
?
?
?
?
? ?
???
ii
ii
lililili
cs
sc
aaaa
2)
);,,2,1( niaa kiiii ???? ?
( 6) i f
?
?? Aa nn ?1
t hen 输出
nna
el se
1?? kk
,返回 ( 3) ；
( 7);1?? nn
if
2?n
t hen 返回 ( 3) el se 输出
11a
，停止计算。
例 7,3.5 试用带平移量的单步 QR 算法，计算
?
?
?
?
?
?
?
?
?
?
??
3 1 0
1 1 2
0 2 1
A
的全 部 特征值 。
解
1?k
，取
3331 ?? a?
，则
?
?
?
?
?
?
?
?
?
?
?
?
???
0 1 0
1 4 2
0 2 2
11
1
~
IAA ?
( 1) 确定
),2,1( 1?J
，并计算
11 ),2,1( AJ ?
2
2
,
2
2
,22
21
1
11
1
2
21
2
11
????????
v
a
s
v
a
caav
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
??
1 0 0
0
2
2
2
2
0
2
2
2
2
1 0 0
0
0
),2,1(
1 ii
ii
cs
sc
J ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
1 0 0
0
2
2
2
2
0
2
2
2
2
),2,1(
1
?J
( 2) 确定
),3,2( 2?J
，计算
1
~
12 ),2,1(),3,2( AJJ ??
3
3
,
3
6
,3
32
2
22
2
2
32
2
22
???????
v
a
s
v
a
caav
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
3
6
3
3
0
3
3
3
6
0
0 0 1
0
0
0 0 1
),3,2(
22
222
cs
scJ ?
1112
6
6
0 0
3
3
3 0
2
2
23
2
2
),2,1(),3,2( RAJJ
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
???
（ 3 ） 构造
IQRA k??? 112
,即
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
3
10
6
2
0
6
2
3
5
2
6
0
2
6
2
),3,2(),2,1(
2112
IJJRA
k
TT
???
2?k
，取
3
10
332
?? a?
，则
?
?
?
?
?
?
?
?
?
?
?
?
???
0 0, 2 3 5 7 0 2 0
0, 2 3 5 7 0 2 6 6 6 6 6 7.1 1, 2 2 4 7 4 5
0 1, 0 0 4 7 4 5 3 3 3 3 3 3.5
22
1
~
IAA ?
类似上述
1?k
时的计算过程可得
?
?
?
?
?
?
?
?
?
? ?
?
3, 3 7 2 2 4 8 0, 0 0 6 7 9 3 0
0, 0 0 6 7 9 3, 9 7 8 4 0 01 0, 3 0 6 7 8 0
0 0, 3 0 6 7 8 0 3 5 0 6 5 1.2
3
A
3?k
，取
3 7 2 2 4 8.3333 ?? a?
，同理可算得
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
3, 3 7 2 2 8 2 101, 6 5 0
101, 6 5, 9 9 8 7 5 81 0, 0 7 3 6 2 6
0 0, 0 7 3 6 2 6 3 7 1 0 4 3.2
7
7
4
A
由于
?
??
???? Aa
57
32
10
2
1
101, 6 5
，故取
372282.31 ??
。
对
4
A 进行收缩，即划去第三行，第三列得
?
?
?
?
?
? ?
?
,9 9 8 7 5 81 0, 0 7 3 6 2 6
0, 0 7 3 6 2 6 3 7 1 0 4 3.2
4
~
A
取
9 9 8 7 5 8.1
444
?? a?
，则
?
?
?
?
?
? ?
???
0 0, 0 7 3 6 2 6
0, 0 7 3 6 2 6 3 6 9 8 0 1.4
4
~
4
~
i
AA ?
同上方式计算可得
?
?
?
?
?
?
?
??
?
,9 9 9 9 9 91 0, 0 0 0 0 2 1
0, 0 0 0 0 2 1 3 7 2 2 8 3.2
5
A
由
5A
可知，
21a
已足够小，故可取
3 7 2 2 8 3.2,9 9 9 9 9 9.1 32 ??? ??
与本题精确解
3 7 2 2 8 1 3 2.2)331(
2
1
2
3 7 2 2 8 1 3 2.3)331(
2
1
3
2
1
????
?
???
?
?
?
相比，带平移的 QR 算法以较快的敛速达到满意精度。
*3,上 Hessenberg矩阵双步 QR算法
单步带平移的 QR 算法，当出现复平移时，整个 QR
算法将在复数域内进行，为了避免复分解运算，我们按以下
三步完成。
（ 1 ） 计算 M =A
2
- s A +tI
（ 2 ） 作分解 M = Q R
（ 3 ） 令 A 2=Q
T
AQ
由于上述工作隐藏了双步 QR 分解，而在实数域内进
行，因此，又称双步隐式 QR 变换。
定理 7.3.2 设
UQ,
均 是 正 交 矩 阵, 且
21,AAUUAAQQ
TT ??
，而
21,AA
均为不可约上
H es se n ber g 矩阵，如果 Q 与 U 第一列相同，则
1A
与
2A
“本
质与相同”，即
DADA 112 ??
，其中
)1,,1,1(d i a g ???? ?D
。
根据定理 7,3.1 我们将双步隐式 QR 算法改进如下,
( 1) 计算 M 的第一列 Me
1
( 2) 确定 H o u s e ho l d e r 矩阵 H
0
,使
1111110 )( QereMeH ??? ?
( 3) 确定 H o u s e ho l d e r 矩阵 H
1
,H
2
,…,H
n - 2
,将矩阵 H
0
AH
0
约化
为上 H e s s e n be r g 矩阵，即
~
222100122,..)(..,AHHHAHHHHH nn ???
若记
210
~
..,?? nHHHQ
，上式即为
AQQ
T~
算法 7.3.3 双步隐式 QR 算法。
( 1) 输入：上 H es se n ber g 矩阵元素
);3(),,,2,1,( ?? nnjia ij ?
( 2) 计算,;; 111111 nnnnnnnnnnnn aaaataas ?????? ????
;);(;
322131221121
21112112
2
1111
aamsaaa
mtsaaaam
????
????
（ 3 ） 构造正交对称矩阵
0H
，作正交相似变换
00 AHH
记
Tmmmx ),,(
312111?
构造 H ouse h ol der 矩阵
0R
,
使
10 exR ??
，即;)(si g n 23122121111 mmmm ????
;;; 313212111 mumumu ???? ?
;);( 1011 TuuIRm ????? ????
令
)4,m i n ( np ?
计算
左变换：
);:1,3:1(*):1,3:1( 0 nARnA ?
右变换：;*)3:1,:1()3:1,:1( 0RpApA ?
( 4) 构造对称正交矩阵
,,,221 ?nHHH ?
约化矩阵 A 为上
H es se n b e rg 矩 阵
对于
2,,2,1 ?? nj ?
做
令
);,:1();,1m i n ();,3m i n ( jpjAxnpqnjp ??????
构造 H ous ehol der 矩阵 33 ?? RR,使
1eRx ???
，进而计算
左变换：
);:,:1(*):,:1( njpjARnjpjA ???
右变换：;*):1,:1():1,:1( RpjqApjqA ???
( 5) 收敛性判别,
1) if
??? 1nna
t hen 输出特征值近似解
nna
且
1?? nn
转 ( 6) ；
2) if
???? 21 nna
t hen 输出二阶矩阵
?
?
?
?
?
?
?
?
???
nnnn
nnnn
aa
aa
G
1
111
所对应的
特征值
21,??
，且;2?? nn
（ 6 ） i f
3?n
t hen 返回 ( 2)
el se i f
1?n
t hen 输出
11a
i f
2?n
t hen 输出
?
?
?
?
?
?
?
2221
1211
aa
aa
G
对应的特征值
21,??
，停止计算。
定理 7.3.1 设矩阵 nnRA ??,且非奇异，则一定存在正交矩
阵 Q,上三角矩阵 R,使
)2.3.7( QRA ?
且当要求 R 的主对角元素均为正数时，则分解式 ( 7.3,2) 是唯一的。
证明 存在性 有矩阵 A 的非奇异性及 H ouse hol der 变换矩
阵的性质 ( 3) 知，一定可构造
1?n
个 H 矩阵：
121,,,?nHHH ?
使
)1,,2,1( 1 ???? nkAHA kkk ?
其中
AA ?1
,而
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
)(
)(
11
)(
22
)(
1
)(
121
n
nn
n
nnn
n
n
n
n
n
n
a
aσ
aσ
aaσ
A ??
?
?
R
?
?
因此有
RAHHHH
nn
?
?? 1221
?
即有
QRA ?
其中,121 ?
?
n
HHHQ ?
为正交矩阵。
唯一性 假设矩阵 A 有两种正交三角分解，即
2211
RQRQA ??
其中,21
为正交矩阵,21
,RR
为上三角矩阵，且
主对角元素均为正数。于是有
DRRQQ
T
?
?
??
1
2121
这里,D 必是既为正交矩阵又是上三角矩阵，故
),,(d i a g
21 n
dddD ??
且
),,2,1(1
2
nid
i
???
，因此,21
DRR ?
，由于 21
,RR
对角元均为正数，故
),,2,1(1 nid
i
???
，即有
2121
,,QQRRID ???
。
例 7,3.2 设矩阵
?
?
?
?
?
?
?
?
?
?
?
5 4 2
1 1 2
1 1 1
-
--A
试作矩阵
QRA ?
分解。
解 为直观起见，下面给出 H 矩 阵形式 。
( 1) 求
1H
，作
AHA 12 ?
。
;3))((s i g n 1 2
13
1
2
1111
?? ?
?i
i
aa?
?
;)2,2,4(,2,4 2 21111 Tuuau ????? ??;1243 3 111 ???? u???
?
?
?
?
?
?
?
?
?
?
???
?
213
122
221
3
1
1
11
--
- -
- --
uuIH
T
?
?4
?
?
?
?
?
?
?
?
?
?
??
3 3 0
3 0 0
3 3 3
12
-
-
--
AHA
( 2) 求
2H
，作
RAHA ?? 223
);1)0(si g n( 3))((si g n 1
2
2
)2(
2
)2(
222
2
??? ?
?
约定
i
i
aa?
?
? ? ;)3,3,0(,3,3,0 2 2
3232
)2(
2221
Tuauauu ????????? ??
;9 3 222 ?? u???
?
?
?
?
?
?
?
?
?
?
???
?
010
100
001
3
1
1
22
uuIH
T
?
?4
R--
--
AHA ?
?
?
?
?
?
?
?
?
?
?
??
3 0 0
3 3 0
3 3 3
223
?
?
?
?
?
?
?
?
?
?
?
??
???
??
1 2 2
2 1 2
2 2 1
3
1
21
HHQ
由矩阵乘法可直接验证
QRA ?
。
7.3.3 QR算法
设
nn
ij RaA
??? )(
,QR 算法是对 A 进行一系列的
正交相似变换，达到求出矩阵 A 的全部特征值和相应的
特征向量。算法如下,
分解：
kkk RQA ?
构造：
,.,,)3,2,1(1 ???? kQRQAQA kkkkTkk
这里 Q
k
为 正交矩阵, R
k
为 上 三角矩阵, 且 当 R
k
主对角
元 均为正数 时, 则 上述 正交三角分解唯一 。
例 7,3.3 设矩阵
?
?
?
?
?
?
?
?
?
?
?
4 1 0
1 2 1
0 1 2
A
试用 QR 算法 ( 7.3,3) 求它的特征值。
解 令
AA ?1
，并对
1A
作 QR 分解得
11
1
2 8 6 3 3 5.3 0 0
4 4 9 4 9 0.2 4 4 9 4 9 0.2 0
4 4 7 2 1 4.0 2 3 6 0 6 8.2 5
9 1 2 8 7 1.0 4 0 8 2 4 8.0 0
3 6 5 1 4 8.0 8 1 6 4 9 7.0 4 4 7 2 1 4.0
1 8 2 5 7 4.0 4 0 8 2 4 8.0 8 9 4 4 2 7.0
RQ
A
?
?
?
?
?
?
?
?
?
?
?
??
???
?
?
?
?
?
?
?
?
?
?
?
???
?
?
于是
,0 0 0 03 3 4 1 6.1 0
3 4 1 6.1, 0 0 0 03, 0 9 5 41
0, 0 9 5 41, 0 0 0 03
112
?
?
?
?
?
?
?
?
?
?
?
??? QRA
同理作
222 QRA ?
，又有
?
?
?
?
?
?
?
?
?
?
??
,7 7 2 71, 9 7 3 80 0
,9 7 3 80, 5 2 1 43, 9 5 5 80
0 9 5 5 8.0, 7 0 5 93
223
QRA
如此下去，可得
?
?
?
?
?
?
?
?
?
?
??
,2 6 8 01, 0 0 4 80 0
,0 0 4 80, 0 0 8 73, 1 2 9 90
0 1299.0, 7 2 3 34
999
QRA
?
?
?
?
?
?
?
?
?
?
???
,2 6 8 01, 0 0 4 80 0
,0 0 2 00, 0 0 3 53, 0 7 8 10
0 0 7 8 1.0, 7 2 8 24
101010
QRA
从
10
A 可以看出，已近似接近对角矩阵，即有特征值
,2680.1,0035.3,7282.4
321
??? ???
与矩阵 A 的三个精确解
2679.133,3,7321.433
321
??????? ???
相比，已有良好精确度。随着迭代次数增加,n
A
将收敛到矩阵
A 的三个精确特征值。
定义 7,3.2 设矩阵
nnijaA ?? )(
，如果对
1?? ji
，均有，
则称矩阵 A 为上 H e ss e n be r g 矩阵，即
( 7, 3, 4 )
1
33332
2232221
1131211
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? nnnn
n
n
n
aa
aaa
aaaa
aaaa
A
???
?
?
?
如果
)1,,2,1(01 ???? nia ii ?
,则 称 矩阵 A 为 不可 约 上
H e ss e n b e r g 阵。
1,约化矩阵 A为上 Hessenberg矩阵
定义 7.3.2 设矩阵
nnijaA ?? )(
，如果对
1?? ji
，均有，则称
矩阵 A 为上 H es se nb er g 矩阵，即
( 7, 3, 4 )
1
33332
2232221
1131211
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? nnnn
n
n
n
aa
aaa
aaaa
aaaa
A
???
?
?
?
如果
)1,,2,1(01 ???? nia ii ?
，则称矩阵 A 为不可约上 H es se nb er g
阵。
算法 7,3,1 约化矩阵 A 为上 H essen b er g 阵。
(1 ) 输入,);,,2,1,( njia
ij
??
(2 ) 对
2,,2,1 ?? nk ?
做
1) 构造初等反射矩阵
T
kkkk
uuIR
1?
?? ?
使;
1
ecR
kkk
???
;))((s i g n 1
2
1
1
2
1 ?
??
?
?
n
ki
ikkkk
aa?
?
2 ? if
kkk a 1???
t hen 做
①
);,,2(;;11 nkjauau jkjkkkk ?????? ?? ?
②;1?? kkk u??
③;1 kka ????
2) 约化计算
?
?
?
?
?
?
??
k
k
kkk
R
I
HAHHA
0
0
,
即计算
k
k
k
k
k
k
k
k
k
R
AR
A
RAR
RA
A
A
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
)(
22
)(
12
)(
22
)(
12
22
12
?1 左变换：
2222 ARA k?
①
);,,1(
1
nkjauv
n
ki
kijij
???? ?
??
?
②
);,,1,( nkjivuaa jiijij ?????
?2 右变换：
k
R
A
A
A
A
?
?
?
?
?
?
??
?
?
?
?
?
22
12
22
12
①
);,,2,1(
1
niuaw
n
kj
kjijj
??? ?
??
?
②
);,,1,( nkjiuwaa jiijij ?????
( 3) 输出：
),,2,1,( njia ij ??
,结束。
? 说明 上述算法对矩阵 A为实对称矩阵约
化为三对角矩阵也实用，如希望减少一
些工作量，则右变换只做 A22Rk→ A22，
即计算 即可。
),.,,2,1( njw j ?
例 7,3.4 设矩阵
?
?
?
?
?
?
?
?
?
?
?
?
??
?
??
?
6 2 4 2
1 4 3 1
3 1 6 2
2 2 1 5
A
试用初等反射矩阵作正交相似变换，约化为上 H ess enb erg
矩阵。
解 1?k
(1) 构造初等反射矩阵
TuuIR
11
1
11
??? ?
使
。1111 ecR ???
1)
。3)21)2)((1())((s i g n 2
1
2222
14
2
2
1211
???????? ?
?i
i
aa?
2)
5321212 ??????? ?au
，
。Tu )2,1,5( ??
。15)5()3(111 ?????? u??
3)
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
0
0
3
,
11 2 10
2 14 5
10 5 10
15
1
1111
1
11
CRuuIR
T
?
（ 2 ） 约化计算
11 AHHA ?
，即
1
221
12
22
12
R
AR
A
A
A
?
?
?
?
?
?
?
?
???
?
?
?
?
?
?
1) 左变换：
22122 ARA ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
89 04 10
11 55 08
52 10 85
15
1
6 2 4
1 4 3
3 1 6
11 2 10
2 14 5
10 5 10
15
1
22122
ARA
2) 右变换：
1
22
12
22
12
R
A
A
A
A
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
2581 706 806
695 1921 635
595 335 1501
204 354 003
15
1
11 2 10
2 14 5
10 5 10
98 40 10
11 55 80
25 01 85
30 03 15
15
1
2
1
22
12
22
12
R
A
A
A
A
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
?
222
1211
11
9 5 1 1 1 1 1 1.5 1 3 7 7 7 7 7 8.3 0 2 2 2 2 2 2 2.3 0
5 2 8 8 8 8 8 9.2 2 9 7 7 7 7 7 8.5 8 2 2 2 2 2 2 2.2 0
6 4 4 4 4 4 4 4.2 4 8 8 8 8 8 8 9.1 1 1 1 1 1 1 1 1.5 3
9 6 6 6 6 6 6 7.1 1, 9 3 3 3 3 3 3 3 3 3 3 3 3 3 3.1 5
Ac
AA
AHHA
2?k
( 1) 构造
TuuIR
22
1
22
??? ?
使
2222 ecR ???
1)
1 3 5 0 6 5 3 4 8.4))((s i g n 2
14
3
2
2322
??? ?
?i
i
aa?
2)
85728757.62323 ???? ?au
T)0 2 2 2 2 2 2 2 2.3,9 5 7 2 8 7 5 7.6( ??u
7 6 8 8 3 8 7 5.28322 ?? u??
3)
??
?
?
??
?
? ?
??? ?
6 8 2 5 0 9 7 0 2.0 7 3 0 8 7 6 5 3 2.0
7 3 0 8 7 6 5 3 2.0 6 8 2 5 0 9 7 0 2.0
22
1
22
TuuIR ?
( 2) 约化计算
22 AHHA ?
，即
2
222
12
22
12
R
AR
A
A
A
?
?
?
?
?
?
??
?
?
?
?
?
1) 变换：
22222 ARA ?
?
?
?
?
?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
??
,6 6 4 2 9 3 1 2 55, 7 3 0 4 5 7 6 71
,3 6 0 4 2 0 6 9 72 9 0 9 1 1 2 8 7 3.5
9 5 1 1 1 1 1 1.5 1 3 7 7 7 7 7 8.3
5 2 8 8 8 8 8 9.2 2 9 7 7 7 7 7 8.5
6 8 2 5 0 9 7 0 2.0 7 3 0 8 7 6 5 3 2.0
7 3 0 8 7 6 5 3 2.0 6 8 2 5 0 9 7 0 2.0
22222
ARA
2) 右变换：
2
22
12
22
12
R
A
A
A
A
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
,1 3 0 6 8 5 9 1 85, 9 5 8 8 4 4 7 82
52, 7 0 7 8 2 1 8 9 7 5 8 2 0 2 9 5 9.5
8 9 3 0 5 2 9 4.2 9 1 6 5 8 1 2 7.0
42, 6 8 7 0 4 6 0 7 30, 0 4 4 7 5 4 1 0
6 8 2 5 0 9 7 0 2.0 7 3 0 8 7 6 5 3 2.0
7 3 0 8 7 6 5 3 2.0 6 8 2 5 0 9 7 0 2.0
,6 6 4 2 9 3 1 2 55, 7 3 0 4 5 7 6 71
,3 6 0 4 2 0 6 9 72 9 0 9 1 1 2 8 7 3.5
6 4 4 4 4 4 4 4.2 4 8 8 8 8 8 8 9.1
9 6 6 6 6 6 6 7.1 1, 9 3 3 3 3 3 3 3
2
22
12
22
12
R
A
A
A
A
最后有
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
1 3 0 6 8 5 9 1 8.5 9 5 8 8 4 4 7 8.2 0 0
7 0 7 8 2 1 8 9 5.2 7 5 8 2 0 2 9 5 9.5 1 3 5 0 6 5 3 4 8.4 0
8 9 3 0 5 2 8 4.2 9 1 6 5 8 1 2 7.0 1 1 1 1 1 1 1 1 1.5 3
6 8 7 0 4 6 0 7 4.2 0 4 4 7 8 4 1 0 3.0 3 3 3 3 3 3 3 3 3.1 5
22
AHHA
2,上 Hessenberg矩阵的单步 QR算法
设上 H e ss e n be r g 矩阵形如式（ 7.3.4 ），即
1
33332
2232221
1131211
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? nnnn
n
n
n
aa
aaa
aaaa
aaaa
A
???
?
?
?
采用 J a c o bi 旋转变换对 A 作 QR 分解。另 p= I,q= i + 1,用
),1,( iiiJ ??
左乘 A,即
)5.3.7()1,...,2,1(),1,( ???? niAiiJA
i
?
取
2
1
22
1
2
1
c o s,si n
iiii
ii
i
iiii
ii
i
aa
a
aa
a
??
?
?
?
?
? ??
这样我们有
1121 ),2,1(),...,,1,2(),,1( RAJnnJnnJ ii ???? ?? ???
即
11 RQA ?
其中
),,1(),,,,2,1( 111 ??? nTT nnJJQ ??
于是令
)1,.,,,2,1)(,1,(1112 ????? niiiJRQRA iT ?
则
)7.3.7)(1,.,.,2,1)(,1,(,~ 112 ????? niiiJRAAAA iT ?即
上述过程反复若干次，直到收敛为止。
为加速收敛，常采用平移方法。
设第 k 次迭代平移量为
k?
，则 QR 算法为,
分解：
kkkk RQIA ?? ?
构造：
IQRQAQA kkkkkTkk ????? 1
平移量
k?
选取应满足
||...|||| k2211 k?????? ??????
这时收敛速度依赖于因子
k
kj
kj
nj
C
??
??
?
?
?
?
???
1
11
m a x
算法 7.3.2 上 H es se nber g 矩阵带平移量的单步 QR 算法。
( 1) 输入：
);0,1(),,,2,1,( ???? ijij ajinjia 时当??
( 2) 计算：;1;m a x
1
1
?? ?
?
??
?
kaA
n
j
ij
ni
( 3);nnk a??
( 4) 分解：
kkkk RQIA ?? ?
1)
);,,2,1( niaa kiiii ???? ?
2) 对
ni,,2,1 ??
做;; 1
2
1
2
1
2
1
2
iiii
ii
i
iiii
ii
i
aa
a
s
aa
a
c
?
?
?
?
?
?
?
?
?2 对
niij,,1,???
做;
11 ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?? ji
ij
ii
ii
ji
ij
a
a
cs
sc
a
a
（ 5 ） 构造
IQRA kkkk ???? 1
1) 对
1,,2,1 ?? ni ?
，
1,,2,1 ?? il ?
做;
)1,()1,( ?
?
?
?
?
? ?
???
ii
ii
lililili
cs
sc
aaaa
2)
);,,2,1( niaa kiiii ???? ?
( 6) i f
?
?? Aa nn ?1
t hen 输出
nna
el se
1?? kk
,返回 ( 3) ；
( 7);1?? nn
if
2?n
t hen 返回 ( 3) el se 输出
11a
，停止计算。
例 7,3.5 试用带平移量的单步 QR 算法，计算
?
?
?
?
?
?
?
?
?
?
??
3 1 0
1 1 2
0 2 1
A
的全 部 特征值 。
解
1?k
，取
3331 ?? a?
，则
?
?
?
?
?
?
?
?
?
?
?
?
???
0 1 0
1 4 2
0 2 2
11
1
~
IAA ?
( 1) 确定
),2,1( 1?J
，并计算
11 ),2,1( AJ ?
2
2
,
2
2
,22
21
1
11
1
2
21
2
11
????????
v
a
s
v
a
caav
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
??
1 0 0
0
2
2
2
2
0
2
2
2
2
1 0 0
0
0
),2,1(
1 ii
ii
cs
sc
J ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
1 0 0
0
2
2
2
2
0
2
2
2
2
),2,1(
1
?J
( 2) 确定
),3,2( 2?J
，计算
1
~
12 ),2,1(),3,2( AJJ ??
3
3
,
3
6
,3
32
2
22
2
2
32
2
22
???????
v
a
s
v
a
caav
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
3
6
3
3
0
3
3
3
6
0
0 0 1
0
0
0 0 1
),3,2(
22
222
cs
scJ ?
1112
6
6
0 0
3
3
3 0
2
2
23
2
2
),2,1(),3,2( RAJJ
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
???
（ 3 ） 构造
IQRA k??? 112
,即
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
3
10
6
2
0
6
2
3
5
2
6
0
2
6
2
),3,2(),2,1(
2112
IJJRA
k
TT
???
2?k
，取
3
10
332
?? a?
，则
?
?
?
?
?
?
?
?
?
?
?
?
???
0 0, 2 3 5 7 0 2 0
0, 2 3 5 7 0 2 6 6 6 6 6 7.1 1, 2 2 4 7 4 5
0 1, 0 0 4 7 4 5 3 3 3 3 3 3.5
22
1
~
IAA ?
类似上述
1?k
时的计算过程可得
?
?
?
?
?
?
?
?
?
? ?
?
3, 3 7 2 2 4 8 0, 0 0 6 7 9 3 0
0, 0 0 6 7 9 3, 9 7 8 4 0 01 0, 3 0 6 7 8 0
0 0, 3 0 6 7 8 0 3 5 0 6 5 1.2
3
A
3?k
，取
3 7 2 2 4 8.3333 ?? a?
，同理可算得
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
3, 3 7 2 2 8 2 101, 6 5 0
101, 6 5, 9 9 8 7 5 81 0, 0 7 3 6 2 6
0 0, 0 7 3 6 2 6 3 7 1 0 4 3.2
7
7
4
A
由于
?
??
???? Aa
57
32
10
2
1
101, 6 5
，故取
372282.31 ??
。
对
4
A 进行收缩，即划去第三行，第三列得
?
?
?
?
?
? ?
?
,9 9 8 7 5 81 0, 0 7 3 6 2 6
0, 0 7 3 6 2 6 3 7 1 0 4 3.2
4
~
A
取
9 9 8 7 5 8.1
444
?? a?
，则
?
?
?
?
?
? ?
???
0 0, 0 7 3 6 2 6
0, 0 7 3 6 2 6 3 6 9 8 0 1.4
4
~
4
~
i
AA ?
同上方式计算可得
?
?
?
?
?
?
?
??
?
,9 9 9 9 9 91 0, 0 0 0 0 2 1
0, 0 0 0 0 2 1 3 7 2 2 8 3.2
5
A
由
5A
可知，
21a
已足够小，故可取
3 7 2 2 8 3.2,9 9 9 9 9 9.1 32 ??? ??
与本题精确解
3 7 2 2 8 1 3 2.2)331(
2
1
2
3 7 2 2 8 1 3 2.3)331(
2
1
3
2
1
????
?
???
?
?
?
相比，带平移的 QR 算法以较快的敛速达到满意精度。
*3,上 Hessenberg矩阵双步 QR算法
单步带平移的 QR 算法，当出现复平移时，整个 QR
算法将在复数域内进行，为了避免复分解运算，我们按以下
三步完成。
（ 1 ） 计算 M =A
2
- s A +tI
（ 2 ） 作分解 M = Q R
（ 3 ） 令 A 2=Q
T
AQ
由于上述工作隐藏了双步 QR 分解，而在实数域内进
行，因此，又称双步隐式 QR 变换。
定理 7.3.2 设
UQ,
均 是 正 交 矩 阵, 且
21,AAUUAAQQ
TT ??
，而
21,AA
均为不可约上
H es se n ber g 矩阵，如果 Q 与 U 第一列相同，则
1A
与
2A
“本
质与相同”，即
DADA 112 ??
，其中
)1,,1,1(d i a g ???? ?D
。
根据定理 7,3.1 我们将双步隐式 QR 算法改进如下,
( 1) 计算 M 的第一列 Me
1
( 2) 确定 H o u s e ho l d e r 矩阵 H
0
,使
1111110 )( QereMeH ??? ?
( 3) 确定 H o u s e ho l d e r 矩阵 H
1
,H
2
,…,H
n - 2
,将矩阵 H
0
AH
0
约化
为上 H e s s e n be r g 矩阵，即
~
222100122,..)(..,AHHHAHHHHH nn ???
若记
210
~
..,?? nHHHQ
，上式即为
AQQ
T~
算法 7.3.3 双步隐式 QR 算法。
( 1) 输入：上 H es se n ber g 矩阵元素
);3(),,,2,1,( ?? nnjia ij ?
( 2) 计算,;; 111111 nnnnnnnnnnnn aaaataas ?????? ????
;);(;
322131221121
21112112
2
1111
aamsaaa
mtsaaaam
????
????
（ 3 ） 构造正交对称矩阵
0H
，作正交相似变换
00 AHH
记
Tmmmx ),,(
312111?
构造 H ouse h ol der 矩阵
0R
,
使
10 exR ??
，即;)(si g n 23122121111 mmmm ????
;;; 313212111 mumumu ???? ?
;);( 1011 TuuIRm ????? ????
令
)4,m i n ( np ?
计算
左变换：
);:1,3:1(*):1,3:1( 0 nARnA ?
右变换：;*)3:1,:1()3:1,:1( 0RpApA ?
( 4) 构造对称正交矩阵
,,,221 ?nHHH ?
约化矩阵 A 为上
H es se n b e rg 矩 阵
对于
2,,2,1 ?? nj ?
做
令
);,:1();,1m i n ();,3m i n ( jpjAxnpqnjp ??????
构造 H ous ehol der 矩阵 33 ?? RR,使
1eRx ???
，进而计算
左变换：
);:,:1(*):,:1( njpjARnjpjA ???
右变换：;*):1,:1():1,:1( RpjqApjqA ???
( 5) 收敛性判别,
1) if
??? 1nna
t hen 输出特征值近似解
nna
且
1?? nn
转 ( 6) ；
2) if
???? 21 nna
t hen 输出二阶矩阵
?
?
?
?
?
?
?
?
???
nnnn
nnnn
aa
aa
G
1
111
所对应的
特征值
21,??
，且;2?? nn
（ 6 ） i f
3?n
t hen 返回 ( 2)
el se i f
1?n
t hen 输出
11a
i f
2?n
t hen 输出
?
?
?
?
?
?
?
2221
1211
aa
aa
G
对应的特征值
21,??
，停止计算。
