§3.QR方法 基本QR方法 60年代出现的QR算法是目前计算中小型矩阵的全部特征值与 特征向量的最有效方法。实矩阵、非奇异。 理论依据:任一非奇异实矩阵都可分解成一个正交矩阵Q和 个上三角矩阵R的乘积,而且当R的对角元符号取定时,分解是 唯一的 基本QR方法的基本思想是利用矩阵的QR分解通过迭代格式 A=2K lA+D=R,O A(k=1,2,…) 将A=A(化成相似的上三角阵(或分块上三角阵),从而求出 矩阵的全部特征值与特征向量 由A=A=QR,即Q1A=R于是A2)=RQ=QAQ,即A2 与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的特征值的 近似。 (A (k) A)=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变换 设向量=(m…,m)y满足2=+…+m2=1,则称 1-212-211 -21n wow H=I-2ww 2n-2n2…:1-22」 为 Householder矩阵或反射矩阵。可证其具有以下性质: (1)H是实对称的正交矩阵,即H=H=H 2)det(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+Ow)=x-0 证:H=-2Mn且|w2=√w2+…+2=1 H(+Ow)=(I-2ww)(+Ow) x+ow-2wWx-2Oww' y x+0w-20=x-0w
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中任意非零向量,且|y2=1,则存在 Householder矩阵H使得x=±|x|2y 证:w x-(±|x 令H=I-21,于是 x千|x x=(1-2w)x=x-2 (x平|x2y2) x|2y12 由2一范数的定义.y2=(xy)(x2y) =xx|×2yx平|x2xy+|2y2y xx2 xy x+x=2(xIlxy') xn)(y1,y2…,yn)=(y,y2…,yn) 代入上式得x=±|xl2y
( ) 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 + = + = = = （ ） 代入上式得