§3QR方法 基本QR方法 60年代出现的QR算法是目前计算中小型矩阵的全部特征值与 特征向量的最有效方法。实矩阵、非奇异。 理论依据:任一非奇异实矩阵都可分解成一个正交矩阵Q和 个上三角矩阵R的乘积,而且当R的对角元符号取定时,分解是 唯一的。 基本QR方法的基本思想是利用矩阵的QR分解通过迭代格式 A=O. k=1,2,… A (k+1 ROK 将A=A化成相似的上三角阵(或分块上三角阵),从而求出 矩阵A的全部特征值与特征向量。 由A=A=QR,即QA=R于是A2)=RQ=QAQ,即A42 与A相似。 同理可得,A)~A(k=2,3,…)。故它们有相同的特征值
§3.QR方法 一、基本QR方法 60年代出现的QR算法是目前计算中小型矩阵的全部特征值与 特征向量的最有效方法。实矩阵、非奇异。 理论依据：任一非奇异实矩阵都可分解成一个正交矩阵Q和 一个上三角矩阵R的乘积，而且当R的对角元符号取定时，分解是 唯一的。 ( ) ( 1) (1) (1) 1 (2) 1 (2) 1 1 1 1 1 1 1 QR QR ( 1,2, ). , , k k k k k k A Q R k A R Q A A A A A Q R Q A R A R Q Q AQ A A + − − = = = = = = = = = 基本 方法的基本思想是利用矩阵的 分解通过迭代格式 将 化成相似的上三角阵（或分块上三角阵），从而求出 矩阵 的全部特征值与特征向量。 由 即 。于是 即 与 相似。 同理可 ( ) ( 2,3, ) k 得， 。故它们有相同的特征值。 A A k =
可证,在一定条件下,基本QR方法产生的矩阵序列{A( “基本”收敛于一个上三角阵(或分块上三角阵)。即主对角 线(或主对角线子块)及其以下元素均收敛,主对角线(或主 对角线子块)以上元素可以不收敛。特别的,如果A是实对称阵, 则{A(}“基本”收敛于对角矩阵。 因为上三角阵的主对角元(或分块上三角阵中,主对角线 子块的特征值)即为该矩阵的特征值,故当k充分大时,A()的 主对角元(或主对角线子块的特征值)就可以作为A的特征值的 近似。 (4()-2)u=0 基本的QR方法的主要运算是对矩阵QR分解,分解的方法有 多种。如 Schmit正交化方法(略)。 基本QR方法每次迭代都需作一次QR分解与矩阵乘法,计算 量大,而且收敛速度慢。因此实际使用的QR方法是先用一系列 相似变换将A化成拟上三角矩阵(称为上 Hessenberg矩阵),然 后对此矩阵用基本QR方法。因为拟上三角矩阵具有较多零元素, 故可减少运算量。化A为相似的拟上三角阵的方法有多种
可证，在一定条件下，基本QR方法产生的矩阵序列｛A(k)｝ “基本”收敛于一个上三角阵（或分块上三角阵）。即主对角 线（或主对角线子块）及其以下元素均收敛，主对角线（或主 对角线子块）以上元素可以不收敛。特别的，如果A是实对称阵， 则｛A(k)｝ “基本”收敛于对角矩阵。 因为上三角阵的主对角元（或分块上三角阵中，主对角线 子块的特征值）即为该矩阵的特征值，故当k充分大时， A(k)的 主对角元（或主对角线子块的特征值）就可以作为A的特征值的 近似。 基本的QR方法的主要运算是对矩阵QR分解，分解的方法有 多种。如Schmit正交化方法(略)。 基本QR方法每次迭代都需作一次QR分解与矩阵乘法，计算 量大，而且收敛速度慢。因此实际使用的QR方法是先用一系列 相似变换将A化成拟上三角矩阵（称为上Hessenberg矩阵），然 后对此矩阵用基本QR方法。因为拟上三角矩阵具有较多零元素， 故可减少运算量。化A为相似的拟上三角阵的方法有多种。 ( ) ( ) 0 k A u − =
豪斯豪尔德( Householder)变换 设向量y=(m…,m)满足h=√2+…+m2=1则称 -2 H=Ⅰ-2w 21211-22 w.w. 为 Householder矩阵或反射矩阵。可证其具有以下性质: (1)H是实对称的正交矩阵,即H=H=H; (2)de(H)=-1 (3)H仅有两个不等的特征值±1,其中是n-1重特征值,-1 是单重特征值,为其相应的特征向量;
二、豪斯豪尔德(Householder)变换 2 2 1 1 2 2 1 1 2 1 2 2 1 2 2 2 1 2 1 ( , , ) 1, 1 2 2 2 2 1 2 2 2 2 2 1 2 1 ; (2)det( ) 1; (3) T n n n T n n n n T w w w w w w w w w w w w w w w w H I ww w w w w w Householder H H H H H H − = = + + = − − − − − − = − = − − − = = = − 设向量 满足 则称 为 矩阵或反射矩阵。可证其具有以下性质： （ ） 是实对称的正交矩阵，即 仅 1 1 n 1 , 1 , ; w 有两个不等的特征值 ，其中 是 重特征值 − − 是单重特征值 为其相应的特征向量
(4)考虑以w为法向量过原点o的超平面S:wx=0 ∈R为任意的数,有H(x+O)=x-Ow 证:H=1-2W且|2=√w2+…+2=1 H(x+Ow)=(-2ww)(x+Ow) xtOw-2wwx-2Owww =x+ow-2Ow=x-ow
2 2 2 1 : 0, , ( ) . 2 1 ( ) ( 2 )( ) 2 2 2 T T n T T T w o S w x R H x w x w H I ww w w w H x w I ww x w x w ww x ww w x w w x w = + = − = − = + + = + = − + = + − − = + − = − (4)考虑以 为法向量过原点 的超平面 为任意的数 有 证： 且 w o x
定理设x,y为R中任意非零向量且|yl2=1,则存在 Householder矩阵H,使得Hx=±1|xl2y x-(±x,y) 正 2令H=1-21,于 x|2y2 Hx=(-2ww)x=x-2xIxll2y a(x2千x(2y2)x Ix +)yl 由2-范数的定义.|x2y2=(x|212y)(xy) =x'xIlyxilxlxy+xyy xx2xby'x+x2=2(x'flly) (x1,x2…xn)(v1,y2…,yn)=(y,y2…,yn)(x1,x2…xn) 代入上式得Hx=±|x2y
( ) 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 : , , 1, , ( ) 2 , ( 2 ) 2 ( ) . 2 ( ) ( ) = n T T T T T T T x y R y Householder H Hx x y x x y w H I ww x x y x x y Hx I ww x x x x y x x x y x x y x x y x x y x x x y x = = − = = − = − = − = 定理 设 为 中任意非零向量 且 则存在 矩阵 使得 。 证： 令 于是 由 －范数的定义. 2 2 2 2 2 2 2 1 2, 1 2 1 2 1 2, 2 2 2( ) ( , )( , , , ) ( , , , )( , ) . T T T T T T T T n n n n x x y x y y x x x y x x x x y x x x x y y y y y y x x x Hx x y + = + = = = （ ） 代入上式得