矩阵的正交三角化及应用

1、矩阵的正交三角化及应用 本节介绍初等反射阵及平面旋转阵，矩阵正交约本节介绍初等反射阵及平面旋转阵，矩阵正交约化，它们在矩阵计算中起着重要作用化，它们在矩阵计算中起着重要作用.5.7.1 初等反射阵 定义定义9 设向量设向量w Rn且且wTw=1，称矩阵，称矩阵H(w)=I- -2wwT为为初等反射阵初等反射阵(或称为或称为豪斯霍尔德豪斯霍尔德(Householder)变换变换).如果记如果记w =(w1,w2,wn)，则，则.212222122221)(2212221212121 nnnnnwwwwwwwwwwwwwwwwH 定理定理25 设有初等反射阵设有初等反射阵H(w)=I- -2wwT

2、, 其中其中wTw=1, 则则 (1) H是对称矩阵是对称矩阵, 即即HT=H. (2) H是正交矩阵是正交矩阵, 即即H- -1=H. (3) 设设A为对称矩阵为对称矩阵, 那么那么A1=H- -1AH=HAH亦是对亦是对称矩阵称矩阵. 证明证明 只证只证H的正交性的正交性, 其它显然其它显然.)(44)2)(2(2IwwwwwwIwwIwwIHHHTTTTTT 设向量设向量u0, 则显然则显然 是一个初等反射阵是一个初等反射阵.222uuuIHT 定理定理26 设设x, y为两个不相等的为两个不相等的n维向量维向量, |x|2=|y|2, 则存在一个初等反射阵则存在一个初等反射阵H, 使使

3、Hx=y. 2yxyxw 证明证明 令令 , 则得到一个初等反射阵则得到一个初等反射阵而且而且),(2222TTTyxyxyxIwwIH .)(2)(22222yxxyxxyxxxyxyxyxxHxTTTT 由由|x|2=|y|2, 有有yTy=xTx, 而数而数xTy=yTx, 从而从而所以得所以得 Hx=x- -(x- -y)=y .22() ()2(),TTTxyxyxyx xy x 容易说明容易说明, w是使是使Hx=y成立的唯一长度等于成立的唯一长度等于1的向的向量量(不计符号不计符号). 定理定理27(约化定理约化定理) 设设x=(x1,x2,xn)T0, 则存在则存在初等反射阵初

4、等反射阵H, 使使Hx=- -e1, 其中其中 ).(21,)sgn(,1221211xuexuxxuuIHT 5.7.2 平面旋转阵 设设x, y R2, 则变换则变换Pxyxxyy 或或,cossinsincos2121 是平面上向量的一个旋转变换，其中是平面上向量的一个旋转变换，其中 cossinsincos)(P为正交矩阵为正交矩阵. Rn中变换：中变换：y=Px，称为称为Rn中平面中平面xi, xj的的旋转变换旋转变换(或称为或称为吉文斯吉文斯(Givens)变换变换)，P=P(i,j,)=P(i,j)称为称为平面旋转矩阵平面旋转矩阵.其中其中x=(x1,x2,xn)T, y=(y1

5、,y2,yn)T, 使而使而jijiPP 11cossin11sincos11),( 显然，显然，P(i, j,)具有性质：具有性质： (1) P与单位阵与单位阵I只是在只是在(i, i), (i, j), (j, i) , (j, j)位置元位置元素不一样，其它相同素不一样，其它相同. (2) P为正交矩阵为正交矩阵(P- -1=PT). (3) P(i, j)A(左乘左乘)只需计算只需计算第第i行行与与第第j行行元素，即元素，即对对A=(aij)mn有有)., 2 , 1(nlaacsscaajliljlil 其中，其中，c=cos，s=sin. (4) AP(i, j)(右乘右乘)只需计

6、算只需计算第第i列列与与第第j列列元素，即元素，即)., 2 , 1(),(),(mlcsscaaaaljliljli 利用平面旋转变换，可使向量利用平面旋转变换，可使向量x中的指定元素变为零中的指定元素变为零. 定理定理28(约化定理约化定理) 设设x=(x1,xi , xj , xn)T, 其其中中xi, xj不全为零，则可选择平面旋转阵不全为零，则可选择平面旋转阵P(i, j,) ，使，使.0,), 0 ,(1个个分分量量是是第第jxxxPxTni 其中其中)./arctan(,22ijjiixxxxx ./sin,/cosxxsxxcjii 证明证明 取取 由由 利用矩阵乘利用矩阵乘法

7、，显然有法，显然有,),(),(1TnjixxxxxxjiP ).,(,jikxxcxsxxsxcxxkkjijjii于是，由于是，由c, s的取法得的取法得. 0,22 jjiixxxx5.7.3 矩阵的QR分解 下面讨论用正交矩阵来约化矩阵，可得到下述结果下面讨论用正交矩阵来约化矩阵，可得到下述结果.设有设有 设设A Rmn且为非零矩阵，则存在初等反射矩阵且为非零矩阵，则存在初等反射矩阵H1, H2, , Hs使使).()1(12上上梯梯形形 ssAAHHH ).()(21212222111211)1(按按列列分分块块nmnmmnnaaaaaaaaaaaaAA (1) 第第1步约化：如果步

8、约化：如果a1=0，取，取H1=I，即这一步不，即这一步不需要约化，不妨设需要约化，不妨设a10，于是可选取初等反射阵使，于是可选取初等反射阵使.,111111111eaHuuIHT 于是于是.000)(22221)2()2(2)2(2)2(22)2(1)2(12112111)1(1 DcBraaaaaaaHaHaHAHmnmnnn 其中其中.,),(,)2()1(21)2(2)2(222)2(122 nmmTmRDRaacar (2) 第第k步约化：设已完成对步约化：设已完成对A上述第上述第1步步第第k- -1步的约化，再进行第步的约化，再进行第k步约化步约化. 即存在初等反射阵即存在初等反

9、射阵H1, H2, , Hk- -1使使,)(121kkAAHHH .110)()()()()(1)(11)3(2)3(2)3(122)2(1)2(1)2(11)2(121)( kmkDcBrRaaaaaaaaaaaaaAkkkkkkmnkmkkknkkkknkkkkknkknkkk 其中其中这里这里, Rk为为k- -1阶上三角阵阶上三角阵,),(1)(1)2(1 kTkkkkkRaar.,),()()1(1)()(knkmkkmTkmkkkkkRDRaac 不妨设不妨设ck0, 否则这一步不需要约化否则这一步不需要约化(如果如果A列满秩列满秩, 则则ck0). 于是于是, 可选取可选取初等

10、反射阵初等反射阵使使.,11ecHuuIHkkkTkkkk 令令,111 kmkHIHkkk第第k步约化为步约化为 kkkkkkkkkkkkkkkkkkkDHcHBrRDcBrRHIAAHHHHAH001)1(121)( 令令s=min(m- -1, n), 继续上述过程继续上述过程, 最后有最后有).()1(12上上梯梯形形RAAHHHss 总结上述讨论给出下述结果总结上述讨论给出下述结果. 定理定理29(矩阵的正交约化定理矩阵的正交约化定理) 设设A Rmn且且A0, s=min(m- -1, n), 则存在初等反射阵则存在初等反射阵H1, H2, , Hs使使).(12上上梯梯形形RAH

11、HHs 且计算量约为且计算量约为n2m- -n3/3(当当mn)次乘法运算次乘法运算. (2) 设设A Rnn为非奇异矩阵为非奇异矩阵, 则则A有分解有分解 定理定理30(矩阵的矩阵的QR分解分解) ,012 RAHHHn其中其中R为为n阶非奇异上三角阵阶非奇异上三角阵. (1) 设设A Rmn且且A的秩为的秩为n(mn), 则存在初等反射则存在初等反射阵阵H1, H2, , Hn使使A=QR, 其中其中Q为正交矩阵为正交矩阵, R为上三角阵为上三角阵. 且当且当R具有正对角元具有正对角元素时素时, 分解唯一分解唯一. 证明证明 (1)由定理由定理29可得可得. (2) 由设及定理由设及定理2

12、9存在初等反射阵存在初等反射阵H1, H2, , Hn- -1使使.22211211121RrrrrrrAHHHnnnnn 记记QT=Hn- -1H2H1, 则上式为则上式为QTA=R, 即即 A=QR, 其中其中Q为正交矩阵为正交矩阵, R为上三角阵为上三角阵. 唯一性唯一性, 设有设有A=Q1R1 =Q2R2, 其中其中Q1, Q2为正交矩为正交矩阵阵, R1, R2为非奇异上三角阵为非奇异上三角阵, 且且R1, R2具有正对角元素具有正对角元素,则则.,222222111111RRRQQRAARRRQQRAATTTTTTTT 由假设由假设, 及对称正定矩阵及对称正定矩阵ATA的的Cholesky分解的唯分解的唯一性一性, 则则R1=R2. 从而可得从而可得Q1=Q2. 下面考虑平面旋转变换来约化矩阵下面考虑平面旋转变换来约化矩阵. 定理定理31(用吉文斯变换计算矩阵的用吉