§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 + = + = = = （ ） 代入上式得
上式得Hx=土|2y 此定理表明,对任一非零向量x,都可以构造 个 Householder变换,它将x变成事先给定的单位 向量的倍数。特别地取y=e,则x经过 Householder 变换后可变成只有一个分量不为零。实际计算时 为避免误差取 x-(±|x,y) x千x,y x千x,y x千‖x|,y x+ x e sign(x →1 x+ e sign(x)
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,n- h hh H h n 的矩阵为拟上三角阵,也称为上海森堡( Hessenberg) 阵。如果次对角线元hn1(=2,3…,n)全不为零则称该 矩阵为不可约的上 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阵
首先,选取矩阵H12使得经H相似变换后的矩阵 H1AH的第一列中有尽可能多的零元素。为此, 应取H1为如下形式H1= 0 其中H1为n-1阶 Householder矩阵。于是有 H1AH, H1A22 H1 其中a1=(a21,a312…,an) 由上节定理,只要取H1使得H1a1=0(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 = − 由上节定理，只要取 使得 就会 使得变换后的矩阵 的第一列出现 个零元
为避免在计算时会产生较大的误差,取 +la,,e,sign(a, a,+, sign(a, →H1(Ha1=| al, e, sign(an) 2 →H 同理,可构造如下列形式 Householder矩阵 00 半半 010 H2=00 使得H2H1AH1H2=** 00 水 如此进行n-2次,可以构造n-2个 Householde矩阵H,H2, n-2 使得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化成拟上三角阵。 222-32 √2/2-√2 A √2 解:因a1=(1,0,0),由H1a1=0(1,00)→H1=1→H1=1 为使 Householder矩阵H满足h2/~√ x+x. e sign(x 由公式v x+1|(2sg(x v=(-√2,√2)-2(1,0) (√-25y,m=m=(业2+, 2 2√2+
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 = − − + = − − = = − +