数值计算 第五讲

数值分析与算法(5),NumericalAnalysis(2)实特征值一定对应实特征向量;(3)非实特征值的共轭也是特征值,其对应的特征向量一定不是实向量,=,det=111212122212=0,WenjianYu,5,特征值的有关性质,非奇异矩阵特征值均不为0,0是奇异矩阵的特征值=()若为对角阵或上(下)三角阵,则其特征值为对角元若为分块对角阵或分块三角阵(对角块均为方阵),则=1相似矩阵的特征值相等矩阵运算结果的特征值:设为的特征值，则定义5.2:设有m个(mn)不同的特征值1,若是特征方程的重根,则称为的代数重数,而的特征子空间的维数其几何重数.,det=det,=11121222,=1,=;,+=+;,1=1;,Th5.2,Th5.3,Th5.4,Th5.5,Th5.6,WenjianYu,6,特征值的有关性质,Th5.7:设n阶矩阵的m个不同的特征值为1,的代数重数为,几何重数为,则=;,不同特征值的特征向量线性无关,且将所有特征子空间的=1个基放在一起,它们是一组线性无关向量若,=,这种矩阵为非亏损阵,否则为亏损阵,非亏损阵有n个特征向量构成全空间的基()Th5.8:1=,为对角阵为非亏损阵实对称阵非亏损,且特征值为实数(可正交对角化)Jordan分解:=1,(特征值分解),=1,=11,设m个不同特征值的几何重数为,则=,对应于个若当块,其维数之和等于,WenjianYu,7,特征值的分布,Motivation一阶定常迭代法(+1)=()+的收敛性,看=max()矩阵的2-范数、2-条件数：cond2=max()min()是关于特征值上界的重要结论定义5.4:对于复矩阵,设=1,在复平面上以为圆心、为半径的圆,称为的Gerschgorin圆盘Th5.9(圆盘定理)的特征值必在某个圆盘上若n个圆盘中有m个是连通的,且与其他圆盘分离,则这m个圆盘恰好包含m个特征值,11,22,33,思考:如何证明?,交互演示网站,WenjianYu,8,圆盘定理的应用,推论:严格对角占优阵,正对角元,其特征值的实部0例:估计矩阵=410101114的特征值分布直接应用圆盘定理,D1与其他两个分离,必含一个实特征值再对应用圆盘定理,3与其他圆盘分离,必含一实特征值13,5,22,2,35,33()5用Matlab的eig命令得到准确特征值为:4.2030,-0.4429,-3.7601还可以先做简单的相似变换,再估计特征值分布,见例5.4,0,-404,D3,D2,D1,-404,3,2,1,WenjianYu,9,幂法与反幂法,WenjianYu,10,计算最大的特征值、特征向量,定义5.5:模最大的特征值称为主特征值,也叫”第一特征值”,它对应的特征向量称为主特征向量主特征值有可能不唯一,例如5,5,3+4,34的模都是5幂法(poweriteration):取任意非零向量0,计算=1,(=1,2,),得到向量序列看一个例子:取0=1,0,0,利用Matlab计算向量序列通过实验看出:相邻两个逐渐呈倍数关系,倍数为3趋近于3对应的特征值向量,=511311421,(例5.2,其主特征值为3),Matlabdemo,更多例子：交互演示网站,WenjianYu,11,幂法,幂法是否总能计算矩阵的主特征值?定理5.10:若矩阵有唯一的主特征值1,且1的几何重数等于代数重数,向量0非零,计算=1,(=1,2,),则证明:设为非亏损阵,且1不是重特征值,lim1=1,lim(+1)()=1,1为主特征向量,12,0=11+,设的线性无关的单位特征向量为,=0=111+,=111+=21,()表示向量的第个分量,lim1=11,lim(+1)()=1,思考:若1=0怎样?,思考:构造例子说明,WenjianYu,12,幂法,关于幂法的说明为亏损矩阵的情况,用到矩阵的Jordan标准型进行证明序列相邻向量的第分量的比值收敛到主特征值,可任选证明中假设了10,在实际应用时随机选取0,总能满足关于幂法的问题实用的幂法:用规格化向量的技术防止溢出定义5.6:记max为向量的绝对值最大的分量,若不唯一则取最小编号的那个.称=/max为向量的规格化向量,11,很大时,可能出现上溢或下溢,=111+=21,收敛速度主要取决于21,WenjianYu,13,实用的幂法,规格化向量例:=3,5,0,max=5,规格化向量为=35,1,0若为规格化向量,则=1,向量1和2的规格化向量分别为1和2,若1=2,则1=2在幂法的每步增加向量规格化操作,max=?,1=0,规格化向量1=1max1=0max0,2=1=20max0,规格化向量2=2max2=20max20,=1=0max10=max=0max0,=1,2,limmax=1,lim=1max1,WenjianYu,14,实用的幂法,算法5.1:计算主特征值1和主特征向量1的实用幂法用相邻两步特征值近似值之差作为判停准则保证向量的值不溢出,取最大分量避免了分量j取值的随意性适用范围:主特征值唯一,1特征子空间满秩,输入：,;输出：1,1.:=;While不满足判停准则do:=;1:=max;主特征值近似值:=/1;规格化End1:=.规格化的主特征向量,每步的主要计算是算一次矩阵与向量乘法若为稀疏矩阵,很容易提高效率,对某些矩阵成立,WenjianYu,15,加速幂法的收敛,原点位移技术为了求的某个特征值,及特征向量,对矩阵=应用幂法前提:是的主特征值,瑞利商(Rayleighquotient)加速实对称矩阵的瑞利商:=,定理5.11:对于实对称矩阵,1,并且当为相应特征值时,上式取等号结合幂法,加速特征值的收敛:每步对计算每步仅多计算两次向量内积,证明中利用”实对称阵可正交对角化”,特征值分布,1,0,且2()较小,自己看课本pp.138-139,例:,=,WenjianYu,16,反幂法,1的特征值是特征值的倒数,对1应用幂法,求最小特征值适用范围:按模最小的特征值唯一,代数重数=几何重数应用:若已知某个特征值,则是=的特征值(一般按模最小),对使用反幂法,算法5.2:计算最小特征值与特征向量的反幂法输入：,;输出：,.:=;While不满足判停准则do:=1;求解线性方程组:=1/max();最小特征值的近似值:=;规格化End:=.规格化的特征向量,求解线性方程组,计算量可能比幂法大很多,与瑞利商结合,WenjianYu,17,小结,幂法可能失败的情况矩阵的主特征值不唯一,例如实矩阵,模最大的特征值不是实数矩阵的主特征值唯一,但是重特征值,且特征子空间维数小于重数初始向量在主特征向量方向没有分量(实际上没问题)反幂法的情况类似说明几点按幂法迭代计算,若前后两次迭代向量成比例,则它一定就是特征向量,也相应求出特征值反幂法结合位移技术,以及瑞利商加速,应用很广泛,WenjianYu,18,应用实例:PageRankTM的计算,Google网络搜索PageRank技术是其创立之初的关键创新之一搜索分两步:找到符合要求的网址,对它们排序显示PageRank是表示网页信息可靠性、重要性的指标一旦有了PageRank,就按它从高到低的顺序显示怎样的网页PageRank高?数学模型n:网页的总数,=:网页链接矩阵若网页j链接到网页i,则=1,否则=0,被推荐,被链接到,1,3,2,=001100110,搜索例子,数学模型(续)是大规模稀疏阵,其非零元数目为?的列元素之和=,等于网页j的”出度”用Markov过程定义PageRank:随机”冲浪”过程访问网页的极限概率设当前在网页j的概率(),下一步看网页i的概率(+1)=:转移矩阵,是个正矩阵设()为第k次跳转后到达各个网页的概率,则(+1)=()为再跳一次后各网页的概率,WenjianYu,19,应用实例:PageRankTM的计算,(页面跳转时总以概率p选择当前页的链接),网页i在j的链接上:,网页i不在j的链接上:,1/+(1)1/,(1)1/,=+1,乘,乘(1-),=+1,=diag(1/),数学模型(续)PageRank:随机”冲浪”过程访问网页的极限概率上述算法(幂法)的理论分析数学本质:求1对应的特征向量矩阵的特点:0,第j列元素之和为1()1;可”放心地”用幂法PageRank反映超链接结构,隔一段时间需重新计算计算中不需对()规格化;不要形成矩阵,WenjianYu,20,应用实例:PageRankTM的计算,(+1)=(),lim()=?,它存在吗?,=1=1,=,1是主特征值,的第j个圆盘,0,1,唯一主特征值,WenjianYu,21,矩阵的QR分解,WenjianYu,22,Householder变换,矩阵的正交三角化高斯消去过程可用正交阵来左乘?是计算所有特征值的算法的基础Householder矩阵定义:且=1,称矩阵=2为Householder矩阵,或初等反射阵=为对称阵为正交阵为对做Householder变换,左乘消去矩阵,=1212212221122221222122122,左乘正交阵,2=1,WenjianYu,23,Householder变换,Householder变换的几何意义以为法向画出超平面S为关于平面S的镜像与的2-范数相等,属于正交变换Th5.14:设,2=2,则存在House-holder矩阵,使=几何的启示:=,Th5.15:可将Th5.14中的设为,S,(初等反射变换),=2=2,=2,=,=2,构造矩阵,200,1,构造时,=+1,=sign(1)2,用正交变换实现消元!,交互演示5.3,WenjianYu,24,Householder变换,Householder变换对向量做正交变换实现消元,结果1中的负号是为了数值稳定例:确定一个Householder变换,对向量实现消元操作,取=2,则实现变换的矩阵为=2,=212,解:=sign12=3,很重要!用向量表示矩阵,只算向量内积,00,构造=+1,=212+300=512,验证:=2,=,=21221530512=300,WenjianYu,25,矩阵的QR分解,用Householder变换实现正交三角化?21=不一定是方阵,上三角阵也同样=12=,其中为正交阵,称为QR分解还有其他正交变换消元的手段:Givens旋转变换,后面将介绍.,Th5.16:对任意矩阵,一定存在QR分解;若为方阵,且的对角元都0,此分解唯一.,左乘正交阵,的情况:,WenjianYu,26,矩阵的QR分解,用Householder变换实现:21=设,构造m阶反射阵1消的第1列:,=1,2,其中为维向量,(2)=1=112(2)022(2)1(2)2(2)02(2)(2)=1|012|1|0|,=1102|0022(2)21(2)|00|,用2实现(2)第2列的消元,同时不影响第1列,令2=12,记2=112,2(2)=1122,2也是Householder阵(其向量的第一个分量为0).,构造2,后续可类似构造,交互演示5.4,WenjianYu,27,算法5.3：基于Householder变换的矩阵正交三角化输入:=1,2,;输出:;1,2,.Fork=1,2,n:=sign()=2;下三角部分第k列的2-范数If=then第k列对角线下方已经全为0Continuewithnextk;End:=0,0,+;构造的向量:=;Forj=k,k+1,n对剩余各列作Householder变换:=;:=(2/);()=()2()EndEnd,算法执行完,变成,另外得到构造1,2,所需的向量总的乘法次数:若考虑向量的稀疏性,总的乘法次数为23/3,2+1+21+32,?思考,Matlab:Q,R=qr(A);R=qr(A),WenjianYu,28,Givens旋转变换,二维平面旋转变换将向量顺时针旋转角度后得到定义二阶Givens矩阵为:是正交阵(几何解释)为对做Givens旋转变换,选择参数c,s,n阶Givens旋转阵仍是正交阵,=,其中=cos,=sin,=cossinsincos,0,10000000001000000000112345,将二阶Givens阵嵌入n阶单位阵:,=135,=222+42,=422+42,WenjianYu,29,Givens旋转变换,例:通过Givens旋转变换进行消元每个Givens旋转阵用参数c,s刻画做一次旋转变换仅影响向量两个元素也可实现矩阵的QR分解,比较适合稀疏矩阵,则:,=2012,000,解:先针对第1,3分量构造二阶旋转矩阵,1=1111,1=222+1=25,1=15,1=10100100101000012012,接着对第1,4分量旋转,求出2=53,2=23，,21=20020100001020025002=3000,仅影响矩阵的两行,=5002,WenjianYu,30,QR迭代算法,WenjianYu,31,计算矩阵的所有特征值,两个问题什么样的矩阵易于求所有特征值?对矩阵做怎样的变换能保持特征值不变?思路：用正交相似变换将矩阵化为三角阵或分块三角阵收缩技术用幂法/反幂法已求出的一个特征值1,特征向量1构造矩阵对1实现消元:,再对做正交相似变换,1,1=1,1=,11,=11,=111,=11,=11,=111,WenjianYu,32,计算矩阵的所有特征值,收缩技术的例子:已知的一个特征值为根据的1特征向量,还可求的特征向量不形成计算:先算=,再=,=311201112,1=2,对应特征向量为1=1,1,0,求其他特征值,解：用Householder变换对1消元,相应的=2=1.4142,构造矩阵的向量为:,=1+1=2.414210,=0.70720.707200.70720.70720001,=231.414201001.41422,易知1的特征值为1和2,是的其他特征值,1,WenjianYu,33,QR迭代算法,理论基础用一系列正交相似变换=,逐渐将矩阵化为上三角或对角块阶数很小的分块上三角矩阵设，若为分块上三角阵，且对角块为1阶或2阶矩阵，则称为拟上三角阵，也叫实Schur型Th5.17(Schur分解):对任意实矩阵,存在正交阵使=,其中为拟上三角阵,其一阶对角块是的实特征值,二阶对角块的特征值是的两个共轭复特征值QR算法,(“二十世纪十大算法”之一),对做QR分解:=,+1=,(=0,1,),生成正交相似矩阵序列,or,WenjianYu,34,QR迭代算法,Th5.18:收敛定理矩阵满足一定条件,则QR迭代的矩阵序列基本收敛于拟上三角阵,“基本收敛”,算法：计算矩阵特征值的QR算法输入：;输出：1,.While不是拟上三角阵do计算的QR分解，得到矩阵和;:=;End根据的对角块求特征值1,.,拟上三角阵例子?,看课本上的例子,正交相似变换是保对称性的,对称,则也对称,对对称阵做Q