第九章矩阵特征值问题的数值方法课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第9章 矩阵特征值问题的数值方法,9.1 特征值与特征向量,9.2 Hermite矩阵特征值问题,9.3 Jacobi方法,9.4 对分法,9.5 乘幂法,9.6 反幂法,9.7 QR方法,第9章 矩阵特征值问题的数值方法 9.1 特征值与特征,1,9.1 特征值与特征向量,设A是n阶矩阵，x是非零列向量.如果有数存在，满足 ，(1),那么，称x是矩阵A关于特征值的,特征向量.,9.1 特征值与特征向量 设A是n阶矩阵，x是非零列向量,2,如果把(1)式右端写为 ，那么(1)式又可写为:,记,它是关于参数的n次多项式，称为矩阵A的特征多项式，其中a,0,=(-1),n,A.,(2),如果把(1)式右端写为 ，那么(1)式又可写为:记它是关,3,显然，当是A的一个特征值时，它必然是 的根.反之，如果是 的根，那么齐次方程组(2)有非零解向量x，使(1)式成立.从而，是A的一个特征值.A的特征值也称为A的特征根.,显然，当是A的一个特征值时，它必然是,4,矩阵特征值和特征向量有如下主要性质：,定理9.1.1 n阶矩阵A是降秩矩阵的充分必要,条件是A有零特征值.,定理9.1.2 设矩阵A与矩阵B相似，那么它们,有相同的特征值.,定理9.1.3 n阶矩阵A与A,T,有相同的特征值.,定理9.1.4 设,i,j,是n阶矩阵A的两个互异特,征值，x、y分别是其相应的右特征向,量和左特征向量，那么，x,T,y=0.,矩阵特征值和特征向量有如下主要性质：定理9.1.1 n,5,9.2 Hermite矩阵特征值问题,设A为n阶矩阵，其共轭转置矩阵记为A,H,.如果A=A,H,，那么，A称为Hermite矩阵.,9.2 Hermite矩阵特征值问题 设A为n阶矩阵，其,6,9.2.1 Hermite矩阵的有关性质,设 是Hermite矩阵A的n个特征值.有以下性质:,全是实数.,有相应的n个线性无关的特征向量，它们可以化为一组标准酉交的特征向量组 ,即,是酉空间中的一组标准酉交基.,9.2.1 Hermite矩阵的有关性质 设,7,记U=(),它是一个酉阵，即U,H,U=UU,H,=I，那么,即A与以 为对角元的对角阵相似.,A为正定矩阵的充分必要条件是 全为正数.,记U=(),它是,8,定理9.2.1 设 是Hermite矩阵A的n个特征值，那么,证:,定理9.2.1 设,9,设x是一个非零向量，A是Hermite矩阵，称 为矩阵A关于向量x的Rayleigh商，记为R(x).,定理9.2.2 如果A的n个特征值为 其相应的标准酉交的特征向量为 那么有,定理9.2.3 设A是Hermite矩阵，那么,设x是一个非零向量，A是Hermite矩阵，称,10,9.2.2 极值定理,定理9.2.4(极值定理)设Hermite矩阵的n个特征值为 ，其相应的标准酉交特征向量为 .用C,k,表示酉空间C,n,中任意的k维子空间，那么,9.2.2 极值定理 定理9.2.4(极值定理)设He,11,9.2.3 Hermite矩阵特征值问题的性态,矩阵特征值问题与求解线性方程组问题一样，都存在当矩阵A的原始 数据有小变化(小扰动)时，引起特征值问题的变化有大有小的问题，如果引起的变化小，称 该特征值问题是,良态的.,反之，称为,病态的,.,矩阵特征值问题的性态是很复杂的，通常分别就单个特征值或整体特征值给出状态数进行分 析.,对于Hermite矩阵,，由于其特征值问题的特殊性质，,其特征值都是良态的,.下面先证明Hermite矩阵特征值的扰动定理.,9.2.3 Hermite矩阵特征值问题的性态,12,定理9.2.5 设矩阵A，E，A+E都是n阶Hermite矩阵，其特征值分别为 那么,证 设矩阵A关于特征值,1,，,2,，,n,的标准酉交特征向量为u,1,，u,2,，u,n,，,是由u,i,，u,i+1,，u,n,生成的n-i+1维子空间.,对 中任意非零向量x,由极值定理,有,定理9.2.5 设矩阵A，E，A+E都是n阶Hermite,13,由定理9.2.3，,又由定理9.2.2，对任意x0，有,从而有,另一方面,A=(A+E)-E.记 为矩阵-E的特征值，那么，,重复上面的过程,可得,从而有,由定理9.2.3，,14,定理9.2.5通常又称为Hermite矩阵特征值的,扰动定理,定理9.2.6 设矩阵A和A=A+E都是n阶Hermite矩 阵，其特征值分别为 和 ，那么,这个定理表明，扰动矩阵E使A的特征值的变化不会超过 E,2,.一般E,2,小，因此，Hermite矩阵特征值是良态的.,定理9.2.5通常又称为Hermite矩阵特征值的扰动定理,15,9.3 Jacobi方法,理论上，实对称矩阵A正交相似于以A的特征值为对角元 的 对角阵.问题是如何构造这样的正交矩阵呢?Jacobi方法就是通过构造特殊的正交矩阵 序列，通过相似变换使A的非对角线元素逐次零化来实现对角化的.,9.3.1 平面旋转矩阵与相似约化,先看一个简单的例子.,9.3 Jacobi方法理论上，实对称矩阵A正交相似于以,16,设 是二阶实对称矩阵，即a,21,=a,12,，其特征值为,1,，,2,.令,使得 记,容易验证B,T,=B,且,设 是二阶实对称矩阵，即a,17,解之得:,当 时,当 时,并规定,解之得:,18,9.3.2 经典的Jacobi方法,设A是实对称矩阵，记A,1,=A.Jacobi方法的基本思想是用迭代格式,A,k+1,=Q,T,k,A,k,Q,k,k=1,2,构造一个相似矩阵序列，使A,k,收敛于一个对角阵.其中 Q,k,为平面旋转矩阵，其旋转角,k,由使A,k,的绝对值 最大元a,(k),pq,=a,(k),qp,=0 或按列依次使A的非对角元 零化来确定.,9.3.2 经典的Jacobi方法 设A,19,定理9.3.1 设A是n阶实对称矩阵，那么由Jacobi方法产生的相似矩阵序列A,k,的非对角元收敛于0.也就是说，A,k,收敛于以A的特征值为对角元的对角阵.,记 其中E,k,是A,k,除主对角元外的矩阵.由平面旋转矩阵的性质,中,对于 ,有,因此,定理9.3.1 设A是n阶实对称矩阵，那么由Ja,20,又由假设,因此,这样,便有,从而,当,又由假设,21,9.3.3 实用的Jacobi方法,循环Jacobi方法必须一次又一次扫描，才能使A,k,收敛于对角阵，计算量很大.在实际计算中，往往用一些特殊方法来控制扫描次数，减少计算量.下面介 绍一种应用最为广泛的特殊循环Jacobi方法阈Jacobi方法.阈Jacobi方法首先确定一个阈值，在对非对角元零化的一次扫描中，只对其中绝对值 超过阈值的非对角元进行零化.当所有非对角元素的绝对值都不超过阈值后，将阈值减少，再重复下一轮扫描，直至阈值充分小为止.减少阈值的方法通常是先固定一个正整数Mn，扫描一次后，让 .而阈值的下界是根据实际问题的精度要求选定的.,9.3.3 实用的Jacobi方法 循环Jacobi方法,22,9.3.4 用Jacobi方法计算特征向量,假定经过k次迭代得到A,k+1,=R,T,k,R,T,1,AR,1,R,k,，(15)这时A,k+1,是满足精度要求的一个近似的对角阵.如果记Q,k,=R,1,R,2,R,k,=Q,k-1,R,k,，(16),那么，Q,k,是一个正交矩阵，且(15)式又可表示为A,k+1,=Q,T,k,AQ,k,.当A,k+1,的非对角元素充分小，Q,k,的第 j列q,j,可以看成是近似特征值a,(k+1),jj,相应的特征向量了.,9.3.4 用Jacobi方法计算特征向量假定经过k次迭代,23,在实际计算中，可以按(16)式在迭代过程中形成Q,k,，把Q,k,看成是Q,k-1,右乘一个平面旋转矩阵得到.不妨记 Q,0,=I，Q,k,的元素按下式计算：,在实际计算中，可以按(16)式在迭代过程,24,9.4 对分法,理论上，一个实对称矩阵正交相似于一个以其特征值为对角元的 对角阵.但是，经典的结果告诉我们，一个大于4次的多项式方程不可能用有限次四则运算 求根.因此，我们不可能期望只用有限次相似变换将一个实对称矩阵约化为一个对角阵.下面先介绍将一个实对称矩阵相似约化为实对称三对角矩阵的方法，再讨论求其特征值的对 分法.,9.4 对分法 理论上，一个实对称矩,25,9.4.1 相似约化为实对称三对角矩阵,将一个实对称矩阵正交相似约化为一个实对称三对角矩阵的算法，可归纳如下：,记A,(1),=A,对k=1,2,n-2,按(4)式、(5)式和(8)式计算 ；,按(9)(12)式，计算A,(k+1),.,9.4.1 相似约化为实对称三对角矩阵 将一个实对称矩,26,第九章矩阵特征值问题的数值方法课件,27,9.4.2 Sturm序列的性质,设实对称三对角矩阵为,其中,i,0(i=1,2,，n-1),其特征矩阵为T-I.记T-I的第i阶主子式为,9.4.2 Sturm序列的性质 设实对称三对角矩阵为,28,这是关于的i次多项式，当i=n时，p,n,()=T-I是矩阵T的特征多项式.令p,0,()1，则有p,1,()=,1,-，p,i,()=(,i,-)p,i-1,()-,2,i-1,p,i-2,()，i=2,3，n.(15),多项式序列p,i,()(i=0,1,，n)称为,Sturm序列,这是关于的i次多项式，当i=n时，pn()=T-I,29,定理9.4.1p,i,()(i=1,2,，n)的根都是 实根.,证 由(14)式，p,i,()是i阶实对称矩阵的特征多项式，因此，p,i,()(i=1,2,，n)的根全是实根.,定理9.4.2,定理9.4.2 设是p,i,()的一个根，那么,p,i-1,()p,i+1,()0，即相邻的两个多项式无公共根；,p,i-1,()p,i+1,()0，即p,i-1,()与p,i+1,()反号.,定理9.4.4 p,i,()的根都是单根，并且将p,i+1,()的根严格隔离.,定理9.4.1pi()(i=1,2,，n)的根都是,30,9.4.3 同号数和它的应用,定义1 设p,0,()1，p,i,()(i=1,2,，n)是一个Sturm序列，称相邻的两个数中符号一致的数目为,同号数,，记为a,i,().若某个p,i,()=0，规定与p,i-1,()反号.,定理9.4.5 设两个实数x,3,n,，可以用乘幂法计算,2,及其相应的 特征向量.在计算,1,和v,后，按(15)式形成n-1阶矩阵B的计算过程称为,收缩方法.,那么，B有与A1除1外的相同的n-1个特征值 2,37,9.6 反幂法,反幂法可以求一个非奇异矩阵A的逆矩阵A,-1,的按模最小的特征值及相应的特征向量，又可以求A的一个近似特征值相应的特征向量.,9.6.1 求按模最小特征值及相应特征向量的,反幂法,又称为,反迭代法,.,9.6 反幂法 反幂法可以求一个非奇异矩阵A的逆矩阵A,38,9.6.2 求近似特征值的特征向量的反幂法,先对矩阵 进行LU分解，记,那么，,(7),下面介绍一种选取特殊的初始向量x,0,的反幂法,半迭代法,.,9.6.2 求近似特征值的特征向量的反幂法 先对矩阵,39,假设 ,选取初始向量x,0,满足x,0,=1，这时z,0,=x,0,.对照(7)式中的第二个式子.可把z,0,看成满足Le=z,0,.(8),这里，e=(1,1，1),T,，而z,0,的各个分量的取值多少是无关重要的.这样，在第一个迭代步的计算中，只需求解(7)式中的上三角方程组Ux,1,=e.“半迭代法”的命名也由此而得.,假设 ,选取初始向量x0满足x0,40,9.7 QR方法,定理9.7.1设A是n阶矩阵，其n个 特征值为 .那么存在一个酉矩阵U，使,U,AU是以为 对角元的上三角矩阵.,9.7.1 两个基本定理,定理9.7.2设A是n阶实矩 阵，那么，存在一个正交矩阵Q，使Q,AQ为一个准上三角矩