1l矩阵的QR分解 Givens矩阵与 Givens变换 定义:设实数c与s满足c2+s2=1,称 (i<j) 为 Givens矩阵(初等旋转矩阵),也记作T=T(,s)。由 Givens矩阵 所确定的线性变换称为 Givens变换(初等旋转变换)。 说明:(1)实数c2+s2=1,故存在θ,使c=cos(6),s=sin()。 (2)y=T1x中T;确定了将向量变成y的一种变换,正是 Givens变 coS(e 换。二阶情况下,y= x确定的正是平面直角坐标系 sin(θ)cos() 中绕原点的一个旋转变换(旋转度)。 (3)以上实 Givens也可推广称为复初等旋转矩阵
11 矩阵的 QR 分解 一．Givens 矩阵与 Givens 变换 1． 定义：设实数 c 与 s 满足 2 2 c s 1 + = ，称 Tij 1 1 c s (i) 1 1 s c (j) 1 1 = − ( i j ) 为 Givens 矩阵（初等旋转矩阵），也记作 T T (c,s) ij ij = 。由 Givens 矩阵 所确定的线性变换称为 Givens 变换（初等旋转变换）。 说明：（1）实数 2 2 c s 1 + = ，故存在 ，使 c cos( ),s sin( ) = = 。 （2） ij y T x = 中 Tij 确定了将向量变成 y 的一种变换，正是 Givens 变 换。二阶情况下， cos( ) sin( ) y x sin( ) cos( ) = − 确定的正是平面直角坐标系 中绕原点的一个旋转变换（旋转 度）。 （3）以上实 Givens 也可推广称为复初等旋转矩阵
j03 (k) 其中c与s仍为满足c2+s2=1的实数,1,02,03,64为实角度。 显然,det(Ui1)=c2ele,+)+s2ee:+0 当日1+04=62+日3时,de(Ui1)=ee+) 当61+64=2+63=2n时,det(Uik)=1 性质 (1)[Tc,)丁=[(s)]=Tc,-,T为正交矩阵。 det [( (2)设x=[5152…5n,y=I=[mmn2…m,则有 mi=csi +s5 -ssi+cs nk=5k(k≠i,j
ik j j 1 2 U j j 3 4 1 1 ce se (i) 1 1 (k) se ce 1 1 = − 其中 c 与 s 仍为满足 2 2 c s 1 + = 的实数， 1 2 3 4 ,,, 为实角度。 显然， 1 4 2 3 2 2 j( ) j( ) det(U ) c e s e ik + + = + 当 1 4 2 3 + = + 时， 1 4 j( ) det(U ) e ik + = 当 1 4 2 3 + = + = 2n 时， det(U ) 1 ik = 2. 性质 （1） 1 T T (c,s) T (c,s) T (c, s) ij ij ij − = = − , Tij 为正交矩阵。 ( ) det T c,s 1 ij = （2）设 T 1 2 n x = ， T ij 1 2 n y T x = = ，则有 i i j j i j k k c s s c (k i, j) = + = − + =
当2+2≠0时,总可以选c=5 5使 十 十 2 0 定理1设x=[512…5n丁≠0,则存在有限个 Givens矩阵的乘积 T,使得Tx=xe1 说明:(1)=2=√xx(为实数时,=√"x(x为复数时) (2)e1=「100 证明lξ1≠0的情形 (1)构造T12(c,s):c 51 十 +E2053 (2)对T12x再考虑T3(c,s):c= +岛+号”+B+ 13112 十 2 十 4 (3)依此类推,构造 十…十 TIk(C,): c +号2+…+2S= +8+… (k=2,3,n hn(n-1(+5++0
当 2 2 i j + 0 时，总可以选 i 2 2 i j c = + ， j 2 2 i j s = + 使 2 2 T i i j 2 2 ij 1 2 i j n j T x 0 0 = + → = + = 定理 1. 设 T 1 2 n x 0 = ，则存在有限个 Givens 矩阵的乘积 T，使得 Tx x e = 1 说明：（1） 2 T 2 x x x x = = (x 为实数时)， H x x x = (x 为复数时）。 （2） T 1 e 1 0 0 0 = [证明]： 1 0 的情形 （1）构造 1 2 12 2 2 2 2 1 2 1 2 T (c,s) :c ,s = = + + T 2 2 T x 0 12 1 2 3 4 n = + （2） 对 T x 12 再考虑 2 2 1 2 3 13 2 2 2 2 2 2 1 2 3 1 2 3 T (c,s) :c ,s + = = + + + + T 222 T T x 0 0 13 12 1 2 3 4 n = + + （3）依此类推，构造 2 2 1 k k 1k 2 2 2 2 2 2 1 2 k 1 2 k T (c,s) :c ,s + + = = + + + + + + (k=2,3,…..n) ( ) T 2 2 2 T T T T T x 0 0 0 1k 1k 1 1k 2 13 12 1 2 k k 1 n − − + = + + +
直至可k=n。令T=TnTn-1T…T12,则有 +十 0 xe 31=0的情形,从第一个不为零的ξ;开始运用上述方法即可 推论:对于任何非零列向量x∈R"及任何单位列向量x(z=1),均存在 着有限个 Givens矩阵的乘积T,使Tx=xz 证明由上述定理,对x存在有限个Gcms矩阵T2,13,…,T的乘 积 )=mTmx1…Tm,使Tx=xe1 对z同理存在有限个 Givens矩阵T2),T3)…,T2)的乘积 (2)(2) n11n-1…113112, 使T(2z=zle XT (2) (2) (1) 即, (1)(1) In In-1 2 其中 (2)T(2) ln1…:1)= T(1) In In I1n-1 2) 2)r(1)r(1 In in-1 为有限个 Givens矩阵的乘积。 二 Householder矩阵与 Householder变换
直至可 k=n。令 T T T T T = 1n 1n 1 12 − ，则有 T 2 2 2 Tx 0 0 0 x e 1 2 n 1 = + + = 1 = 0 的情形, 从第一个不为零的 i 开始运用上述方法即可 推论：对于任何非零列向量 n x R 及任何单位列向量 z( z 1) = ，均存在 着有限个 Givens 矩阵的乘积 T，使 Tx x z = 。 [证明]：由上述定理，对 x 存在有限个 Givens 矩阵 (1) (1) (1) T ,T , ,T 12 13 1n 的乘 积 (1) (1) (1) (1) (1) T T T T T 1n 1n 1 13 12 − = ，使 (1) T x x e = 1 对 z 同理存在有限个 Givens 矩阵 (2) (2) (2) T ,T , ,T 12 13 1n 的乘积 (2) (2) (2) (2) (2) T T T T T 1n 1n 1 13 12 − = ，使 (2) T z z e e = =1 1 即， ( ) ( ) ( ) 1 (1) (2) (2) (2) (1) 1 (2) (2) (2) (1) (1) (1) 1n 1n 1 12 1n 1n 1 12 T x x T z T ( x z) T T x x z T T T T T T x x z − − − − = = → = = 其中 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 1 (2) (2) (2) (1) (1) (1) (2) (2) (2) (1) (1) (1) 1n 1n 1 12 1n 1n 1 12 12 13 1n 1n 1n 1 12 T T T (2) (2) (2) (1) (1) (1) 12 13 1n 1n 1n 1 12 T T T T T T T T T T T T T T T T T T − − − − − − − − = = 为有限个 Givens 矩阵的乘积。 二 Householder 矩阵与 Householder 变换
(51 平面直角坐标系中,将向量x=[512]关于e1轴作为交换,则得到 511「10‖1 I-2 =Hx 般地,可将其推广 1.定义:设单位列向量u∈R,称H=1-2u1为 Householder矩阵(初 等反射矩阵),由 Householder矩阵所确定的线性变换(y=Hx)成为 Householder变换 2.性质 (1)HT=H(实对称),H1=HT(正交),H2=I(对合),H1=H (自逆),detH 为证明第5条,可利用如下引理。 引理:设A∈R,B∈R",则det(m+AB)=det(n+BA) 证明|参考如下的分块矩阵 的行列式,用A左乘第一行块加 a I 到第二行块,然后用(-B)左乘第二行块加到第一行块,有 B B det OI ARA=det(Im +AB)=det/n+BA 0 det(In +Ba 故, det(H)=detI+(-2uu)=1+u1(-2u)=1-2=-1
( ) 2 2 e ( ) 1 1 e ( ) 1 2 , ( ) 1 2 ,− 平面直角坐标系中，将向量 T 1 2 x = 关于 1 e 轴作为交换，则得到 ( ) 1 1 T 2 2 2 2 1 0 y I 2e e x Hx 0 1 = = = − = − − 一般地，可将其推广 1. 定义：设单位列向量 n u R ，称 T H I 2uu = − 为 Householder 矩阵（初 等反射矩阵），由 Householder 矩阵所确定的线性变换（ y Hx = ）成为 Householder 变换 2 . 性质 （1） T H H= （实对称）， 1 T H H − = （正交）， 2 H I = （对合）， 1 H H − = （自逆）， det H 1 = − 为证明第 5 条，可利用如下引理。 引理：设 m n n m A R ,B R ，则 det I AB det I BA ( m n + = + ) ( ) [证明]：参考如下的分块矩阵 n m I B A I − 的行列式，用 A 左乘第一行块加 到第二行块，然后用（-B）左乘第二行块加到第一行块，有 ( ) ( ) n n n m n m m m I B I B I BA 0 det det det I AB det det I BA A I 0 I BA A I + = = + = = + − + − 故， ( ) ( ) T T det H det I 2uu 1 u ( 2u) 1 2 1 = + − = + − = − = −
-2uu I-2 u=h °H2=(I-2uu -2uu=L-)T_2uu+4uu'uu 定理2.对于任何非零列向量x∈R及任何单位列向量z∈R",存在 Householder矩阵H,使得Hx=xz 证明当x=xz时,选u满足ux=0,则H=(-2u1)x=x=xz 当x≠z时,选n=2M乙,有 -12=(x-x)(x-x) =XX+X ZZ X+X Z =2(x1x-2x)=2(x-x)x x一XZ(X-XZ Hx=I-2 x=x- 定理3.初等旋转矩阵( Givens矩阵)是两个初等反射矩阵的乘积。 证明参见p202,较容易。我们这里主要是给出一种几何解释。 (e1) 从表明上看,似乎一种反射变换即可代替旋转变换。实际上是不对的, 因为这样的反射变换对应的对称轴沿(e1+6/2)方向,与1有关
( ) ( ) T T T T T T • = − = − = H I 2uu I 2 u u H ( )( ) 2 T T T T T T • = − − = − − + = H I 2uu I 2uu I 2uu 2uu 4uu uu I 定理 2. 对于任何非零列向量 n x R 及任何单位列向量 n z R ，存在 Householder 矩阵 H，使得 Hx x z = 。 [证明] 当 x x z = 时，选 u 满足 T u x 0 = ，则 ( ) T Hx I 2uu x x x z = − = = 当 x x z 时，选 x x z u x x z − = − ，有 ( ) ( ) ( ) ( ) ( ) 2 T T T T T 2 T T T x x z x x z x x z x x x z z x z x x z 2 x x x z x 2 x x z x − = − − = + − + = − = − ( ) T x x z (x x z) Hx I 2 x x x x z x z x x z x x z − − = − = − − = − − 定理 3. 初等旋转矩阵（Givens 矩阵）是两个初等反射矩阵的乘积。 证明参见 p202 ，较容易。我们这里主要是给出一种几何解释。 ( ) 1 1 e ( ) 2 2 e 1 从表明上看，似乎一种反射变换即可代替旋转变换。实际上是不对的， 因为这样的反射变换对应的对称轴沿 ( ) 1 + / 2 方向，与 1 有关
52(e2) 实际上,旋转变换可由这样两次反射变换的作用来代替 首先,关于沿(/4)对称轴作反射变换,则原向量沿61方向转至 (-1+6/2) 22(e2) 2 其次,关于沿(30/4)对称轴作反射变换,则向量反射至沿 81|+29+61|=01+6。正是原向量沿Q1方向转0的结果。 2 旋转变换可用两个反射变换的连续作用来代替,即T;=HH但 是反射变换却不可能用多个旋转变换的连续作用来代替。这是因为 de(t),de(n)=1由两个-1的乘积可得1,但多个1的乘 积只能是1,不是-1
( ) 1 1 e ( ) 2 2 e 1 4 实际上，旋转变换可由这样两次反射变换的作用来代替。 首先，关于沿 (/4) 对称轴作反射变换，则原向量沿 1 方向转至 (− + 1 / 2)。 ( ) 1 1 e ( ) 2 2 e 4 3 1 2 − 其次，关于沿 ( 3 / 4 ) 对称轴作反射变换，则向量反射至沿 1 1 1 2 2 4 − + + = + 。正是原向量沿 1 方向转 的结果。 • 旋转变换可用两个反射变换的连续作用来代替，即 T H H ij v u = 。但 是反射变换却不可能用多个旋转变换的连续作用来代替。这是因为 ( ) ( ) det T 1,det H 1 ij − 。由两个－1 的乘积可得 1，但多个 1 的乘 积只能是 1，不是－1
、QR分解 1.定义:如果实(复)矩阵A可化为正交(酉)矩阵Q与实(复)上三 角矩阵R的乘积,即A=QR,则称上式为A的QR分解 2.定理4:设A是n阶的非奇异矩阵,则存在正交(酉)矩阵Q与实(复) 上三角矩阵R使得A=QR,且除去相差一个对角元素的绝对值(模) 全为1的对角因子外,上述分解唯一。 证明|设A记为A=[a1a2…an]A非奇异→a1,a2;…,an线性 无关 采用Gram- schmidt正交化方法将它们正交化,可得 2101 b=a3-k3b1-k32b2 →(q;,q;)=8 bn=an-knjbi-kn2b2 . b ←-(a;,b;)=0
三、 QR 分解 1. 定义：如果实（复）矩阵 A 可化为正交（酉）矩阵 Q 与实（复）上三 角矩阵 R 的乘积，即 A QR = ，则称上式为 A 的 QR 分解。 2. 定理 4：设 A 是 n 阶的非奇异矩阵，则存在正交（酉）矩阵 Q 与实（复） 上三角矩阵 R 使得 A QR = ，且除去相差一个对角元素的绝对值（模） 全为 1 的对角因子外，上述分解唯一。 [证明]：设 A 记为 A a a a = 1 2 n ，A 非奇异 1 2 n → a ,a , ,a 线性 无关 采用 Gram-schmidt 正交化方法将它们正交化，可得 1 1 1 1 1 2 2 2 21 1 2 2 3 3 31 1 32 2 i j ij n n n n1 1 n2 2 nn 1 n 1 n n b b a q b b b a k b q b b a k b k b (q ,q ) b b a k b k b k b q b − − = = = − = = − − → = = − − − − = ( ) ( ) ( ) i j ij i j j j a ,a k a ,b 0 b ,b = =
21 bIC C=QR Q是正交(酉)矩阵 R是实(复)上三角矩阵 唯一性:.用反证法。设存在两个QR分解,A=QR=Q1R1,则 Q=Q1RIR=Q1D →D为上三角矩阵 而I=Q"Q=(QD)(QD)=D"D →D为酉(正交)矩阵 故,D只能为对角阵 a11al2…a1 D= →a12=0;a13=a23=0;…D是对角 元素绝对值(模)全为1的对角阵。 这一证明方法可推广为: 定理5.设A是m×n的实(复)矩阵,且其n个列线性无关,则A具有 分解A=QR。其中Q是mxn阶实(复)矩阵,且满足 QQ=I(QQ=),R是n阶实(复)非奇异三角矩阵。除了相差一个 对角元素的绝对值(模)全为1的对角阵因子外,上述分解唯
21 n1 n 2 1 2 n 1 2 n 1 2 n 1 2 1 2 n n 1 k k 1 k a a a b b b b b b C 1 b b q q q C QR b = = = = Q 是正交（酉）矩阵 R 是实（复）上三角矩阵 唯一性: 采用反证法。设存在两个 QR 分解， A QR Q R = = 1 1 ，则 1 Q Q R R Q D 1 1 1 − = = → D 为上三角矩阵 而 ( ) ( ) H H H 1 1 I Q Q Q D Q D D D = = = → D 为酉（正交）矩阵 故，D 只能为对角阵 11 12 1n 22 2n 12 13 23 nn a a a a a D a 0;a a 0; a = → = = = D 是对角 元素绝对值（模）全为 1 的对角阵。 这一证明方法可推广为： 定理 5. 设 A 是 m n 的实（复）矩阵，且其 n 个列线性无关，则 A 具有 分 解 A QR = 。其中 Q 是 m n 阶实（复）矩阵，且满足 T H Q Q I(Q Q I) = = ，R 是 n 阶实（复）非奇异三角矩阵。除了相差一个 对角元素的绝对值（模）全为 1 的对角阵因子外，上述分解唯一
3.求QR分解的方法 「方法一用 Givens方法 将n阶非奇异矩阵A写为 (1) b 则存在有限个Gven矩阵的乘积T1,使得 Tb=b0e1→TA A0)写成A0=/么(y →存在T2,使得 (2) (u)写成A-2)b(a-y7r →存在Tn_1,使得 (n=2/rn,A(u=2)=|21m n-1.n 0‖I 0 0‖10 令T 0T1lor210x0r1,则有 2 3
3. 求 QR 分解的方法 [方法一]采用 Givens 方法 将 n 阶非奇异矩阵 A 写为 T T (1) b A = 则存在有限个 Givens 矩阵的乘积 T1 ，使得 ( ) ( ) ( ) ( ) 1 1 1 11 12 1n (1) (1) 1 1 1 1 a a a 0 T b b e T A A 0 = → = (1) A 写成 ( ) ( ) T T 2 1 b A = → 存在 T2 ，使得 ( ) ( ) ( ) ( ) ( ) 2 2 2 22 23 2n 1 2 2 a a a 0 T A A 0 = (n 2) A − 写成 ( ) ( ) T T n 1 n 2 b A − − = → 存在 Tn 1− ，使得 (n 2) A − ( ) ( ) ( ) ( ) n 1 n 1 n 2 n 1,n 1 n 1,n n 1 n 1 nn a a T A 0 a − − − − − − − − = 令 n 2 n 3 2 1 n 1 n 2 2 3 I 0 I 0 1 0 I 0 T T 0 T 0 T 0 T 0 T − − − − = ，则有