资源描述
1第九章 矩阵特征值与特征向量计算矩阵特征值问题有物理、工程背景特征值， 对应的特征向量:nAx: x特征多项式 ()detIA特征值 0 特征向量 的基础解系。()Ix定理 1. 如果 为 A 的特征值的集合，则：1,.nA11()2det()3()noiinioatrABB: 若 x 是 B 对应于 的特征向量，则 Tx 是 A 对应于同一特征1,T值的特征向量。定理 2 (Gerschgorin 圆盘定理)设 ，则 得每一个特征值必属于下述某个圆盘之中：)ijnAa1(1,2.,)niijjain 证：设 特征值， 对应的特征向量 x()0IAx21(,.)0;maxTnikxx 第 个方程 i 1niija/1ji iijjxa 有 ：得证，且 对应的特征向量第 个分量绝对值最大，在第 个圆盘中。 iReyleigh 商：设 -实对称矩阵， 的 Reyleigh 商定义为：A0x (,)AxR定理 3：设 对称，特征值 ，对应特征向量 n:12n组成标准正交组 则：1,.nx(,)ijijx 1 1(,)nAx 2 1 00main()nxxRR: 幂法与反幂法设 有完全特征向量组（n 个线性无关的特征向量）()ijAa1231.n: 幂法 任取初值 10010,.kkvvAvAv: 3，以后我们用符号 表示向量 的第 i 个分量。1()limkiv()kivkv一般 为避免溢出1()ki表示向量 绝对值最大的分量001112221max().()kkkvuvAvuv 不 会 溢 出 ()kvkv此时 ，1max()k 收 敛 速 度 1max()()kkvOr21 当 时也可用12 1.ss 方法的证明：设 的特征向量为 （线性无关） ，A,.nxA:1(,.)ndiagTx1122102(,.)(,.),.nnnAxxxTTvaax 41021121211.().()().()0()kkk knk knkkknkvAvaxaxxaxax 1()()limkiikikiv加速. 原点平移法BApI12(),.,n适当选 ，使p2211求 的主特征值B Rayleigh 加速设 对称 A123.n 则 11(,)()kkuO5反幂法， 有完全特征向量系A123.0nn: 的特征值为 ， 且 1,n 11.n通过求 的主特征值 来间接求1An迭代公式： 01max()kkkvuA 1k kvvu通 过 求 解 方 程 ： 求 得 。相似变换法方法的思想是找适当的 P 通过 相对好算来计算 A 的特征1:,()AB值，如果对 不加限制，则从 求 ，很可能是病态方程，所以只能用酉相似变换法，即限制 为酉阵（注意特征值一般是复的） 。酉阵 ()()HijnjinAaa HUI6酉相似变换的优点 求逆容易 1 1HU 2 ()1mincondU酉变换能把任意矩阵变换成怎样的矩阵？定理（Schur 分解定理）设 ，则存在 n 阶酉阵 ，使nA:， 为上三角形矩阵。HAUT证明：设 的一个特征值为 ，对应的特征向量为 ， 找11x2 使得 为酉阵。(1)n:， (,)xU (,)AU1111,0HHHUAhxA 2()1212210nAAUU : 12122*()()0HU为酉阵，. 如此进行下去，即得： 酉阵12 U1*:HnUAT定理：（实的 Schur 分解定理）, 存在正交阵 ，使n:R712120kTkTRA 为一阶或二阶矩阵。i实际上，一阶对应实特征值， 二阶矩阵对应一对共轭复特征值关键在于求 或 R，Chur 定理的证明中，有了特征值，特征向量才有 ，UU不能直接用于求特征值。求一般矩阵全部特征值的 QR 算法我们把算法分为 5 步讲解 初等反射阵. 1问题：给定 中的向量 x， y，如何找正交阵 使得 ？由于正交变n:Hxy换保内积，给定的 x， y 必须满足条件 |xy给定单位向量 ，构造矩阵 ，这样定义的2,1nw 2TIwH 称为初等反射阵，易验证初等反射阵具有性质 ， 是正1H交阵，对称阵，对合阵。有 2, ,nxyxyxyu:， 可 得 到 ： 存 在 使 ，事实上只须 令21TuIuH8即可。2()uxyQR 分解定理： A 可表示为 A=QR 其中 Q 为正交阵而 R 为上三角阵。(),ijna证明：把 A 写成列向量形式 ，不妨设 （否则跳过这1(,.)na10a一步）根据 的结果可知存在初等反射阵 ，使得 1 1H1,e， 1HA(2)*0a(2)(1)nAR同理存在 n-1 阶初等反射阵 ，使得2H，令 ，(2)(2)(3)*0aHAA22101HA1(2)(3)*0aA.如此继续下去，存在一系列初等反射阵 ，使得11,nH9，令 即得。121.nHAR 1nQHQR 分解一般不唯一，至少主对角线上的元可 。若 A 非奇异，且限制的对角元为正，则唯一。 R证：设 ，由于 A 非奇异， ，两边均为上三21AR 112TR角正交阵，对角阵 ， 的对角元为正1(,.)nidiag 12,注意 A 的 QR 分解中的 不相似于122i I A，求 A 的特征值还须更复杂的方法。QR 方法 3设 （分解好）令 以 代入得 QRBRQTTAQBTBA对 B 仍可作 QR 分解，再算 RQ:基本 QR 算法： 1kkkAQR（ 的 分 解 ）k=1,2.易知：定理 1： 1 12()2,.3 (QR)TkkkkkkAQQRRA 的 分 解定理 2：设 ，其特征值满足， ，A 有标nx:12.0n10准形， 1AxD， 有 分解， ，1(.)ndiag1LU1xL则 *k nR 本 质 上即 ()0limkjiijaij不 一 定 存 在注意 Q 的列向量不收敛于特征向量集合若 A 对称，满足定理条件，则 收敛于对角阵，若不满足， 可能不kAkA收敛于对角阵。A 本身为正交阵 ,eg011Q1RI1kA一般情形的 QR 算法收敛性较为复杂，特殊的，若 A 的等模特征值只有重实特征值或多重共轭复特征值，则 QR 算法产生的 本质上收敛于分块上k三角阵。1111*mlB 为 A 的实特征值， 块 的特征值为 A 的复共轭特征值，注意1.m2iB的元素不一定收敛，但特征值收敛。iB一次迭代计算次数（即一次 QR 分解）计算量 不可接受。3()On改进的方法：正交相似变换成上 H 阵，再对上 H 阵用 QR 算法。Householder 方法定义：方阵 ，如果当 ，则称 为上()ijnBb10ijijb时 ， BHessenberg 阵，即：12121,0nnnbbB 问题：如何用正交相似变换化一般 为上 Hessenberg 阵nA:现考虑用一系列初等反射阵，将 化为上H 阵( 如同大多数矩阵分解我们还是用减缩的方法 )12把矩阵写成列向量的形式： 找初等反射阵 使1(,.)nAa1H， ,如前，很容易找到2112(,.,)nAHd*0,Td使得 取 的形式（不唯一） ，设 但现在a112HIu 的第一列要取 的形式。 为使右乘 后， 的第一列不变，1()1 A的第一列应为1H110(1,0.)TH 因此必须 。1()u下 ， ，由 知：d求 与 11()ad 1da， ，2121(),nis 111u，1121311)(0,.,)Tnwadasa 可能 ，为避免相近数相减，取 。从而2s2sg(121gn()s令 ， ，2211aw1THIw(,sgn(),0.,)Tda 13第 步变换，仅是第一步的重复，只不过把变换应用与 阶方阵上。i 1ni若 为对称， （上 阵） 显然 为对称。 为三对角矩阵。ATRBH B一次变换的计算量 。35()4n:但对上 H 阵作一次 QR 分解计算量仅为 预处理的方法。2()On对上 H 阵作 QR 分解的 Givens 变换在 中， 2:cosinP Px 把向量 逆时针方向旋转 角度，P 称为旋转矩阵。x推广到 称为平面旋转矩阵。(,)nij1(,)1csiPijscjij ， （可以认为 ）21cscos,in设 2(,.,.)Tijnxaa:14， 则1(,),.)TnPijxb(,)iijjijkcassacbaij 如果取 则22jijijs， （1）,0iijbab为正交阵， 左乘： 只改变 的第 行和第 行。右乘： (,)Pij ()PAij只改变 的第 列和第 列。 改变 的的第 行、Aij(,)(,)TijPAi第 行，第 列和第 列其余元素不动。ij这样的 称为 Givens 矩阵或 Givens 旋转变换，它具有下(,)ij列性质：1 为正交矩阵；P2 与单位阵相比，只有在 4 个位置上的元素不同；(,),(),ijij3 作用于向量 ，只改变 的第 两个元素：x,ij4. 的前(i-1)行和前(i- 1)列与单位阵 I 相同。P通过（1）式，我们看到作旋转变换可 有针对性地使某个元素变零，而用初等反射阵则一次使一串元素变为零。显然，用旋转变换也可实现矩阵的 QR分解，特别是当 A 为上 Hessenberg 阵时，每一列用一次，总共用 n-1 次旋转变换即可实现 QR 分解，大大减少了计算量。算法对上 Hessenberg 矩阵 ，用 QR 算法迭代一次可分两步：A15(1) 用 Givens 变换作 QR 分解：左乘 将 化 0， ，左乘 将 化 0， ，左乘12Pa ,1iP,ia 将 化 0，得上三角阵 R,n,n(2) 右变换 2A1231,TnR定理 设 为上 Hessenberg 矩阵，那么由 开始作 QR 算法所产生的矩阵1 1A序列 的每个矩阵 均为上 Hessenberg 矩阵。kk证明：只需要证明一步就可以了。设对上 Hessenberg 矩阵 用 Givens 旋k转变换作 QR 分解，即 ，或1,2,312nkPPR。现作反乘 。1231,TknkkAPRQ kAQ1231,TnP分两步来证明 仍然为上 Hessenberg 矩阵。（1）容易证明 是上 Hessenberg 矩阵，这是因为12k1212*0k nrcsRPr 。1212*00*crsc （2 ） 任一上 Hessenberg 矩阵 与 的乘积仍是上 Hessenberg 矩阵。H1,iP作分块乘法16，其中1 121, 3 30sssii pi pxx xHXIHXPPP，2iiics而 ,1 ,1.11, 1, 1.,ii iiiiiipihchsshccsHP 显然，最后结果仍为上 Hessenberg 矩阵。 最后一个问题，在 1(,).(1,2)(,).(1,)TTk kAPnAPn中，左乘和右乘是否能同时进行，以减少存储量，简化程序？实际上关键的问题是要能找到正确的 ，注意 是由,i(,)Pm(,).(,)km的第 m 列确定改变的是上述矩阵的第 m 行和 m+1 行，而对任意矩阵 B，的第 m 列与 B 的第 m 列相同，因此对1,2.2,1TTBP的第 m 列作同样目()()().(2,1)TTkAP标的 Givens 变换，也能得到正确的 ，所以左右变换可以按下列顺序同时进行： (2,3)1(2,3)1(,)(3,4),(2)(1,)4(,),2T Tkk kTkPPAPPA带位移的 QR 算法数列 构造 算法ksk17（1 ） A（2 ）对 分解ksIQRk=1,2,.（3 ）新矩阵1TkkkARsIA（4 ） TKQ（5 ） 12():)(.()ksIsI有 QR 分解式 kAR如果选 ，则可把 分离，迭代进行到 充分小， 有形()knSan(),1|knakA式 (4为 例 440B ：对 B（减一阶）续续用 QR 算法。收敛快。QR 算法的证明、细节与改进定理 2.1 的证明：18引理 ，当 时若 ，则kkMQRkMIkQRI，证： TTTk， 第一行为()kijnrk()()()1121,knr ()2()kkr()0,2,ijjn 同理逐行计算得11,kkkkRIIQMRI定理的证明 11()()kkkkijAxDLUxDLl 元素：01()kijkijij由于 ij 另一方面：1: 0()()maxkkkkijijkjjDLIEEOic 可设1()()k kkXQRAIDUQIREDU 19当 K 充分大时， 非奇异1 1k kREIRE ()kQII由引理()()k ()()kkARDU的另一形式，QR 分解112(,.)ndiaguu上式改写成()1()212(kkkkAQDRDU正 交 阵 对 角 元 为 正与上式同一 QR 分解。kkR()21()1kkU代入定理 1 之（2） 得：1AQRD()()21 21(TkTkkkkkAQ为上 所以有()IR()1()1kTkkBDR（对角线保持次序）1*n2012121()()()kTkkijiijjADB为对角阵，2i1()0kij()j1ikijiiABRDHouseholder 算法：假定对 进行了 步变换，得到()(1,2.,)kAn ()()()121310kkk kaAU21H用 左 乘 都 不 改 变 第 一 列()()()()()1223knknkA: 要求 阶正交阵()20ka()21kkkRae， 使()()21/1()()2()11,sgn ()3nkkk iikkkaRue () 0() kkTkn InIuUR阶 (不须做矩阵乘法，做一系列内积)()()()12131 20kkkkkAaAURA21()21()()()323(41113) ()()23223(4)56(7)kkkTkk kkTkkRaeAuARu） 算法：对 做 ,.,n 在(4)(7)中，新的冲掉老的(6),(7)可合并，一个 的矩阵右乘 阶方阵。()k()nk
展开阅读全文