矩阵特征问题的求解简.ppt

1 引言,矩阵特征问题的求解,物理、力学及工程技术领域中的许多问题在数学上都可归结为求方阵特征值和特征向量的问题，如振动问题：桥梁的振动、机械振动、电磁振荡、地震引起的建筑物的振动等等；物理学中的临界点、临界值的确定；微分系统中的稳定性研究。这些常见的问题都与方阵的特征值和特征向量有关。,求方阵的特征值和特征向量是数学、物理学、力学、电磁电工学以及工程技术所面临的一个共同问题。,定义：矩阵 AR nn，若有数和非零向量x R n 使得A x x，则 称 为A的特征值，x称为对应的特征向量。在线性代数中的求法：解特征多项式|E-A|=0.,利用线性代数中的上述方法计算特征值和特征向量是十分困难的;我们的目的是寻求一种适合计算机运行的近似解法,且简单、可行、有效。,复习相关理论,定义 设矩阵A,BR nn，若有可逆阵P，使,定理1 若矩阵A,BR nn且相似，则,B=P-1 AP,则称A与B相似。,（1）A与B的特征值完全相同；,（2）若x是B的特征向量，则Px便为A的特征向量。,定理2：设AR nn具有完全的特征向量系，即存在n个线性无关,其中i为A的特征值，P的各列为相应于i的特征向量。,的特征向量构成Rn的一组基底，则经相似变换可化A为对角阵。,即 矩阵A与对角阵相似的充要条件是A 有n 个线性无关的特征向量,即有可逆阵P，使,定理3：AR nn，1,n为A的特征值，则,（2）A的行列式值等于全体特征值之积，即,（1）A的迹数等于特征值之和，即,定义：设AR nn为对称矩阵，对任意xR n，x0，则称比值,矩阵 A关于向量 x 的瑞雷(Rayleigh)商,瑞雷(L.Rayleigh)英国数学家，18421919,定理4 设AR nn为对称矩阵，其特征值12n，则,1）对任意 xR n，x0，,2）,3）,定理5（Gerschgorin圆盘定理）设AR nn，则,表示以aii为中心，以 半径为的复平面上的n个圆盘。,（2）如果矩阵A的m个圆盘组成的并集S（连通的）与其余,（1）A的每一个特征值必属于下述某个圆盘之中，,n m个圆盘不连接，则S内恰包含m个A的特征值。,1 乘幂法,定理6 设A Rnn有n个线性无关的特征向量，若1,2,n为A的n个特征值且满足,对任取初始向量x(0)Rn，(x(0)0)对乘幂公式,确定的迭代序列x(k)，有下述结论：,乘幂法与反幂法,乘幂法是一种求矩阵的按模最大的特征值及其特征向量的方法。,（1）当 时，对i=1,2,n,收敛速度取决于 的程度，r 1收敛快，r 1收敛慢，,且x(k)（当k充分大时）为相应于1的特征向量的近似值。,（2）当 时,a）若1=2，则主特征值1及相应特征向量的求法同（1）；,收敛速度取决于 程度。向量,分别为主特征值1、2相应的特征向量的近似值。,b）若1=-2，对i=1,2,n,c）若，则连续迭代两次，计算出x(k+1)，x(k+2)，,然后对j=1,2,n 解方程,求出、后，由公式,解出主特征值1、2。此时收敛速度取决于 的程度。,乘幂法方法步骤,设为n 维向量，令 r=max(x)表示向量x分量中绝对值最大者。,1.任意给定初始向量(非零)v(0)=u(0)0，取r0=max(v(0);,2.产生迭代序列：,为求A矩阵的按模最大的特征值1和其相应的特征向量1，,v(1)=Au(0)，取r1=max(v(1),v(2)=Au(1)，取r2=max(v(2),v(k)=Au(k-1)，取rk=max(v(k),3.循环次数控制：当|rk-rk-1|时,结束循环，输出rk 1，u(k)1,定理7 设ARnn有n个线性无关的特征向量1，2 n，1,2,n为A的n个特征值，且满足,则对任初始向量v(0)=u(0)0，由规范化的乘幂法公式确定的向量序列v(k)，u(k)满足,(1),（2）u(k)1为相应于主特征值1的特征向量.,例 用乘幂法求矩阵A的按模最大的特征值及其相应的特征向量，其中,解：取初始向量v(0)=u(0)（0，0，1）T,则 v(1)=Au(0)=(2，4，1）T;r1=max(v(1)=4;u(1)=1/4(2，4，1）T=(0.5，1，0.25）T;,v(2)=Au(1)=(4.5，9，7.75）T;r2=max(v(2)=9;,结果如下：,r1=4.000000,u(1)=(0.500000,1.000000,0.250000)T|r1-r0|=4.000000,r2=9.000000,u(2)=(0.500000,1.000000,0.861111)T|r2-r1|=5.000000,r3=11.444445,u(3)=(0.500000,1.000000,0.730582)T|r3-r2|=2.444445,r4=10.922330,u(4)=(0.500000,1.000000,0.753556)T|r4-r3|=0.522115,r5=11.014222,u(5)=(0.500000,1.000000,0.749354)T|r5-r4|=0.091892,r6=10.997417,u(6)=(0.500000,1.000000,0.750117)T|r6-r5|=0.016805,r7=11.000469,u(7)=(0.500000,1.000000,0.749979)T|r7-r6|=0.003052,r8=10.999914,u(8)=(0.500000,1.000000,0.750004)T|r8-r7|=0.000555,r9=11.000015,u(9)=(0.500000,1.000000,0.749999)T|r9-r8|=0.000101,r10=10.999997,u(10)=(0.500000,1.000000,0.750000)T|r10-r9|=0.0000180.0001=,Aitken加速法,通过前面的讨论容易看出由于当k充分大时，存在常数c 0使得,因此,从上式解出1得,该值能比rk更快接近于1,1.任意给定初始向量(非零)v(0)=u(0)0，取r0=max(v(0);,2.产生迭代序列：,v(1)=Au(0)，取r1=max(v(1),v(2)=Au(1)，取r2=max(v(2),Aitken加速法得方法步骤,取,v(k)=Au(k-1)，取rk=max(v(k),于是该法迭代收敛速度大于乘幂法。,Rayleigh商加速,定理 设ARnn对称矩阵，|1|2|n|,为A的n个特征值，,则对任初始向量v(0)=u(0)0，由规范化的乘幂法公式确定的向量序列v(k)，u(k):v(k)=Au(k-1)，u(k)=v(k)/max(v(k),（2）u(k)1为相应于主特征值1的特征向量.,取,那么(1)rk 1,若 A 有|1|2|n|，则 A1 有,设ARnn可逆，则无零特征值，由,反幂法,反幂法是一种求矩阵的按模最小的特征值及其特征向量的方法。,Ax=x,(x 0),则有,A1 的主特征值 A的绝对值最小的特征值,如何计算 x(k+1)=A-1 x(k)?,解线性方程组 A x(k+1)=x(k),对应同样一组特征向量。,规范化反幂法公式为,每次需要解方程组求v(k+1),由于每次需要解方程组，而方程组的系数矩阵是相同的，所不同的是右端的常数项，为此考虑运用Doolitel 三角分解法。,如果考虑到原点移位加速的反幂法，则记B=A-0I，,对任取初始向量(非零)v(0)Rn，,反幂法方法步骤,(1)将矩阵A作Doolitel 三角分解 ALU；,(2)任意给定非零初始向量v(0)=u(0)0，取r0=max(v(0);,(4)循环次数控制：当|rk-rk-1|时,结束循环，输出rk n，u(k)n,(3)产生迭代序列：,I）解方程组：Ly=u(0);U v(1)=y,取r1=max(v(1)1,并取 u(1)=r1 v(1);,II）解方程组：Ly=u(1);U v(2)=y,取r2=max(v(2)1,并取 u(2)=r2 v(2);,例：用反幂法求矩阵A的按模最小的特征值及其相应的特征向量，其中,解：,r1=3.600000,|v1=(0.200000,-0.400000,1.000000)|r1-r0|=3.600000 r2=3.000000,|v2=(0.800000,-1.000000,1.000000)|r2-r1|=0.600000 r3=1.304348,|v3=(1.000000,-0.956522,0.565217)|r3-r2|=1.695652 r4=1.169492,|v4=(1.000000,-0.830508,0.372881)|r4-r3|=0.134856r5=1.224913,|v5=(1.000000,-0.775086,0.307958)|r5-r4|=0.055422r6=1.249279,|v6=(1.000000,-0.750720,0.283862)|r6-r5|=0.024366,取v(0)=u(0)=(0，0，1)T,Ly=u(0),y=(0，0，1)T，U v(1)=y，v(1)=(0.0555，-0.1111，0.27777)T,r1=max(v(1)1=3.6,u(1)=r1 v(1)=3.6(0.0555，-0.1111，0.27777)T=(0.2,-0.4,1.0)T,r7=1.259909,|v7=(1.000000,-0.740091,0.274433)|r7-r6|=0.010630 r8=1.264507,|v8=(1.000000,-0.735493,0.270629)|r8-r7|=0.004598r9=1.266482,|v9=(1.000000,-0.733518,0.269066)|r9-r8|=0.001975,r10=1.267326,|v10=(1.000000,-0.732675,0.268417)|r10-r9|=0.000844,r11=1.267685,|v11=(1.000000,-0.732315,0.268146)|r11-r10|=0.000359,r12=1.267837,|v12=(1.000000,-0.732163,0.268032)|r12-r11|=0.000153,r13=1.267902,|v13=(1.000000,-0.732098,0.267984)|r13-r12|=0.000065,对应的特征向量为 3 v(k)=(1.000000,-0.732098,0.267984),于是按模最小的特征值 3 r13=1.267902，,真值为3,练习：用反幂法求矩阵A的按模最小的特征值及其相应的特征向量，其中,解：,取v(0)=u(0)=(0，0，1)T,r1=-0.500000,|v1=(-0.500000,1.000000,-0.500000)|r1-r0|=0.500000,r2=-0.200000,|v2=(1.000000,-0.900000,0.300000)|r2-r1|=0.300000,r3=0.166667,|v3=(1.000000,-0.716667,0.200000)|r3-r2|=0.366667,r4=0.186916,|v4=(1.000000,-0.663551,0.171340)|r4-r3|=0.020249,r5=0.193724,|v5=(1.000000,-0.645745,0.161738)|r5-r4|=0.006808,r6=0.196118,|v6=(1.000000,-0.639484,0.158362)|r6-r5|=0.002394,r7=0.196974,|v7=(1.000000,-0.637245,0.157155)|r7-r6|=0.000856,r8=0.197282,|v8=(1.000000,-0.636440,0.156721)|r8-r7|=0.000308,r9=0.197393,|v9=(1.000000,-0.636150,0.156564)|r9-r8|=0.000111,r10=0.197433,v10=(1.000000,-0.636045,0.156508)|r10-r9|=0.000040,1预备知识,1）若A是上（或下）三角阵或对角阵，,则A的主对角元素即是A的特征值。,2）若矩阵P满足PTP=E，则称P为正交矩阵。,显然PT=P-1，且P1,P2,是正交阵时，,其乘积P=P1P2Pk仍为正交矩阵。,对称矩阵的雅可比(Jacobi)旋转法,2雅克比方法,引例：考虑矩阵,其中 1=a11cos2 a12sin2+a22sin2，,2=a11sin2+a11sin2+a22cos2,定义：称矩阵,为平面旋转矩阵,第i行,第i列,第j列,第j行,平面旋转矩阵P 的性质：,1)P是正交矩阵，即 PPT=E;,2)A是实对称矩阵，则 B=PTAP 仍是实对称矩阵，且A与B具有相同的特征值；,3)若 B=PTAP，则|A|F=|B|F，其中,即经旋转变换后，对角线上元素的平方和将增加.,雅可比(Jacobi)旋转法的方法步,1.选取矩阵A的非对角线元素中绝对值最大的元素 aij=aji(ij)；,2.确定平面旋转矩阵P1=Pij(),其中,与 aij 同号。作变换A1=P1TAP1=(aij(1),3.重复2的工作：作变换Ak=PkTAPk=(aij(k),Pk=Pij(),则有如下关系：,将 限制在下列范围内,如果,这样得到的矩阵序列Ak是收敛的，,且Ak（k）aii(k)i（k）;,在迭代过程中，若max|aij(k)|，结束运算。,2.取 P=P1 P2 Pk中的列向量即为i所对应的特征向量的近似值,则1.取i aii(k)，,例：用Jacobi方法计算矩阵A的特征值和相应的特征向量,特征值的精确解 12=-0.9339707868005558,3,特征向量:,直接从三角函数关系式计算sin 和cos，记,则,当 时，有下面三角恒等式：,于是,采用下面公式计算 sin,特征向量的计算,记 P0=E,则 Pk=Pk-1Pk-1T,Pk 的元素为：,算法：,1从A(k-1)中找出绝对值最大元素,2若，则为对角阵，停,若,（1）令,（3）,（4）,（5）计算特征向量,P0=I,QR方法,定义.设W是实的n维列向量，且WTW+1，则称n阶矩阵 H=E-2WWT 为Housholder(豪斯豪尔特)矩阵，或称为镜像反射矩阵，也称为初等反射矩阵。若设 W=(w1，w2，wn）T 则,初等反射矩阵的性质：,1）对称性：HT=H,2）正交性：HTH=E,3）对合性：H2=E,QR方法的收敛性定理：,设矩阵A(aij)Rnn满足下列条件：1)A的特征值有性质|1|2|n|0;2)A有标准形A=PP-1，且有P-1=LU 三角分解.则由QR算法产生的序列Ak本质上收敛于上三角矩阵RA,子空间迭代法,斯密特（Schmidt）正交化过程：,设1，2，3 为R3上的三个线性无关的向量，,令，则1为单位长度的向量，再令,可以验证（1,2）=0，即1与2正交。若令,则,即与1,2正交，将其单位化为,于是向量组1,2,3构成R3上一组标准正交基，且,其中Q=1,2,3为正交矩阵，R是上三角阵。,对n维向量空间，设1,n为Rn上n个线性无关的向量，,类似有,即,Q为正交阵，R 为上三角阵,将n个线性无关向量变换为n个两两正交向量的方法称为,斯密特正交化方法。,斯密特正交化过程将可逆阵A分解为正交阵与上三角阵的乘积。,希望|2/1|越小越好。,不妨设 1 2 n，且|2|n|。,取 0（常数），用矩阵B=A-0E 来代替A进行乘幂迭代。,(i=1,2,n),设i(i=1,2,n)为矩阵B 的特征值，则B 与A 特征值之间,应有关系式：,原点位移法,关于矩阵B的乘幂公式为,为加快收敛速度，适当选择参数0，使,达到最小值。,当i(i=1,2,n)为实数，且12 n时，取,则为(0)的极小值点。这时,