第七章对称特征值

第七章对称特征值问题的计算方法基本性质对称QR方法Jacobi方法7.1基本性质对称矩阵特征值均为实数，而且其特征向量可以构成Rn的一组标准正交基，即有定理1(谱分解定理）若A是n阶对称矩阵，则存在正交矩阵Q使得定理2（极小极大定理）设A是n阶对称矩阵，并假定A的特征值为λ1≥…≥

λn,则有其中表示中所有k维子空间的全体。定理3设n阶对称矩阵A和B的特征值分别为则有该定理表明对称矩阵的特征值总是十分良态的。定理4设A和A+E是两个n阶实对称矩阵，并假定q1是A的一个单位特征向量，Q=[q1,Q2]是n阶正交矩阵，QTAQ和QTEQ分块如下若则存在A+E的一个单位特征向量使得定理4表明，特征向量的敏感性依赖于对应特征值与其他特征值之间的分离程序。定理5设A是m×n阶实矩阵，则存在正交矩阵U和V，使得其中注：定理5给出的是矩阵A的奇异值分解，数称为A的奇异值。V的列向量称为A的右奇异向量；U的列向量称为A的左奇异向量。定理6设A和B均为m×n实矩阵，并假定它们有奇异值分别为则有该定理表明矩阵的奇异值也是十分良态的。作业：习题72，3，47.2对称QR方法实对称矩阵的三对角化隐式对称QR迭代隐式对称QR算法7.2.1三对角化

对称矩阵的三对角化就是把一个对称矩阵经一系列正交约化使其成为对称的三对角矩阵。

显然，把第6章“矩阵的上Hessenberg化”算法应用于实对称矩阵A，则由对称性可知，所得到的上H矩阵就是对称的三对角矩阵。

注意到A的对称性，上Hessenberg化算法可以改进，以减少运算量。这就是本节要介绍的实对称矩阵的三对角化算法。即经n-2次Householder约化，把A化成三对角矩阵T第1步：把矩阵A分块写成依v构造n-1阶Householder变换,并令用H1约化A(0)得到显然，第1步约化的主要工作量是计算，设则有上式的推导过程：由对称性，的计算过程为：算法7.2.1(实对称矩阵三对角化：Householder变换法)时间复杂度：7.2.2隐式对称QR迭代实现了对称矩阵的三对角化之后，下面的任务就是选取适当的位移进行QR迭代。由于实对称矩阵的特征值均为实数，只需进行带原点单步位移即可。带原点位移的QR迭代格式：由于QR迭代保持上Hessenberg形和对称性的特点，则迭代产生的Tk都是对称三对角矩阵。和非对称QR方法一样，仍然假定迭代中所出现的Tk均是不可约的，即次对角线元均不为零。（1）位移的选取：的两个特征值中靠近αn的那一个，即取其中这就是著名的威尔金森(Wilkinson)位移.Wilkinson证明了这两种位移最终都是三次收敛的，并且说明了为什么后者比前者好[12].第1种选法：选取μk=T(n,n).第2种：取μk为Tk右下角子矩阵（2）如何具体实现一次QR迭代

当然，可以利用Givens变换直接实现的QR分解，进而完成一步QR迭代。但是，更漂亮的做法是以隐含的方式来实现由T到的变换。QR迭代实质是用正交变换将T约化为，即.因此,根据定理6.4.3，本质上是由Q的第1列完全确定的。从利用二元正交变换实现QR迭代的过程可知，Qe1=G1e1，其中G1=G(1,2,ϴ)，且ϴ满足因此，可以先对T用G1做一次正交约化，得到然后调用算法7.2.1，把B正交约化为三对角阵，即得到算法7.2.2(带Wilkinson位移的隐式对称QR迭代)时间复杂度：10n.7.2.3隐式对称QR算法算法7.2.3(计算实对称矩阵的谱分解：隐式QR方法)（1）输入A;（2）三对角化：T=QTAQ;（3）收敛性判定：i）将满足的元素置零。ii）确定最大的非负整数m和最小的非负整数l,使得其中均为三对角阵，且iii）若m=n，输出有关信息，结束;否则进入下一步.（4）QR迭代：对T22调用算法7.2.2迭代一次，即（5）然后返回（3）.作业：习题79，11，137.3

Jacobi方法Jacobi方法是求实对称矩阵全部特征值和特征向量的最古老的方法之一，是由Jacobi于1846年提出的。他依据实对称矩阵可通过正交相似变换约化为对角阵这一特点，用一系列适当选取的平面旋转变换将一个实对称矩阵逐步约化为对角阵。尽管该算法收敛速度与QR算法无法相比，但该算法具有编程简单、并行效率高等特点，近年来又重新受到人们的重视。7.3.1经典Jacobi方法

设A=[αij]是n阶实对称矩阵。Jacobi方法的目标是将A的非对角“范数”逐步约化为零.所用的基本工具就是Givens正交变换：其中，1≤p<q≤n,ep,eq均是单位向量.Jacobi方法每迭代一步需要完成：1）确定p和q；确定旋转角ϴ，使得2）用G=G(p,q,ϴ)对A一次正交约化：A:=GTAG.（1）Jacobi迭代法的正交约化过程：显然，每迭代一步，倘若将A约化为B.

则A,B仅第p行（列）与第q行（列）不一样，其余元素均相同。且以上计算式子的推导，可借下两式：（2）c和s的计算：从最后一个式子知c和s应满足如果αpq=0，则只需取c=1,s=0即可。如果αpq≠0，则令于是有解得取t为绝对值较小者，即由于则有（3）p和q的选择：注意到Jacobi