§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 + = + = = = （ ） 代入上式得
上式得Hx=±|xl2y 此定理表明,对任一非零向量x,都可以构造 Householder变换,它将x变成事先给定的单位 向量的倍数。特别地取y=e,则x经过H fuseholder 变换后可变成只有一个分量不为零。实际计算时, 为避免误差取 x-(±|x12y) X+ → ‖x|1y 2 x+lle, sign(x, +x) e sign(
2 2 2 2 2 2 2 . , , ( ) i Hx x y x Householder x y e x Householder x x y x x y w w x x y x x y = = − = = 上式得 此定理表明，对任一非零向量 都可以构造 一个 变换，它将 变成事先给定的单位 向量的倍数。特别地取 则 经过 变换后可变成只有一个分量不为零。实际计算时， 为避免误差取 2 2 2 ( ) ( ) i i i i x x e sign x w x x e sign x + = +
化一般矩阵为拟上三角阵 称形如 h h,n,- h, h 2i hhh h, h H h 的矩阵为拟上三角阵,也称为上海森堡( Hessenberg) 阵。如果次对角线元h-1(=2,3…,m)全不为零,则称该 矩阵为不可约的上 Hessenberg矩阵。 讨论用 Householder变换将一般矩阵A相似变换成 Hessenberg 阵
三、化一般矩阵为拟上三角阵 11 12 1 1 1 21 22 2 1 2 32 33 3 1 1 ( 2,3, , ) , Householder n n n n n nn nn ii h h h h h h h h H h h h h h h i n A − − − − = = 称形如 的矩阵为拟上三角阵，也称为上海森堡（Hessenberg) 阵。如果次对角线元 全不为零 则称该 矩阵为不可约的上Hessenberg矩阵。 讨论用 变换将一般矩阵 相似变换成 Hessenberg阵
首先,选取矩阵H1使得经H相似变换后的矩阵 H1AH的第一列中有尽可能多的零元素。为此 应取H1为如下形式H1 其中H为n-1阶 Householder矩阵。于是有 H H1AH、Ha1H142B1其中a=(a1,a31,…an 由上节定理,只要取H1使得H1a1=a(1,0,…,0),就会 使得变换后的矩阵H1AH的第一列出现n-2个零元
1 1 1 1 1 1 1 1 1 11 2 1 1 1 21 31 1 1 1 1 22 1 22 2 12 13 1 22 , 1 0 0 0 0 1 ( , , , ) , ( , , , ) , T T n T n H H H AH H H H H n Householder a a H H AH a a a a H a H A H a a a a a A = − = = = = 首先，选取矩阵 使得经 相似变换后的矩阵 的第一列中有尽可能多的零元素。为此， 应取 为如下形式 其中 为 阶 矩阵。于是有 其中 2 2 1 1 1 1 1 . (1,0, ,0) , 2 n n nn T a a a H H a H AH n = − 由上节定理，只要取 使得 就会 使得变换后的矩阵 的第一列出现 个零元
为避免在计算时会产生较大的误差取 a+a,,e,sign(,) a1+| a,l,e, sig(a)儿 >HI (Hia,=a,,,sign(a, ) H 同理,可构造如下列形式 Householder矩阵 100 010 水水 ●香 H2=00 使得H2H1AH1H2 水水 00 如此进行n-2次,可以构造n-2个 Householder矩阵H1H2 Hn2使得Hn2…H2H1AH1H2…Hn2=H 其中H为上 Hessenberg矩阵。特别地,当A为实对称矩阵,则 经过上述正交变换后,H变为三对角阵
1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 2 2 1 2 2 , ( ) ( ( ) ) ( ) 1 0 0 0 0 1 0 0 0 0 0 0 w a a e sign a w H H a a e sign a a a e sign a H Householder H H + = = + = 为避免在计算 时会产生较大的误差 取 。 同理，可构造如下列形式 矩阵 2 1 1 2 1 2 2 2 2 1 1 2 2 * * * * * * * * * * * * * 2 2 , , , , . n n n H H AH H n n Householder H H H H H H AH H H H H Hessenberg A H − − − = − − = 使得 * 如此进行 次，可以构造 个 矩阵 使得 其中 为上 矩阵。特别地，当 为实对称矩阵，则 经过上述正交变换后， 变为三对角阵
例用 Householder变换将矩阵A化成拟上三角阵 5-22√2-3√2 105√2/2-√2/2 √2 0 0√2 解:因a1=(120,0),由H1a1=0(1,00)→H1=1→H1=1 「-√2 为使 Householder矩阵H2满足H2 √2 由公式1 x+xlb, sign(x (-√2,√2)-2(,0 Ix+l>, sign(x,lI (2-22y,m=w=(y2+V
1 1 1 1 1 2 2 2 2 : 5 2 2 2 3 2 1 0 5 2 2 2 2 0 2 1 0 0 2 4 1 (1,0,0) , (1,00) . 2 1 , 2 0 ( ) ( T T i i i Householder A A a H a H I H I Householder H H x x e sign x w x x e sign x − − − = − − − = = = = − = + = + 例用 变换将矩阵 化成拟上三角阵。 解：因 由 为使 矩阵 满足 由公式 ' 2 ' ' , ( 2, 2) 2(1,0) ) 2 2 2 ( 2 2, 2) ( , ) , 2 2 2 2 T T i T T w w w w = − − + = − − = = − +