南京大学计算机科学与技术系：《数值计算方法》课程教学资源（PPT课件）第7章 矩阵特征值和特征向量的数值解法 7.3 QR算法（2/2）

7.32矩阵的QR分解 定理73.1设矩阵A∈R,且非奇异,则一定存在正交矩 阵Q,上三角矩阵R,使 A=OR (732) 且当要求R的主对角元素均为正数时,则分解式(732)是唯一的 证明存在性有矩阵A的非奇异性及 Householder变换矩 阵的性质(3)知,一定可构造n-1个H矩阵:H1,H2…,Hn-1使 kAk(k=1,2 1)

7.3.2 矩阵的QR分解 定理 7.3.1 设矩阵 n n A R   ，且非奇异，则一定存在正交矩 阵 Q，上三角矩阵 R，使 A = QR (7.3.2) 且当要求 R 的主对角元素均为正数时，则分解式(7.3.2)是唯一的。 证明 存在性 有矩阵 A 的非奇异性及 Householder 变换矩 阵的性质(3)知，一定可构造 n −1个 H 矩阵： 1 2 1 , , , H H  Hn− 使 ( 1,2, , 1) Ak+1 = Hk Ak k =  n −

其中A1=A,而 12 (n 2n R nn

其中 A1 = A，而                   − − − = − − ( ) ( ) 1 1 ( ) 2 2 ( ) 1 ( ) 1 1 2 n n n n n n n n n n n n n a σ a σ a σ a a A     R  =

因此有 H, hHA=R 即有 A=OR 其中,g=h1H2…Hnm为正交矩阵

因此有 Hn−1 Hn−2 H2 H1 A = R 即有 A = QR 其中，Q = H1 H2 Hn−1 为正交矩阵

唯一性假设矩阵A有两种正交三角分解,即 QR=O2R 其中,Q1Q2为正交矩阵,R1,R2为上三角矩阵,且 主对角元素均为正数。于是有 1Q2=R1R2=D

唯一性 假设矩阵 A 有两种正交三角分解，即 A = Q1 R1 = Q2 R2 其中， 1 2 Q ,Q 为正交矩阵， 1 2 R , R 为上三角矩阵，且 主对角元素均为正数。于是有 Q Q R R D T  − = = 1 1 2 1 2

这里,D必是既为正交矩阵又是上三角矩阵,故 D=dag(dl1,d2…dn) 且d2=l(i=12.…,n),因此,R1=DR2,由于R1R2 对角元均为正数,故d=1(=1,2,…m),即有 D=I,R1=R2,Q1=Q2

这里，D 必是既为正交矩阵又是上三角矩阵，故 diag ( , , ) D = d1 d2 dn 且 1( 1,2, , ) 2 d i n i = =  ，因此，R1 = DR2 ，由于 1 2 R , R 对 角 元 均 为 正 数 ， 故 d 1(i 1,2, ,n) i = =  ，即有 1 2 1 2 D = I,R = R ,Q = Q

例7.3.2设矩阵 -1 2-45 试作矩阵A=QR分解 解为直观起见,下面给出H矩阵形式

例 7.3.2 设矩阵           = 2 4 5 2 1 1 1 1 1 - A - - 试作矩阵 A = QR 分解。 解 为直观起见，下面给出 H 矩阵形式

(1)求H1,作A2=H1A。 1=sgn(a1)∑a2)2=3 a,to 2,u=(4,2,2) 3×4=12: 1-2-2 H1=I-p1u=-22-1

(1) 求 H1 ，作 A2 = H1 A。 1 sign ( )( ) 3; 2 3 1 1 2 1 = 11  1 = i=  a ai  2 4, 2, (4,2,2) ; 1 11 1 2 T u = a + = u = u =  3 3 4 12; 1 =1 u1 =  =            = − = − 3 1 2 2 2 1 1 2 2 3 1 1 1 1 - - - - - - - H I uu T 

33-3 A,=H1A=00-3 (2)求H2,作A3=H2A2=R T°a2=sgn(a2)∑a2)=3(约定sgn(0)=1) 2°u1=0,u (2) +O2=3 (2 3,u=(0,3,-3)

 4           = = 0 3 3 0 0 3 3 3 3 2 1 - - - - A H A (2)求 H2 ，作 A3 = H2 A2 = R 1 sign ( )( ) 3 ( sign (0) 1); 2 2 (2) 2 (2) 2 2 2 2 =  = = = 约定 i  a ai  ( ) 2 0, 3, 3, (0,3, 3) ; 2 2 3 3 2 (2) 1 2 2 2 T u = u = a + = u = a = − u = − 

H2=1-P2 001 0-3-3=R 1-2-2 Q=H1H2=1-2-12 由矩阵乘法可直接验证A=QR

3 9; 2 =  2 u2 =            = − = − 0 1 0 0 0 1 1 0 0 3 1 1 2 2 H I uu T   4 - - R - - A H A =           = = 0 0 3 0 3 3 3 3 3 3 2 2           − − − − − − = = 2 2 1 2 1 2 1 2 2 3 1 Q H1 H2 由矩阵乘法可直接验证 A = QR

7.3.3QR算法 设A=(an)∈R",QR算法是对A进行一系列的 正交相似变换,达到求出矩阵A的全部特征值和相应的 特征向量。算法如下: 分解:Ak=QRk 构造:A1=QkAQ=RQ(k=12,3 这里Q为正交矩阵,Rk为上三角矩阵,且当Rk主对角 元均为正数时,则上述正交三角分解唯

7.3.3 QR算法 设 n n A aij R  = ( ) ，QR 算法是对 A 进行一系列的 正交相似变换，达到求出矩阵 A 的全部特征值和相应的 特征向量。算法如下： 分解： Ak = Qk Rk 构造： ( 1,2,3,...) A +1 = Q Ak Qk = Rk Qk k = T k k 这里 Qk 为正交矩阵，Rk 为上三角矩阵，且当 Rk 主对角 元均为正数时，则上述正交三角分解唯一