数值分析讲稿黑白

§3.QR基本QR方法的基本思想是利用矩阵的QR分解通过迭代格式A(kA(k

QkRk

(k1,2,L将AA(1)化成相似的上三角阵（或分块上三角阵），从而求出矩阵A的全部特征值与特征向量。 由AA(1)Q1R1,即Q1AR。于是A(2)R Q 与A相似。同理可得，Ak):A(k2,3,L)。故它们有相同的特征值。不收敛。特别的，如果A是实对称阵，则｛A(k)｝“基A(k)的主对角元（或主对角线子块的特征(A(k )u 设A为n阶非奇异实矩阵，记A[a1,a2 ,an],其 , ,L,a2,a 1 2a2,a

)T(j1,2,L,取ba/

a a, ba

12 2

b,

a2,a2,a2,a1,1a a1, a1a2,a2,a2,a1,1a b

取 b'/

,

一般地取

k ak,i

b'/

(k2,3,Lk则向量组b1,b2,L,bn正交，且即ak ak,b1b1L ak,bk1k

1(k1, 即 , , b k k A[a1a2

,an][b1,b2,a2,

,bn

an, b' b'

an,b O QOb b n

an,b'bn

n 这就是用 it正交化方法对矩阵进行的QR分解 0例:用 it正交化方法对A1 1进行QR分解23 223解:

(2,1,0)T,

(1,2,1)T,

(0,1,2)T因而有b1

(2, ,0)T b'a2 a2,b1b(1,2,1)b

( ,

,5

(3,6,1)T b' ( , )Tb2 b22

63a3 a3, b1 a3, b21,21,2,314

kb3

(b' b'

bkb

akak,bibi

bb'/ 所以Aa1a2,Lan1,2L,bn

a2,

an, b' b'OO

an,b2 MM

35 3566

bb5 5

b b 1515

14

7二 豪尔德(Householder)变w2w2

w2Lw2, 1 2ww n2w 1 HI2wwT 2 12wn为Householder矩阵或反射矩阵。可证其具有以下性质H仅有两个不等的特征值1，其中1是n1重特征值,考虑以w为法向量过原点的超平面SwTxR为任意的数,有Hxw)xw2L1nw2证：HIw2L1nw2H(xw)(I2wwT)(xxw2wwTx2wwTwxw2wxw定理:设xy为Rn)中任意非零向量,

1则存在y2x2Householder矩阵H,使得Hx y2x2x( y证：w y

令HI2wwT 于2xm22

xm 2Hx(I2wwT)xx2

(xTm

yT)y2y2xm2yx2x22yx2x2由2－范数的定义.

xm

2(xx2x

y)T(x 2x=xTx2x

yTx

xTy

x2yTxx2xx22xTx22

yTx

22(xTm

yT)222x2代入上式得Hx 222x2x2上式得Hx x2此定理表明，对任一非零向量x都可以构造一个Householder变换，它将x变成事先给定的单位向量的倍数。特别地取yei则x经过Householder变换后可变成只有一个分量不为零。实际计算时，为避免误差取x(

x

esign(xx2esign(xx2esign(xii2

w

xm 三、化一般矩阵为拟上三角称形如 h1n 2n 2nH

h3nMMhnn的矩阵为拟上三角阵，也称为森堡（Hessenberg)阵。如果次对角线元hii1i2,3,Ln)全不为零,则称该矩阵为不可约的上Hessenberg矩阵。讨论用Householder变换将一般矩阵A相似变换成Hessenberg首先，选取矩阵H1使得经H1相似变换后的矩H1H1的第一列中有尽可能多的零元素。为此，应取 0

2nH1为如下形式H1

H

H

h3n

hnnH1n1Householder矩阵。于是有 H AH H

T

其中a1(a21, ,a)T H1A22H1a a2n ( , ,a)T, 13

1 ann由上节定理，只要取H1使得H1a1(1,0, ,0T),就使得变换后的矩阵H1AH1的第一列出现n2个零元。为避免在计算w时会产生较大的误差,a1

esign(a x a1esign(a 212w a1esign(a 212yxmy H1。H1a1同理，可构造如下列形式Householder矩阵

esign(a )a a

H2

使得H2H1AH1H2

H

M

如此进行n2次，可以构造n2个Householder矩阵H1,H2 Hn2使得

Hn2LH2H1AH1H2 Hn

H其中H为上Hessenberg矩阵。特别地，当A为实对称矩阵，则经过上述正交变换后，H变为三对角阵。例:用Householder变换将矩阵A化成拟上三角阵5 2 A

20 00 a1(100

,由H

(1,0,

H

IH

I 2

1为使HouseholderH

满

2

0 0 w

x x

esign(x esign(x

w' 2 2)T2(1, 2

w2)Twww

2 2 )T 2 H2I2ww22 2

222 0222

222 12222

2 2 2

2 2

2 22222

于是有HH2H1AH1H 022 22

0

22 22

22 2

0

22

22

0

0 2

20

22222

3 2 2四、拟上三角矩阵的QR因为拟上三角阵H的特殊形状，通常用n1个旋转变换（又称Givens变换）可将它化成上三角矩阵，从而得到H的QR分解式。具体步骤为 h1n 2n 2nH

h3n设h210(否则进行下一步），

hnn hnn取旋转矩阵，其中r

h h

cos

h11 10cos sin 00r1sinh21r11

sinV21

cos O

1r h(2 h(2 h(2) 2 h(2 h(2 h(2 2 则V21H

(2 (2 33

h(2)3

H(2 Mnn h(2 nn

1 1 其

(h(2))2(h(2)cos2

h h

sin2

V

h(3) r

2nh h

hh

h(3) 4n3n 4nhLhL

h(3) nn (k kk1 h(k h(k h(k h(k)1O 1k O

h(k h(k h(k k k k k1nhh (khh

(k

h(k h(k h(k h(k k

k k1n M h(kh

h(k)(kk1

0 OOVk1

1cos sinsin cos

Oh(k h(k其中cosk

,

sin (h((h(k)) (h(kkkk1)

k1k.于 Vk1k

(k 1 h(k1

h(k

h(k1)O O

1k hk (khk h(k

h(k

(kh hh(k h(k

h(k

k h(k1) k2k

k2n k2n M h(k h(k1) nn H(k因此，最多做n1次旋转变换，即得H(n)

LV h(n) h(n) h(n) r

h(n)

h(n) h(n) HVTVTLVT RQR 其中QVTVTLVT仍为正交矩阵。可算出完成这 可证明HRQ仍是拟上三角阵，于是可按上述 例：用QR方法求矩阵A 4的全部特征值

解：首先将A化成拟上三角阵，取62xxesign(x2ii62xxesign(x2ii2esign(xii2w

(0.957092, w2I2wwT2 02 0.277350

0.832050 于

0.832050 HHAH

2.230767H即为与相似的拟上三角矩阵。将H进行QR分解 1

52cos151 sin52 取

8.597089于是V21再取r2

2.230767(0.438310)2(0.438310)2cos2 0.438310r2sin 0.153846r2

0.943564于是V

8.597089 2.541982

1.471953 QVTVT

H(12)

五、带原点移位的QR方理论分析和实际计算均表明，QR方法产生的矩阵序(k)的右下角对角元素h(k)最先与A的特征值接近。可证明，若矩